Kollisionsabfrage in Doom

[starcow]

Ich schaue mir grad dieses Video
https://www.youtube.com/watch?v=ubdda0DuFvM
von Zero Master an (einer der wohl besten DooM Spieler überhaupt) - und bin absolut fasziniert.
Einerseits natürlich von diesen Skills - andereseits von der Tatsache, dass die Kollisionsabfrage eine solche unglaubliche Menge an Kreaturen und Projektilen bewältigen kann.
Ich meine, eine solche Anzahl an Objekten müsste sich ja bereits in der Broad-Phase der Kollisionsabfrage bemerkbar machen - was die Berechnungszeiten betrifft. Es scheint aber, als ob diese alte Engine das alles mühelos wegsteckt.

[Krishty]

Hammergeiles Video.

AFAIK nutzt Doom einen BSP-Tree, wie damals in Zerbies Büchern. Wenn die Objekte eh im BSP-Tree stecken und punktförmig sind (sind die Schüsse, denke ich mal?), musst du nur Objekte auf Kollision prüfen, die im selben Leaf des Baumes stecken. Das dürfte die Sache ungemein schneller machen.

[xq]

Jo, das war auch ungefähr meine Vermutung. Und BSP-Checks sind im 2-dimensionalen halt literally dot(wand_normale, meine_pos - wand_pos) < radius) was am ende auf zwei multiplikation und zwei subtraktionen rausläuft. Viel weniger geht eigentlich nicht

[Lord Delvin]

Macht schon Lust, mal wieder was mit Billboards zu bauen.
Ich würde auch erwarten, dass die Projektile Punkte sind. Bei den Gegnern würde mich das überraschen; die brauchen aber eigentlich auch nur eine Kollision, wenn sie ihre Bewegung planen, wenn man keine Physik mit Kräften hat.

Die eigentlich spannende Frage ist, was Gegner dazu bringt, ein Projektil zu erzeugen.
Meint ihr man könnte es bringen, Gegner nur aktiv zu haben, wenn sie sichtbar sind?
Ich meine bei so simplen Gegnern würde das kaum auffallen, oder?

[starcow]

Jo, das war auch ungefähr meine Vermutung. Und BSP-Checks sind im 2-dimensionalen halt literally dot(wand_normale, meine_pos - wand_pos) < radius) was am ende auf zwei multiplikation und zwei subtraktionen rausläuft. Viel weniger geht eigentlich nicht

Das ist wirklich schnell! Ich meine aber gelesen zu haben, dass Carmack für die Gegner-Kollisionen ursprünglich noch ein Gird implementiert hatte (Spatial Hashing). Erst später habe ihn jemand aus dem Team darauf aufmerksam gemacht, dass er den BSP-Tree nicht nur fürs Rendering, sondern auch für die Gegner-Kollision nutzen könne.
Ob die Release-Version noch ein Grid für die Gegner implementiert hatte, weiss ich allerdings auch nicht.

Hammergeiles Video.

AFAIK nutzt Doom einen BSP-Tree, wie damals in Zerbies Büchern. Wenn die Objekte eh im BSP-Tree stecken und punktförmig sind (sind die Schüsse, denke ich mal?), musst du nur Objekte auf Kollision prüfen, die im selben Leaf des Baumes stecken. Das dürfte die Sache ungemein schneller machen.

Gute Frage. Ich dachte jetzt immer an Kreise - aber vielleicht reicht auch blos ein Punkt. :-)

Die eigentlich spannende Frage ist, was Gegner dazu bringt, ein Projektil zu erzeugen.
Meint ihr man könnte es bringen, Gegner nur aktiv zu haben, wenn sie sichtbar sind?
Ich meine bei so simplen Gegnern würde das kaum auffallen, oder?

Ich denke, das würde schon eher schnell mal auffallen. Die Kreaturen sollten ja schon weiter agieren resp. attackieren, wenn man ihnen den Rücken zudreht. Und man würde ja auch irgendwie erwarten, dass sie nicht gleich erstarren, wenn man hinter einer Ecke verschwindet, oder?
Bei Doom bekämpfen sich die Monster ja auch untereinander, wenn sie sich mal versehentlich getroffen haben. :-)

[Krishty]

Die eigentlich spannende Frage ist, was Gegner dazu bringt, ein Projektil zu erzeugen.

Du hast recht. Ich schließe mich den anderen an, dass „Gegner schießen nur, wenn sichtbar“ sehr wohl auffallen würde, aber tatächlich ist die spannendere Frage für mich nun: „Läuft die KI für all die Gegner tatsächlich in jedem Frame?!“ (Denn KI dürfte noch aufwändiger als das Spawnen von Projektilen sein.)

[Lord Delvin]

Das mit dem Rückenzudrehen ist ein gutes Argument. Vermutlich eine Kugel, wie eine Aggrorange. Womöglich noch ein endlicher Automat, der es Kreaturen erlaubt "lebendig" zu werden und zu bleiben.