Ich progge grad zur Übung mal nen Arkanoid-Clone.

Ich hab nur ein Problem:
Wenn der Ball auf einen Stein trifft, habe ich keine Ahnung, wie er wegspringen muss. (Bzw. ich weiss nich, wie ich das proggen soll)

Für die Bricks habe ich jeweils ein Rechteck:

RECT rBrickCollisionRect;

und für den Ball ne Bounding-Sphere:

POINT pBallPosition;
int iBallRadius;

Collision-Detection kann ich ja noch machen, aber wie weiss ich nun, auf welche Seite des Bricks der Ball auftrifft??

thx, cu, MfG the_viking

(( My =]=H=O=M=E=> Page! ))
Coder bei Brainshock-Interactive und bei Z-Software
My ICQ: #160959446

Zitat:

Collision-Detection kann ich ja noch machen, aber wie weiss ich nun, auf welche Seite des Bricks der Ball auftrifft??

Häh? Ist das nicht eigentlich Bestandteil der Collision-Detection? Ich hoffe, die Kollision besteht nicht darin, daß du einfach schaust, ob der Ball in dem Stein drin ist, das funktioniert nämlich nicht (stell dir vor, der Ball ist so schnell, daß er einfach durch den Stein durchfliegt).

Hier mal ein Denkansatz.

Beschreibe die Bewegung des Balls als f(t) = x0 + t*v
x0 ist die Position (x,y), an der sich der Ball zu Beginn des Frames befindet. v ist die Geschwindigkeit (x,y) des Balls. Anders ausgedrückt ist v die Strecke, die der Ball innerhalb eines Frames zurücklegt.
Dann gelten zwei wichtige Bedingungen: f(0) = x0; in anderen Worten, zum Zeitpunkt "0", am Anfang des Frames, befindet sich der Ball dort, wo er am Anfang des Frames ist (logisch...)
Außerdem: f(1) = x0 + v ist die Position, an der sich der Ball am Ende des Frames (zum Zeitpunkt "1") befindet. Wenn keine Kollision stattfindet ist der Ball am Ende des Frames bei x0+v, d.h. du addierst einfach die Geschwindigkeit zu seiner momentanen Position dazu.

Du hast jetzt eine Möglichkeit, die Flugbahn des Balles zu beschreiben. Wenn die Flugbahn einen Block schneidet kommt es zur Kollision - klar.

Du mußt jetzt für jede Seite jeden Blockes überprüfen, ob die Flugbahn in diese Seite hineingeht. Nimm z.B. die linke Seite eines Blockes. Die linke Seite eines Blockes ist eine Strecke, wenn du die ins unendliche verlängerst hast du eine Gerade. Ihre Geradengleichung ist:
x = const.
Die Gerade enthält alle Punkte, die an einer bestimmten x-Stelle sind, und einen beliebigen y-Wert haben (y taucht in der Gleichung nicht auf, ist also beliebig).
Du mußt jetzt die Flugbahn des Balles mit dieser Gerade schneiden. Zur Erinnerung, die Flugbahn wird als f(t) = x0+t*v beschrieben (x0 und v sind Vektoren). Wenn du diese Formel in ihre x- und y-Komponenten zerlegst erhältst du:

x = x0 + t*vx
y = y0 + t*vy

Damit kannst du die x/y-Position des Balles zu jedem Zeitpunkt berechnen. Nun mußt zu herausfinden, zu welchem Zeitpunkt t der Ball die Gerade der Blockseite schneidet. Das ist ein sehr einfaches Gleichungssystem, das du lösen kannst, in dem du obiges x = const. einsetz:

const = x0 + t*vx

umgeformt: t = (const - x0) / vx

Interessant an dieser Gleichung ist der Nenner, vx. Wenn vx gleich 0 ist ist t nicht definiert (Division durch 0 ist nicht erlaubt). Das ist aber logisch, denn wenn vx=0 ist, dann bewegt sich der Ball vertikal nach oben oder unten, d.h. er kann mit der ebenfalls vertikale Seite des Blockes gar nicht zusammenstoßen! Im Programm mußt du natürlich den Fall vx==0 überprüfen, damit es keine Division durch 0 gibt.

Mit t = (const-x0)/vx kannst du natürlich den Zeitpunkt, zu dem sich die Flugbahn und die Gerade der Blockseite schneiden, bestimmen. Wenn t < 0 ist oder t > 1 ist, dann bedeutet das, daß sie sich in diesem Frame erst gar nicht schneiden. Du kannst diese Seite des Blocks also getrost ignorieren (die anderen Seiten des Blockes mußt du aber nach wie vor überprüfen!).

Nun wissen wir also, daß der Ball in diesem Frame die Gerade dieser Seite des Blocks schneiden wird. Es kann aber sein, daß der Ball unterhalb oder überhalb der eigentlichen Seite vorbeifliegt. Um das zu überprüfen mußt du die y-Koordinate berechnen, an der sich die Gerade mit der Flugbahn schneidet. Oben hatten wir:

y = y0 + t*vy

In diese Gleichung setzt du einfach das vorher berechnete t ein, dann kannst du y errechnen. Wenn y unterhalb der Oberkante und oberhalb der Unterkante des Blocks ist kommt es zur Kollision.

Du mußt jetzt diese Berechnung für alle Seiten des Blockes durchführen (für die Ober- bzw. Unterseite müssen x und y natürlich vertauscht werden). Wenn der Ball mit keiner Seite kollidiert ist alles in Ordnung. Wenn er mit mehr als einer Seite kollidiert mußt du die t-Werte für die Kollisionen vergleichen - die Seite mit dem niedrigsten t-Wert ist die Seite, mit der die Kollision stattgefunden hat.

Du hast jetzt also den exakten Kollisionspunkt. Je nachdem, ob du eine horizontale oder eine vertikale Seite getroffen hast mußt du entweder vy := -vy oder vx := -vx zuweisen.

Um perfekte Physik zu erreichen mußt du den Ball nach einer Kollision in einem Frame noch weiterbewegen. Wenn der Ball zum Zeitpunkt t = 0.1 kollidiert, muß er noch um (1.0-t)*v, d.h. um 0.9*v weiterbewegt werden - natürlich mit der neuen Bewegungsrichtung. Und auch für die Abprallbewegung, die nur noch (1.0-t)*v weit geht mußt du wieder Kollision durchführen. Und dann paßt alles =)

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

... womit die Aussage "zur Übung" in ein ganz anderes Licht gerückt wäre =)

TheTinySteini
Coder Poke646
"Don't Panic" - Hitchhiker's Guide to the Galaxy

*PERFECT*, Prefect! *g* thx... beschäftige mich damit

thx, cu, MfG the_viking

(( My =]=H=O=M=E=> Page! ))
Coder bei Brainshock-Interactive und bei Z-Software
My ICQ: #160959446

*Thread Ausgrab*

Omg, ja auch ich muss mich bei Prefect für diesen überaus belehrenden Thread bedanken :))

Auf der Basis der von Prefect genannten Technik, habe ich die ganze Sache so weit umgeschrieben, damit es auch für Hitboxes im 2D-Raum funktioniert.

Anfänglich hatte ich ein paar Schierigkeiten (z.B. wegen Konzentrationsmangel ein fatales || anstelle eines && geschrieben =) aber ca 3h langem Überlegen und auf Zetteln-Rumkritzeln und 1000x Nachrechnen hat's dann geklappt :)

=> Ich finde dieser Thread gehört verschoben dieses
=> Knowledgedatabase Board (sowas gab's hier doch, oder?),
=> damit dieser Thread nicht in den Tiefen der schon so
=> riesigen Datenbank verloren geht!

C ya :)

Against TCPA | Resourcecode.de | Blender 3D | [ Darkzone | Pandorra | Alpine ]

Sorry, dass auch ich den Thread wieder ausgrabe, aber taten sich einige Fragen auf (2 um genau zu sein):

-)Was ist const, in der obigen Rechnung? Nein, fangen wirs anders an: Was ist eine Geradengleichung überhaupt?
In der Schule werden wir das wahrscheinlich niemals behandeln und Google hat mir im Endeffekt immer irgendwelche Dinge ausgespuckt, die schon darauf bauen, dass man weiß, was eine Geradengleichung überhaupt ist.

-)Was bedeutet ':=' ?
Darauf hatte Google überhaupt keine Antwort, da man danach scheinbar nicht suchen darf. Ob das irgendwelche zusätzlichen Zeichen, wie zb + sind?

Grüße und Vielen Dank,
Zgerk

„Und da wir uns ja seit heute etwas näher gekommen sind, kann ich nur sagen: Mir hilft da immer Norther volle Lautstärke (so wie jetzt), sodass die ganzen unrasierten, Wasserpfeife rauchenden, alternativen Wichsstudenten aus ihren, aus Bananenschalen und Abfall gebastelten, Sitzkissen fliegen.“

:= bedeutet "ist definitiert als"

\o tanz den naziprau! o/

And more than ever, I hope to never fall,
Where enough is not the same it was before

Zitat:

Was ist const, in der obigen Rechnung?

C++:
const int x = 5;

Zitat:

Was ist eine Geradengleichung überhaupt?

Als Mathematiker ist man natürlich fasziniert von solchen Geraden (rote Linie) und möchte unbedingt in der Lage sein den Y-Wert der Geraden zu jeder Stelle (X-Wert) zu ermitteln. Das ist der Punkt an dem die Geradengleichungen zum Einsatz kommen.

Eine Geradengleichung sieht so aus: f(x) = mx + b

Hierbei ist x eine Variable, an dessen Stelle ein Wert in f(x) eingesetzt werden kann. Zum Beispiel: f(5) = m*5 + b

Nun haben wir hier aber noch 2 unbekannte "Variablen" im Funktionsterm. Fangen wir bei m an. Bei m handelt es sich im Grunde genommen um eine Konstante, die die Steigung des Graphen angibt. Schaust du nochmal in die Skizze, siehst du ein paar blaugezeichnete Dreiecke. Solche Dreiecke nennt man Steigungsdreieck, mit dem man (zumindest bei einer Geraden) an jeder x-beliebigen Stelle des Graphen die Steigung der Geraden errechnen kann.
Dazu zeichnet man ein beliebiges Dreieck an die Gerade und misst dann die Längen der Katheten dieses Dreiecks. In diesem Fall ist x = 5 und y = 10.
m ergibt sich aus y/x -> m = y/x -> m = 10/5 -> m = 2
Das heißt, dass die Steigung der Geraden an jeder Stelle 2 beträgt (wäre die Steigung an jeder Stelle eine Andere, hätten wir es hier nicht mit einer Geraden zu tun ^_^)

m ist eine Konstante (2) nun sind wir schon so weit: f(x) = 2x + b

So, what's left ? Klar, da ist noch dieses b !
b ist der sogenannte y-Achsenabschnitt. In meiner Skizze entspringt die Gerade dem Ursprung des Koordinatensystems (x=0 | y=0). Deshalb ist b in diesem Fall 0. Sollte der Graph aber zb die y-Achse an der Stelle x=0 beim y-Wert 5 schneiden, so wäre b = 5.

Okay.. nun sind wir so weit: f(x) = 2x + 0 bzw. f(x) = 2x

Möchten wir nun also den y-Wert an der Stelle 5 errechnen, so können wir das nun tatsächlich machen, indem wir für x den Wert 5 einsetzen:

f(5) = 2 * 5 = 10 (ein Blick in den Graphen verrät uns, dass das stimmt!)

Das war aber reichlich langweilig, da wir diesen Wert auch locker vom Graphen ablesen hätten können. Probieren wir doch mal etwas, das wir mit dem Geodreieck nicht hätten messen können.. wie wär's mit 7,662 ?

Kein Problem: f(7,662) = 2 * 7,662 = 15,324 Wunderbar!

Die entsprechende C/C++ Funktion sähe dann so aus:

float y(float x)
{
return (2*x);
}

bzw. um das ganze etwas variabler zu gestalten:

float y(float x, float m, float b)
{
return(m*x + b);
}

Ein Aufruf für unseren Fall sähe dann so aus: y(5, 2, 0);

Aber irgendwann wird's auch echt mal langweilig, wenn man nur die y-Werte errechnen kann. Jedoch gibt es ja noch so Sachen wie Termumformungen. Mit Hilfe solcher Techniken, lässt sich die oben gezeigte Funktion z.B. so umstellen, dass wir einen Y-Wert in die Funktion einsetzen und dann den X-Wert (also die Stelle) ermitteln, an dem der Y-Wert im Graphen dem eingesetzten Wert entspricht.

Gehen wir also zur Ausgangsfunktion zurück und machen uns das Leben ein wenig einfacher, indem wir für f(x) nun y einsetzen: y = mx + b
Unser Ziel ist es, das ganze nach x aufzulösen.

Dazu subtrahiere ich zunächst b vom Term und erhalte: y - b = mx
Jetzt gilt es noch das m dort wegzubekommen.
Also dividiere ich durch m und erhalte: (y - b) / m = x bzw x = (y - b) / m
Machen wir daraus wieder eine Funktion: f(y) = (y - b) / m
Und setzen unsere bekannten Werte ein: f(y) = (y - 0) / 2 also f(y) = y/2
So können wir durch Einsetzen eines beliebigen Y-Wertes die entsprechende Stelle (X-Wert) herausfinden:

f(10) = 10/2 = 5 (siehe Graph: stimmt)
f(20) = 20/2 = 10 (siehe Graph: stimmt auch)

Nun.. das ist eigentlich schon (fast) das ganze Geheimnis von Geradengleichungen. Natürlich kannst du das Ganze auch noch nach b umformen.. aber das muss ich jetzt wohl nicht mehr vorführen.

Ich hoffe das hier hat dir etwas geholfen und unterstützt dich beim Verstehen dieses Threads. Viel Spaß noch dabei ;-)

Against TCPA | Resourcecode.de | Blender 3D | [ Darkzone | Pandorra | Alpine ]

Also erstmal riesiges Thx, TheVoice für die Arbeit, die du dir gemacht hast =)

Langsam, denke ich, fange ich an es zu verstehen. Das einzige, was mir immer noch nicht einleuchtet ist das

x = const

der linken Seite eines Blocks. Soll das dafür stehen, dass der Graph/die linke Seite keine Steigung hat?
Das denke ich nicht, denn es muss ja nicht so ein Block sein:
▒
(Ja, ich weiß: ASCII-Arts rulen :D) Er kann ja auch gedreht sein.

Also das leuchtet noch nicht ganz ein :)

Grüße,
Zgerk

/edit: Ack das Zeichen geht nicht.
Naja ASCII wärs 177 gewesen.

„Und da wir uns ja seit heute etwas näher gekommen sind, kann ich nur sagen: Mir hilft da immer Norther volle Lautstärke (so wie jetzt), sodass die ganzen unrasierten, Wasserpfeife rauchenden, alternativen Wichsstudenten aus ihren, aus Bananenschalen und Abfall gebastelten, Sitzkissen fliegen.“

@Zgerk (grr, ich wollte grad lag schreiben): ¢Æ

/edit
Mist, der ASCII tut nicht :(

[MfG Cerberus]
Wenn die Welt auf dem Kopf steht, liegt Dir der Himmel zu Füssen!

Voice hat leider nur die halbe Wahrheit gesagt was Geraden angeht.
y = f(x) = mx + t beschreibt eine Gerade in Form einer Funktion. Diese Darstellung hat einen entscheidenden nachteil: es ist unmöglich, Vertikalen mit ihr zu beschreiben (diese hätten ja unter anderem quasi eine unendliche Steigung m, und das gibt Streß).

Deswegen beschreibt man Gerade (im 2-dimensionalen Raum) auch gerne als
g: ax + by + c = 0
Alle Punkte (x, y) die auf der Geraden liegen erfüllen diese Gleichung und umgekehrt.
Solange b != 0 kann man diese Form sehr leicht in die Funktionsform umwandeln. Wenn b = 0, dann hat man:
ax + c = 0 bzw. x = -c/a
Alle Punkte, die auf dieser Geraden liegen haben einen x-Wert von -c/a. Über den y-Wert ist nichts ausgesagt; das bedeutet, daß y jeden beliebigen Wert annehmen kann (diese eigentlich simple Tatsache ist die Hauptschwierigkeit für viele). Alle Punkt mit dem gleichen x-Wert und beliebigen y bilden natürlich eine vertikale Gerade.

Wenn in meinem ursprünglichen Post x = const steht ist das const also der x-Wert der vertikalen Gerade, die die Seite eines Blockes bildet.

Wenn du schräge Blöcke haben willst mußt du halt die volle Form ax + by + c = 0 verwenden und a und b richtig setzen. Weil ich nicht alles immer wieder schreiben will, http://www.resourcecode.de/?tutorial=1&id=78 (ist zwar mehr auf 3D ausgelegt, aber weil Geraden in 2D und Ebenen im 3D letztendlich dasselbe sind paßt es auch teilweise).

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

Vielen Dank an Prefect und TheVoice. Zusammen mit dem Ray-Polygon-Collision Tutorial (wo auch die Ebenengleichung verwendet wird) von Gametutorials, denke ich es zu verstehen und auch implementieren zu können.

Leider fehlt mir zu letzterem im Moment die Zeit, aber das werde ich nachholen.

Also vielen Dank euch beiden, nochmal :)

Grüße,
Zgerk

„Und da wir uns ja seit heute etwas näher gekommen sind, kann ich nur sagen: Mir hilft da immer Norther volle Lautstärke (so wie jetzt), sodass die ganzen unrasierten, Wasserpfeife rauchenden, alternativen Wichsstudenten aus ihren, aus Bananenschalen und Abfall gebastelten, Sitzkissen fliegen.“

man KANN eine vertikale ganz einfach so beschreiben: x=5 (zb ... )
das ist dann die mathematisch richtige beschreibung einer senkrechten zur x-achse, die selbige im punkt bla(5|0) schneidet, im 2dimensionellem raum.