49 | 搜索：如何用A*搜索算法实现游戏中的寻路功能？
该思维导图由 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-197143- 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-19894 
1有一点不明白，希望老师能解答一下。实际上，我们可以换一种抽象的思路，把整个地图分割成一个一个的小方块。在某一个方块上的人物，只能往上下左右四个方向的方块上移动。请问障碍物是怎么绕过的呢？作者回复: 也可以，你这个抽象成二维数组喽，那就是邻接矩阵的表示方法，可以站人的用1表示，不能站人的方块用0表示，bfs就能得到最优解。
2019-08-2015
『LHCY』真实游戏中也是用的小方块来做的吗？比如要往(1，1)方向走，先把模型角度调整，然后移动是一个个小方格走的，因为方格太小使肉眼分辨不出？作者回复: 是的，你说的没错！
2019-01-18314
yongxiang王争老师，我把代码输入运行，并把过程打印出来，发现代码运行的过程跟您说的A*算法的三点区别中的第三点不一样，不会在遍历到目标顶点时退出while循环。您看是不是27行的break只是退出了for循环，无法退出while循环，是不是需要增加以下的修改： if (nextVertex.id == t) { queue.clear(); break; }作者回复: 嗯嗯 我更新下，是个bug：）
2019-01-199
皇家救星我记得以前看过的a*算法介绍还有close和open表，这里好像没提到？作者回复: 那就是俩人造的概念 并没有太大意义。
2019-01-185
且听疯吟仔细阅读了下代码，感觉代码中存在错误点，每次应该是取最小的 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-1944
隆隆优化a*的话 是走扩大方块好 还是设置中转点好呢？作者回复: 这个各有利弊，要具体看呢
2019-02-134- Geek_18b741对于dijkastra算法来说，当终点出队列的时候dist已经是最小值。所以找到的是最短路径。终于知道为什么bfs得到的是最短路径了。谢谢老师。
作者回复: 赞
2019-10-222 
QQ怪中间有障碍物怎办作者回复: 有障碍的就不会有连线，也就不存在路径。
2019-03-0721
