【算法•日更•第三十七期】A*寻路算法
2024-10-09 12:04:06
▎写在前面
这是一种搜索算法,小编以前总是念成A乘寻路算法,没想到一直念错。
请大家都念成A星寻路算法,不要像小编一样丢人了。
▎A*寻路算法
☞『引入』
相信大家都或多或少的玩过一些游戏吧,那么游戏中的这些AI角色是如何实现自动追踪玩家的呢?
难道是用普通的搜索吗?这种东西似乎有点太慢了,还没有过去就已经被玩家给打趴下了。
那么我们应该找到一种快速的办法,于是A*算法便有了用武之地。
☞『定义』
☞『特点』
没有别的,就是快(也简单)。
☞『算法核心』
比如说我们的AI角色站在绿色方块上,需要移动到红色方块,每次只能上下左右方向移动一格:
我们需要维护两个集合:分别是openlist和closelist,openlist表示还没有到达的可能会去的点的集合,closelist表示已经到达的点的集合。
同时还有一个公式F=G+H。G是已经走过的路的代价,H是还需要的代价(无视障碍)。那么F就是对这个点的评估值,每次选最小的F格子走。
那么举个栗子吧,下一步是这样走的:
上面的是F,下面的两个分别是G和H的值,我们只需要找小的F值就可以了。
当然是这么走了:
然后重复操作即可。
▎这个算法为什么平时不用?
正确性无法保证:因为这样不一定是最优的,对于竞赛来说是不可取的,而AI不一定需要最优。
最新文章
- 华为5700s配置链路聚合
- STM32堆栈溢出
- Sublime Text 3初阶
- JS 下拉菜单
- Unity ScriptableObject的使用
- sentos nginx安装
- 转-- WebView使用实例(html5、文件下载和远程URL)
- VR就是下一个浪潮_2016 (GMGC) 全球移动游戏大会观后感
- Struts2的国际化
- HDUOJ Clear All of Them I 状压DP
- 解决 asp.net 伪静态 IIS设置后 直正HTML无法显示的问题
- Hibernate table schema 的设置与应用
- 全球多个 TOP 网站藏挖矿代码,5 亿 PC 沦为矿工
- Alpha冲刺置顶随笔
- yii 邮箱封装
- POJ - 1830:开关问题 (开关问题-高斯消元-自由元)
- C# 6.0:新的Dictionary Initializer
- 剑指offer(17)层次遍历树
- 用flask实现的分页
- pytest文档14-函数传参和firture传参数request
热门文章
- rpm -ivh vsftpd-3.0.2-22.el7.x86_64.rpm出现error: open of vsftpd-3.0.2-22.el7.x86_64.rpm failed: No such file or directory的解决方法
- 两种 HTTP 方法:GET 和 POST
- PHP设计模式之----观察者模式
- python学习笔记1 -- 面向对象编程类和实例
- PHP cos() 函数
- Ploya定理学习笔记
- java中的枚举类enum
- day7.关于字符串的相关操作
- 一文打尽Java继承的相关问题
- 41-native关键字的理解