【免费】49丨搜索：如何用A搜索算法实现游戏中的寻路功能？1资源-CSDN文库

需积分: 0 102 浏览量 2022-08-03 15:10:36 上传评论收藏 1.57MB PDF 举报

资源详情

资源评论

资源推荐

49 | 搜索：如何用A*搜索算法实现游戏中的寻路功能？

2019-01-18 王争

数据结构与算法之美

进入课程

讲述：修阳

时长 09:58 大小 9.13M

魔兽世界、仙剑奇侠传这类 MMRPG 游戏，不知道你有没有玩过？在这些游戏中，有一个

非常重要的功能，那就是人物角色自动寻路。当人物处于游戏地图中的某个位置的时候，我

们用鼠标点击另外一个相对较远的位置，人物就会自动地绕过障碍物走过去。玩过这么多游

戏，不知你是否思考过，这个功能是怎么实现的呢？

算法解析

实际上，这是一个非常典型的搜索问题。人物的起点就是他当下所在的位置，终点就是鼠标

点击的位置。我们需要在地图中，找一条从起点到终点的路径。这条路径要绕过地图中所有

障碍物，并且看起来要是一种非常聪明的走法。所谓“聪明”，笼统地解释就是，走的路不

能太绕。理论上讲，最短路径显然是最聪明的走法，是这个问题的最优解。







下载APP 

在 Dijkstra 算法的实现思路中，我们用一个优先级队列，来记录已经遍历到的顶点以及这

个顶点与起点的路径长度。顶点与起点路径长度越小，就越先被从优先级队列中取出来扩

展，从图中举的例子可以看出，尽管我们找的是从 s 到 t 的路线，但是最先被搜索到的顶

点依次是 1，2，3。通过肉眼来观察，这个搜索方向跟我们期望的路线方向（s 到 t 是从西

向东）是反着的，路线搜索的方向明显“跑偏”了。

之所以会“跑偏”，那是因为我们是按照顶点与起点的路径长度的大小，来安排出队列顺序

的。与起点越近的顶点，就会越早出队列。我们并没有考虑到这个顶点到终点的距离，所

以，在地图中，尽管 1，2，3 三个顶点离起始顶点最近，但离终点却越来越远。

如果我们综合更多的因素，把这个顶点到终点可能还要走多远，也考虑进去，综合来判断哪

个顶点该先出队列，那是不是就可以避免“跑偏”呢？

当我们遍历到某个顶点的时候，从起点走到这个顶点的路径长度是确定的，我们记作 g(i)

（i 表示顶点编号）。但是，从这个顶点到终点的路径长度，我们是未知的。虽然确切的值

无法提前知道，但是我们可以用其他估计值来代替。

这里我们可以通过这个顶点跟终点之间的直线距离，也就是欧几里得距离，来近似地估计这

个顶点跟终点的路径长度（注意：路径长度跟直线距离是两个概念）。我们把这个距离记作

h(i)（i 表示这个顶点的编号），专业的叫法是启发函数（heuristic function）。因为欧几

里得距离的计算公式，会涉及比较耗时的开根号计算，所以，我们一般通过另外一个更加简

单的距离计算公式，那就是曼哈顿距离（Manhattan distance）。曼哈顿距离是两点之间

横纵坐标的距离之和。计算的过程只涉及加减法、符号位反转，所以比欧几里得距离更加高

效。

原来只是单纯地通过顶点与起点之间的路径长度 g(i)，来判断谁先出队列，现在有了顶点到

终点的路径长度估计值，我们通过两者之和 f(i)=g(i)+h(i)，来判断哪个顶点该最先出队

列。综合两部分，我们就能有效避免刚刚讲的“跑偏”。这里 f(i) 的专业叫法是估价函数

（evaluation function）。

1

2

3

int hManhattan(Vertex v1, Vertex v2) { // Vertex 表示顶点，后面有定义

return Math.abs(v1.x - v2.x) + Math.abs(v1.y - v2.y);

}

 复制代码

剩余13页未读，继续阅读

评论0

内容反馈

养生的控制人

粉丝: 18
资源: 333

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip