STL sort und "sweep & prune"

Design Patterns, Erklärungen zu Algorithmen, Optimierung, Softwarearchitektur
Forumsregeln
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.
Antworten
Benutzeravatar
starcow
Establishment
Beiträge: 523
Registriert: 23.04.2003, 17:42
Echter Name: Mischa Schaub
Kontaktdaten:

STL sort und "sweep & prune"

Beitrag von starcow »

Abend Zusammen

Ich versuche gerade mein kleines Kollisions-Projekt mit einem Vorselektions-Algorithmus auszustatten.
Eigentlich hatte ich geplant, ein "sweep & prune" Algorithmus dazu einzusetzen. So, wie er mir damals von joeydee netterweise erklärt wurde.
Nur stelle ich jetzt fest, dass dies, in dieser Form wohl nicht möglich sein wird (glaube ich zumindest).

Bild

Meine ganze Programm-Struktur beruht nämlich darauf, dass die Spielfiguren Zug-um-Zug bewegt werden.
In einer Momentaufnahme also zu entscheiden, welche Objekte sich untereinander in ihrem Kollisionsbereich schneiden, ist damit eigentlich schon wieder zu viel Information. Ich müsste eher in der Lage sein, möglichst schnell zu entscheiden, welche Spielfiguren für die aktuell behandelte Spielfigur ein "Hindernis" darstellen könnten - um dann möglichst schnell mit dem nächsten Charakter (Spielfigur) weiterzufahren.

Nach längerem Nachdenken bin ich nun auf folgende Idee gekommen: Für die Figuren erstelle ich nicht eine einzelne Liste, sondern mache die Anzahl davon abhängig, wie viele unterschiedliche Charaktergrössen (Charakteren sind immer als Kreise abstrahiert) vorhanden sind. Die Elemente innerhalb der einzelnen Listen werden dann wiederum nach der X- oder (alternativ) Y-Position sortiert.
Folgende Grafik zeigt, was ich meine:

Bild

Die zentrale Idee: Kennt man den Radius der Kreise, kann man entscheiden, wo man in der Liste einsteigen - und wieder aussteigen kann, ohne dabei die ganze List durchlaufen zu müssen. Denn noch schneller als ein einfacher Vorabtest, ist es, gar nicht testen zu müssen.

Der "kritische Streifen" ist in der Grafik aufgehellt dargestellt. Liegt ein Kreiszentrum innerhalb dieses Streifens (X-Position), muss also weiter (genauer) geprüft werden. Sobald man aber auf das erste Kreis-Element stösst, dessen X-Wert grösser ist, als der höhere Grenzbereich des Streifens, kann man aus dem Vorselektions-Algorithmus aussteigen.

Extrem cool wäre, wenn man diese Idee so kombinieren könnte, dass es zeitgleich auch einen "kritischen Streifen für die Y-Werte geben würde. Aber eine Liste kann man halt Prinzip bedingt nicht gleichzeitig nach zwei gleichwertigen Kriterien sortieren. Oder seht ihr da vielleicht doch eine Möglichkeit, wie das gehen könnte?

Zudem sind noch weitere Fragen offen:
1) Nachdem eine Figur bewegt wurde, muss sie natürlich in ihrer Liste neu einsortiert werden. Wie schnell dies dann der STL-Algorithmus für ein einzelnes Element ausführen kann, ist für mich nicht abzuschätzen. Vielleicht werden ja sämtliche Zeiteinsparungen gleich wieder aufgefressen - und es wäre möglicherweise schneller gewesen, stattdessen einfach alle Elemente mit einem simplen Vortest abzuklären.

2) Eigentlich müsste man die ganze Idee immer doppelt ausführen - einmal für den kritischen Streifen der X-Werte und einmal für die Y-Werte. Denn wenn man Pech hat, erwischt man die Achse, auf welcher die Verteilung der Figuren bezüglich diesem Selektions-Algorithmus deutlich ungünstiger ist.

Im fertigen Spiel rechne ich eigentlich mit einem Maximum von 1000 Figuren. Oder anders formuliert: Ich wäre sehr glücklich, wenn es mit dieser Anzahl noch gut lauffähig wäre.

Was denkt ihr zu diesem Ansatz?

Gruss, starcow
Freelancer 3D- und 2D-Grafik
mischaschaub.com
NytroX
Establishment
Beiträge: 358
Registriert: 03.10.2003, 12:47

Re: STL sort und "sweep & prune"

Beitrag von NytroX »

Extrem cool wäre, wenn man diese Idee so kombinieren könnte, dass es zeitgleich auch einen "kritischen Streifen für die Y-Werte geben würde. Aber eine Liste kann man halt Prinzip bedingt nicht gleichzeitig nach zwei gleichwertigen Kriterien sortieren. Oder seht ihr da vielleicht doch eine Möglichkeit, wie das gehen könnte?
Ja, geht, das nennt man Quadtree.
Das ist auch der klassische Ansatz, um die Anzahl der möglichen Kollisionen zu reduzieren.
Den kannst du dann einfach updaten, wenn du eine Figur bewegst.
https://de.wikipedia.org/wiki/Quadtree
(Unter den Weblinks gibts auch eine Java-Anleitung inkl. Implementierung für Kollisionserkennung)
Benutzeravatar
Jonathan
Establishment
Beiträge: 2353
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: STL sort und "sweep & prune"

Beitrag von Jonathan »

Ich habe auch noch diesen Link hier gefunden:

https://dai.fmph.uniba.sk/upload/8/87/Ca15_lesson05.pdf

Da werden noch ein paar mehr Broad-Phase Alogirthmen vorgestellt: Hierarchical grids, Spatial hashing und Pair management. DIe Folien sehen zumindest nett gemacht aus, es lohnt sich sicherlich, die mal durchzuarbeiten.

Kollisionsbehandlung ist ja nun schon so ein altes Thema (eigentlich nicht, aber es ist halt super relevant und damit gut erforscht), dass man vermutlich gar nicht selber viel denken muss, sondern einfach gucken kann, was die 2-3 Ansätze sind die sich durchgesetzt haben, was deren Vorteile sind und was auf die eigene Situation am besten passt.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Jonathan
Establishment
Beiträge: 2353
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: STL sort und "sweep & prune"

Beitrag von Jonathan »

Hab mal im Bullet Physics Handbuch mal nachgeschaut (ist allerdings wohl von 2015):
Several different broadphase acceleration structures are available:
• btDbvtBroadphase uses a fast dynamic bounding volume hierarchy based on AABB tree
• btAxisSweep3 and bt32BitAxisSweep3 implement incremental 3d sweep and prune
• btSimpleBroadphase is a brute force reference implementation. It is slow but easy to understand and useful for debugging and testing a more advanced broadphase.
Die unterschiedlichen BVH's (Octree, Quadtree, BSP-Tree) sind glaube ich vom Laufzeitverhalten im Wesentlichen gleich und es hängt wohl von der Scene ab, wann welches am Besten funktioniert. Glücklicherweise sind die eigentlich alle schnell implementiert, man kann da also gut ein wenig testen.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
starcow
Establishment
Beiträge: 523
Registriert: 23.04.2003, 17:42
Echter Name: Mischa Schaub
Kontaktdaten:

Re: STL sort und "sweep & prune"

Beitrag von starcow »

Super, ich danke euch! Das ist wirklich extrem spannend!
Ich habe zwar auch schon von solchen Trees gehört, konnte mir aber nur bedingt (in diesem Zusammenhang) etwas darunter vorstellen.

Ich hab jetzt mal versucht einen Überblick zu gewinnen und glaube so ein Quadtree könnte eine gute Wahl sein. Dieses Konzept scheint ja ganz grundsätzlich eine interessante Sache zu sein und in verschiedenen Zusammenhängen aufzutauchen. An dieser Stelle also sicher sehr lohnenswert, sich mal näher damit zu beschäftigen.
Das grobe Grundprinzip glaube ich verstanden zu haben - einige Dinge werfen für mich vom Konzept her jedoch noch Fragen auf.

- Meine Spielfiguren bewegen sich ja "Zug-um-Zug". Wenn ich also eine Spielfigur bewege, muss ich dann folglich den ganzen Quadtree neu aufbauen? Oder läss sich dieser irgendwie effizient umsortieren?

- Verstehe ich das richtig, dass ich mit rechteckigen Bounding-Boxes um meine Kreise arbeiten muss?

- Wenn also meine "Elemente" nicht blos Punkte sind, sondern eine Ausdehnung besitzen (Rechtecke), kann es ja sein, dass ich keine weitere Teilung des Grids vornehmen kann, ohne dass dabei dieses eine Element mehrere Felder besetzen würde. Stoppe ich dann den Unterteilungsprozess - selbst wenn sich dann noch mehrere Elemente in der gleichen Zelle befinden?

Auf Stackoverfolw hab ich noch ein interessantes Tutorial gefuden:
https://stackoverflow.com/questions/419 ... lision-det
macht das auf euch einen guten Eindruck?

Gruss, starcow
Freelancer 3D- und 2D-Grafik
mischaschaub.com
NytroX
Establishment
Beiträge: 358
Registriert: 03.10.2003, 12:47

Re: STL sort und "sweep & prune"

Beitrag von NytroX »

Ich würde an deiner Stelle erstmal mit einem regelmäßigen Tree anfangen, damit du ein Gefühl dafür bekommst, wie es funktioniert.
Optimieren kann man später immer noch, ich stimme Jonathan zu, ich würde auch einfach bissel rumprobieren.
Ich hatte dich so verstanden, dass deine Kreise unterschiedliche Größen haben können, aber sich nicht gigantisch unterscheiden.

Daher könntest du mit der Unterteilung z.B. dann aufhören, wenn nur ein Element in der Node ist, oder die Seitenlänge dem 4-fachen Radius des größten Kreises entspricht (ist willkürlich, einfach mal was ausprobieren).

Wenn du eine Spielfigur bewegst, nimm sie einfach aus dem Tree raus und füge sie wieder ein.
Das Unterteilen bzw. Zusammenfügen kannst du ja einfach in deine insert- bzw. remove Methode reinbauen.
D.h. dann werden immer nur 2 Subtrees pro Bewegung neu gebildet, wenn sich das Objekt über Quad-Grenzen hinweg bewegt.

Bounding-Boxen brauchst du eigentlich nicht für die Kreise, du musst ja jeweils nur feststellen, in welchem Viertel vom Quadtree sie sind. Und dafür reicht der Mittelpunkt +/- der Radius.

Für Kreise, die auf den Grenzen sind, gibt es eigentlich 2 Strategien:
a) Du fügst sie in den Quad ein, wo der Mittelpunkt liegt. Dann musst du bei der Kollisionserkennung immer ein Quad und ggf. die Nachbar-Quads mit einbeziehen
b) Du fügst sie in beide ein. Dann sind die Kollisions-Tests lokal, aber du hast mehr Objekte im Quadtree.

Bei deinen 1000 Spielfiguren würde ich dir zu (b) raten.
Benutzeravatar
starcow
Establishment
Beiträge: 523
Registriert: 23.04.2003, 17:42
Echter Name: Mischa Schaub
Kontaktdaten:

Re: STL sort und "sweep & prune"

Beitrag von starcow »

Leider harzt es grad ein wenig... :-X
Ich glaube zwar das Grundprinzip verstanden zu haben, aber in meinem spezifischen Szenario ist mir nicht klar, wie ich die Situation effizient gelöst bekomme.
NytroX hat geschrieben: 19.11.2019, 22:06 Ich würde an deiner Stelle erstmal mit einem regelmäßigen Tree anfangen, damit du ein Gefühl dafür bekommst, wie es funktioniert.
...
Ich hatte dich so verstanden, dass deine Kreise unterschiedliche Größen haben können, aber sich nicht gigantisch unterscheiden.
Was ist ein regelmässiger Tree? Ein binary-Tree (1d)?
Ja, die Kreise repräsentieren Gegner, Geschosse und allenfalls noch weitere Objekte. Aber in aller Regel dürften sich diese nicht mehr als um den Faktor 10 unterscheiden (Bossgegner : Geschoss).

Mein Problem ist aktuell, dass die Tutorials, die ich finden konnte, entweder mit unendlich kleinen Punkten arbeiten oder nur eine "Momentaufnahme" auf Kollision analisieren. In meinem Fall aber, bewegt sich immer ein Objekt von einer Start- zu einer Zielposition.
Deshalb sehe ich auch irgendwie keine andere Möglichkeit, als um diesen "Pfad" ein Rechteck zu ziehen.

Bild

So bleibt mir - glaube ich - nicht viel anderes übrig, als zu prüfen, welche Kreise innerhalb dieses Rechteckes liegen.
Nur, was nützt mir dann mein schön sortierter Quadtree, in welchem max. zwei Kreise in einer Zelle liegen, wenn ich dann mit einem Rechteck daher komme? :-)

Eine leichte abgeänderte Alternative scheint diese hier zu sein:
https://www.youtube.com/watch?v=D6nrGYf ... Yy&index=5

Dabei werden die Zellen nicht einfach mittig geviertelt, sondern der Raum an jener Koordinatenstelle geteilt, an welcher der (weitere) Kreis eingefügt wird.
Es scheint mir aber, als gäbe es bei diesem Ansatz wesentlich mehr zu prüfen. So kann ich ja nicht mehr einfach die entsprechende Zelle suchen, sondern muss den ganzen Baum herunter wandern (wie im Video zu sehen).
Kann das für meine Situation sinnvoll sein?

Gruss, starcow
Freelancer 3D- und 2D-Grafik
mischaschaub.com
Benutzeravatar
Jonathan
Establishment
Beiträge: 2353
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: STL sort und "sweep & prune"

Beitrag von Jonathan »

Ein paar kurze Anmerkungen:

- Ja, du würdest vermutlich mit achsenausgerichteten Rechtecken um deine Kreise arbeiten. Ist aber nicht so schlimm, der Quadtree soll ja nur die weit entfernten Objekte grob aussortieren, die eigentliche Kollisionsabfrage ist danach immer noch genau, und so viel größer als ein Kreis ist ein Quadrat jetzt auch nicht.

- Für bewegte Objekte ist das Rechteck um den gesamten Bereich tatsächlich eine gute Idee. Du wirst ja vermutlich keine super schnellen Objekte haben, ich würde vermuten, dass bei 60 fps dieses Bewegungsrechteck selten mehr als doppelt so groß wie das eigentliche Objekt ist. Also auch nicht so schlimm.

- Für Objekte mit Ausdehnung (also wohl alle): Wie gesagt, ich bin nicht super tief im Thema drin, aber folgendes sollte funktionieren (und 'ok' schnell sein): Du hast eine Klasse "Quadtreenode" die neben einer Liste an Spielobjekten 4 Referenzen auf die Unterknoten speichert. In der untersten Ebene sind diese 4 Referenzen (bzw. Pointer) leer. Zum einfügen eines Objektes fängst du auf der obersten Ebene an und prüfst ob das Objekt mit seiner Bounding Box komplett in einen der 4 Unterknoten passt. Wenn ja, reichst du es an diesen Knoten weiter, wenn sein speicherst du es in der Liste auf der aktuellen Ebene. Du hast dann also in allen Baumebenen potentiell Objekte. Um ein Objekt auf Kollision zu testen, testest du es mit allen Objekten auf der aktuellen Ebene und rekursiv mit allen Unterknoten die es berührt.
Dieser Ansatz ist ziemlich einfach zu implementieren und dürfte für die meisten Fälle schon ausreichend schnell funktionieren. Wenn viele Objekte auf der Kante zwischen Knoten liegen werden diese natürlich andauernd getestet, aber das sollte fürs erste auch ok sein.
Wenn du dann ein Objekt bewegst, schaust du ob es von der aktuellen Ebene aus gesehen jetzt komplett in einem Unterknoten liegt (dann fügst du es rekursiv dort ein) oder ob es die Bounding-Box des aktuellen Knoten verlassen hat (dann musst du es rekursiv nach oben schieben).
Du musst natürlich nicht 4 Unterknoten haben, sondern kannst auch nur horizontal oder nur vertikal teilen (oder abwechselnd). Wenn du beispielsweise einen sehr langen (in horizontaler Richtung) aber schmalen Knoten hast, ist horizontaler teilen nicht sehr nützlich weil dann sehr viele Objekte auf der horizontalen Trennlinie liegen und nicht tiefer einsortiert werden können. Teilst du in so einer Situation nur vertikal landen mehr Objekte in tieferen Ebenen. Aber das sind eher Details.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
marcgfx
Establishment
Beiträge: 2050
Registriert: 18.10.2010, 23:26

Re: STL sort und "sweep & prune"

Beitrag von marcgfx »

Nur mal schnell erklärt wie ich es in Devader mache, da du scheinbar was ähnliches lösen willst wie ich. Das Spielfeld wir in ein Grid aufgeteilt. Gegner, Schüsse sind Kreise und werden in jedem Grid registriert welches sie berühren. Für die Kollisionsabfrage wird jedes Grid einzeln überprüft.
NytroX
Establishment
Beiträge: 358
Registriert: 03.10.2003, 12:47

Re: STL sort und "sweep & prune"

Beitrag von NytroX »

Hi, sorry ich kam vor dem Wochenende nicht dazu, nochmal was zu schreiben.
Mit "regelmäßig" meinte ich, dass alle Äste im Baum die gleiche Länge haben.
Also so:

Code: Alles auswählen

regelmäßig:

        root
       /    \
     N1      N2
    /  \    /  \
  N11 N12 N21 N22
  
  
unregelmäßig:
      
        root
       /    \
     N1      N2
    /       /  \
  N11     N21 N22


Du kannst erstmal mit einer festen Anzahl anfagen, also z.B. 2 oder 3 Ebenen, damit deine Logik unkompliziert bleibt und du ein Gefühl dafür bekommst.
Es geht ja zunächst ums Verständnis. Wenn du erstmal eine einfache Implementierung hast - optimieren kann man später immer noch.
Die unterste Ebene ergibt dann quasi ein Grid, welches aus gleich großen Quads besteht.

Die bewegten Objekte könntest du als Quad darstellen, so wie in deinem Bild (ein Kreis würde aber auch gehen).
Wie Jonathan schon gesagt hat, geht es ja erstmal nur um das grobe Aussortieren von Objekten, die weit weg sind.



Hier mal ein Beispiel in C# (ohne Garantie, nur kurz getestet):

Code: Alles auswählen

#nullable enable

using System;
using System.Collections.Generic;

namespace QuadtreeExample
{
    class Circle
    {
        public double mx = 0;
        public double my = 0;
        public double radius = 1;
    }

    class Quad
    {
        public double xpos = 0;
        public double ypos = 0;
        public double width = 0;
        public double height = 0;

        public Quad? parent = null;
        public Quad? q1 = null;
        public Quad? q2 = null;
        public Quad? q3 = null;
        public Quad? q4 = null;

        public List<Circle> circles = new List<Circle>();

        public bool HasChildren => q1 != null && q2 != null && q3 != null && q4 != null;

        public void GenerateChildren()
        {
            if (!HasChildren)
            {
                q1 = new Quad() { parent = this, xpos = this.xpos, ypos = this.ypos, width = this.width / 2, height = this.height / 2 };
                q2 = new Quad() { parent = this, xpos = this.xpos + this.width / 2, ypos = this.ypos, width = this.width / 2, height = this.height / 2 };
                q3 = new Quad() { parent = this, xpos = this.xpos, ypos = this.ypos + this.height / 2, width = this.width / 2, height = this.height / 2 };
                q4 = new Quad() { parent = this, xpos = this.xpos + this.width / 2, ypos = this.ypos + this.height / 2, width = 800, height = 800 };
            }
        }

        public bool IsCircleOverlappingThisQuad(Circle c)
        {
            bool xOverlap = c.mx + c.radius >= xpos && c.mx - c.radius < xpos + width;
            bool yOverlap = c.my + c.radius >= ypos && c.my - c.radius < ypos + height;
            return xOverlap && yOverlap;
        }

        public void AddCircle(Circle c)
        {
            if (IsCircleOverlappingThisQuad(c))
            {
                if (HasChildren)
                {
                    q1?.AddCircle(c);
                    q2?.AddCircle(c);
                    q3?.AddCircle(c);
                    q4?.AddCircle(c);
                }
                else
                {
                    circles.Add(c);
                }
            }
        }

        public void GetCollisionCandidates(Circle circle, SortedSet<Circle> collisionCandidates)
        {
            if (IsCircleOverlappingThisQuad(circle))
            {
                if (HasChildren)
                {
                    q1?.GetCollisionCandidates(circle, collisionCandidates);
                    q2?.GetCollisionCandidates(circle, collisionCandidates);
                    q3?.GetCollisionCandidates(circle, collisionCandidates);
                    q4?.GetCollisionCandidates(circle, collisionCandidates);
                }
                else
                {
                    foreach (var c in circles)
                    {
                        collisionCandidates.Add(c);
                    }
                }
            }
        }
    }

    class MainClass
    {
        static void Main(string[] args)
        {
            //test1
            {
                var root = new Quad() { xpos = 0, ypos = 0, width = 1600, height = 1600 };
                root.GenerateChildren();
                var circleForTheQuadtree = new Circle() { mx = 1000, my = 200, radius = 150 };
                root.AddCircle(circleForTheQuadtree);

                var circleForCollisionDetection = new Circle() { mx = 200, my = 200, radius = 300 };
                var collisionCandidates = new SortedSet<Circle>();
                root.GetCollisionCandidates(circleForCollisionDetection, collisionCandidates);
            }
            //test2
            {
                var root = new Quad() { xpos = 0, ypos = 0, width = 1600, height = 1600 };
                root.GenerateChildren();
                var circleForTheQuadtree = new Circle() { mx = 850, my = 200, radius = 150 };
                root.AddCircle(circleForTheQuadtree);

                var circleForCollisionDetection = new Circle() { mx = 600, my = 200, radius = 300 };
                var collisionCandidates = new SortedSet<Circle>();
                root.GetCollisionCandidates(circleForCollisionDetection, collisionCandidates);
            }

            return;
        }
    }
}




Anmerkungen:
  • Ich generiere einfach ein Quad mit 4 Unter-Quads. Ist erstmal nur zur Veranschaulichung.
  • Im Test1 wird ein Kreis angelegt, der im Quadtree im NordOsten eingetragen wird. Der 2. Kreis liegt im Nordwesten, es gibt keine Kollisionsmöglichkeit.
  • Im Test2 wird ein Kreis angelegt, der im Quadtree doppelt eingetragen wird, weil er mit seinem Radius über die Grenze ragt. Daher wird er für jeden Kreis, der im NordWesten liegt, auch als Kandidat für eine Kollision herangezogen.
  • Mann muss sich Gedanken machen, was passiert, wenn man genau die Grenze trifft. Ich habe die Quads "links" und "oben" ausgerichtet, d.h. die Mittellinie gehört immer zum rechten bzw. unteren Quad.
  • Es könnte Sinn machen, aus den Kreisen einfach eine AABB (AxisAligned BoundingBox) zu machen, oder ein entsprechendes Interface zu verwenden.
Bugs könnten viele vorhanden sein, aber ich hoffe, die Idee wird etwas klarer :-P
Benutzeravatar
starcow
Establishment
Beiträge: 523
Registriert: 23.04.2003, 17:42
Echter Name: Mischa Schaub
Kontaktdaten:

Re: STL sort und "sweep & prune"

Beitrag von starcow »

Erstmal vielen Dank für die wertvollen Inputs!
Ich glaube das Prinzip jetzt verstanden zu haben - am Code-Beispiel bin ich noch dran.
Was ich jedoch noch immer nicht nachvollziehen kann, ist die Geschichte mit den Objekten, die aufgrund ihrer Grösse mehrere Zellen belegen.
Ich hab hierzu ein "Problem-Szenario" entworfen, bei welchem ich auf folgende Probleme stosse:

Bild
(Ordnung der Äste: Start links oben, Uhrzeigersinn)

1) Für den gelben Kreis "D", benötigt man 12 Abfragen um ihn in die Zellen einordnen zu können. Würde sich der Baum an den entsprechenden Stellen noch mehr verästeln, könnten dabei auch noch deutlich grössere Zahlen rauskommen. Kann sich das nicht problematisch auf die Laufzeit niederschlagen?

2) Der Kreis "D" belegt jetzt nicht nur den "Leaf" Nordost von A (mit seinem Mittelpunkt), sondern viele weitere. Eigentlich müsste man ja jetzt an jedem "leaf" vier weitere (vorerst leere) Äste ansetzten. Nur bräuchte man dazu ja irgendein Koordinaten- oder Referenzpunkt. Wie soll man sonst entscheiden, welcher Ast durch ein gegebenen Falls neuen Punkt "E" besetzt wäre?
marcgfx hat geschrieben: 28.11.2019, 09:59 Nur mal schnell erklärt wie ich es in Devader mache, da du scheinbar was ähnliches lösen willst wie ich. Das Spielfeld wir in ein Grid aufgeteilt. Gegner, Schüsse sind Kreise und werden in jedem Grid registriert welches sie berühren. Für die Kollisionsabfrage wird jedes Grid einzeln überprüft.
Interessant! Auf diesen Ansatz bin ich jetzt auch schon einige male gestossen. Ist das die "spatial hasing" Methode?
Wie legst du denn dieses Gitter an? Geht das auch irgendwie dynamisch, so dass sich auch zur Laufzeit die Grösse ändern kann? Oder muss man bei diesem Ansatz die Anzahl Zellen (und damit die maximale Kartengrösse) vorab festlegen?

Gruss starcow
Freelancer 3D- und 2D-Grafik
mischaschaub.com
Benutzeravatar
marcgfx
Establishment
Beiträge: 2050
Registriert: 18.10.2010, 23:26

Re: STL sort und "sweep & prune"

Beitrag von marcgfx »

Interessant! Auf diesen Ansatz bin ich jetzt auch schon einige male gestossen. Ist das die "spatial hasing" Methode?
Wie legst du denn dieses Gitter an? Geht das auch irgendwie dynamisch, so dass sich auch zur Laufzeit die Grösse ändern kann? Oder muss man bei diesem Ansatz die Anzahl Zellen (und damit die maximale Kartengrösse) vorab festlegen?
Wie der Ansatz heisst weiss ich nicht mal. Habe ehrlich gesagt nie recherchiert sondern einfach probiert (hatte schon mal was gelesen/gesehen). In meinem Fall ist das Spielfeld limitiert, ein dynamischer Ansatz hat meiner Meinung nach nur wenig Sinn gemacht. Teuer ist das registrieren/entfernen der Objekte im Grid, das Grid zu ändern würde dazu führen alle registrationen neu zu machen. Die Gittergrösse habe ich nach einigen Tests festgelegt, es gibt einen sweet-spot. Sind die Grids zu klein muss man viele registrationen anpassen, sind sie zu gross kommt es zu vielen Kollisionstests. Dazu kommt, dass ich in jedem Frame das gesamte Grid durchlaufen muss.
NytroX
Establishment
Beiträge: 358
Registriert: 03.10.2003, 12:47

Re: STL sort und "sweep & prune"

Beitrag von NytroX »

Bei einem Grid geht man normalerweise so vor, wie marcgfx beschrieben hat, es hat eine feste Größe.

Das wichtigste ist, dass du deine Daten kennst und dann den dazu passenden Lösungsansatz wählst, das ist bei allen Algorithmen so.

Meiner Meinung nach ist dein Ansatz gerade komplett falsch, du denkst dir schon "Problem Szenarien" aus, die wahrscheinlich selten bis nie eintreten.
Mach das so wie marcgfx und probier erstmal rum mit einer Idee, die dir zusagt; wenn der Ansatz nicht klappt, dann versuch was anderes. Wenn es funktioniert, aber "nicht optimal" ist, ist das doch völlig egal - vor allem, wenn es das erste Mal ist, dass du sowas machst.

Für einen Quadtree wäre es der absolute worst-case, wenn alle Objekte auf den "Linien" sitzen.
Zudem betrachte mal den Unterschied zwischen Kreis "C" und "D" in deinem Szenario.
Das geht komplett gegen die Annahme, die ich aufgrund deines ersten Bildes oben getroffen hatte:
NytroX hat geschrieben:Ich hatte dich so verstanden, dass deine Kreise unterschiedliche Größen haben können, aber sich nicht gigantisch unterscheiden
Ein kd-tree wäre da ein besserer Ansatz - der ist zwar auch leicht zu verstehen, aber in der realen Umsetzung richtig kompliziert; das ist nichts für erste Gehversuche bei der Kollisionserkennung.

Aber auch dafür gibt es viele Lösungsansätze. Aber es macht glaube ich wenig Sinn, alle Detail-Lösungen aufzuzeigen, bevor du überhaupt vor diesem Problem stehst. (Mal ein Beispiel: handelt es sich bei dem großen Kreis um einen Endboss, kann man ggf. davon ausgehen, dass er nur 1 Mal auf der Map auftaucht. Dann kann man ihn außerhalb des Quadtrees verwalten. Man sucht einfach im Quadtree alle Objekte in seiner Nähe und macht die Kollisionsberechnung dann extra)

Bei 1000 Objekten kannst du theoretisch auch eine Datenbank nehmen, die einen Spatial Index unterstützt. Dann machste ein SQL und bekommst einfach alle Kollisionen zurück und brauchst dich auch nicht drum zu kümmern, wie es funktioniert (für Java z.B. http://h2database.com). Ist wahrscheinlich eher nichts für Web-Games (hat also auch Nachteile, es kommt wie gesagt immer drauf an).

Hier mal eine Übersicht (da sind auch die Algorithmen verlinkt, wie so ein Index funktioniert; Grid, Quadtree und kd-Tree sind selbstverständlich auch dabei). https://en.wikipedia.org/wiki/Spatial_d ... tial_index
Benutzeravatar
kimmi
Moderator
Beiträge: 1405
Registriert: 26.02.2009, 09:42
Echter Name: Kim Kulling
Wohnort: Luebeck
Kontaktdaten:

Re: STL sort und "sweep & prune"

Beitrag von kimmi »

Habe das alles nur überflogen.- Aber wenn du axis-aligned Bounding-Boxes hast, sollte dir ein KD-Tree hier gute Dienste leisten( siehe https://en.wikipedia.org/wiki/K-d_tree )

Gruß, Kim
Benutzeravatar
starcow
Establishment
Beiträge: 523
Registriert: 23.04.2003, 17:42
Echter Name: Mischa Schaub
Kontaktdaten:

Re: STL sort und "sweep & prune"

Beitrag von starcow »

@Kimmi
Danke für den Input. Mir scheint aber, ein K-D-Tree ist gerade eines der anspruchsvollsten Konzepten überhaupt.

@NytroX
Ok, ich verstehe was du meinst und sehe ein, dass mein Beispiel mit dem grossen gelben Kreis wohl ziemlich "ungünstig" gewählt war :-D. Ich werde in diesem Fall erstmal das "spatial hashing" Prinzip ausprobieren. Dass scheint für den Einstieg tatsächlich besser geeignet - und wohl in meinem Szenario auch vergleichbar leistungsfähig.
Eine Sache beim Quadtree würde ich aber dennoch sehr gerne (von der Idee her) verstehen. Ich habe dazu nochmals ein Beispiel erstellt, dieses mal eines, in einem realitätsnahen Szenario.

Bild

Der rote Kreis "C" muss ja, da er eine Unterteilungslinie schneidet, auf zwei Ästen des Kreises "B" Blätter anlegen.
Nur hat jetzt eines der Blätter von "C" keinen Referenzpunkt mehr. Fügt man jetzt einen weiteren Kreis "D" auf der entsprechenden Zelle ein, lässt sich dieser nicht mehr einsortieren.

Ich verstehe noch nicht, wie ich genau in einem solchen Fall vorgehen muss.

Gruss starcow
Freelancer 3D- und 2D-Grafik
mischaschaub.com
Benutzeravatar
Chromanoid
Moderator
Beiträge: 4254
Registriert: 16.10.2002, 19:39
Echter Name: Christian Kulenkampff
Wohnort: Lüneburg

Re: STL sort und "sweep & prune"

Beitrag von Chromanoid »

Ich kenne Quadtrees (für die broad phase) eigentlich nur so, dass die Unterteilung von vorne herein unabhängig zu irgendwelchen Objekten festgelegt ist und man die Objekte je nach Größe und Position an die jew. Knoten packt. Man teilt einen begrenzten Raum rekursiv in vier gleich große Sektoren auf, bis eine hinreichend kleine Einteilung erreicht ist. Hier nur eine Unterteilung (Raum 1 wird einmal aufgeteilt):

Code: Alles auswählen

1-------------+
|+-----+-----+|
||  2  |  3  ||
||     |     ||
|+-----+-----+|
||  4  |  5  ||
||     |     ||
|+-----+-----+|
+-------------+
Würde man jetzt ein Objekt haben, das die Kästchen 2 und 3 schneidet, würde es in 1 sortiert werden. Jeder prüft dann Kollisionen mit den Objekten im eigenen Knoten und den Eltern-Knoten.

edit: Ich glaube was Du im GIF machst, ist ein point-based quadtree. Solange man keine statischen Objekte hat, die sinnvolle Unterteilungen vorgeben können, würde ich davon glaube ich abraten. Hier werden beide Varianten kurz angesprochen: https://pdfs.semanticscholar.org/cd43/d ... 9757b3.pdf
In Deinem GIF ist der Fehler glaube ich bei C. C würde wie B bei A einsortiert werden und würde i.d.R. nicht selbst unterteilen oder die Hierarchieebene mit B tauschen.
NytroX
Establishment
Beiträge: 358
Registriert: 03.10.2003, 12:47

Re: STL sort und "sweep & prune"

Beitrag von NytroX »

Wie Chromanoid ja schon geschrieben hat, geht man normalerweise so vor, dass man einfach die Fläche jeweils in der Mitte teilt.
Anbei ein Bild:
quadtree.png
Das Vorgehen wäre wie folgt:
- Wir fügen Kreis (1) hinzu.
- Wir fügen Kreis (2) hinzu.
- Wir stellen fest, dass nun 2 Kreise in einem Rechteck (dem großen) vorhanden sind, daher teilen wir die Fläche (schwarzes Kreuz).
- Wir fügen Kreis (3) hinzu.
- Wieder stellen wir fest, dass im rechten unteren (Südosten) Viereck 2 Kreise sind (2 und 3). Wir teilen also den SE-Quadranten erneut (graues Kreuz).
- Wir fügen Kreis (4) hinzu.
- Und wieder sind 2 Kreise in einem Quadrant: dem Südwesten. Auch den können wir wieder teilen (hellgrau angedeutet, aber im Baum links noch nicht drin).
- Dann wären wir "fertig".

Dabei legt man bestimmte Teilungsregeln fest:
- die maximale Anzahl der Kreise, die in einem Quadranten sein dürfen, bevor er geteilt wird (hier: max. 1 Kreis).
- die Mindestgröße der Quadranten. Z.B. könnte man entscheiden, dass der hellgraue Quadrant zu klein ist, und dann aufhören.


Nehmen wir mal an, die letzte Teilung machen wir nicht mehr (hellgrau ist zu klein) und wir bekommen den Tree wie links oben angedeutet.
Wenn wir jetzt auf alle Kollisionen prüfen wollen, gehen wir einfach einmal den Tree durch.
Für alle Quadranten, die mehr als 1 Kreis haben, prüfen wir gegen alle anderen darin vorhandenen Kreise.

Also konkret:
- /root/NW ist leer => fertig
- /root/NE hat nur einen Kreis => fertig
- /root/SE/TreeNode/NW hat nur einen Kreis => fertig
- /root/SE/TreeNode/NE hat nur einen Kreis => fertig
- /root/SE/TreeNode/SE hat nur einen Kreis => fertig
- /root/SE/TreeNode/SW hat 2 Kreise => jetzt machen wir eine echte/teure Kollisionsprüfung

D.h. wir sind den Baum einmal durchgegangen, und haben nur 1 Kollisionsprüfung machen müssen.

Die Kreise sind hier im Vergleich zur "Spielwelt" sehr groß - wenn man sich eine Map mit vielen Objekten vorstellt, dann:
- gibt es viel öfter leere Quadranten
- kommt es seltener vor, dass ein Objekt auf der Linie ist
- gibt es mehr Ebenen im Baum; ich habe nach 2 bzw. 3 Ebenen aufgehört
- bringen die ersparten Kollisionsprüfungen wesentlich mehr, hier haben wir ja effektiv nur 2 Prüfungen vermieden



Was du gemacht hast, ging mehr in Richtung kd-tree. Dort teilt man nicht einfach in der Mitte, sondern am Objekt.
Aber auch nicht die Mitte vom Objekt, sondern am äußeren Rand (die Hauptfrage ist nur, an welchem).
Und man teilt abwechselnd in den Dimensionen, also bei 2d einmal horizontal und einmal vertikal.
Und dafür muss man verschiedene Strategien einsetzen, damit am Ende ein effizienter Tree rauskommt.
Man kann den kd-tree aber auch vielseitig einsetzen:
- Wenn ich Kollisionsprüfungen machen will, sollte ich möglichst in einem Sektor nur ein Objekt haben.
- Wenn ich eine Sichtbarkeitsprüfung machen will (was muss ich nicht rendern, weil der Spieler es eh nicht sehen kann), dann will ich möglichst große, leere Sektoren haben.
Und danach passe ich die Teilungsstrategie an.
Und das ist kompliziert, darum hatte ich gesagt, dass ein kd-tree erstmal nix ist, um damit warm zu werden :-)
Benutzeravatar
Chromanoid
Moderator
Beiträge: 4254
Registriert: 16.10.2002, 19:39
Echter Name: Christian Kulenkampff
Wohnort: Lüneburg

Re: STL sort und "sweep & prune"

Beitrag von Chromanoid »

@Nytrox: ist es echt üblich bei Überschneidungen Objekte in zwei Knoten einzuordnen (bei dir 2 und 4)? Mir scheint das viel Overhead zu sein.
odenter
Establishment
Beiträge: 207
Registriert: 26.02.2009, 11:58

Re: STL sort und "sweep & prune"

Beitrag von odenter »

Weil es hier auch um Quadtrees ging und ich in einem anderen Zusammenhang gerade diese Antwort auf Stackoverflow gefunden habe:
https://stackoverflow.com/questions/419 ... lision-det

Ist vielleicht für den einen oder anderen Interessant, vielleicht auch nur langweilig. :)
NytroX
Establishment
Beiträge: 358
Registriert: 03.10.2003, 12:47

Re: STL sort und "sweep & prune"

Beitrag von NytroX »

@Chromanoid:
Keine Ahnung, habe ich mal irgendwo gesehen und hat für mich gut funktioniert :-P
(Mein Programm oben war in C#, d.h. ich dupliziere das Objekt ja nicht wirklich; sind ja Reference Types, also quasi alles nur Pointer)

Man kann ja Objekte mit einer Ausdehnung in den nächsten/angrenzenden Quadranten haben - damit muss man irgendwie umgehen.
Natürlich kann man das auch anders lösen, z.B. einfach die Objekte in den Parent hängen; ich glaube das wäre wohl der klassische Ansatz.
Dann muss man halt später bei der Prüfung in die Kind-Quadranten verzweigen; ich muss halt nie über Quadranten oder Ebenen hinweg prüfen; aber ich weiß nicht, ob das am Ende ein Vorteil oder eher ein Nachteil ist. Habe es nie direkt verglichen.
Es könnte auch einen Unterschied machen, ob man eher eine statische Szene hat (z.B. Terrain oder Räume mit einem Spieler drin), oder eine dynamische (z.B. Arena mit vielen beweglichen Gegnern).
Wahrscheinlich baut es jeder etwas anders: https://www.flipcode.com/archives/Octre ... tion.shtml

Wenn ihr andere Ideen habt oder andere Erfahrungen gemacht habt - immer her damit :-)


@odenter:
Danke für den Link, sehr interessant.
Die Bilder dort sind auch um Welten besser als meine Paint-Versuche ;-)

Edit:
Habe noch das hier gefunden, die Argumentation ist ähnlich wie bei mir.
https://stackoverflow.com/questions/338 ... -in-a-game
(Ist sogar der gleiche User wie im Link von odenter)
Ich finde es ein bisschen Schade, dass in vielen Tutorials auf sowas garnicht eingegangen wird - die benutzen oft nur Punkte.
Benutzeravatar
starcow
Establishment
Beiträge: 523
Registriert: 23.04.2003, 17:42
Echter Name: Mischa Schaub
Kontaktdaten:

Re: STL sort und "sweep & prune"

Beitrag von starcow »

@Chromanoid
Danke für das Paper! Werde es mir gerne durchlesen.

@odenter
Auf den selben Beitrag bin ich auch gestossen. Finde ich auch ziemlich beeindruckend.

@NytroX
Vielen Dank nochmals für diese sehr genaue und gute Erklärung! Das klärt nun die Sache für mich! :daumen:

Ich sehe jetzt auch, dass ich folglich ein leicht anderes Quadtree-Konzept einsetzen muss.
Wenn ich nun aber den Raum immer mittig Teile, anstatt diese Teilung auf den Objektkoordinaten vorzunehmen, heisst das ja auch, dass ich die Map-Grösse (Spielfeld) von Beginn an verbindlich festlegen muss. Objekte dürfen sich demnach auch nicht nachträglich in einen Bereich manövrieren, der ausserhalb dies Gebietes liegt. Seh ich das richtig? Das wäre dann quasi die Einschränkung gegenüber der anderen Methode, welche wiederum nur mit Punkten ohne Ausdehnung funktionieren kann.

Gruss starcow
Freelancer 3D- und 2D-Grafik
mischaschaub.com
Antworten