python - 算法帮助 : Building game board, 但需要知道方 block 何时被锁定

Question

我构建了一个由网格组成的游戏板，然后随机分配网格，将“墙”分配给一个单元格。构建单元格后，我如何检查某个单元格是否已“锁定”，以便我不会将玩家放在那里。

我考虑过这个问题，第一次之前我想出了检查四周是否有四堵墙，但很明显，一个牢房可能被开放的牢房包围，然后又被墙包围。

另一个是“逃到外面”的算法，它基本上是试图找到一条通往外墙的路径，这意味着它没有被锁在里面，但是如果方 block 在外墙上并且被方 block 包围它会被锁在里面。

这通常是如何处理的？如果这对任何代码示例很重要，我将使用 python。

谢谢!

Answer 1

你基本上想要一个 floodfill 算法。
http://en.wikipedia.org/wiki/Floodfill

编辑
我想我误解了你对“锁定”和“逃脱”的定义。
如果您的游戏板有限，则那里的每个单元格都被锁定在某个空间中。如果我没理解错的话，你只是希望那个空间足够大。那么，您可以使用洪水填充算法轻松计算出它的面积。