cocos creator主程入门教程(十)—— A*寻路

摘要: 五邑隐侠,本名关健昌,10年游戏生涯,现隐居五邑。本系列文章以TypeScript为介绍语言。

这一篇介绍A*寻路算法。在RPG、SLG、模拟经营类游戏,有需要给角色寻路的需求,一般寻路我们采用A*寻路算法,A*寻路算法是一种广度优先启发性算法。

先说说什么叫广度优先。搜索分为广度优先和深度优先,主要体现在对节点的展开上。深度优先一直往一个方向查找,如果没办法查找下去,在当前节点改变方向继续查找,直到找到终点。如果无法继续查找,就回退上一格重复操作。广度优先把当前节点放入待探索列表,循环从待探索列表里取出节点进行展开,直到找到终点。如果待探索列表为空,说明没有路可走。

启发性指算法在待探索列表里取节点时,先预测哪个节点的路径可能会最短,优先对该节点展开,A*算法基于对未探索路径的假设和预测,假设所有路都能通行前提下总路径最短值。在图论里,介绍过有一种寻找最短路径的算法叫Dijkstra算法,该算法基于贪心算法,即当前选择探索的节点,为尚未确定最短路径,当前源点能到达且路径最短的节点。Dijkstra算法基于已知距离源点最短。为了便于理解这两种算法的区别,先介绍下Dijkstra算法。

Dijkstra算法知道所有可能的节点,如下图,知道总共有ABCDE5个节点,寻找从A点出发到各点的最短路径。

cocos creator主程入门教程(十)—— A*寻路

1)算法有两个数组,一个维护当前已知最终最短路径的节点数组S,找到为路径字符串和长度,否则为空字符串,初始只有起点A点标记为“A”。另一个数组V,维护各个节点“目前所知”从源点出发最短的路径长度(不一定是最终的最短路径,初始B标记为6,D为7),已经找到最终最短路径的标记为0(初始时起点A标记为0),目前无法到达的标记为无穷大。

2)循环从数组V中获取标记非0,非无穷大,路径最短的节点,在数组S中标记为1,修正V中其他节点的最短路径。直到数组S中所有节点都标记为1

如上图,寻路的过程为:

V:(A,0),(B:6),(C:无穷大),(D:7),(E:无穷大),S:(A,“A”),(B:“”),(C:“”),(D:“”),(E:“”)

V:(A,0),(B:0),(C:11),(D:7),(E:18),S:(A,“A”),(B:“AB”),(C:“”),(D:“”),(E:“”)

V:(A,0),(B:0),(C:10),(D:0),(E:18),S:(A,“A”),(B:“AB”),(C:“”),(D:“AD”),(E:“”)

V:(A,0),(B:0),(C:0),(D:0),(E:18),S:(A,“A”),(B:“AB”),(C:“ADC”),(D:“AD”),(E:“”)

V:(A,0),(B:0),(C:0),(D:0),(E:0),S:(A,“A”),(B:“AB”),(C:“ADC”),(D:“AD”),(E:“ABE”)

这里,Dijkstra算法基于知道所有可能的节点,目标节点也有多个,每个节点可以直接到达的节点数没有限制。

游戏里的寻路是目标节点只有一个,中间节点可能有多个,每个节点可以直接到达的节点数最多4个(如果是8个方向是8)

cocos creator主程入门教程(十)—— A*寻路

将数组改成列表会更灵活,现在将数组V改成open队列,将数组S改成close队列。如上图,要找到A到E的路径,仍然按照Dijkstra算法思路,

1)先将A放入open队列,路径长度为0

2)循环从open列表里拿出路径长度最短的节点,将其放入close队列并记录上一节点,对其4个方向进行展开,如果已经在open、close队列,修正其最短路径长度;如果不可走,忽略;否则放入open队列并计算其路径长度。

3)如果找到E点,通过E点的上一节点,上一节点的上一节点...一直反推到A点,形成反推路径,从而找到A到E的最短路径。

4)如果还没找到E点,open 队列为空,A到E路不通。

如上图,从Dijkstra算法修改过来的寻路算法,按照红色、绿色、蓝色、黄色节点,逐步展开寻找才找到A到E的最短路径,很多没用的分支,效率低。

A*的优化思路主要在挑选节点展开时,假设找到一个中间节点B后,中间节点B到E的路都是可走的。这时候最短路径长度是计算经过B点A到E的最短路径(AB)+(BE)。在RPG游戏中,最简单的情况是,A到B的路径长度等于从A走到B经过的格子数,B到E的路径长度等于假设B到E的路都相通情况下B走到E经过的格子数。A*算法每次展开节点时都尽可能的往可能最短的路径去展开寻找,减少没必要的分支,提高寻路效率。

下面是A*寻路算法过程

1)先将A放入open队列,记录其上一节点为空

2)循环从open列表里拿出节点N,N为经过该点N,A到E路径预测长度最短的节点,将其放入close队列;对其4个方向进行展开,如果已经在open、close队列,修正其上一节点;如果不可走,忽略;否则放入open队列并记录其上一节点为N。

3)如果找到E点,通过E点的上一节点,上一节点的上一节点...一直反推到A点,形成反推路径,从而找到A到E的最短路径。

4)如果还没找到E点,open 队列为空,A到E路不通。

A*寻路算法先说到这里,下一篇我们将介绍有限状态机和行为树。

上一篇:max file descriptors [4096] for elasticsearch process is too low, increase to at least [65536]


下一篇:《JavaScript Dom 编程艺术》读书笔记-第4章