1

我需要检查我的游戏角色可以到达的网格的所有单元格。为此，我需要从字符位置开始，然后“淹没”该区域以找到所有可到达的单元格（例如，未被墙壁阻挡的单元格）。

在此图中，玩家是P，阻挡玩家的墙壁由 表示X。我需要检查玩家所在区域的所有单元格。

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

有没有很好的迭代算法来做到这一点？目前我正在递归地执行此操作。

4

2 回答 2

2

将初始位置放入队列中。

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
于 2012-03-25T14:11:13.373 回答
1

您可以使用BFS。用矩形网格表示区域。网格的每个单元格都是图中的一个顶点，当且仅当两个单元格都不是墙并且单元格是相邻的时，两个顶点之间才存在边。

于 2012-03-25T14:11:15.153 回答