算法帮助：构建游戏棋盘，但需要知道何时方块被锁定
我做了一个游戏棋盘，这个棋盘是一个网格，然后随机给每个格子加上“墙”。当这些格子都建好后，我想知道怎么检查某个格子是否被“锁住”，这样我就不能把玩家放在那儿。
我考虑过这个问题，最初我想的是检查四周是否都有墙，但显然，一个格子可能被开放的格子包围，而这些开放的格子又被墙包围。
还有一种方法是“逃离外部”的算法，基本上是试图找到通往外墙的路径，如果能找到，就说明这个格子没有被锁住。但如果这个格子在外墙上，并且被其他格子包围，那它就是锁住的。
通常是怎么处理这个问题的呢？我在用Python，如果有代码示例的话。
谢谢！
4 个回答
我不太确定你的游戏棋盘长什么样，但如果它像这样：
+----------------------+
| +-----+ |
| | c | |
| | | |
| +-----+ |
| |
| |
| |
+----------------------+
而你想避免把角色放在 c 上，因为它是“被围住的”，虽然它并不是完全被墙包围，你可以很简单地实现一种叫做左手或右手算法的方法——只不过这次不是为了逃出迷宫，而是检查你是否能回到同一个坐标。
这其实要看你的游戏地图有多大。如果是小地图的话，可以用一种快速的路径寻找算法来计算每个格子之间的距离。这样做还有个好处，就是可以避免把玩家放得太靠近其他玩家或游戏中的其他元素。
第二种选择是设计一个墙体生成器，这个生成器的原则是不能创建封闭的房间。在roguelike游戏社区，他们对如何生成随机的（像地牢一样的）地图而不出现封闭房间进行了不少研究。你可以看看他们的成果。
最后，如果你需要在一个超大的地图上找到一个合适的空地，使用细节层次的方法会很有帮助。你可以为地图上分散的稀疏点找到一个连接图（这可以直接由你的地图生成器得出）。这样就足够用来放置玩家了。不过如果你需要在某个特定点获取更多细节，找到通往这些点的路径可以告诉你这个房间是否被锁住了。这种方法在非常密集的迷宫中可能不太管用。
你基本上想要的是一种叫做“洪水填充”的算法。
http://en.wikipedia.org/wiki/Floodfill
编辑
我觉得我之前对你提到的“锁定”和“逃脱”的定义理解错了。
如果你的游戏板是有限的，那么每个格子都被锁定在某个空间里。如果我理解得没错的话，你只是想让这个空间足够大。其实，你可以用洪水填充算法轻松计算出它的面积。