一、为什么地图网格化?
位置描述:
鼠标位置使用像素坐标描述。
地图位置使用经度纬度描述。
为了方便描述地图上元素的位置,将地图网格化。
二、什么是曼哈顿距离?
曼哈顿距离(Manhattan distance):两点在南北方向上的距离加上在东西方向上的距离,即D(I,J)=|XI-XJ|+|YI-YJ|。
计算曼哈顿距离时,忽略两点之间的障碍物。
若有两点(1,2)和(3,4),则曼哈顿距离 = |3 -1| + |4 - 2| = 4
三、A*算法涉及的名词
开启列表:存放即将进行分析的可达位置。
关闭列表:存放已经分析完毕的可达位置。
估价函数:f(n) = g(n) + h(n)
f(n) 是从初始点经由节点n到目标点的估价函数。
g(n) 是在地图中从初始节点到n节点的实际代价h(n) 是从n到目标节点最佳路径的估计代价。
h(n)是估计代价,可以使用曼哈顿距离作为估计代价。
四、A*算法步骤
1、将起始位置放入开启列表。
2、获取开启列表中F(n) 值(经由点n的估价值)最小的位置,且曼哈顿距离最小,作为当前位置。
3、判断当前位置是否为终点,若为终点,将终点放入关闭列表并执行第八步。
4、将当前位置从开启列表中移除,并放入关闭列表。
5、获取当前位置可达的位置。注意:关闭列表中的位置不可达。
6、将当前位置可达的位置放入开启列表。
7、若开启列表不为空,则从第二步继续循环。
8、若终点存在关闭列表,则返回路径,否则未找到路径。
五、A*算法优化
1、地图粒度没必要划分到像素点。像素点的划分粒度对于搜索来说代价太高。
建议划分的粒度在不影响使用的情况下取最大值。
2、每次新位置放入开启列表时,给列表排序(建议选择快速排序算法),
这样每次从开启列表取位置时,只取第一个位置即可。
这种方式适用于超大地图,分支节点多的地图。
3、可以前进到相邻的对角线上的位置(8个方向)。建议使用8方向而非4方向。
相邻对角线上位置的代价建议为1.4。
4、不同位置的损耗。在地图中,位置有两种状态,可通过和不可通过。
但有的可通过位置可能移动代价更高,比如,堵车道路上的位置。
5、对于超级大的地图寻路,可以把大地图划分为N个小区域。先使用A*算法
在N个小区域里找到路径,在路径上的每个小区域里再次使用A*算法找到
最终的路径。
6、Dijkstra(狄克斯特拉)算法:该算法与A*算法区别在于估价函数, Dijkstra 算法
没有h(n)。Dijkstra 算法每次迭代时选择的下一个顶点是标记点之外距离源点最
近的顶点。但由于dijkstra算法主要计算从源点到其他所有点的最短路径,所以
算法的效率较低。
对于多个目标位置,建议采用Dijkstra算法。比如停车场有多个出口,需要找到离
当前位置最近的出口。
-=各种=-寻路算法演示:
http://qiao.github.io/PathFinding.js/visual/
- 大小: 193.8 KB
分享到:
相关推荐
A*走路 自动寻路A*算法 易语言源码优化版 A*走路 自动寻路A*算法 易语言源码优化版 A*走路 自动寻路A*算法 易语言源码优化版
下载本程序仅可演示A*自动寻路算法实现(java),该程序是基于我写的网络版贪吃蛇基础上编写的(网络版贪吃蛇...wasd键控制太阳的方向,鼠标左击目的地,会根据A*自动寻路算法计算出一条最优路线,太阳按最优路线移动。
3dA*自动寻路算法 这个就放着,,以后用的着自己下,没别的用途
没积分了,下不了资源,只求一分,A*寻路算法 源码 c#
基于Unity5.4.4版本,随机障碍物,动态实现寻路,UnityA星寻路完整Demo
一个寻路算法的实现类源代码,采用A*算法实现,有一个类库和一个小的例子组成
之前有弄出了最短路径的寻路算法,现在看起来,觉得条理不够清晰,注释也少,所以此次特地对寻路算法进行了整理,几乎每行都有注释,结构清晰了很多,接口友好,套用起来很方便...
编译环境VS2003 ,封装好的一个A*算法 , 使用方法见程序,留出来地图接口,地图为2维数组,设置好之后,该类找到一条路径,并返回所找到的路径。
自动寻路 A*算法 压缩包中有代码和执行供朋友们学习使用.
VB 中的A星寻路算法 用了折半快速插入有序队列可以很快的添加结点数据 数组是以距离从大到小的一个有序队列 每次取数组中最后的数据,可以快速删除 例如:redim preserve A(ubound(A)-1)
六边形A*寻路算法源码(As3版本)在六边形战棋类游戏中可以使用
献给想用VB开发游戏的人,我本来想用VB做一个游戏结束和VB的相遇,然后进入另一个世界VC的世界,但是只差一点点就可以完成了,最后还是放弃了...自己的理想
Python2.x版的A*寻路算法,实现了基本的A*算法,可以显示寻路图,测试运行pathFinder.py,输入地图文件a_map.txt,起点7,0 终点7,9
A*寻路算法实现,模拟寻路算法,描述了A*寻路算法的具体实现可以在unity运作文件,可以到看到A*寻路算法的原理
FLASH AS3 A*自动寻路算法!
A*自动寻路的算法,基于unity,通过点击屏幕可以知道运行的详细步骤,通过颜色,对当前点,路障,目标点,以及路径进行了标注
A*算法、自动寻路算法C++源码
使用A*算法求解迷宫寻路问题,使用python编程,人工智能导论课后实验
visual c++游戏编程库的源程序,如A*算法 A星算法 AStar自动寻路算法