Algorithmus zum "Überfluten" eines Bereichs

Ich muss alle Zellen eines Gitters überprüfen, die mein Spielcharakter erreichen kann. Um dies zu tun, muss ich von der Position des Charakters ausgehen und dann den Bereich überfluten, um alle erreichbaren Zellen zu finden (z. B. Zellen, die nicht durch eine Wand blockiert sind).Algorithmus zum "Überfluten" eines Bereichs

In dieser Zeichnung ist der Player P und die Wände, die den Player blockieren, werden durch X dargestellt. Ich muss alle Zellen in dem Bereich untersuchen, in dem sich der Spieler befindet.

X X X X X X X X 
X  X X  X 
X P  X X X X 
X X   X X 
X X X X X X X 
X X X X X X X X

Gibt es einen netten iterativen Algorithmus, dies zu tun? Momentan mache ich das rekursiv.

Quelle

2012-03-25 Paul Manta

@sch Nichts. Ich möchte nur wissen, ob es eine iterative Alternative gibt. –

Ich denke, die rekursive Lösung ist die beste. –

Es gibt eine Reihe von Algorithmen auf Wikipedia, sicherlich wird man für Sie arbeiten: http://en.wikipedia.org/wiki/Flood_fill –

Setzen Sie die Anfangsposition in eine Warteschlange.

while queue is not empty 
    remove an entry from the queue 
    add all reachable neighbours not yet marked to the queue (unless they are already in) 
    mark position as reachable 
end while

Quelle

2012-03-25 14:11:13

Dies ist nicht iterativ, Sie haben gerade die Rekursion durch einen expliziten Stapel ersetzt. – orlp

@Nightcracker: falsch. Es ist eine Warteschlange, kein Stapel. Bitte mod up wieder ... – wildplasser

Und das ist nicht iterativ wie? –

Sie können BFS verwenden. Stellen Sie den Bereich in einem rechteckigen Raster dar. Jede Zelle des Gitters ist ein Eckpunkt in dem Graphen, und genau dann gibt es eine Kante zwischen zwei Eckpunkten, wenn beide Zellen Nichtwände sind und die Zellen benachbart sind.

Quelle

2012-03-25 14:11:15

Algorithmus zum "Überfluten" eines Bereichs

Antwort

Verwandte Themen