Kollisionsabfrage in Doom

Programmiersprachen, APIs, Bibliotheken, Open Source Engines, Debugging, Quellcode Fehler und alles was mit praktischer Programmierung zu tun hat.
Antworten
Benutzeravatar
starcow
Establishment
Beiträge: 523
Registriert: 23.04.2003, 17:42
Echter Name: Mischa Schaub
Kontaktdaten:

Kollisionsabfrage in Doom

Beitrag von 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.
Freelancer 3D- und 2D-Grafik
mischaschaub.com
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Kollisionsabfrage in Doom

Beitrag von 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.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
xq
Establishment
Beiträge: 1581
Registriert: 07.10.2012, 14:56
Alter Benutzername: MasterQ32
Echter Name: Felix Queißner
Wohnort: Stuttgart & Region
Kontaktdaten:

Re: Kollisionsabfrage in Doom

Beitrag von 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
War mal MasterQ32, findet den Namen aber mittlerweile ziemlich albern…

Programmiert viel in ⚡️Zig⚡️ und nervt Leute damit.
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: Kollisionsabfrage in Doom

Beitrag von 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?
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Benutzeravatar
starcow
Establishment
Beiträge: 523
Registriert: 23.04.2003, 17:42
Echter Name: Mischa Schaub
Kontaktdaten:

Re: Kollisionsabfrage in Doom

Beitrag von starcow »

xq hat geschrieben: 30.12.2021, 10:52 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.
Krishty hat geschrieben: 30.12.2021, 01:15 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. :-)
Lord Delvin hat geschrieben: 30.12.2021, 12:56 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. :-)
Freelancer 3D- und 2D-Grafik
mischaschaub.com
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Kollisionsabfrage in Doom

Beitrag von Krishty »

Lord Delvin hat geschrieben: 30.12.2021, 12:56Die 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.)
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: Kollisionsabfrage in Doom

Beitrag von 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.
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Antworten