一些需要先有的概念一、A*寻路算法是启发式算法二、该算法对于代价(权重/距离)的计算为f(总代价) g(该点到原点的代价适用欧几里得距离曼哈顿距离) h(该点到终点的代价适用曼哈顿距离)三、算法节点之间有父子关系四、进入开启列表的是寻找到的可以走的区域进入关闭列表的是已经确定这个点到原点的距离是最小的五、该算法是没有死路概念的如果没有任何一条路能够进入终点不做限制的情况下可以遍历所有的可行节点算法过程在起点遍历周围八个节点(即八方)若不为障碍的情况下计算 f(总代价) 并加入开启列表记录父节点为起点。在开启列表中找到 f(总代价) 最小的节点加入关闭列表(加入后应在开启列表中移除)并且遍历该节点周围的八个节点计算 f(总代价) 并加入开启列表记录该节点为父节点。重复上面的过程直到找到终点。找到终点后根据父节点来倒推回起点确定路线。一些问题一、若终点被障碍围住了怎么办答在不加以限制的情况下该算法会遍历所有可以走的节点直到开启列表为空。该算法没有死路的概念它的 h(该点到终点的代价) 为无视障碍的距离即它在计算的时候认为所有地方都可以走但只有进入开启列表的才是实际能走的。比如起点与终点之间有一条封闭的死路但是该路段末端到终点的距离很短那么该算法会优先进入该死路不会在意走这条路有没有障碍因为计算中 h(该点到终点的代价) 会越来越小直到计算到末端再也没有新的节点进入开启列表算法才会找另外的路前往终点。若终点完全被围住没有路可以进去则会遍历所有可行节点。所以如果有需要的话可以优化比如限制最大可遍历数量或者进行预处理(比如进行一次洪水填充Flood Fill判断起点和终点是否在同一个连通区域)二、如果周围遍历的节点原先在开启列表中怎么办答先重新计算该节点的 f(总代价)若是新的 f(总代价)比原f小则记录新的 f(总代价)以及新的父节点。三、若存在多个相同代价的节点选哪个答没有区别的这个主要看排序哪个排在最前面(或最后面看列表的排序)因为如果找到的是死路那么迟早会轮到另一个相同代价的节点。如果不是死路那么找到的就是正确的路了。当然对于这个算法而言如果正确的路需要绕路那么它可能是走走一条路再走走另一条路这个是很正常的。总结比较基础的寻路算法适用于自动走格子之类的。对于障碍物较多则耗能较多会趋向有方向的广度遍历。可用但是需要做限制。个人观点仅用于记录需要代码的可以让豆包生成噢喵~