最好懂的自动寻路，图文解释

365bet足球网址 🕒 2025-09-08 04:34:29 👤 admin 👁️ 7855 👍 311

const stage = [

[0, 0, 0, 1, 0, 0, 0, 0],

[0, 0, 1, 0, 0, 0, 1, 0],

[0, 0, 0, 0, 1, 0, 0, 0],

[1, 0, 1, 0, 0, 1, 1, 0],

[0, 0, 0, 0, 1, 0, 0, 0],

[0, 1, 1, 0, 0, 0, 1, 0],

[0, 0, 0, 1, 0, 0, 0, 0],

[0, 0, 0, 0, 1, 0, 1, 0],

];

.square {

border: 1px solid #000;

@apply w-[100px] h-[100px];

}

怎么让路和墙丰富起来

有些同学可能有疑问了，我要做墙做怪物，墙有很多种，怪物也有很多种，仅有0和1怎么表示呢？

把[0,1]换成对象就好了，以前端为例，可以直接用JSON,把上面的代码修改一下

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

地图编辑器

种类是丰富了，但是我想做一个英雄联盟这样的地图，那不得写到宇宙二次爆炸？那该怎么做呢？

玩过魔兽争霸的朋友可能知道，有一个东西叫地图编辑器，从编辑器里诞生Dota，Dota衍生LOL，Lol变异成王者农药，农药里的三国的关羽能骑马砍战国末期的嬴政....

很久以前做了一个简单的地图编辑器，墙能够粉刷，其实还做了怪物来着，后面觉得实现方式有问题，给删了。

前半段演示画墙，后面演示走路

核心就是用可视化创建地图数据

寻路

来到核心内容了，代码一大堆，网上搜的到，AI能生成，但都没那么容易理解。

要想写出代码，先要了解业务逻辑

寻路前的数据

寻路，至少要知道自己在哪儿，要去哪儿。

App导航需要先获取你的位置，再输入目的地，最后确认路线，这里也是如此，寻路前需要最基本的数据

起点和终点【蓝色，粉色】

将起点加入到已走过的路

起点和终点不能相同【没写】

还有不能出界，导航从广州到上海，想必你也不想从西藏方向出发，再从美国那边飞回来吧

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

typescript

复制代码

/**

* @description 寻找路径

* @param map 二维数组

* @param start 起始点

* @param end 终点

* @returns 路径数组

*/

export const findPath = (stage: number[][], start: number[], end: number[]) => {

//终点坐标

const [endX, endY] = end;

// 将起点加入队列，这是整个寻路的核心

// 也是结束的条件之一，如果队列空了，表示没有找不到路了

const queue = [[start]];

//如果终点为障碍物，则不走了

if (grid[endY][endX] === 1) {

return [];

}

//已经走过的路，用SET去重

const visited = new Set();

//将起点设为已经走过的路

visited.add(`${start[0]},${start[1]}`);

//开始寻路

}

开始寻路

寻路

探索的过程只能一格一格的找，一次找很多步，容易错过终点

如果没有找到终点，并且还有没走过的路，就要一直找，【核心驱动】

搜索：

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

图示寻路过程：

蓝块是我们的本体，粉色是终点

旁边的色块是搜索的结果，

红色代表出界或已走过，总之不能走的地方，且不会加入到队列

深绿色代表优先走，会加入到队列，且下一次循环就要走到这个点【很重要】

浅绿色代表能走，且经过检测不是终点，但不会加入队列

优先级取决于方向的顺序，可以根据情况调整，比如知道目标点在最下面，可以把去下面的方向调整到最前面来

代码

ini

复制代码

// 方向，下面有解释

const DIRECTIONS = [

[0, 1],

[1, 0],

[-1, 0],

[0, -1],

];

/**

* @description 寻找路径

* @param grid 二维数组

* @param start 起始点

* @param end 终点

* @returns 路径数组

*/

export const findPath = (grid: number[][], start: number[], end: number[]) => {

const [endX, endY] = end;

/* 三维数组 */

const queue = [[start]];

if (grid[endY][endX] === 1) {

return [];

}

const visited = new Set();

visited.add(`${start[0]},${start[1]}`);

while (queue.length > 0) {

/* 取出最后一个加入的坐标 */

const lastRoute = queue.shift();

if (lastRoute) {

/* 取出新的坐标 */

const route = lastRoute[lastRoute.length - 1];

/* 新的坐标的x,y，用于判断是否为终点 */

const [x, y] = route;

if (x === endX && y === endY) {

/* 如果是终点则返回 */

return lastRoute;

}

/* 继续根据方向寻找，下面有解释 */

for (const [dx, dy] of DIRECTIONS) {

/* 周围的坐标，上下左右 */

const newX = dx + x;

const newY = dy + y;

const newRoute = [...lastRoute, [newX, newY]];

/* 如果找到坐标，就别找了 */

if (newX === endX && newY === endY) {

return newRoute;

}

/* 检测边界，下面有解释 */

if (collisionDetection(grid, x, y, !visited.has(`${newX},${newY}`))) {

visited.add(`${x},${y}`);

//将新的坐标和旧的队列一并加入到路线中

queue.push(newRoute);

}

}

}

}

return [];

};

难点解析

边界检测

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

所以地图有几个地方不能去，

上下左右的边界不能走

已经走过的路，不能走，否则就一直绕圈，完蛋啦。

障碍物也不能走，穿墙了就到都处是路

typescript

复制代码

/**

* @description 边界检测

* @param stage 二维数组

* @param x 当前的横坐标

* @param y 当前的纵坐标

* @param alreadyPassed 是否已经过

*/

export const collisionDetection = (

stage: number[][],

x: number,

y: number,

alreadyPassed: boolean

) => {

const MAX_X = stage[0].length - 1; /* 右边 */

const MIN_X = 0 /* 左边 */,

MIN_Y = 0; /* 上边 */

const MAX_Y = stage.length - 1; /* 下边 */

return (

x <= MAX_X &&

x >= MIN_X &&

y >= MIN_Y &&

y <= MAX_Y &&

stage[y][x] !== 1 &&//判断不能是障碍物

alreadyPassed

);

};

方向

以我们正常去移动用的方式去看，只要修改横轴纵轴坐标即可，如下

往右移动x+=1

往左移动x-=1

往上移动y-=1

往下移动y+=1

但这里不相同，需要没走一步，就要四周观察，查看四次，所以被设计成了这样，当然坐标数组可以用对象代替，方便调整顺序

csharp

复制代码

const DIRECTIONS = [

[0, -1], //上

[1, 0], //下

[-1, 0], //左

[0, 1], //右

];

//方向结合当前的坐标，就能检测周围了

let [x,y]=current;//假设当前坐标为[0,0]

for (const [dx, dy] of DIRECTIONS) {

/* 周围的坐标，上下左右 */

const newX = dx + x;

const newY = dy + y;

//循环次数 方向 新的坐标 备注

// 1 DIRECTIONS[0]=[0, -1] [0, -1] 出界了

// 2 DIRECTIONS[1]=[1, 0] [1, 0] 往右走一格

}

队列

这可能是最难理解的一部分了,然而我也很难用一两张图去表达，这个过程是动态的，除非做成动画，可目前还没有加这个技能点,那只能大致说说了

const queue = [[start]];

队列详解

队列初始化数据是queue=[[[0,0]]],是一个三维数组，

最里面一层是坐标

中间一层是真正的路线

最外层是终止条件，始终只有一个数据，当四处都是障碍物，没有路线的时候[queue.length=0]，终止循环

发现有可用的坐标的话，把坐标加入到路线中，再把路线加入到queue中

简单流程

(flag)发现可用的坐标，更新到路线和队列中，取出最新的坐标，继续寻找,回到前面的(flag)继续发现，直到找到目标

走路

执行完上面的findPath，我们就能找到路了,路长这个样子

lua

复制代码

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

接下来该走路了。

有的同学可能肃然起敬，这个我熟，for循环，把路线中的每个点都赋值给英雄就好了。

好吧，你又中招了，for循环让整个寻路失去了意义

ini

复制代码

//错误演示

const routes = findPath(stage, start.value, end.value);

// routes=[[0,1],[0,2],[0,3]] 示例结构，非真实代码

routes.forEach((v) => {

const [x, y] = v;

hero.value.x = x;

hero.value.y = y;

});

看效果

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

核心原因是for计算没有延迟，中间的确经过了我们之前得到的路径，但由于太快，我们看不到

没有延迟，制造延迟，用定时器模拟for循环

创造一个变量i=0，相当于for的累加

代码

ini

复制代码

// 我们需要移动的目标英雄

const hero = ref({

x: 0,

y: 0,

});

const move = () => {

let i = 0;

//我们通过上面的函数最终找到的路线

const routes = findPath(stage, start.value, end.value);

//如果没找到，就不执行了

if (!routes || routes.length === 0) {

return;

}

//多次点击，先清空上一次执行的定时器

clearInterval(flag);

flag = setInterval(() => {

if (routes.length > 0 && i++ < routes.length - 1) {

const [x, y] = routes[i];

hero.value.x = x;

hero.value.y = y;

} else {

start.value = [...end.value];

i = 0;

clearInterval(flag);

}

}, 50);

};

完整代码

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

ini

复制代码