Kugel/Kreis prallt von Eck/Kante ab

[dino]

hä?

ich habe eine richtungsvariable als Integer und werde die berechneten gradzahlen immer runden

[Cöster]

Zitat:

Zitat von Sidorion

Nichts, weil Du u.U. nicht alle 1° einen Pixel hast, sondern alle 0,576° oder alle 3,6678°, je nachdem wie groß Dein Kreisradius ist.
Bei Raduis 0 hast du 1 punkt, bei 1 sinds 4, bei 2 vielleicht 12 usw.
1. musst Du immer berechnen, weil sich der Kreis in eine der acht Haupt-und nebenachsen um 1 Pixel bewegt.

Bei 5 Grad hat man vielleicht Floats für die Koordinaten, aber die kann man ja runden und dann hat man schon alle Pixel auf der Kreisbahn. Die Speichert man sich dann in einen array oder so und fragt bei verschiebung nach rechts, links, oben oder unten dann immer jeweils die Hälfte dieses Arrays ab. Das sind dann all die Punkte, auf denen sich jetzt der Kreis befindet wo er vorher noch nicht war.

[Sidorion]

Andersrum wird ein Schuh draus. Die Koordinaten der zu testenden Pixel sind natürlich Integer, aber der Winkel, den sie aufspannen nicht. Drum würde ich deren Anzahl ermitteln (hängt vom Radius ab) und dann ihre Lage und Winkel in einem Array speichern, und zwar sortiert nach Winkel. Dann kann man abhängig vom Richtungsvektor den ersten und letzten ermitteln (Kreuzprodukt=0) und testet alle dazwischen auf Kollision.

Übrigens: Die Richtung als Integer speichern ist quatsch, da Du sonst zu große Rundungsfehler beim Abprallen bekommst.

[Cöster]

Nur die zu zeichnenden Koordinaten sind Integer. Die wirklichen Koordinaten sind natürlich Floats, bei der Kollision sollte man aber die Integer-Koordinaten prüfen, genau wie du es meintest. Die sind die gerundeten Floats.
Natürlich sind die Richtungen eigentlich Floats. Anhand dieser Float-Werte werden dann die neuen wirklichen Koordinaten (Floats) berechnet, wenn der Kreis um die Länge eines Pixels in die Richtung bewegt wird. Die Integer-Koordinaten können sich dann jeweils aber höchstens um einen Pixel verändern. Es gibt also bei den Integer-Koordinaten nur 8 mögliche Richtungen: 0, 45, 90, 135, 180, 225, 270 oder 315 Grad. Dann kommt die Kollisionsabfrage mit diesen Integer-Koordinaten.

Es wird dann auch nicht zu großen Rundungsfehlern kommen, weil alle Rechnungen mit den Floats gemacht werden. Nur bei der Kollisionsberechnung werden Integer genommen.

[dino]

ok ich machs so, nur ist mein Kreis mehr als nur ein Punkt, also kriege ich mehr als 8 Richtungen

[Cöster]

Wenn du ihn um die Länge von z.B. 5 Pixeln verschiebst, kann es natürlich sein, dass du ihn z.B. um 3 Pixel nach rechts und 4 nach unten verschiebst. Dann hättest du auch mehr als 8 Richtungen. Wenn du den Kreis zwischen den Kollisionsabfragen aber immer nur um die Länge eines Pixels in Float-Richtung verschiebst, stehen für die Integer nur 8 Richtungen zur Auswahl.

[dino]

nein der ort hab ich mir immerschon float erdacht...
nur grad wollte ich unter umständen als integer nehmen aber so genau sind wir nun

[Cöster]

Zitat:

Zitat von dino

nein der ort hab ich mir immerschon float erdacht...
nur grad wollte ich unter umständen als integer nehmen aber so genau sind wir nun

??? Was? Ich versteh kein Wort.

Was sind denn die Vorteile, wenn du den Winkel als Integer nimmst? Und wieso hast du jetzt mehr als 8 Richtungen (bei integer-Koordinaten, irgendwo brauchst du die ja auch als Integer, zum Zeichnen)

[dino]

TPoint Integer: ich werde sie mir nicht als integer speichern sondern bei jedem aufruf der floatvariable runden
Richtungen: da ich einen großen Kreisund nicht bloss nen Pixel habe erhöht sich die Anzahl an Pixel, die überwacht werden müssen...
Winkel (in Grad) als Integer: ich dachtemir erst,dann beschränkt sich das ganze auf 360 verschiedene Möglichkeiten, sehe aber nun davon ab

[Cöster]

Zitat:

Zitat von dino

Richtungen: da ich einen großen Kreisund nicht bloss nen Pixel habe erhöht sich die Anzahl an Pixel, die überwacht werden müssen...

Die Anzahl der Punkte natürlich. Aber du hast trotzdem nur 8 mögliche Richtungen, wenn du zwischen den Kollisionsabfragen immer nur um einen Pixel verschiebst.

Beispiel:
Du hast einen Kreis (Mittelpunkt: 0,0), den du pro Sekunde um 3 Pixel nach unten und 4 nach rechts verschiebst. Die Strecke, die in einer Sekunde zurückgelegt wird, beträgt also 5 (denn 3²+4²=5²).
Du verschiebst zwischen den Kollisionsabfragen aber immer nur um die Länge eines Pixels. Pro Sekunde machst du also 5 mal die Kollisionsabfrage:
Zuerst verschiebst du um 3/5 nach unten und 4/5 nach rechts (Mittelpunkt jetzt: 4/5, 3/5) und machst dann die Kollisionsabfrage, allerdings mit den gerundeten Koordinaten (1,1). Verschiebung also nach unten-rechts.
Dann verschiebst du nochmal genau so weit (Mittelpunkt jetzt: 8/5, 6/5). Der Mittelpunkt für die Kollisionsabfrage ist jetzt 2,1. Die Verschiebung jetzt also nur nach rechts.

So kommt man am Ende nur auf 8 mögliche Richtungen: oben, unten, rechts, links und die 4 Richtungen, die dazwischen liegen. Die Anzahl der zu überwachenden Pixel ist dann der halbe Umfang des Kreises, also pi*Radius.

[dino]

achso...
die Richtungsvariablen nicht als Integer zu deklarieren stand für mich von vornerein fest!

es ging mir darum alle Pixel zu erfassen, die den Kreis berühren und der Richtung zugewandt sind

[Florian H]

Hallo,

ich bin gerade ziemlich verwirrt.

Ich habe offensichtlich damals nicht mehr auf den Beitrag geantwortet, geschweige denn ihn als erledigt markiert.

Und gerade habe ich ihn zufällig nach fast einer Stunde google-Suche zu dem Thema gefunden, weil ich gerade bei einem auch schon etwas älteren Programm von mir, das ich wieder ausgegraben habe, vor exakt dem Problem stehe - wohl dasselbe Programm wie damals.

Jedenfalls habe ich hier ja eine prima Lösung und ärgere mich, dass ich vorhin exakt den Gedanken zu schnell wieder verworfen habe.

Auch wenns 1,5 Jahre später ist: Danke an alle für eure Antworten, zumindest die ersten 5-6 waren ja noch aufs eigentliche Thema bezogen :stupid:
Werde mich jetzt an die Implementierung machen, dann kann ich hoffentlich bald ins Bett.

Edit: Ich glaube, ich bin doch zu doof, oder es ist zu spät. Aber jetzt kriege ich das mit dem Abprallwinkel nicht so richtig gebacken.
Also wie die Kugel an der schiefen Gerade abprallt. Habe da alles mögliche mit Winkeln und Skalarprodukten probiert, aber nur seltsame Resultate erzielt.
Habe also die Geschwindigkeit der Kugel (Richtungsvektor) und den Normalenvektor der Gerade vom Kugelmittelpunkt zum Kollisions-Eck des Quadrates. Nur wie die jetzt zusammen verwurstelt werden, damit ein richtiger Ergebnis-Richtungsvektor rauskommt, ist mir grade nicht klar.

[dino]

sollte

richtungsvektor vorher - 2* normierter Richtungsvektor :(mittelpunkt->kollisionspunkt)

nicht das richtige Ergebnis liefern?

[Florian H]

Zitat:

Zitat von dino

sollte

richtungsvektor vorher - 2* normierter Richtungsvektor :(mittelpunkt->kollisionspunkt)

nicht das richtige Ergebnis liefern?

Danke schonmal für deine Antwort!

Ich habe das mal getestet, aber entweder habe ich es falsch verstanden (was mich nicht wundern würde, offenbar reicht eine Woche Semesterferien, um jeglichen Zugang zur Mathematik zu verlieren :wall: ), oder es stimmt noch nicht ganz.

Im Anhang mal ein Bild: Der Ball kommt horizontal angeflogen und trifft so auf die rechte obere Kante, dass der Richtungsvektor (Mittelpunkt->Kollisionspunkt) "im 45°-Winkel steht", normiert also (1,1) entspricht.
Der Ball müsste dann, wie hier erörtert wurde, an dessen Normalenvektor abprallen, also senkrecht nach oben rollen (gelber Vektorpfeil).
Laut deiner Formel (und meiner Interpretation) bewegt er sich aber nach schräg rechts oben (Richtungsvektor (3,-2) ), was ja ansich nicht sein kann.

Woran liegt's?

[dino]

ich dachte alle vektoren sind und bleiben normiert (das heisst, dass die norm gleich 1 ist, was der fall ist, wenn bei einem vektor die komponenten quadriert, addiert, gewurzelzieht 1 ergibt also auch wenn man nur quadriert und addiert)

aber wenn ich die Vektoren normiere klappt das auch nicht

ich denk nochmal drüber nach :)

[Florian H]

Ein Kumpel hat jetzt tatsächlich eine funktionierende Lösung gewusst, die ich euch natürlich nicht vorenthalten will:

Zitat:

also zunaechst mal normierst du den geschwindigkeitsvektor (vx,vy), so dass er norm 1 hat (also vx^2+vy^2=1 ist).

dann ist das skalarprodukt aus geradenrichtungsvektor g = (gx,gy) und geschwindigkeitsvektor v = (vx,vy) gegeben durch <v,g> = vx*gx+vy*gy

vektorrechnung: die projektion von v auf g ist <v,g>*g (wenn v norm 1 hat)

damit ist das Lot von v auf g das orthogonale komplement dazu also v-<v,g>*g

das Lot musst Du nun 2x subtrahieren um zu spiegeln, also vneu = v - 2*(v-<v,g>*g)

dann waere für den fall dass v und g senkrecht sind vneu = -v, also einfach zurueck

:drunken:

[dino]

deckt sich das mit dem, was ich hier gerade ausgerechnet hab?

also zunächst richtungsvektor vorher und vektor mittelpunkt->kollisionspunkt normieren

dann:

vorher=(v1,v2)
Kollision=(k1,k2)
Ergebnis=(v1-2*Wurzel[v1²k1²+v2²k2²]*k1,v2-2*Wurzel[v1²k1²+v2²k2²]*k2)

oder wenn man nicht vorher normiert:

vorher=(v1,v2)
Kollision=(k1,k2)
Ergebnis=((v1/Wurzel[v1²+v2²])-2*Wurzel[(v1²/[v1²+v2²])(k1²/[k1²+k2²])+(v2²/[v1²+v2²])(k2²/[k1²+k2²])]*(k1/Wurzel[k1²+k2²]),(v2/Wurzel[v1²+v2²])-2*Wurzel[(v1²/[v1²+v2²])(k1²/[k1²+k2²])+(v2²/[v1²+v2²])(k2²/[k1²+k2²])]*(k2/Wurzel[k1²+k2²]))

:balloon:

[Cyf]

Zitat:

Zitat von dino

nun das sind aber sehr sehr viele Punkte...

Deswegen braucht Kollisionberechnung in der Regel auch viel Rechenzeit, bei Spielen wird die Karte (oder was auch immer dein Spielbereich ist) deswegen in der Regel in Gebiete aufgeteil und die Objekte in diesen geordnet gespeichert, so dass bei der Berechnung nur die Punkte im selben Gebiet überprüft werden müssen.

Nachteile:
-keine Kollisionsberechnung, wenn deine Kugel mit überaschend hoher Geschwindigkeit von einem in ein anderes Gebiet übergeht, sowas muss man dann erst noch überprüfen.
-mit Objekten deren Mittelpunkt sich in verschiedenen Gebieten befindet, die aber aufgrund ihrer Größe trotzdem kolidieren müssten, siehts auch schwierig aus

Bei vielen (3D-)Spielen konnt man früher übrigens diese Unterteilung daran erkennen, dass nur eine bestimmte Anzahl Gebiete hinter dem Spieler noch gezeichnet wurde und danach ausgeblendet. Allerdings überprüft man da nun in der Regel einfach erst die Sichtbarkeit.

[dino]

Zitat:

also zunaechst mal normierst du den geschwindigkeitsvektor (vx,vy), so dass er norm 1 hat (also vx^2+vy^2=1 ist).

dann ist das skalarprodukt aus geradenrichtungsvektor g = (gx,gy) und geschwindigkeitsvektor v = (vx,vy) gegeben durch <v,g> = vx*gx+vy*gy

vektorrechnung: die projektion von v auf g ist <v,g>*g (wenn v norm 1 hat)

damit ist das Lot von v auf g das orthogonale komplement dazu also v-<v,g>*g

das Lot musst Du nun 2x subtrahieren um zu spiegeln, also vneu = v - 2*(v-<v,g>*g)

dann waere für den fall dass v und g senkrecht sind vneu = -v, also einfach zurueck

vorher(geschwindigkeitsvektor v?)=(v1,v2)
Kollision(geradenrichtungsvektor g?)=(k1,k2)

Skalarprodukt:

v1*k1+v2*k2

projektion auf vorher:

(k1*(v1*k1+v2*k2),k2*v1*k1+v2*k2)

Lot ist dann

( v1-k1*(v1*k1+v2*k2) , v2-k2*(v1*k1+v2*k2) )

Ergebnis = ( v1-2*(v1-k1*(v1*k1+v2*k2)) , v2-2*(v2-k2*(v1*k1+v2*k2)) )

oder auch

Ergebnis = ( 2*(k1*(v1*k1+v2*k2))-v1 , 2*k2*(v1*k1+v2*k2))-v2 )

ist wohl so garnicht das selbe wie

(v1-2*Wurzel[v1²k1²+v2²k2²]*k1,v2-2*Wurzel[v1²k1²+v2²k2²]*k2)

wobei er wahrscheinlich recht hat

oh man ich bin im 3. Semester MAthematik und baue hier nur blödsinn :(