济南网络营销网站建设,网上免费做网站,公司网页设计怎么弄,Wordpress怎么配合HTML关于自动寻路#xff0c;在游戏中还是经常会遇到的。如角色如何代价最小(距离少#xff0c;时间快#xff0c;方式支持)移动到某个位置。本篇记录下A*寻路的流程与优化。
为了做一个可以方便展示在web的demo#xff0c;更好拆解寻路的步骤#xff0c;所以本篇用了cocos c…关于自动寻路在游戏中还是经常会遇到的。如角色如何代价最小(距离少时间快方式支持)移动到某个位置。本篇记录下A*寻路的流程与优化。
为了做一个可以方便展示在web的demo更好拆解寻路的步骤所以本篇用了cocos creater ts实现。
A星算法是dijkstra的升级版(算法-迪杰斯特拉)也是属于广度搜索遍历不同于dijkstraA星不需要遍历图中所有的节点。而是尽可能的去靠近终点。可以做个想象地图比作一个挂起来的迷宫起点在上方终点在下方从上方注入水水会随着重力尽可能向下方(终点)流去。
所以AStar 是可以找到一个最快的路径即当前的最优解但这个最快不是唯一的也可能不是最优的。有点像贪心。其时间复杂度为O(logN)
A星算法用到的几个变量
设定起点为A终点为B。开放列表(OpenList)记录所有待检测的节点。关闭列表(CloseList)记录所有已经检测过的节点。G值当前节点到下一个节点N(八点 之一)的代价。H值下一个节点N到终点B的代价。忽略有墙F值F G H
代价值的计算
垂直或者左右相邻记作10斜对角相邻记作1010≈14
约定
八点指“上、下、左、右、左上、左下、右上、右下”共八个点。有效八点指八点中剔除 不可达的点(墙)已经加入CloseList / OpenList的点 三围指 上面定义的三个值“G, H, F”。
算法流程
将起点作为当前点放入OpenList。遍历所有OpenList找到F值最小的点(MinFNode)如果F相同则先择H值最小的点。把MinFNode从OpenList移除并加入CloseList。 没有有效八点回到步骤2。拥有有效八点,遍历MinFNode的有效八点根据以下情况计算三围。 相邻点不在OpenList中。计算三围加入OpenList。相邻点已在OpenList中, 跳过。 如果当前点是终点则结束寻路否则回到步骤2。直到达到终点回溯找到起点。
可视化Demo
用cocos creater 做了一个demo详细展示出寻路的步骤。 如下绿色节点是在OpenList中找到的最小节点只需依次点击绿色方块直到达到终点。最后绘制出寻路路径。
CSDN显示不出来自行打开查看 https://game.tonychenn.cn/apps/AStarSearchPath/index.html
或者算法-A星寻路查看完整文章感受最佳查看效果。
