最好懂的自动寻路-前端
先看效果黑块是障碍物，可以理解成游戏里的墙
白块是可走的路
点哪里走哪里，类似于游戏里的移动
在线演示
前言
本节采用BFS算法，没有涉及到一些更深层次的优化。
代码用的vue3+ts,单组件，复制粘贴即可运行，核心的代码就一个函数，可以用GPT转成其他语言并运行
鄙人没有从事这方面工作，纯属兴趣爱好，只能带大家看看寻路到底是怎么个回事，以下均为个人理解。
先说业务逻辑，再贴实现代码
寻路三步走：画图->寻路->走路。
[*]地图的根本作用是让位置更直观
[*]核心难点是寻路
[*]走路是最终目的
我们就以这样的顺序开始吧
画图
怎么去实现地图，图到底长什么样呢？如果从没接触过，那看起来有点抽象，先看实现地图的代码
现象：观察右边的图片，注意0,1和黑白方块
总结：【0=白块】，【1=黑块】
IF(X=4&Y=0){
渲染黑块
}ELSE{
渲染白块
}实现
我这里的布局很简陋
const stage = [
,
,
,
,
,
,
,
,
];
.square {
border: 1px solid #000;
@apply w- h-;
}怎么让路和墙丰富起来
有些同学可能有疑问了，我要做墙做怪物，墙有很多种，怪物也有很多种，仅有0和1怎么表示呢？
把换成对象就好了，以前端为例，可以直接用JSON,把上面的代码修改一下
接下来只要根据image渲染不同的图片，type和style可以用来做逻辑，比如经过style=地狱门的时候就扣血，经过砂石路移动速度变慢，判断是否经过，就是看英雄的坐标和障碍物是否重叠。
地图编辑器
种类是丰富了，但是我想做一个英雄联盟这样的地图，那不得写到宇宙二次爆炸？那该怎么做呢？
玩过魔兽争霸的朋友可能知道，有一个东西叫地图编辑器，从编辑器里诞生Dota，Dota衍生LOL，Lol变异成王者农药，农药里的三国的关羽能骑马砍战国末期的嬴政....
很久以前做了一个简单的地图编辑器，墙能够粉刷，其实还做了怪物来着，后面觉得实现方式有问题，给删了。
前半段演示画墙，后面演示走路
核心就是用可视化创建地图数据
寻路
来到核心内容了，代码一大堆，网上搜的到，AI能生成，但都没那么容易理解。
要想写出代码，先要了解业务逻辑
寻路前的数据
寻路，至少要知道自己在哪儿，要去哪儿。
App导航需要先获取你的位置，再输入目的地，最后确认路线，这里也是如此，寻路前需要最基本的数据
[*]起点和终点【蓝色，粉色】
[*]将起点加入到已走过的路
[*]起点和终点不能相同【没写】
[*]还有不能出界，导航从广州到上海，想必你也不想从西藏方向出发，再从美国那边飞回来吧
所对应的代码如下，有了最基本的数据后才能寻路
/**
* @description 寻找路径
* @param map 二维数组
* @param start 起始点
* @param end 终点
* @returns 路径数组
*/
export const findPath = (stage: number[][], start: number[], end: number[]) => {
//终点坐标
const = end;
// 将起点加入队列，这是整个寻路的核心
// 也是结束的条件之一，如果队列空了，表示没有找不到路了
const queue = [];
//如果终点为障碍物，则不走了
if (grid === 1) {
return [];
}
//已经走过的路，用SET去重
const visited = new Set<string>();
//将起点设为已经走过的路
visited.add(`${start},${start}`);
//开始寻路
}开始寻路
[*]寻路
[*]探索的过程只能一格一格的找，一次找很多步，容易错过终点
[*]如果没有找到终点，并且还有没走过的路，就要一直找，【核心驱动】
[*]搜索：
[*]每经过一个点，都要找一下上下左右有没有终点的坐标，如此循环
图示寻路过程：
[*]蓝块是我们的本体，粉色是终点
[*]旁边的色块是搜索的结果，
[*]红色代表出界或已走过，总之不能走的地方，且不会加入到队列
[*]深绿色代表优先走，会加入到队列，且下一次循环就要走到这个点【很重要】
[*]浅绿色代表能走，且经过检测不是终点，但不会加入队列
[*]优先级取决于方向的顺序，可以根据情况调整，比如知道目标点在最下面，可以把去下面的方向调整到最前面来
代码
// 方向，下面有解释
const DIRECTIONS = [
,
,
[-1, 0],
,
];
/**
* @description 寻找路径
* @param grid 二维数组
* @param start 起始点
* @param end 终点
* @returns 路径数组
*/
export const findPath = (grid: number[][], start: number[], end: number[]) => {
const = end;
/* 三维数组 */
const queue = [];
if (grid === 1) {
return [];
}
const visited = new Set<string>();
visited.add(`${start},${start}`);
while (queue.length > 0) {
/* 取出最后一个加入的坐标 */
const lastRoute = queue.shift();
if (lastRoute) {
/* 取出新的坐标 */
const route = lastRoute;
/* 新的坐标的x,y，用于判断是否为终点 */
const = route;
if (x === endX && y === endY) {
/* 如果是终点则返回 */
return lastRoute;
}
/* 继续根据方向寻找，下面有解释 */
for (const of DIRECTIONS) {
/* 周围的坐标，上下左右 */
const newX = dx + x;
const newY = dy + y;
const newRoute = [...lastRoute, ];
/* 如果找到坐标，就别找了 */
if (newX === endX && newY === endY) {
return newRoute;
}
/* 检测边界，下面有解释 */
if (collisionDetection(grid, x, y, !visited.has(`${newX},${newY}`))) {
visited.add(`${x},${y}`);
//将新的坐标和旧的队列一并加入到路线中
queue.push(newRoute);
}
}
}
}
return [];
};
难点解析
边界检测
普通地图，一般都是有边界的，且限定不能出界，所以需要准备相关条件进行判断，障碍物也是边界
所以地图有几个地方不能去，
[*]上下左右的边界不能走
[*]已经走过的路，不能走，否则就一直绕圈，完蛋啦。
[*]障碍物也不能走，穿墙了就到都处是路
/**
*@description 边界检测
* @param stage 二维数组
* @param x 当前的横坐标
* @param y 当前的纵坐标
* @param alreadyPassed 是否已经过
*/
export const collisionDetection = (
stage: number[][],
x: number,
y: number,
alreadyPassed: boolean
) => {
const MAX_X = stage.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 !== 1 &&//判断不能是障碍物
alreadyPassed
);
};看效果
可以看到，都是点哪里去哪里，全程闪现
核心原因是for计算没有延迟，中间的确经过了我们之前得到的路径，但由于太快，我们看不到
没有延迟，制造延迟，用定时器模拟for循环
创造一个变量i=0，相当于for的累加
代码
const DIRECTIONS = [
, //上
, //下
[-1, 0], //左
, //右
];
//方向结合当前的坐标，就能检测周围了
let =current;//假设当前坐标为
for (const of DIRECTIONS) {
/* 周围的坐标，上下左右 */
const newX = dx + x;
const newY = dy + y;
//循环次数 方向 新的坐标 备注
// 1 DIRECTIONS= 出界了
// 2 DIRECTIONS= 往右走一格
}完整代码
用vue实现，复制粘贴即可运行
[,,]
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]