Hänge bei meinem Mini-Spiel an den Kollisionen fest

[starcow]

Tach Zusammen.

Ich komme bei meinem kleinen Mini-Spiel irgendwie bei den Kollisionen nicht weiter.
Genauer gesagt, fehlt mir die konkrete Idee, wie man so etwas sinnvoll lösen kann.

Um mal bisschen deutlicher zu machen was mir vorschwebt, habe ich eine Grafik erstellt.


Es soll zu Beginn erstmal nur zwei Typen von Objekten geben. Kreaturen und Projektile.
Mit Projektile sind z.B Pfeile gemeint, die eine Kreatur abfeuern können soll.
Dabei steuert man als Spieler vorerst einfach eine der Kreaturen.
Kreaturen und Projektile sind beides Entitys, die in einem Manager gemeinsam verwaltet werden.
Es soll nun ein Ereignis ausgelöst werden, wenn die beiden Objekt-Typen miteinander, untereinander oder an den Wänden kollidieren.

Mein Problem ist, dass ich nicht weiss, welche Art von Kollision nun sinnvoll wäre.
Einfach Kreise gegeneinander abzufragen, würde ich vermutlich noch irgendwie hinbekommen. Da muss ja auch nicht viel anderes gemacht werden, als die Distanz zum Mittelpunkt untereinander zu vergleichen.

Wie aber prüfe ich das ganze gegen eine Wand? Hier entsteht doch sehr schnell das Problem, dass bei sich schnell bewegenden Kreaturen/Projektilen, deren "Sprünge" (von der letzten Position zur neuen Position) so gross werden können, das sie Hinternisse einfach "überspringen".
Hier fehlt mir komplett ein Ansatz.
Zudem wäre es ja wünschenswert, wenn man an den Wänden entlang "silden" würde. So wie es einem aus vielen anderen Spielen bekannt ist.
Soll heissen, nicht ein simples laufen/stoppen, sondern eine Art stark vereinfachte Physik. Idealerweise könnte man dann auch die anderen Kreaturen umher schupsen.

Bei dem Material was ich so im Netz gefunden habe, werden meistens nur Kreise oder Rechtecke miteinander verglichen. Da ist mir zudem aufgefallen, dass sich diese beiden Methoden schon ziemlich stark unterscheiden und sich ein "Kreis-System" nicht ohne weiteres mit Rechtecken erweitern lässt.
Welche Methode wird denn in der Regel für Spiele dieser Art genommen?

Habt ihr irgendein Tipp für mich, wie ich da weiter kommen kann?
Oder vielleicht eine Empfehlung zu einem Tutorial, Buch oder Video?

Gruss starcow

[Schrompf]

Da gibt's viele Methoden. Und keine "Richtige". Wie immer also :-) Außerdem kann man das Problem hübsch in verschiedene Aufgabenstellungen unterteilen.

Das Beispielbild ist prima, denn es zeigt ganz offensichtlich, dass Dir "Kreis gegen Rechteck" reichen würde, wenn Du Character vs. Spielwelt prüfen willst. Definiere pro besetztem Tile ein Quadrat. Bei Splatter habe ich aus der TileMap die blockierenden Tiles genommen und deren Pixel auf "Alpha > 0.5" geprüft, das geht auch.

Dann die Tests selbst:

Du brauchst hier Kreis gegen Quadrat. Da gibt es einen coolen Trick, von dem ich gar nicht weiß, ob der einen Namen hat: Man reduziert die Position des Kreises relativ zum Quadratmittelpunkt um die Quadratausmaße. Also X und Y so, dass sie zwischen -w und +w 0 ergeben und jenseits davon jeweils um w gekürzt werden. Dann brauchst Du anstatt "Kreis gegen Quadrat" nur noch "Kreis gegen Punkt" prüfen.

Dann die Reaktion auf die Kollision:

Ich habe bei Splatter einen Halbkreis aus Testpunkten rund um jeden Charakter in Bewegungsrichtung geprüft. Das ist natürlich nicht nötig, wenn Du wie oben beschrieben Kreis gegen Quadrat prüfst, sondern ist nur bei Per-Pixel-Kollision nötig. Wenn ein Punkt kollidiert, dann entfernst Du den Anteil der Bewegungsrichtung in Richtung dieses Punktes aus der Bewegungsrichtung. Klingt kompliziert, aber ist ganz einfach:

- Oh, ich kollidiere
- Wieviel meiner aktuellen Bewegungsrichtung geht in Richtung dieser Kollision?
- Punktprodukt!
- Diesen Anteil entferne ich aus der Bewegungsrichtung.

Also z.B.: Charakter bewegt sich rechts hoch. Kollision mit Wand über ihm. Du entfernst den Teil nach oben aus der Bewegungsrichtung. Übrig bleibt der Teil nach rechts. Ergebnis: Charakter rutscht die Wand entlang.

[Schrompf]

Achja, noch was:

Wenn Du schnellere Objekte hast, dann wird aus allen "Punkt gegen Irgendwas" ein "Strecke gegen Irgendwas". Das ist z.B. für Schüsse relevant, weil die sich üblicherweise schnell bewegen. "Strecke gegen Kreis" und "Strecke gegen Rechteck" sind aber mathematisch keine Dramen, das kriegst Du hin. "Strecke gegen Pixel" ist ein bisschen kniffliger, aber eigentlich nur mühsam: Man macht pro Tile einen Vortest "Strecke gegen Quadrat" und hangelt sich innerhalb des Tiles im Abstand von zwei drei Pixeln vorwärts.

[joeydee]

Schrompf hat schon recht, eine Menge Möglichkeiten.
Ich glaube, bei Kenney's Dreamland hatte ich ausschließlich nur (ungedrehte) Quadrate gegeneinander getestet. Also nur Überlappungen auf den Achsen bestimmt. Und ein "weiches" Abfedern, damit das nicht so auffällt. Auch damit kann man schon ein Spiel machen. Ich wollte mal wissen, wie simpel es grundsätzlich geht ohne groß zu stören.

Was auch gut geht: Alle Entitys sind Kreise, der Level besteht aus Boxen. Alle Kreise untereinander testen, danach jeden Kreis einzeln gegen den Level testen, das sind dann zwei getrennte Vorgänge. Statt jeder (ob Box oder Kreis) gegen jeden.

Wenn du beliebige unvorhersagbare verschiedene Formen(-typen) gegeneinander testen willst, kommst du um Fallunterscheidungen für die Testroutinen sowie hierarchische Ordnungen kaum herum. Es gäbe noch das Separating-Axis-Theorem für beliebige Formen, löst aber auch nicht alles. Je eleganter du das lösen willst (sprich: egal wer mit wem kollidiert, und egal wer statisch oder dynamisch ist, es soll immer richtig reagieren, und ich will neue Parameter nicht in x Fallunterscheidungen anpassen und irgendwelche Fake-Fälle abfangen müssen), desto mehr musst du in Richtung Physikengine schielen. Box2D z.B. arbeitet glaube ich sehr stabil und in vielen Sprachen als freie Lib zu haben.

Was ich aktuell mache:
- Alles erstmal als Kreis/Kugel behandeln und Abstände untereinander prüfen.
- Wenn ein Kollisionsobjekt Detailinformationen hat (Ich bin ein Würfel) wird das größere als dieses Detail, das kleinere weiter als Kugel behandelt.
- Die komplexeste mögliche Prüfung ist bei dieser Einschränkung also lediglich: Kreis zu Oberfläche.
- Dafür muss jeder Objekttyp "nur" eine Funktion shortestDistanceToSurface(position) implementieren.
- Auch ein Maze-Level ist ein einzelner Objekttyp; dessen shortestDistanceToSurface()-Implementierung ist dann selbst für etwaige Optimierungen verantwortlich.
- Außerdem wird entsprechend jeweils eine eigene "testRay(position, direction)"-Implementierung für Schüsse und Sichtbarkeitstests gefordert.
- Das sind die Gemeinsamkeiten die alle meine Hüllen haben, eben mit der Einschränkung dass eines davon immer als Kugel behandelt werden muss, da shortestDistanceToSurface() natürlich nur gegen einen Punkt simpel ist.

Praxistests in 3D für dieses Prinzip sind mein "Cyberhive"-Prototyp sowie die aktuelle ZFX-Action. Kein Physik-Ersatz, aber man kann damit einiges Faken und ich finde es ist absolut spieletauglich für einfache Unterhaltungssoftware.

[starcow]

Erstmal vielen Dank an euch für die guten und ausführlichen Antworten!
So langsam glaube ich eine Ahnung zu bekommen, wie das ganze aufgebaut werden muss.

Was ich u. A. aus euren Posts raus lese, ist folgendes (zusammengefasst):
1) Eine universal Methode für Kollisionen ist in der Spiele-Programmierung meist wenig sinnvoll, da dies zu komplexen physik-simulations-nahen (aufwändigen) Lösungen führen würde
2) Es ist sinnvoll verschiedene Methoden zur Kollisionserkennung anzuwenden - und zwar abhängig davon, wie das eigentliche Objekt beschrieben wird (Punkt, Linie, Kreis, Rechteck, etc.)
3) Es ist aus performance Gründen wichtig, zuvor die Liste der Objekte durch zubürsten. Also Objekte frühzeitig auszusortieren, die keine genaue Kollisionsprüfung benötigen, weil sie mit Sicherheit genug weit voneinander entfernt sind.

Wenn ich 3) richtig verstanden habe, wäre der Einsatz des "Sweep & Prune" Algorithmus ein sinnvoller in meinem Spiel.
Ersetzt dieser "Sweep & Prune" Algorithmus denn nun auch die Geschichte mit den binären Bäumen? Oder kommt das auch noch oben drauf?
Jeden Falls scheint dieser "Sweep & Prune" Algorithmus zuerst eine "Bounding-Box" um das Objekt zu ziehen. Würde dieser auch mit Linien als Objekte noch funktionieren?

Wenn ich Dich, Schrompf, jetzt richtig verstanden habe, empfiehlst du mir folgende Kollisionsmethoden:
- Feine gegen Feinde / Feinde gegen Player -> Kollision von Kreisen
- Player / Feinde gegen Wände -> Kollision von Kreisen gegen Rechtecke (Tiles)

Wenn ich bei den Wänden auf "Kreise gegen Rechtecke" teste, verliere ich dadurch die Möglichkeit auch schräge Wände ins Spiel einbauen zu können? Erkenne ich das richtig? Könnte man - um sich die Möglichkeit der "schrägen Wände" zu erhalten - die Kreise (Player, Enemys, Items) einfach gegen Linien testen?
Soll heissen:
-> Kreis gegen Kreis: Bei Player, Feinden und Projektile untereinander
-> Linie gegen Kreis: Bei Player, Feinden, Projektile gegen Wände

Zum "Sweep & Prune" Algorithmus habe ich bis jetzt "nur" ein 26-Seitiges PDF-Dokument gefunden. Ist das echt so komplex? Oder schiesst diese Erklärung etwas übers Ziel hinaus?

Gruss starcow

[NytroX]

Ich glaub die Sweep & Prune mit 26 Seiten schießt etwas übers Ziel hinaus.
Ist eigentlich ganz einfach (Ich gehe mal von einer 2d Welt aus):
Jedes Objekt besteht aus mehreren Punkten. Immer wenn du ein Objekt bewegst, gehst du alle Punkte des Objekts durch und merkst dir einfach den maximalen und minimalen X und Y Wert.
Wenn du jetzt prüfen willst, ob Objekt1 möglicherweise mit Objekt2 kollidiert, prüfst du einfach diese Werte gegeneinander.
(Also z.B. wenn Objekt1.maxX < Objekt2.minX, dann können die sich ja garnicht treffen.)
Das machst du dann in X und Y Richtung jeweils 2 Mal, und nur wenn du eine Kollision dann nicht ausschließen kannst, machst du den eigentlichen/komplexeren Kollisionscheck.
Wenn das nicht gerade ein Handy-Spiel werden soll und du nur ein paar hundert Objekte hast, brauchst du auch keinen Baum dafür oder sowas.

Da auf deinem Bild Räume zu sehen sind, kannst du gegen Wände auch einfach prüfen, in dem du es umgekehrt machst: Wenn das Objekt in einem Raum ist, kollidiert es nicht mit der Wand.
Das kannst du auch für die Kollisionsabfrage der Objekte untereinander nutzen: Du brauchst ein Objekt nur mit anderen Objekten zu vergleichen, die sich im gleichen oder in einem angrenzenden Raum befinden.
Das setzt aber voraus, dass ein Objekt nie so schnell sein kann, dass es einen Raum oder eine Wand "überspringt". Am besten kriegt man das hin, wenn man die Physikberechnung von der Grafik (d.h. von der Framerate) ordentlich trennt.
(siehe hier: https://www.spieleprogrammierer.de/wiki ... Spiellogik)

[marcgfx]

Für Devader registriere ich alle Objekte in Grids. 100x100 pixel. Alle Objekte sind Kreise. Ein Objekt kann sich in mehreren Grids gleichzeitig befinden, für die Grid Registration verwende ich ein Rechteck um das Objekt als Referenz. Ich schliesse die Position aus dem letzten Frame ebenfalls in dieses Rechteck ein. Alles was in einem Grid ist könnte theoretisch miteinander kollidieren. Da viele kleine Schüsse schnell mal zu vielen Berechnungen führen habe ich folgendes gemacht: Ich führe im Grid verschiedene Listen, manche Listen kollidieren nicht miteinander. Manche Listen kollidieren mit sich selber. Schüsse sind in einer Liste and kollidieren nicht untereinander. Für schnelle Objekte gibt es eine Berechnung des Aufschlagpunkts, für langsame wird der nahste Punkt als Kollisionspunkt verwendet. Die Wände könntest du ebenfalls im Grid registrieren, oder du baust das Grid so, dass die Wände ein komplettes Grid füllen.

[joeydee]

Mit deinen Einschätzungen liegst du richtig, und:
26 Seiten braucht man nicht für Sweep & Prune ;)

Grid (auch "Hanging Moss"), Binärbaum, Sweep&Prune sind jeweils eine Methode zur Reduzierung des Aufwands beim Test "jeder gegen jeden". Du solltest dir alle einmal anschauen und die Grundprinzipien dahinter verstehen, um bei deinen Projekten jeweils das sympathischste heraussuchen und bei Bedarf kombinieren oder erweitern zu können.

Kurz zu Tiles, Schrägen, Sonderformen und Strahlen:
Ein im regelmäßigen Raster angeordneter Tile-Level bringt in sich schon eine gewisse Struktur mit, die man für Optimierungen nutzen kann. z.B. weiß man sofort anhand von Objektposition und -Größe, welche Tiles für Kollision in Frage kommen (solange das Objekt kleiner ist als ein Tile, können es maximal 4 sein). Deshalb wirft man nicht sämtliche Tiles in eine andere Struktur und testet sie mit dem Rest der beweglichen Objekte, das kann die Sache nur verschlechtern. Daher kommt das Aufteilen der Testroutinen.
Sonderformen können auch erstmal als Bounding-Box bzw. Tile welches sie umschließt angesehen werden. Bei Kollision wird dann nicht direkt auf die virtuelle Box reagiert, sondern weiter auf deren (komplexeren) Inhalt geprüft, also z.B. das Liniensegment das sie durchläuft.
Strahlen nehmen meist eine Sonderrolle ein, da sie theoretisch "unendlich" weit gehen können (zumindest bis zur Levelgrenze), also große Bounding-Boxen brauchen die die Form nicht sonderlich gut umschreiben wenn der Strahl nicht gerade auf einer Achse liegt. Auch hier kann man z.B. in einem Tile-Level optimieren welche Tiles überhaupt auf der Strecke liegen, um Strahlen zu kürzen die auf Wände treffen, um die Bounding-Box des Strahls möglichst früh zu verkleinern. Oder im Falle eines Hanging-Moss-Grids direkt auf die Listen testen.
In "einfachen" Spielen werden Schüsse übrigens oft nicht als Punkt simuliert der zeitlich auf einer Strecke fliegt, sondern als Strahl und damit unendlich schneller Schuss. Zeitverzögerungen kann man faken. Physikalisch korrektere Schüsse (bewegtes MG und scheinbare Kurvenbahn der Projektile z.B.) kann man machen, indem man den Ursprungsstrahl je Frame segmentiert und in jedem Frame nur das aktuelle Segment betrachtet.

Zu Sweep & Prune bereite ich noch eine kürzere Erklärung vor als die 26 Seiten, gib mir noch 1 Tag Zeit, ich bin noch Action-geschädigt ;)

[joeydee]

Habs im anderen Thread gepostet, dort ging es ja um mögliche Optimierungsstrukturen:
https://zfx.info/viewtopic.php?f=4&t=43 ... 583#p57583

Hier ist ja die eigentliche Kollisionsprüfung und -Response das Thema.