Vereinfachung von vielen (Rechtecken) Kollisions-Volumen
Verfasst: 14.07.2019, 00:12
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. :)
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. :)