Algorithmus zur Auswahl aller Zellen in Räumen / Regionen

7

Ich habe eine 2D-Spielkarte, die aus mehreren "Räumen" besteht.

Hier ist zum Beispiel ein 2D-Kartenraster: (Braune Zellen = Wandkacheln)

Geben Sie hier die Bildbeschreibung ein

Wenn ich auf eine Kachel klicke (die nicht braun ist), möchte ich ein Array aller Zellen in der Region erhalten, auf die ich geklickt habe. (Wenn die Region von braunen Kacheln begrenzt ist, sonst nichts tun)

Zum Beispiel gibt es im obigen Bild zwei Bereiche, die beide grau gefärbt sind. Wenn ich auf Zelle (4,4) klicke, erhalte ich ein 4x5-Array von Zellen ab (3,3).

Kennt jemand einen guten leistungseffizienten Algorithmus dafür? Ich muss idealerweise nicht quadratische Räume berücksichtigen.

algorithm tiles maps user25147
quelle
Siehe auch: gamedev.stackexchange.com/questions/31909/…
MichaelHouse

Antworten:

6

Dies wird als Floodfill bezeichnet . Sie können es auf Wikipedia nachschlagen.

Eine Möglichkeit zur Implementierung besteht darin, eine Liste der besuchten vund ausstehenden Quadrate zu erstellen pund so etwas zu tun

v = {}
p = {}
p <- (x, y)
while p is not empty
    (this_x, this_y) = p[0]
    remove p[0] from p
    if (this_x, this_y) is not in v, and (this_x, this_y) is not a wall
        v <- (this_x, this_y)
        // Add the adjacent squares...
        p <- (this_x + 1, this_y + 1)
        p <- (this_x + 1, this_y - 1)
        p <- (this_x - 1, this_y + 1)
        p <- (this_x - 1, this_y - 1)
    end
end

Die Quadrate im Raum sind diejenigen, die noch übrig sind, vwenn Sie fertig sind.

Es gibt auch verschiedene Möglichkeiten, dies zu optimieren, aber Sie sollten die Hauptidee verstehen.

Panda Pyjama
quelle
Dieser Algorithmus überschreitet leicht Grenzen und berücksichtigt keine Auswahl außerhalb des von Wänden begrenzten Bereichs. Muss vorsichtig damit sein.
MichaelHouse
1
Hängt von der Sprache ab, in der Sie es implementieren, und von der Semantik, die Sie Werten außerhalb der Grenzen geben. Dies ist in Lua absolut sicher, wenn Sie nilWerte als Wände betrachten.
Panda Pyjama
9

Ein einfacher Flutfüllungsalgorithmus passt gut zu Ihnen.

Geben Sie hier die Bildbeschreibung ein

Lassen Sie es im Verlauf eine Liste mit Kacheln erstellen. Befindet sich eine benachbarte Kachel außerhalb der Grenzen Ihres Gitters, wird diese gesamte Region nicht von den braunen Kacheln begrenzt und kann ignoriert werden.

MichaelHouse
quelle