冒险游戏 - 在房间内漫游

Question

我正在用Python和Pygame做一个冒险游戏。我的主要问题是怎么定义房间的边界，让主角在里面走动而不会每次都撞到边界。可惜的是，我从来没有学过算法，所以对怎么计算路径一点头绪都没有。我知道这个问题比较笼统，也不容易回答，但如果能给我一点方向上的建议，我会非常感激。谢谢！

Answer 1

可惜的是，我从来没有学习过算法，所以我对如何计算路径一点头绪都没有。

在你开始写游戏之前，应该先了解一下这些知识。虽然一开始需要花点时间和精力，但这样做可以让你以后省下很多麻烦。

Answer 2

有两种简单的方法可以定义你在这个游戏中的边界。

第一种方法是把你的区域划分成一个网格，然后用一个二维数组来记录网格中哪些方块是可以通过的。通常，这个数组也会存储地图信息，所以在每个位置上，会有一个数字表示这个方块是草地、墙壁、道路还是山等（这样程序就知道该显示什么图像）。大致的样子是这样的：

######
#.#  #
# ## #
#    #
######

如果你想要一种“迷宫”的效果，墙壁比较细，那就需要用一个更复杂的二维数组来表示网格方块之间是否有竖直的墙壁，以及是否有横向的墙壁。大致的样子（虽然用ASCII画出来有点拉伸，但希望你能明白）是这样的：

 - - - -
| |     |
   - - 
|       |
 - - - -

接下来要决定的是你的角色可以朝哪个方向移动（上下左右是最简单的，但对角线也不是太难）。然后程序基本上需要“脑海中”探索这个区域，从你当前的位置开始，希望能找到目的地。

一个简单的搜索方法，适合上下左右移动，并且能找到最短路径（如果有的话），叫做广度优先搜索。这里有一些伪代码：

queue = new Queue #just a simple first-in-first-out
queue.push(startNode)
while not queue.empty():
    exploreNode = queue.pop()
    if isWalkable(exploreNode): #this doesn't work if you use
                                #"thin walls". The check must go
                                #where the pushes are instead

        if isTarget(exploreNode):
            #success!!!
        else:
            #push all neighbours
            queue.push( exploreNode.up )
            queue.push( exploreNode.down )
            queue.push( exploreNode.left )
            queue.push( exploreNode.right )

这个算法在大地图上运行比较慢，但可以让你熟悉一些图形搜索和路径寻找的概念。一旦你确认它能正常工作，你可以尝试用A*算法或类似的算法替换它，这样应该能在更短的时间内得到相同的结果！

A*和许多其他搜索算法使用的是一个优先队列，而不是先进先出队列。这让它们可以优先考虑“更有可能”的路径，但如果发现更直接的路径被阻挡了，也会考虑绕路的路径。

Answer 3

我建议你了解一下A*搜索算法，因为它在游戏中常用来解决路径问题。

如果这个游戏是二维的（或者说2.5维），我建议你使用瓦片系统，这样检查碰撞会更简单。网上有很多信息可以帮助你入门。