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?
Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Superwayne« (08.11.2015, 17:11)