Vereinfachung von vielen (Rechtecken) Kollisions-Volumen

Design Patterns, Erklärungen zu Algorithmen, Optimierung, Softwarearchitektur
Forumsregeln
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.
Antworten
Dummie
Beiträge: 97
Registriert: 09.02.2004, 20:45

Vereinfachung von vielen (Rechtecken) Kollisions-Volumen

Beitrag von Dummie »

Hey,

ich habe ein Level aus vielen verschiedenen Elementen erstellt und jedes dieser Elemente bringt sein eigenes Kollisionsvolumen mit. Viele dieser Elemente wiederholen sich, so ist z.B. der Boden in meinem Level aus vielen Kacheln zusammengesetzt. Es ist natürlich quatsch, dass jede Kachel ein eigenes Kollisionsvolumen mitbringt, aber das ist zunächst mal die Ausgangssituation und hier kommt auch die geplante Optimierung ins Spiel, denn ich möchte alle Kollisionsvolumen finden, die direkt nebeneinander liegen und somit zu einem einzigen Kollisionsvolumen vereint werden können. Im Falle der Kacheln könnte der gesamte Boden zu einem einzigen Kollisionsvolumen zusammengefasst werden.

Wie könnte ein solcher Algorithmus aussehen? Aktuell fehlt mir ein guter Plan, wie ich das umsetzen könnte. Vermutlich müsste ich für jedes Kollisionsvolumen schauen, ob es einen Nachbarn hat und wie weit dieser entfernt ist. Sofern die Differenzen nicht zu groß sind kommt es in die Liste. Allerdings klappt das ja nur, wenn es nicht diagonal davon liegt, denn ansonsten ließe sich das ja gar nicht als ein Rechteck vereinfachen. Da alles außerdem irgendwie voneinander abhängt müsste ich das vermutlich sogar mehrmals laufen lassen. Vermutlich geht es aber irgendwie in die Richtung Flood Fill?

TLDR: Gegeben ist eine Liste von Rechtecken. Wie lässt sich diese Liste durch noch weniger Rechtecke repräsentieren? Sprich zwei direkt benachbarte Rechtecke werden zu einem vereint. Das Ergebnis ist also eine start reduzierte Liste an Rechtecken. Rechteckte die nicht vereinfacht werden können bleiben einfach unverändert erhalten.

Vielleicht hat ja jemand eine Idee oder kennt sogar einen existierenden Algorithmus dafür? Ich suche zwar nach einer 3D-Lösung, aber auch ein Ansatz in 2D würde mich schon sehr viel weiter bringen. :)
Dateianhänge
Kollisionen_Kombiniert.png
Kollisionen.png
Dummie
Beiträge: 97
Registriert: 09.02.2004, 20:45

Re: Vereinfachung von vielen (Rechtecken) Kollisions-Volumen

Beitrag von Dummie »

Okay, ich hab mal ein wenig experimentiert. Wirklich glücklich bin ich hiermit allerdings noch nicht.

Im Endeffekt versuche ich einfach die Volumen zu verschmelzen und schaue dann, ob sie noch die richtige Größe, etc. haben.

Code: Alles auswählen

// Vorher sortieren
simplified = simplified.OrderBy(o => o.center.y).OrderBy(o => o.center.x).OrderBy(o => o.center.z).ToList();

        for (int iterations = 0; iterations < 1000; ++iterations)
        {
            bool dirty = false;

            for (int i = 0; i < simplified.Count; ++i)
            {
                for (int j = 0; j < simplified.Count; ++j)
                {
                    // Wir ignorieren uns selber natürlich
                    if (i == j)
                        continue;

                    Bounds b1 = simplified[i];
                    Bounds b2 = simplified[j];

                    // Würden sich die Volumen überlappen? Wenn nicht, dann sind sie vermutlich eh zu weit entfernt.
                    if (!b1.Intersects(new Bounds(b2.center, b2.size * 1.01f)))
                        continue;

                    Bounds newBounds = new Bounds(b1.center, b1.size);

                    // Wir erzeugen einfach ein neues Volumen und vergrößern es so dass das andere Volumen hineinpasst
                    newBounds.Encapsulate(b2);

                    // Wie viele Achsen haben wir verändert?
                    int changeCount = 0;

                    if (!Mathf.Approximately(newBounds.size.x, b1.size.x))
                    {
                        // Sicherstellen das wir nur kompatible Volumen betrachten
                        if (b1.size.y != b2.size.y || b1.size.z != b2.size.z)
                            continue;

                        ++changeCount;
                    }

                    if (!Mathf.Approximately(newBounds.size.y, b1.size.y))
                    {
                        // Sicherstellen das wir nur kompatible Volumen betrachten
                        if (b1.size.x != b2.size.x || b1.size.z != b2.size.z)
                            continue;

                        ++changeCount;
                    }

                    if (!Mathf.Approximately(newBounds.size.z, b1.size.z))
                    {
                        // Sicherstellen das wir nur kompatible Volumen betrachten
                        if (b1.size.x != b2.size.x || b1.size.y != b2.size.y)
                            continue;

                        ++changeCount;
                    }

                    // Wir erlauben nur maximal eine Achse zu verändern
                    if (changeCount > 1)
                        continue;

                    // Die zwei beiden rauswerfen
                    simplified.Remove(b1);
                    simplified.Remove(b2);

                    // Und durch unser größeres ersetzen
                    simplified.Add(newBounds);

                    dirty = true;

                    break;
                }
            }

            if (!dirty)
                break;
        }
Man kann in den Screenshots gut erkennen (vorallem an der Decke) wie viele Volumen zusammengefasst wurden. Allerdings sieht man auch, dass der Algorithmus dann irgendwann terminiert hat, da es keine kompatiblen Größen mehr gefunden hat.

Vielleicht wird ja langsam klar was ich vorhabe und vielleicht hat noch jemand eine bessere Idee. Die Geschwindigkeit des Algorithmus ist auch nicht wichtig. Das Ergebnis zählt :)
Dateianhänge
unoptimiert.png
optimiert.png
joeydee
Establishment
Beiträge: 1039
Registriert: 23.04.2003, 15:29
Kontaktdaten:

Re: Vereinfachung von vielen (Rechtecken) Kollisions-Volumen

Beitrag von joeydee »

Du willst das nur für schnellere Kollisionsabfragen zusammenfassen, nicht zum Rendern?
Mach besser Space-Partitioning, z.B. sortiere alle Volumes in einen Octree ein.

Falls du mit deinem Algo weiterexperimentieren möchtest: ziele nicht auf exakte Volumes ab. Fasse zwei berührende Boxen zusammen, wenn deren gemeinsame BoundingBox in einer bestimmten Toleranzgrenze bleibt, aber behalte die Info über die Child-Boxen in einer Baumstruktur. Gegen die kannst du dann hierarchisch testen. Hauptsache auf oberster Ebene musst du nur gegen wenige Boxen testen. Ich vermute aber, je nachdem welche Boxen zufällig zuerst zusammengefügt wurden, wird es mit so einer Methode mal bessere, mal weniger gute Gesamtlösungen geben, sprich: es entsteht nicht zwangsläufig ein ausgewogener Baum.
Dummie
Beiträge: 97
Registriert: 09.02.2004, 20:45

Re: Vereinfachung von vielen (Rechtecken) Kollisions-Volumen

Beitrag von Dummie »

Danke für die Antwort! Ja, ich mache das ausschließlich, um die Kollisionsabfragen zu beschleunigen. Alleine der Boden besteht aus ~700 Kollisionsvolumen, obwohl er eigentlich durch ein einziges repräsentiert werden könnte. Mein Kollisions-System legt auch bereits ein Grid über die Welt (sie besteht nur aus diesem einen recht großen Raum, das wird sich auch nicht ändern) und testet bereits nur die Kollisionen innerhalb einer Zelle. Ich weiß auch nicht, ob das wirklich messbar ein Performance-Problem ist, aber mich hat auch einfach die Lust gepackt hier mal etwas zu basteln :)

Tatsächlich hatte ich mittlerweile überlegt ein weiteres Grid über die Welt zu legen und einfach entsprechend ein bool zu setzen, falls sich die Zelle innerhalb eines Kollisionsvolumens befindet. Sofern die Auflösung des Grids hoch genug ist, müsste mir das anschließend durch ein bisschen iterieren recht gute kombinierte Kollisionsvolumen liefern. Wird aber sicherlich verdammt langsam sein, aber diese Information generiere ich ja glücklicherweise nicht zur Laufzeit. Insofern stört mich das gar nicht. Es muss nur funktionieren :)

Das werde ich also wohl als nächstes mal testen. Ich denke das Ergebnis wird auch nicht perfekt sein, aber viel besser wird es vielleicht gar nicht gehen. Ich werde berichten. Weitere Ideen und Anregungen sind natürlich immer gerne gesehen :)

Edit: Die Lösung mit dem Grid liefert gerinfügig bessere Ergebnisse, aber ist ebenfalls nicht perfekt. Vermutlich könnte ich es weiter verbessern, indem ich nur gewisse Collider erlaube miteinander zu verschmelzen. Das würde verhindern das andere Collider miteinander verschmolzen werden, die das Ergebnis verschlechtern. Trotzdem habe ich hiermit meine Anzahl an Collider deutlich reduziert und das war ja eh das Hauptziel. Richtig perfekt wird es vermutlich nur händisch.
Antworten