spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hallo,

ich versuche zurzeit für mein Tilemap basiertes 2D Spiel zur Laufzeit Collider generieren zu lassen. Dazu habe ich mir folgende Vorgehensweise überlegt:

1. Tilemap in ein zweidimensionales boolean Array umwandeln. Wahr bedeutet an der Stelle muss ein collider generiert werden.
2. Zusammenhängende Bereiche suchen (werden in einer Klasse "Region" als neues zweidimensionales Array gespeichert) und zu einer Liste hinzufügen. Dazu wird ein Startpunkt in eine Queue eingefügt. Für jeden Punkt in der Queue werden die Nachbarpunkte betrachtet und ebenfalls in die Queue eingefügt, falls sie den selben Wert wie der Startpunkt haben.
3. Für jede Region die Außenlinie bilden
4. Die Außenlinie als neuen Pfad für den Collider (PolygonCollider2D in Unity, um genau zu sein) abspeichern.

Die Erstellung der Region klappt soweit, nun habe ich aber das Problem, dass in einer Region weitere Regionen eingeschlossen sein können. Die entsprechende Matrix kann dann zum Beispiel so aussehen:

1 1 1
1 0 1
1 1 1

An dieser Stelle möchte ich gerne das Verhalten den PolygonCollider2D ausnutzen: Wenn ein Pfad innerhalb eines anderen Pfads existiert, findet eine Kollision nur zwischen den Pfaden statt. Bezogen auf das Beispiel: Bei der 0 in der Mitte würde also keine Kollision stattfinden.
Das ganze hat den Vorteil, dass auch funktioniert, wenn ein Pfad einen Pfad enthält, der wieder einen Pfad enthält (und so weiter).

Nun suche ich einen Algorithmus, um Regionen innherhalb von Regionen zu erkennen. Ich hatte ursprünglich vor, den gleichen Ansatz wie unter 2. zu benutzen, jedoch stellt folgende Matrix ein Problem für den Ansatz dar:

1 1 1 1
1 1 0 1
0 1 1 1

Wie erkenne ich, dass die 0 unten links nicht innerhalb der Region liegt? Vielleicht habt ihr ja eine Idee für mich oder kennt einen Algorithmus der mein Problem bereits löst?


// Edit:
Ach ja, zwei wichtige Ergänzungen noch dazu:

1. Bereiche hängen nur horizontal/vertikal zusammen.
0 1
1 0
hängt also nicht zusammen.

2. Eine Möglichkeit zu überprüfen, ob ein potentieller Startpunkt tatsächlich innerhalb der Region liegt, wäre zu prüfen ob jeweils oben, unten, rechts und links ein Feld mit einem anderen Eintrag existiert. Allerdings scheint mir das für beliebig große Regionen sehr ineffizient. Gibt es dazu eine bessere Idee?

Zitat von »MitgliedXYZ«

Wie wäre es, wenn du dir die Entfernung jeder 0 zu jeder anderen 0 berechnest. Ist sie unendlich groß, gibt es keinen Weg von einer 0 zur anderen 0.
Ist jetzt bestimmt nicht der effizienteste Ansatz, müsste aber funktionieren.

Ich fürchte die Effizienz wäre dabei wirklich ein Problem, da der Spieler die Spielwelt (Tilemap) direkt manipulieren kann und die Collider jedes mal neu berechnet werden müssen.
Weiterhin bleibt das Problem, dass ich dann immer noch nicht weiß, welche 0 innerhalb der 1en steht und welche nicht. Oder habe ich da was übersehen?

Danke für den Link, der ist sehr interessant. Der Two-Pass Algorithmus könnte die Performance schon bei der ursprünglichen Inselfindung erhöhen. Momentan laufe ich für jede neue Region extra über die Matrix.

Die Löcher innerhalb der Regionen könnte ich mit dem Algorithmus herausbekommen, indem ich Vordergrund und Hintergrund vertausche. Dann bekomme ich zwar auch den Hintergrund außen herum als Region, den könnte ich dann allerdings über die minimalen/maximalen x/y Werte wieder aussortieren. Wenn beispielsweise der kleinste x Wert in der Region dem linken Rand entspricht, dann kann die Region nicht umschlossen sein und wird aussortiert.
Mir fällt dabei gerade auf, dass der Ansatz auch für meine ursprüngliche Idee funktioniert, allerdings dürfte der Two-Pass Algorithmus deutlich perfomanter sein.

Kurzes Feedback: Der two-pass Algorithmus löst mein Problem sehr effizient! Die Framerate liegt bei Neuberechnung der Collider in jedem Frame für eine größere Welt bei ~300 fps statt ~400fps ohne Neuberechnung. Dabei ist noch keine Optimierung vorgenommen (z.B. nur neu berechnen, falls sich der Collider überhaupt ändert).

PS: Das im Anhang ist natürlich keine größere Welt