spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Wenn Du das Iso-Tile als 4 Linien ansiehst, dürfte es nicht so schwer sein. Ein Rechteck siehst Du auch als 4 Linien an. Den Schnittpunkt zwischen zwei Linien zu bestimmen ist ja nicht so schwer, und den Schnittpunkt zwischen Kreis und Linie auch. Also müsstest Du so alles hinkriegen.

Schnittpunkt zwischen zwei Linien im 2D-Raum:

Linie 1:
Startpunkt (ax, ay), Richtung (bx, by)
s steht für den Abschnitt auf der Linie.
x = ax + s * bx
y = ay + s * by

Linie 2:
Startpunkt (cx, cy), Richtung (dx, dy)
t steht für den Abschnitt auf der Linie.
x = cx + t * dx
y = cy + t * dy

Gleichsetzen:
ax + s * bx = cx + t * dx
ay + s * by = cy + t * dy

Rüberbringen:
ax + s * bx - cx - t * dx = 0
ay + s * by - cy - t * dy = 0

Umformen:
s * bx + t * (-dx) = cx - ax
s * by + t * (-dy) = cy - ay

2 Gleichungen mit 2 Variablen (s und t), die wir kennen möchten! Determinante D bilden:

D =
|bx, -dx|
|by, -dy| = -bx*dy + by*dx = by*dx - bx*dy

Nun die Determinante für s (man könnte auch t nehmen, es ist egal):

Ds =
|cx - ax, -dx|
|cy - ay, -dy| = ax·dy - ay·dx - cx·dy + cy·dx

Damit können wir den Abschnitt s des Schnittpunkts berechnen:

s = Ds / D
= (ax·dy - ay·dx - cx·dy + cy·dx) / (by*dx - bx*dy)

Wenn für D null rauskommt, dürfte es keinen Schnittpunkt geben. Achtung: hier wird mit Geraden gerechnet, nicht mit Linien. Daher musst Du nachher noch prüfen, ob der gefundene Schnittpunkt an der Stelle s überhaupt in der Linie drin ist. Wenn Du als Richtungsvektoren (bx, by) bzw. (dx, dy) direkt den Verbindungsvektor zwischen den zwei Punkten, aus denen Du die Linie erstellen möchtest, angibst, dann muss s im Intervall [0; 1] liegen, ansonsten ist es außerhalb der Linie.

Die Koordinaten des Schnittpunkts sind nun:
sx = ax + s * bx
sy = ay + s * by

Oder, wenn Du t anstatt s ausrechnest:
sx = cx + t * dx
sy = cy + t * dy

Es ist egal, ob Du s oder t nimmst, es kommt derselbe Schnittpunkt raus - wenn es denn einen gibt.

Schneidet eine Linie einen Kreis?

Linie:
Startpunkt (px, py), Richtung (dx, dy)
s steht für den Abschnitt auf der Linie.

Kreis:
Mittelpunkt (mx, my), Radius r

Für alle Punkte (x, y) auf dem Kreis gilt, dass die Entfernung zum Mittelpunkt gleich dem Radius ist. Also:

(x - mx)² + (y - my)² = r²

Jetzt setzen wir für x und y die Linie ein:

((px + s * dx) - mx)² + ((py + s * dy) - my)² = r²

Löse das nach s auf... da kommt was ziemlich Langes raus
Hier findest Du was dazu: http://mathworld.wolfram.com/Circle-LineIntersection.html

Cool David, kannst du das nich noch mit zu deinen tuts stellen? Is ja schon fast ein tut. Dann brauch man, wenn man das nochmal nachlesen will nich immer hier im forum nach dem thread suchen.

Hi!

Hier noch eine andere Art, den Schnittpunkt zwischen zwei Linien zu bestimmen:

Gerade 1 geht von x1/y1 zu x2/y2
Gerade 2 geht von x3/y3 zu y4/y5

Zuerst die Steigungen der beiden Geraden ausrechnen:

m1 = (y2-y1) / (x2-x1)
m2 = (y4-y3) / (x4-x3))

Dann die Nulldurchgänge der y Achse:

b1 = y1-x2*m1
b2 = y3-x3*m2

Dann kann man den Schnittpunkt berechnen:

xs = (b1-b2) / (m2-m1)
ys = m1*xs+b1


Wichtig sind 2 Sonderfälle:
Wenn (m1 == m2) && (b1==b2) sind, dann hat man unendlich viele Schnittpunkte (Geraden liegen aufeinander)
Wenn (m1==m2) && (b1!=b2) sind, dann sind die Geraden parallel und es gibt keinen Schnittpunkt.


Wenn Du nun einen Schnittpunkt hast, musst Du noch prüfen ob das auch für die Linien-Segmente gilt. Einfach schauen ob zb xs zwischen x1 und x2 liegt und y3 und y4 auf unterschiedlichen Seiten sind.


Auch wenn Du drum gebeten hast nicht mit Pixelgenauer Kollision zu kommen: Ich finde das im Grunde einfacher. Einfach alle Tiles bei denen die Bounding-Box Kollision anspringt pixelgenau prüfen. Musst ja nur die Bereiche locken und je nach den transparenten Farben schauen.


cya...TheWanderer

@TheWanderer: Die Methode mit der Steigung hat aber einen Nachteil: Du kannst so keine vertikalen Geraden verwenden, weil die ja dann eine "unendliche" Steigung hätten, d.h. Du teilst da irgendwo durch null. Der Vektoransatz ist flexibler.

@Ghandi: Ja, könnte ich machen!

Hi!

@Patrick:
So schwer ist das auch wieder nicht. Wenn Du natürlich nur Tiles hast, die das Rect fast ganz ausfüllen, ist das ok. Sobald es sich aber um Schrägen, Kugeln etc handelt, wird der Spieler keine Lust haben es zu Spielen wenn Du keine Lust hast ne faire Kollision einzubauen =)
Als wir damals die Demo-Version von Takatis rausgebracht haben, haben uns einige für die "nur Boundingbox Kollision" fast gesteinigt =)


@David:

Formel:
m1 = (y2-y1) / (x2-x1)
m2 = (y4-y3) / (x4-x3))


Ausführung:
temp = (x2-x1);
if (temp == 0)
temp = 0.000001f;
m1 = (y2-y1)/temp;

PS: Das merkt keiner


cya...TheWanderer