如何通过百度地图找到去飞机场的最短路径？吃豆人Pacman游戏中一个幽灵(ghost)应该如何尽快吃到食豆人(pacman)呢？这两个问题，有什么共同的地方呢？

它们都与路径搜索（path-finding)有关。

对于吃豆人游戏，我们可能需要一个迷宫地图：依据迷宫地图中相邻的正方形之间的连接情况，找到一条沿着黑色方块的路线，就可将幽灵导向吃豆人。而为了找到从火车站到机场的行车路线，我们可能会使用百度地图，基于道路的连接情况，从中找到最合适的路径，若没有道路直接连接火车站与机场，则可以通过相关的几条路转接。

以Pacman游戏为例，问题可以简化为如何把幽灵如何从起始点移动到目标点（Pacman所在的位置）。为了实现这一点，游戏程序需要确定幽灵的移动路径，以便到达Pacman当前的位置，然后设计移动幽灵的动画。注意，可能会找到多条路径，一般程序会选择最短的路径。

图3 简化的Ghost找Pacman的算法

图3是一个简化的路径搜索算法的演示。我们先假定移动的规则：墙壁由灰色方块组成，可以通过的位置为空。在每个步骤中，游戏角色可以从一个正方形移动到相邻的正方形，但是不能对角移动。在每个步骤中移动1个格子使幽灵更靠近目标 - Pacman当前位置。但是，“靠近目标”是什么意思？朝着目标直线行进往往会导致撞墙。该算法需要确定哪个周围的方块确实“更靠近目标”，我们可以通过为每个方块分配一个“成本”来代表从该方块到目标顶点所需的最少移动步数。

以下是为每个方块分配成本的算法：
1）从目标方块开始。标记为0，表示离开目标方块为0步；
2）找到距离目标方块正好一步之遥的迷宫中的所有方块。 用数字1标注它们。在该迷宫例子中，目标点是出口方块，只有一个方块距离出口方块1步，标记为1。
3）现在找到距离目方块正好2步的迷宫中的所有方块， 这些方块距离标记为1的方块还有一步，并且尚未被标记，用数字2标记这些方块。
4）标记距离目标方块正好3步的迷宫中的所有方块，它们与标记为2的方块距离一步，尚未被标记。用数字3标记这些方块。
5）按照与目标距离增加的顺序，在迷宫中标记所有方块。用数字k标记方块后，找到与标记为k的方块距离为1的并且尚未标记的方块，为它们标记为k+1。

最后，该算法会为角色出发的方块做标记。此时，程序可以从该方块开始依次选择方块，使得方块的数字总是依次减少，一直到目标方块，把这些方块依次连接起来，就是得到的搜索路径。

本文描述的是一种非常简单的路径搜索算法，属于路径规划算法。在实际应用中，常见的路径规划算法有：最速下降法、部分贪婪算法, Dijkstra算法、Floyed算法、SPFA算法(Bellman_Ford的改进算法)、A*算法、D*算法、图论最短算法、遗传算法、元胞自动机、免疫算法、禁忌搜索、模拟退火、人工神经网络、蚁群算法、粒子群算法等等。