数据结构与算法之美
王争
前 Google 工程师
283752 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 81 讲
基础篇 (38讲)
数据结构与算法之美
15
15
1.0x
00:00/00:00
登录|注册

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

迷宫问题的解决方法
实际软件开发中的应用
平衡路线质量和执行效率
其他启发式搜索算法
启发式搜索算法概述
人物自动寻路功能实现
地图抽象成有向有权图
最短路径 vs 次优路径
结束条件
A*算法主要逻辑
估价函数
顶点和边的定义
A*算法优化
最短路径 vs 次优路径
搜索问题
思考题
应用场景
启发式搜索算法
A*算法在游戏寻路中的应用
A*算法的局限性
A*算法实现
算法解析
A*算法

该思维导图由 AI 生成,仅供参考

魔兽世界、仙剑奇侠传这类 MMRPG 游戏,不知道你有没有玩过?在这些游戏中,有一个非常重要的功能,那就是人物角色自动寻路。当人物处于游戏地图中的某个位置的时候,我们用鼠标点击另外一个相对较远的位置,人物就会自动地绕过障碍物走过去。玩过这么多游戏,不知你是否思考过,这个功能是怎么实现的呢?

算法解析

实际上,这是一个非常典型的搜索问题。人物的起点就是他当下所在的位置,终点就是鼠标点击的位置。我们需要在地图中,找一条从起点到终点的路径。这条路径要绕过地图中所有障碍物,并且看起来要是一种非常聪明的走法。所谓“聪明”,笼统地解释就是,走的路不能太绕。理论上讲,最短路径显然是最聪明的走法,是这个问题的最优解。
不过,在第 44 节最优出行路线规划问题中,我们也讲过,如果图非常大,那 Dijkstra 最短路径算法的执行耗时会很多。在真实的软件开发中,我们面对的是超级大的地图和海量的寻路请求,算法的执行效率太低,这显然是无法接受的。
实际上,像出行路线规划、游戏寻路,这些真实软件开发中的问题,一般情况下,我们都不需要非得求最优解(也就是最短路径)。在权衡路线规划质量和执行效率的情况下,我们只需要寻求一个次优解就足够了。那如何快速找出一条接近于最短路线的次优路线呢?
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

A*搜索算法在游戏开发中的应用是一种常见的技术,能够实现角色的自动寻路功能。该算法结合了广度优先搜索和启发式搜索的优点,通过评估每个可能路径的代价来找到最优路径,为玩家提供流畅的游戏体验。文章介绍了A*算法的原理和实现方式,以及与Dijkstra算法的对比。A*算法通过综合考虑顶点到终点的路径长度估计值,能够更快速地找到次优路线,但并不能找到最短路径。文章还提到了A*算法的代码实现逻辑,以及对Dijkstra算法的简单改造。总的来说,A*搜索算法为游戏开发带来了新的可能性,为玩家提供更加智能化和流畅的游戏体验。文章内容涉及算法原理、代码实现和技术优化,对于游戏开发者和技术爱好者来说具有一定的参考价值。文章还提到了A*算法的代码实现逻辑,以及对Dijkstra算法的简单改造。总的来说,A*搜索算法为游戏开发带来了新的可能性,为玩家提供更加智能化和流畅的游戏体验。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《数据结构与算法之美》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(59)

  • 最新
  • 精选
  • hua168
    我之前是打算生管理,去个小公司,发现也要会开发,去年就毅然去学java,维护懂java会有帮助,也可以搞下大数据……再学一门本职运维开发需要python…… 我就是这样打算的… 同学说我们学历低只要大专,问我要大家考研究生不?我感觉我不去大公司的话没什么用吧?但一想很多要求本科,自考研究生不知道承认不?尤其公司,再说就算看完都老了吧……意义有多大?

    作者回复: 看得到@hua168同学对职业规划很迷茫。 我来逐一回答一下你的问题: 1. 自考学历对你来说没用。绝大部分卡学历的公司,只看第一学历;不卡学历的那部分公司,你自考本科也没必要。自考学历对一小部分人有用,具体哪部分人适合我就不展开讲了,总之不适合你。但是,你没有因为学历自卑,公司这么多,总有不卡学历的。我见过很多大专文凭,技术去贼拉子好的,照样去大公司。 2. 不管是大公司还是小公司,都会卡年龄。不过所谓的卡年龄并不是说年龄大了就没人要了。而是能力跟年龄不符,年龄一大把却跟人家工作两三年经验能力差不多,要钱还贼高,那估计确实没人要。 3. 不要再去学java了。如果你还想走技术路线,那就要专精尖,这个我前一条回复说过了。 4. 我还是说了,对于技术一般的人来说,如果要升管理岗,还是那句话“要有领导气质”,另外,你要包装一下简历,一些很小公司的领导是识别不出来的:)听起来是不入流的建议,但是,我确实是认真的。 5. 实际上,年龄大了,技术没有太大竞争力,去个安稳的公司很好,比如国企性质的一些互联网保险公司,具体你自己搜搜吧,我这里不方便说公司名字。 以上建议只针对你本人的情况,并且是我的个人建议。如有不投,你自己斟酌。

    2019-01-19
    7
    143
  • hua168
    大神,能问一个题外话吗,关于自己人生规划,水平和眼界所限,想不通, 都说大神级见识很广也多,能给我这个35岁只维护过四五十台linux服务器的运维指条路吗? 现在很迷茫和压力大~~ 能力如下: 一.网络:CCNA水平,自过了CCNP忘记了,当过2年网管 二、维护过asp.net电商网站,3年,只有简单的,兼职网管 三、linux运维,只在一家电商做了3年多,会 1.web:nginx、tomcat配置(少用)+php:nignx的rewirte和反代 2.数据库:mysql、mongoDB、redis 配置及主从,不会mycat、Cetus之类 3.反代:会nginx、haproxy简单配置 4.存储:NFS、fastDFS、hadoop简单看了一下 5.版本控制:只会git及搭建gitlab+jenkins(简单的CI/CD) 6.监控:简单配置zabbix+shell脚本 7.虚拟化:kvm安装及配置、docker(k8s还没学) 8.云计算:openstack只会安装做过实验 9.测试:只会ab工具 10.日志:ELK安装配置,还没结合java(在学中) 11.大数据:没使用过(不会flume、storm、spark、flink、kafka) 12.脚本:主要是shell为主、会点python 四、编程能力:自学,没项目经验 1.前端: 1)HTML(HTML5不怎看) 2)css(laiui、学了一下vue) 3) js、jquery框架、ES6简单看了一下 2.PHP:语法简单的thinkphp5框架 3.java:考虑要维护java web在学 只看了java、jsp及servet、spring、springMVC、spring Boot(这个为主) 4.python:考虑运维用到 python:会简单的脚本 django:只会官网简单的 问题是:现在已35岁了,失业,怎办?年龄摆在那里,能力好像不强,学历大专。 能给个建议吗?非常感谢~~

    作者回复: 我下面说的话,可能会伤害到你,不过,我是非常认真的。 从你对运维相关的技术点的描述上,可以看出,你应该没有在一个稍微大点的公司工作过吧,所以,很多技术都用的不够深,都只是略知一二,没有自己拿得出手的东西。 建议你去稍微大点公司锻炼一下技术,同时,也能给你的履历加分。 不过,以你的年龄和履历,去稍微大点的公司可能也不现实了,因为现在好点的公司都卡学历、背景,更别说技术了。 所以,我建议你找一个运维领域的风口技术去研究,比如你提到的k8s。这种技术才兴起,会的人不多,所以招聘公司都不会太卡学历、经历,只要会,是个人都要,可以借机去个大点的公司。这会是你的一个转折点。 而且。现在,经济下行,互联网行业都压缩招聘。你正好利用这1、2年,沉下心来,抓住一个技术方向,研究深、研究透。 还有一条路,那就是做管理岗位。这个要看你有没有领导气质了:)如果有领导范,年龄大,工作经历多,也可以忽悠到一些小公司的管理岗。实际上,对你来说,这条路也是不错的。 还有一条路,那就是靠去天使轮的创业公司逆袭。这条路有点赌博的意思。不过,如果公司搞大了,你也会青云直上,这辈子都不愁了:)

    2019-01-19
    8
    94
  • 1
    有一点不明白,希望老师能解答一下。实际上,我们可以换一种抽象的思路,把整个地图分割成一个一个的小方块。在某一个方块上的人物,只能往上下左右四个方向的方块上移动。请问障碍物是怎么绕过的呢?

    作者回复: 也可以,你这个抽象成二维数组喽,那就是邻接矩阵的表示方法,可以站人的用1表示,不能站人的方块用0表示,bfs就能得到最优解。

    2019-08-20
    15
  • 『LHCY』
    真实游戏中也是用的小方块来做的吗?比如要往(1,1)方向走,先把模型角度调整,然后移动是一个个小方格走的,因为方格太小使肉眼分辨不出?

    作者回复: 是的,你说的没错!

    2019-01-18
    3
    14
  • yongxiang
    王争老师,我把代码输入运行,并把过程打印出来,发现代码运行的过程跟您说的A*算法的三点区别中的第三点不一样,不会在遍历到目标顶点时退出while循环。您看是不是27行的break只是退出了for循环,无法退出while循环,是不是需要增加以下的修改: if (nextVertex.id == t) { queue.clear(); break; }

    作者回复: 嗯嗯 我更新下,是个bug:)

    2019-01-19
    9
  • 皇家救星
    我记得以前看过的a*算法介绍还有close和open表,这里好像没提到?

    作者回复: 那就是俩人造的概念 并没有太大意义。

    2019-01-18
    5
  • 且听疯吟
    仔细阅读了下代码,感觉代码中存在错误点,每次应该是取最小的 min(e.w + e.f),但是在下面的代码中只看到了计算出了估值量f,并没有看到对其进行比较大小,不知道争哥觉得对不对? if (minVertex.dist + e.w < nextVertex.dist) { // 更新 next 的 dist,f nextVertex.dist = minVertex.dist + e.w; nextVertex.f = nextVertex.dist+hManhattan(nextVertex, vertexes[t]); predecessor[nextVertex.id] = minVertex.id; if (inqueue[nextVertex.id] == true) { queue.update(nextVertex); } else { queue.add(nextVertex); inqueue[nextVertex.id] = true; } }

    作者回复: 你搞错了,f=g+h, g=dist, h=hManhattan

    2019-03-19
    4
    4
  • 隆隆
    优化a*的话 是走扩大方块好 还是设置中转点好呢?

    作者回复: 这个各有利弊,要具体看呢

    2019-02-13
    4
  • Geek_18b741
    对于dijkastra算法来说,当终点出队列的时候dist已经是最小值。所以找到的是最短路径。终于知道为什么bfs得到的是最短路径了。谢谢老师。

    作者回复: 赞

    2019-10-22
    2
  • QQ怪
    中间有障碍物怎办

    作者回复: 有障碍的就不会有连线,也就不存在路径。

    2019-03-07
    2
    1
收起评论
显示
设置
留言
59
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部