Hier geistern ein paar ziemlich … „interessante“ … Ideen rum 
Die Sache mit den 4 Rechtecken ist erstmal nicht „falsch“ oder „richtig“. Wenn sie hilft, das Ziel zu erreichen, kann sie ja kaum pauschal „falsch“ sein. Allerdings leuchtet mir der Grund nicht ganz ein. Wie hoch/breit sind diese Rechtecke? 1 Pixel? Was kann man in diesem Fall mit diesen Rechtecken machen, was man nicht auch mit einer Linie machen könnte?
Die „einfachste“ Lösung, die du jetzt vorgeschlagen hast, ist gar nicht so unüblich - zumindest in einer ähnlichen Form.
Aber erstmal kurz vorneweg: Du hast einen Schritt der Größe (+5, -20) als problematisch bezeichnet, aber das wäre es nicht mal unbedingt: Allgemein müßte/sollte man für solche Berechnungen ohnehin float/double verwenden. Dann könnte man den Schritt z.B. in 20 Teilschritte zerlegen, jeden mit der Größe (5.0/20.0, -1.0). Aber da lauert auch schon die entscheidende Frage: Wie viele Teilschritte soll man machen? Man hätte einen Trade-off zwischen Genauigkeit und Effizienz.
Man geht ja davon aus, dass man zum Zeitpunkt t einen Zustand hat, wo KEINE Kollision vorliegt. Dann macht man einen Schritt, und hat dann einen Zustand zum Zeitpunkt t+1.0 (also einen Zeitschritt später), wo EINE Kollision vorliegt. Und jetzt will man möglichst genau rausfinden, wann die Kollision „angefangen“ hat. Eine übliche Lösung ist deswegen eine binäre Suche:
Man schaut nach, ob beim Zustand t+0.5 eine Kollision vorliegt (also „in der Mitte“ der beiden Zustände). Falls nicht, weiß man, dass die Kollision irgendwo zwischen t+0.5 und t+1.0 angefangen haben muss. Dann überprüft man den Zeitpunkt t+0.75. Wenn dort keine Kollision vorliegt, muss der Kollisionszeitpunkt irgendwo zwischen t+0.75 und t+1.0 liegen. So schachtelt man den echte Zeitpunkt ziemlich schnell ein.
Der andere Ansatz, mit der Linie und den Schnittpunkten, ist nicht unbedingt sooo kompliziert.
Aber woher weiß ich dann von welcher Seite sich die Spielfigur nähert?
Man kennt ja die Bewegungsrichtung. Die Linie ist ja definiert durch Start- und Endpunkt. Und der Schnittunkt wird berechnet als ein Wert zwischen 0 und 1, wobei 0 dem Startpunkt und 1 dem Endpunkt entspricht.
Vielleicht bastel’ ich da heute Abend mal eine Kleinigkeit, weiß aber noch nicht, ob das alles zeitlich hinhaut (eigentlich ist meine TODO-Liste übervoll…)
*** Edit ***
Joa, hab’ mal was gebastelt. Das ist natürlich nur eine schnell hingehackte Demo, aber verdeutlicht vielleicht die Idee (und enthält vielleicht ein paar praktische Snippets… ich hatte schonmal angefangen, diese ganzen „Intersection“-Sachen (die ich schon 1000 mal gebraucht und 100 mal geschrieben habe) zu sammeln, mit der (sich selbst nicht ganz ernst nehmenden) Vision, schrittweise auf einen Java-Port von http://www.geometrictools.com/ hinzuarbeiten, aber … man kommt ja zu nichts mehr… wenn man dauernd Forenbeiträge beantwortet )).
Wenn man die Maus bewegt, verändert man die „neue“ Position die das Spieler-Objekt haben soll.
Wenn man die Maus draggt, verändert man die „aktuelle“ Position des Spieler-Objekts.
Es zeichnet die Linien zwischen den Eckpunkten des Spieler-Objekts an der alten und der neuen Position, und die Schnittpunkte dieser Linien mit irgendeiner Kante des „Hindernisses“. Wenn es eine Kollision gibt, wird ausgegeben, wo die war und wann sie stattgefunden hat.
Nochmal: Das ist NUR eine kleine Demo. Um sowas direkt in einem Spiel mit vielen Objekten zu machen, sollte man auf die ganze „convenience-methoden“ verzichten, die im Moment aus dem (absolut minimalistischen!) „GameObject“-Interface die für die Kollisionserkennung benötigten Informationen zusammensuchen, und stattdessen die „GameObjects“ schon mit den passenden Infos ausstatten.
package bytewelt.cd;
import java.awt.Color;
import java.awt.Component;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.RenderingHints;
import java.awt.event.MouseEvent;
import java.awt.event.MouseMotionListener;
import java.awt.geom.Ellipse2D;
import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.List;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;
interface GameObject
{
double getMinX();
double getMinY();
double getMaxX();
double getMaxY();
}
class SimpleGameObject implements GameObject
{
private double minX;
private double minY;
private double maxX;
private double maxY;
public SimpleGameObject(
double minX, double minY,
double maxX, double maxY)
{
this.minX = minX;
this.minY = minY;
this.maxX = maxX;
this.maxY = maxY;
}
@Override
public double getMinX()
{
return minX;
}
@Override
public double getMinY()
{
return minY;
}
@Override
public double getMaxX()
{
return maxX;
}
@Override
public double getMaxY()
{
return maxY;
}
}
public class CollisionDetection
{
public static void main(String[] args)
{
SwingUtilities.invokeLater(new Runnable()
{
@Override
public void run()
{
createAndShowGUI();
}
});
}
private static void createAndShowGUI()
{
JFrame f = new JFrame();
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
Component collisionDetectionPanel =
new CollisionDetectionPanel();
f.getContentPane().add(collisionDetectionPanel);
f.setSize(800,800);
f.setLocationRelativeTo(null);
f.setVisible(true);
}
}
class CollisionDetectionPanel extends JPanel implements MouseMotionListener
{
private GameObject obstacle;
private GameObject player;
private GameObject playerNextStep;
CollisionDetectionPanel()
{
obstacle = new SimpleGameObject(400, 200, 450, 600);
player = new SimpleGameObject(100, 300, 200, 400);
playerNextStep = player;
addMouseMotionListener(this);
}
@Override
protected void paintComponent(Graphics gr)
{
super.paintComponent(gr);
Graphics2D g = (Graphics2D)gr;
g.setColor(Color.WHITE);
g.fillRect(0, 0, getWidth(), getHeight());
g.setRenderingHint(
RenderingHints.KEY_ANTIALIASING,
RenderingHints.VALUE_ANTIALIAS_ON);
g.setColor(Color.DARK_GRAY);
g.fill(asRectangle(obstacle));
g.setColor(Color.BLUE);
g.fill(asRectangle(player));
g.setColor(new Color(0,0,255,128));
g.fill(asRectangle(playerNextStep));
// Obtain the corner points of the player object
// and of the player object after it has done
// the next step
List<Point2D> corners = getCorners(player);
List<Point2D> cornersNextStep = getCorners(playerNextStep);
// Compute the lines that describe the movement
// of the corners
List<Line2D> cornerMovements = new ArrayList<Line2D>();
for (int i=0; i<4; i++)
{
Point2D c = corners.get(i);
Point2D n = cornersNextStep.get(i);
Line2D cornerMovement = new Line2D.Double(c,n);
cornerMovements.add(cornerMovement);
}
g.setColor(Color.GRAY);
for (Line2D cornerMovement : cornerMovements)
{
g.draw(cornerMovement);
}
// Note: Doing the collision detection in the paintComponent method
// is of course NOT appropriate in general. This is only a demo,
// and it is done here so that the points can be painted easily
// Obtain the lines that describe the
// border of the obstacle
List<Line2D> obstacleLines = getLines(obstacle);
double firstCollisionTime = Double.MAX_VALUE;
int firstCollisionCorner = -1;
int firstCollisionBorder = -1;
Point2D location = new Point2D.Double();
for (int i=0; i<4; i++)
{
Line2D cornerMovement = cornerMovements.get(i);
for (int j=0; j<4; j++)
{
Line2D obstacleLine = obstacleLines.get(j);
// Check
// - each line that describes the movement of a corner
// - and each line that describes an obstacle border
// for intersections
Point2D collisionPoint =
Intersection.computeIntersectionSegmentSegment(
cornerMovement, obstacleLine, location);
if (collisionPoint != null)
{
double cx = collisionPoint.getX();
double cy = collisionPoint.getY();
g.setColor(Color.RED);
g.fill(new Ellipse2D.Double(
cx-3, cy-3, 6, 6));
// The location.getX() value is the relative
// position (between 0 and 1) on the line
// that describes the movement of the corner
double collisionTime = location.getX();
if (collisionTime < firstCollisionTime)
{
firstCollisionTime = collisionTime;
firstCollisionCorner = i;
firstCollisionBorder = j;
}
}
}
}
if (firstCollisionCorner != -1)
{
g.setColor(Color.BLACK);
g.drawString("First collision:", 20, 40);
g.drawString("Corner "+firstCollisionCorner, 20, 60);
g.drawString("hits border "+firstCollisionBorder, 20, 80);
g.drawString("at time "+firstCollisionTime, 20, 100);
}
}
private static List<Point2D> getCorners(GameObject gameObject)
{
List<Point2D> corners = new ArrayList<Point2D>();
for (int c=0; c<4; c++)
{
corners.add(getCorner(gameObject, c));
}
return corners;
}
private static List<Line2D> getLines(GameObject gameObject)
{
List<Line2D> lines = new ArrayList<Line2D>();
for (int c=0; c<4; c++)
{
lines.add(getLine(gameObject, c));
}
return lines;
}
private static Line2D getLine(GameObject gameObject, int index)
{
return new Line2D.Double(
getCorner(gameObject, index),
getCorner(gameObject, (index+1)%4));
}
private static Point2D getCorner(GameObject gameObject, int index)
{
double x0 = gameObject.getMinX();
double y0 = gameObject.getMinY();
double x1 = gameObject.getMaxX();
double y1 = gameObject.getMaxY();
switch (index)
{
case 0 : return new Point2D.Double(x0, y0);
case 1 : return new Point2D.Double(x0, y1);
case 2 : return new Point2D.Double(x1, y1);
case 3 : return new Point2D.Double(x1, y0);
}
return null;
}
private static Rectangle2D asRectangle(GameObject gameObject)
{
Rectangle2D r = new Rectangle2D.Double(
gameObject.getMinX(), gameObject.getMinY(),
gameObject.getMaxX() - gameObject.getMinX(),
gameObject.getMaxY() - gameObject.getMinY());
return r;
}
@Override
public void mouseMoved(MouseEvent e)
{
playerNextStep = new SimpleGameObject(
e.getX(), e.getY(),
e.getX()+player.getMaxX()-player.getMinX(),
e.getY()+player.getMaxY()-player.getMinY());
repaint();
}
@Override
public void mouseDragged(MouseEvent e)
{
player = new SimpleGameObject(
e.getX(), e.getY(),
e.getX()+player.getMaxX()-player.getMinX(),
e.getY()+player.getMaxY()-player.getMinY());
repaint();
}
}
class Intersection
{
/**
* Epsilon for floating point computations
*/
private static final double epsilon = 1e-6f;
/**
* Computes the intersection of the specified line segments and returns
* the intersection point, or <code>null</code> if the line segments do
* not intersect.
*
* @param line0 The first line segment
* @param line1 The second line segment
* @param location Optional location that stores the
* relative location of the intersection point on
* the given line segments
* @return The intersection point, or <code>null</code> if
* there is no intersection.
*/
public static Point2D computeIntersectionSegmentSegment(
Line2D line0, Line2D line1, Point2D location)
{
return computeIntersectionSegmentSegment(
line0.getX1(), line0.getY1(), line0.getX2(), line0.getY2(),
line1.getX1(), line1.getY1(), line1.getX2(), line1.getY2(),
location);
}
/**
* Computes the intersection of the specified line segments and returns
* the intersection point, or <code>null</code> if the line segments do
* not intersect.
*
* @param s0x0 x-coordinate of point 0 of line segment 0
* @param s0y0 y-coordinate of point 0 of line segment 0
* @param s0x1 x-coordinate of point 1 of line segment 0
* @param s0y1 y-coordinate of point 1 of line segment 0
* @param s1x0 x-coordinate of point 0 of line segment 1
* @param s1y0 y-coordinate of point 0 of line segment 1
* @param s1x1 x-coordinate of point 1 of line segment 1
* @param s1y1 y-coordinate of point 1 of line segment 1
* @param location Optional location that stores the
* relative location of the intersection point on
* the given line segments
* @return The intersection point, or <code>null</code> if
* there is no intersection.
*/
public static Point2D computeIntersectionSegmentSegment(
double s0x0, double s0y0,
double s0x1, double s0y1,
double s1x0, double s1y0,
double s1x1, double s1y1,
Point2D location)
{
if (location == null)
{
location = new Point2D.Double();
}
Point2D result = computeIntersectionLineLine(
s0x0, s0y0, s0x1, s0y1, s1x0, s1y0, s1x1, s1y1, location);
if (location.getX() >= 0 && location.getX() <= 1.0 &&
location.getY() >= 0 && location.getY() <= 1.0)
{
return result;
}
return null;
}
/**
* Computes the intersection of the specified lines and returns the
* intersection point, or <code>null</code> if the lines do not
* intersect.
*
* Ported from
* http://www.geometrictools.com/LibMathematics/Intersection/
* Wm5IntrSegment2Segment2.cpp
*
* @param s0x0 x-coordinate of point 0 of line segment 0
* @param s0y0 y-coordinate of point 0 of line segment 0
* @param s0x1 x-coordinate of point 1 of line segment 0
* @param s0y1 y-coordinate of point 1 of line segment 0
* @param s1x0 x-coordinate of point 0 of line segment 1
* @param s1y0 y-coordinate of point 0 of line segment 1
* @param s1x1 x-coordinate of point 1 of line segment 1
* @param s1y1 y-coordinate of point 1 of line segment 1
* @param location Optional location that stores the
* relative location of the intersection point on
* the given line segments
* @return The intersection point, or <code>null</code> if
* there is no intersection.
*/
public static Point2D computeIntersectionLineLine(
double s0x0, double s0y0,
double s0x1, double s0y1,
double s1x0, double s1y0,
double s1x1, double s1y1,
Point2D location)
{
double dx0 = s0x1 - s0x0;
double dy0 = s0y1 - s0y0;
double dx1 = s1x1 - s1x0;
double dy1 = s1y1 - s1y0;
double len0 = Math.sqrt(dx0*dx0+dy0*dy0);
double len1 = Math.sqrt(dx1*dx1+dy1*dy1);
double dir0x = dx0 / len0;
double dir0y = dy0 / len0;
double dir1x = dx1 / len1;
double dir1y = dy1 / len1;
double c0x = s0x0 + dx0 * 0.5;
double c0y = s0y0 + dy0 * 0.5;
double c1x = s1x0 + dx1 * 0.5;
double c1y = s1y0 + dy1 * 0.5;
double cdx = c1x - c0x;
double cdy = c1y - c0y;
double dot = dotPerp(dir0x, dir0y, dir1x, dir1y);
if (Math.abs(dot) > epsilon)
{
double dot0 = dotPerp(cdx, cdy, dir0x, dir0y);
double dot1 = dotPerp(cdx, cdy, dir1x, dir1y);
double invDot = 1.0/dot;
double s0 = dot1*invDot;
double s1 = dot0*invDot;
if (location != null)
{
double n0 = (s0 / len0) + 0.5;
double n1 = (s1 / len1) + 0.5;
location.setLocation(n0, n1);
}
double x = c0x + s0 * dir0x;
double y = c0y + s0 * dir0y;
return new Point2D.Double(x,y);
}
return null;
}
/**
* Returns the perpendicular dot product, i.e. the length
* of the vector (x0,y0,0)x(x1,y1,0).
*
* @param x0 Coordinate x0
* @param y0 Coordinate y0
* @param x1 Coordinate x1
* @param y1 Coordinate y1
* @return The length of the cross product vector
*/
private static double dotPerp(double x0, double y0, double x1, double y1)
{
return x0*y1 - y0*x1;
}
}
: