最好懂的自动寻路-前端

先看效果

黑块是障碍物，可以理解成游戏里的墙
白块是可走的路
点哪里走哪里，类似于游戏里的移动
在线演示

前言

本节采用BFS算法，没有涉及到一些更深层次的优化。
代码用的vue3+ts,单组件，复制粘贴即可运行，核心的代码就一个函数，可以用GPT转成其他语言并运行
鄙人没有从事这方面工作，纯属兴趣爱好，只能带大家看看寻路到底是怎么个回事，以下均为个人理解。
先说业务逻辑，再贴实现代码

寻路三步走：画图->寻路->走路。

• 地图的根本作用是让位置更直观
  
• 核心难点是寻路
  
• 走路是最终目的
  

我们就以这样的顺序开始吧
画图

怎么去实现地图，图到底长什么样呢？如果从没接触过，那看起来有点抽象，先看实现地图的代码
现象：观察右边的图片，注意0,1和黑白方块

总结：【0=白块】，【1=黑块】

1. IF(X=4&Y=0){
2.     渲染黑块
3. }ELSE{
4.     渲染白块
5. }

复制代码

实现

我这里的布局很简陋

1.   
2.    
3.   
6. const stage = [
7.   [0, 0, 0, 1, 0, 0, 0, 0],
8.   [0, 0, 1, 0, 0, 0, 1, 0],
9.   [0, 0, 0, 0, 1, 0, 0, 0],
10.   [1, 0, 1, 0, 0, 1, 1, 0],
11.   [0, 0, 0, 0, 1, 0, 0, 0],
12.   [0, 1, 1, 0, 0, 0, 1, 0],
13.   [0, 0, 0, 1, 0, 0, 0, 0],
14.   [0, 0, 0, 0, 1, 0, 1, 0],
15. ];
17. .square {
18.   border: 1px solid #000;
19.   @apply w-[100px] h-[100px];
20. }

复制代码

怎么让路和墙丰富起来

有些同学可能有疑问了，我要做墙做怪物，墙有很多种，怪物也有很多种，仅有0和1怎么表示呢？
把[0,1]换成对象就好了，以前端为例，可以直接用JSON,把上面的代码修改一下

接下来只要根据image渲染不同的图片，type和style可以用来做逻辑，比如经过style=地狱门的时候就扣血，经过砂石路移动速度变慢，判断是否经过，就是看英雄的坐标和障碍物是否重叠。
地图编辑器

种类是丰富了，但是我想做一个英雄联盟这样的地图，那不得写到宇宙二次爆炸？那该怎么做呢？
玩过魔兽争霸的朋友可能知道，有一个东西叫地图编辑器，从编辑器里诞生Dota，Dota衍生LOL，Lol变异成王者农药，农药里的三国的关羽能骑马砍战国末期的嬴政....
很久以前做了一个简单的地图编辑器，墙能够粉刷，其实还做了怪物来着，后面觉得实现方式有问题，给删了。
前半段演示画墙，后面演示走路
核心就是用可视化创建地图数据

寻路

来到核心内容了，代码一大堆，网上搜的到，AI能生成，但都没那么容易理解。
要想写出代码，先要了解业务逻辑
寻路前的数据

寻路，至少要知道自己在哪儿，要去哪儿。
App导航需要先获取你的位置，再输入目的地，最后确认路线，这里也是如此，寻路前需要最基本的数据

• 起点和终点【蓝色，粉色】
  
• 将起点加入到已走过的路
  
• 起点和终点不能相同【没写】
  
• 还有不能出界，导航从广州到上海，想必你也不想从西藏方向出发，再从美国那边飞回来吧
  

  

所对应的代码如下，有了最基本的数据后才能寻路

1. /**
2. * @description 寻找路径
3. * @param map 二维数组
4. * @param start 起始点
5. * @param end 终点
6. * @returns 路径数组
7. */
8. export const findPath = (stage: number[][], start: number[], end: number[]) => {
9.   //终点坐标
10.     const [endX, endY] = end;
11.   //        将起点加入队列，这是整个寻路的核心
12.   //        也是结束的条件之一，如果队列空了，表示没有找不到路了
13.     const queue = [[start]];
14.   //如果终点为障碍物，则不走了
15.     if (grid[endY][endX] === 1) {
16.       return [];
17.     }
18.   //已经走过的路，用SET去重
19.   const visited = new Set<string>();
20.   //将起点设为已经走过的路
21.   visited.add(`${start[0]},${start[1]}`);
22.   //开始寻路
23. }

复制代码

开始寻路

• 寻路
  

• 探索的过程只能一格一格的找，一次找很多步，容易错过终点
  
• 如果没有找到终点，并且还有没走过的路，就要一直找，【核心驱动】
  

• 搜索：
  

• 每经过一个点，都要找一下上下左右有没有终点的坐标，如此循环
  

图示寻路过程：

• 蓝块是我们的本体，粉色是终点
  
• 旁边的色块是搜索的结果，
  

• 红色代表出界或已走过，总之不能走的地方，且不会加入到队列
  
• 深绿色代表优先走，会加入到队列，且下一次循环就要走到这个点【很重要】
  
• 浅绿色代表能走，且经过检测不是终点，但不会加入队列
  
• 优先级取决于方向的顺序，可以根据情况调整，比如知道目标点在最下面，可以把去下面的方向调整到最前面来
  

代码

1. // 方向，下面有解释
2. const DIRECTIONS = [
3.   [0, 1],
4.   [1, 0],
5.   [-1, 0],
6.   [0, -1],
7. ];
8. /**
9. * @description 寻找路径
10. * @param grid 二维数组
11. * @param start 起始点
12. * @param end 终点
13. * @returns 路径数组
14. */
15. export const findPath = (grid: number[][], start: number[], end: number[]) => {
16.   const [endX, endY] = end;
17.   /* 三维数组 */
18.   const queue = [[start]];
20.   if (grid[endY][endX] === 1) {
21.     return [];
22.   }
23.   const visited = new Set<string>();
24.   visited.add(`${start[0]},${start[1]}`);
26.   while (queue.length > 0) {
27.     /* 取出最后一个加入的坐标 */
28.     const lastRoute = queue.shift();
29.     if (lastRoute) {
30.       /* 取出新的坐标 */
31.       const route = lastRoute[lastRoute.length - 1];
32.       /* 新的坐标的x,y，用于判断是否为终点 */
33.       const [x, y] = route;
34.       if (x === endX && y === endY) {
35.         /* 如果是终点则返回 */
36.         return lastRoute;
37.       }
38.       /* 继续根据方向寻找，下面有解释 */
39.       for (const [dx, dy] of DIRECTIONS) {
40.         /* 周围的坐标，上下左右 */
41.         const newX = dx + x;
42.         const newY = dy + y;
44.         const newRoute = [...lastRoute, [newX, newY]];
45.         /* 如果找到坐标，就别找了 */
46.         if (newX === endX && newY === endY) {
47.           return newRoute;
48.         }
49.         /* 检测边界，下面有解释 */
50.         if (collisionDetection(grid, x, y, !visited.has(`${newX},${newY}`))) {
51.           visited.add(`${x},${y}`);
52.           //将新的坐标和旧的队列一并加入到路线中
53.           queue.push(newRoute);
54.         }
55.       }
56.     }
57.   }
58.   return [];
59. };

复制代码

难点解析

边界检测

普通地图，一般都是有边界的，且限定不能出界，所以需要准备相关条件进行判断，障碍物也是边界
所以地图有几个地方不能去，

• 上下左右的边界不能走
  
• 已经走过的路，不能走，否则就一直绕圈，完蛋啦。
  
• 障碍物也不能走，穿墙了就到都处是路
  

1. /**
2. *  @description 边界检测
3. * @param stage 二维数组
4. * @param x 当前的横坐标
5. * @param y 当前的纵坐标
6. * @param alreadyPassed 是否已经过
7. */
8. export const collisionDetection = (
9.   stage: number[][],
10.   x: number,
11.   y: number,
12.   alreadyPassed: boolean
13. ) => {
14.   const MAX_X = stage[0].length - 1; /* 右边 */
15.   const MIN_X = 0 /* 左边 */,
16.     MIN_Y = 0; /* 上边 */
17.   const MAX_Y = stage.length - 1; /* 下边 */
19.   return (
20.     x <= MAX_X &&
21.     x >= MIN_X &&
22.     y >= MIN_Y &&
23.     y <= MAX_Y &&
24.     stage[y][x] !== 1 &&//判断不能是障碍物
25.     alreadyPassed
26.   );
27. };

复制代码

看效果

可以看到，都是点哪里去哪里，全程闪现

核心原因是for计算没有延迟，中间的确经过了我们之前得到的路径，但由于太快，我们看不到
没有延迟，制造延迟，用定时器模拟for循环
创造一个变量i=0，相当于for的累加

代码

1. const DIRECTIONS = [
2.   [0, -1],        //上
3.   [1, 0],                //下
4.   [-1, 0],        //左
5.   [0, 1],                //右
6. ];
7. //方向结合当前的坐标，就能检测周围了
8. let [x,y]=current;//假设当前坐标为[0,0]
9. for (const [dx, dy] of DIRECTIONS) {
10.       /* 周围的坐标，上下左右 */
11.       const newX = dx + x;
12.       const newY = dy + y;
13.    //循环次数                                                方向                                                                        新的坐标                                备注
14.    //   1                                DIRECTIONS[0]=[0, -1]                                        [0, -1]                                出界了                         
15.    //   2                                DIRECTIONS[1]=[1, 0]                                        [1, 0]                                往右走一格               
16. }

复制代码

完整代码

用vue实现，复制粘贴即可运行

1. [[0,1],[0,2],[0,3]]

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！