寻路算法(一)广度优先搜索与迪杰斯特拉算法

我小时候特别喜欢画迷宫玩,有时候偷偷在课堂上画一幅超大的迷宫,然后给小伙伴们玩。不过可惜的是我只擅长(瞎)画迷宫,但不擅长解迷宫,所以自己画的迷宫到底有几条出口、哪条是最短的其实我自己也不知道。

后来有段时间玩梦幻西游,游戏有个找 NPC 的功能,选择一个 NPC,角色就自己往 NPC 那边跑了,小时候特别好奇,路上那么多房子和死胡同,他怎么就知道要绕路,还能找到一条几乎是最短的路出来的?后来才明白,原来这里面涉及到一些寻路算法。

今天介绍一下两种常见的寻路算法,分别是广度优先算法(Breadth First Search)和迪杰斯特拉算法(Dijkstra's Algorithm)。另外一种更广为人知的A*寻路算法我们下期再说。

抛开游戏里面精致的画面,其实寻路算法本质上是一种图的搜索算法,游戏地图里面哪些可以走、哪些是墙、哪些走起来会慢一点,这些都可以抽象成图的一个个节点。我们先用一个最简单的数组来表示:点 . 代表该位置可走,W 代表该位置不可走。

可以想象这是一个 5 * 5 的迷宫,每个节点可以通过上下左右四个方向移动一个距离,大致就像下面这样,我们以左上角为坐标轴的原点来描述。

广度优先算法(Breadth First Search)

广度优先算法是最简单也是最直观的寻路算法,顾名思义,尽可能广地寻找终点,与其说是寻路算法,不如说只是从起点开始遍历地图来找到终点。

寻找终点

首先我们需要做的是把上面代表迷宫的数据解析为一个图结构。每一个格子代表一个节点,这个图提供一个方法getNeighbors,用来获取指定格子周围的邻居,邻居代表可以移动的格子,所以不会返回墙。

我们通过维护一个队列frontier,来存放将要进行探索的节点。从起点开始,如果他的邻居有还没有探索过的节点,就将该邻居放进队列,直到所有可达的节点探索完。

完整代码见https://github.com/sunhengzhe/path-finding/blob/master/Breadth-First-Search/a.graph-search.js

寻找路线

由此迷宫的所有可达的格子都会被遍历一遍,只要终点可达,那么一定会存放在visited字典里。那么怎么求出起点到终点的路线呢?既然我们能从起点到达终点,那我们当然能存放中间经过的节点了。

这里利用链表或者字典都可以,这里使用了字典来存放,comeFrom字典的key -> value代表key节点是从value节点到达的。所以我们只需要在往frontier中入列的时候,顺便把节点间的关系存放一下就行了。

完整代码见https://github.com/sunhengzhe/path-finding/blob/master/Breadth-First-Search/b.find-path.js

提前结束

至此路线也能求出来了,但是有个小问题,当我们找到终点的时候,遍历还在继续,剩余的地方实际上没有必要继续探索了,因为我们已经拿到了最短路径。需要判断一下,当当前节点为终点时终止循环。

迪杰斯特拉算法(Dijkstra's Algorithm)

广度优先算法虽然简单,但是局限性也比较大,特别是它假定了路和路之间的代价是相同的。但在游戏中我们一般会有很多种地形,比如在石板路上走路是最快的,在草地上可能慢一点,在山地、沼泽里最慢。那么这里不能简单实用 BFS 来寻路了,我们需要引入权重来代表每一种地形的代价。

首先我们使用/来表示山地,在.中移动需要花费1的代价,但是在/中需要花费5。

我们引入一个costSoFar字典,key -> value代表到达节点key需要花费value的代价。

另外我们需要走得快的格子要先走,如果还是简单地把所有邻居同时推到队列里,那么有山地的地方可能提前到达终点,反而让代价少的路没有走到。所以我们需要引入优先队列的数据结构。

优先队列在普通队列的先进先出的基础上增加了优先级的概念,优先级高的元素会先出列。优先队列的实现是另外一个话题,在此不详细阐述。因为我们希望代价低的路先走,所以我们使用最小堆来实现优先队列,具体代码可以参考https://github.com/sunhengzhe/path-finding/blob/master/Dijkstra's-algorithm/priorityQueue.js。

改写关键代码如下:

最后形成的图如下,节点的数字代表到达节点的最小代价。

启发式寻路算法

还有像A* 寻路算法之类的算法属于启发式算法,我们下次再聊。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180702G024A000?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券