A星寻路算法_第二章
逻辑类中,有一个静态接口,是用来计算,两个方块之间距离的,通过Mathf.Abs计算距离的绝对值,再通过Mathf.Max和Mathf.Min拿到最大/小数值,换算得到,两者之间的距离
重写Tostring字符显示函数,还有对应上IComparable接口的,CompareTo比较函数,是以priority进行比较排序即可
抽象类BasePathFinder,是基础的寻路逻辑,其中包含两个方块逻辑BlockLogic,分别是开始和结束逻辑点; 再弄几个队列容器,分别存储,不同阶段的方块逻辑集合;
GetPathBlockLst函数接口,是先拿到结束的方块逻辑点m_endBlock,然后一个while死循环,把节点插到队列0索引; 再拿到m_endBlock的前一个检测方块preBlock,然后设为当前block方块,再进入下一个while死循环,等于是倒着,拿到整条链路; 最后返回,这个队列容器lst即可;
检测邻近方块,这个DetectNeighborBlock抽象函数,有四次重写,分别对应四种寻路逻辑,A星寻路是其中一种
计算路径逻辑,是一个Task任务设置初始方块逻辑点,再清空各个队列容器; 死循环while判断,如果等待检测的队列m_detectQue包含结束节点,就通过GetPathBlockLst函数,倒着拿到整个链路,然后基于break跳出; 上述这个,是寻路找到结束点,跳出的逻辑,在跳出之前,是m_detectQue出队元素,调用DetectNeighborBlock函数,使用寻路算法,完成不同的寻路逻辑;
方块地图BlockMap,统一管理,方块逻辑BlockLogic,其中的xyCount,是纵横的最大数目,m_blockArr作为一个二维数组,也是用来存储,创建出来的,所有方块逻辑; 初始化函数InitMap赋值最大xy数目,实例化二维数组,然后遍历,对其中的单个方块逻辑,调用InitBlockLogic完成初始化;
还可以统一消选所有节点
俩函数接口,分别是将逻辑节点的Walkable存到,对应的布尔二维数组stateArr,还有从stateArr这个二维数组,遍历,重新设置对应的布尔值,到对应索引的逻辑节点Walkable
readonly只读的二维数组allDirs,通过几个Vector2元素,完成各个方向的定义
边界内判断,确认xy没有越界
调用上述的边界判断接口,还有各个方向,完成节点周边,对应逻辑节点集合的添加整理
UpdateMapData函数接口,遍历,统一更新节点的周边邻近逻辑节点数据集合
因为寻路排序,是需要引入,优先级的概念,也弄一个PEQue排序类,继承自IComparable接口,具体的逻辑解析,参考基于堆实现优先级队列即可
寻路相关逻辑,一共有四个,分别是这几个实现,都是继承自,基础寻路逻辑BasePathFinder,他们的逻辑大致相同,区别在于priority优先级的判断不同
首先,是广度优先搜索算法(breadth First Search, BFS),对应的是BreadFirstPathFinder脚本; 判断已完成队列,等待检测队列中,都没包含这个neighborBlock,就会进入寻路的逻辑判断; 调用GetLogicBlockDistanc接口,拿到俩逻辑节点之间的neighborDistance距离; sumDistance等于,检测总节点原本的距离,加上新的这个节点距离neighborDistance; 它的优先级priority是,已完成队列m_finishLst的总数;
然后,是Dijkstras迪杰斯特拉最短路径算法,对应的是DijkstrasPathFinder逻辑,进入逻辑的前提布尔判断,还有总距离的计算逻辑,跟之前的,都一样; 在总距离是否无穷大的IsPositiveInfinity判断后,确保节点的sumDistance总距离是遍历周边,最小的; 而且priority优先级是,sumDistance总距离;
然后,是贪心算法,对应的是GreedyPathFinder逻辑,其他逻辑大致一致,它的优先级priority判断是,节点和最终结束节点m_endBlock,之间的距离
然后,这是A星算法,对应的是AStarPathFinder逻辑,其他逻辑,大致一致,它有使用Dijkstras迪杰斯特拉的最短路径逻辑,确保是拿到周边,最短的路径sumDistance; 同时,它又拿到节点,和最终结束节点,之间的距离,这是贪心算法的相关逻辑; A星算法的优先级,是最短路径,加上节点到最终节点距离;