前言:
当前小伙伴们对“算法寻路问题有哪些类型”大致比较看重,姐妹们都需要学习一些“算法寻路问题有哪些类型”的相关资讯。那么小编也在网上收集了一些有关“算法寻路问题有哪些类型””的相关文章,希望咱们能喜欢,兄弟们快快来学习一下吧!点击上方"java全栈技术"关注,每天学习一个java知识点
比如像这样子:
第一步:把起点放入OpenList
第二步:找出OpenList中F值最小的方格,即唯一的方格Node(1,2)作为当前方格,并把当前格移出OpenList,放入CloseList。代表这个格子已到达并检查过了。
第三步:找出当前格上下左右所有可到达的格子,看它们是否在OpenList当中。如果不在,加入OpenList,计算出相应的G、H、F值,并把当前格子作为它们的“父亲节点”。
图中,每个格子的左下方数字是G,右下方是H,左上方是F。
Round2 ~ 第一步:找出OpenList中F值最小的方格,即方格Node(2,2)作为当前方格,并把当前格移出OpenList,放入CloseList。代表这个格子已到达并检查过了。
Round2 ~ 第二步:找出当前格上下左右所有可到达的格子,看它们是否在OpenList当中。如果不在,加入OpenList,计算出相应的G、H、F值,并把当前格子作为它们的“父亲节点”。
为什么这一次OpenList只增加了两个新格子呢?因为Node(3,2)是墙壁,自然不用考虑,而Node(1,2)在CloseList当中,说明已经检查过了,也不用考虑。
Round3 ~ 第一步:找出OpenList中F值最小的方格。由于这时候多个方格的F值相等,任意选择一个即可,比如Node(2,3)作为当前方格,并把当前格移出OpenList,放入CloseList。代表这个格子已到达并检查过了。
Round3 ~ 第二步:找出当前格上下左右所有可到达的格子,看它们是否在OpenList当中。如果不在,加入OpenList,计算出相应的G、H、F值,并把当前格子作为它们的“父亲节点”。
剩下的就是以前面的方式继续迭代,直到OpenList中出现终点方格为止。这里就仅用图片简单描述了,方格中数字表示F值:
说明:
这里对于A*寻路的描述做了很大的简化。实际场景中可能会遇到斜向移动、特殊地形等等因素,有些时候需要对OpenList中的方格进行重新标记。
文章转载程序员小灰
标签: #算法寻路问题有哪些类型