本文主要是介绍一种非常简单有效的基于格子的寻路算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这是之前手游项目中琢磨出来的一个简单易行, 同时感觉比较高效的一个寻路算法. 当然有一个前提, 是基于格子的寻路, 你的格子可以是正方形, 六边形等. 总之, 从一个格子移动到旁边任何一个格子的代价是相等的, 也就是步数都是一, 这个算法可能也适应于其它场景, 当然我对寻路算法也没什么研究, 仅仅是解决了我所遇到的问题.
这是一个最短路径寻路算法.
地图如下, 6 * 6, 当时项目中实际的地图尺寸为5 * 14, 没有关系. 原理是一样的.
假设我们要从1.2(x = 1, y = 2)移动到5.4, 图中的红色部分.
如果地图上没有任何障碍, 那么其中一条(有多条)最短路径可能是 1.2-->2.2-->3.3-->4.4-->5.4, 一共是4步. 算法的实现步聚如下:
1. 开放列表(存放等待扫描其周围的格子) .
将1.2加入到开放列表. 扫描它的周围, 理论上, 如果你是四边形的格子, 那么任何一个格子的周围都有8个格子(不考虑边界), 扫描完后, 记下这8个格子到1.2这个坐标的距离, 都是一步, 所以下面这个图中标记的全是1, 这是第一轮扫描.
2. 将1.2从开放列表中移除(它已经扫描过了), 并将刚才扫描的8个格子加入到开放列表.
3. 扫描这8个格子的周围, 将它们周围未扫描过(已扫描过的不要参与)的格子标记距离为2, 这是第二轮扫描, 结果如下.
4. 依次类推, 扫描完剩余的格子,
这篇关于一种非常简单有效的基于格子的寻路算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
