实现两种寻路算法:Dijkstra算法
和 A*自动寻路算法
。
项目预览:https://navigate-pixi.vercel.app
主要技术栈:
- pixi.js
- react
- vite
Dijkstra 算法是最经典的图搜索
算法之一,属于广度优先算法
。也叫迪杰斯特拉算法。
将每一步四周八个方向(上、下、左、右、左上、右上、左下、右下)的最小权重值
计算出来,一次类推将可行走区域的所有格子的权重计算出来,再找到到达终点的最短路径
。
时间复杂度为O(n^2)
,空间复杂度为O(n^3)
。
A算法是每走一步计算周围八个方向的格子的权重,选择选择权重小的格子进行下一步,知道终点。
A的权重计算是 f(n) = g(n) + h(n)
,取f(n)最小值
:
g(n)
指的是从起始格子到格子n的实际代价
h(n)
指的是从格子n到终点格子的估计代价
,有三种计算方式:对角线距离
、曼哈顿距离
、斜线距离
。
当 f(n)相等,取最小的 g。
A*算法的时间平均复杂度为O(NLogN)
,最差的情况是从起点出发把所有的格子都走了一遍,最后才找到目的地。
A*算法不是百分百能找到最短路径,是近似最短路径。正如上面原理介绍的一样,它是一步走完选择四周权重值最小的进行下一步,并不是最短路径。