最好懂的自动寻路-前端

平哥走天下 發表於 2025-4-23 11:57:00

<div class="lake-content">
<h1 id="wMz6N">先看效果</h1>
黑块是障碍物，可以理解成游戏里的墙
白块是可走的路
点哪里走哪里，类似于游戏里的移动
在线演示
<img src="https://img2024.cnblogs.com/blog/1049707/202504/1049707-20250423115435106-1980563019.gif">

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

寻路三步走：画图->寻路->走路。
<ul class="ne-ul">
<li id="u516e09ac" data-lake-index-type="0">地图的根本作用是让位置更直观</li>
<li id="ua1b3585b" data-lake-index-type="0">核心难点是寻路</li>
<li id="u9b5bbc26" data-lake-index-type="0">走路是最终目的</li>
</ul>
我们就以这样的顺序开始吧
<h1 id="XZtNs">画图</h1>
怎么去实现地图，图到底长什么样呢？如果从没接触过，那看起来有点抽象，先看实现地图的代码
现象：观察右边的图片，注意0,1和黑白方块
<img src="https://img2024.cnblogs.com/blog/1049707/202504/1049707-20250423115455901-1652932991.png"><img src="https://img2024.cnblogs.com/blog/1049707/202504/1049707-20250423115447155-986644716.png">
总结：【0=白块】，【1=黑块】
<pre id="bVcqy" class="ne-codeblock language-plain highlighter-hljs" data-language="plain" data-dark-theme="true"><code>IF(X=4&Y=0){
渲染黑块
}ELSE{
渲染白块
}</code></pre>
<h2 id="rvwTg">实现</h2>
我这里的布局很简陋
<pre id="NF6da" class="ne-codeblock language-vue highlighter-hljs" data-language="vue" data-dark-theme="true"><code><div class="grid">
<div v-for="(item, k) in stage" :key="k" class="flex">
<div
 v-for="(m, n) in item"
 :key="n"
 class="square"
 :class=""
 ></div>
</div>
</div>

const stage = [
,
,
,
,
,
,
,
,
];

.square {
border: 1px solid #000;
@apply w- h-;
}</code></pre>
<h2 id="vByz8">怎么让路和墙丰富起来</h2>
有些同学可能有疑问了，我要做墙做怪物，墙有很多种，怪物也有很多种，仅有0和1怎么表示呢？
把换成对象就好了，以前端为例，可以直接用JSON,把上面的代码修改一下
<img src="https://img2024.cnblogs.com/blog/1049707/202504/1049707-20250423115504586-817008495.png">
接下来只要根据image渲染不同的图片，type和style可以用来做逻辑，比如经过style=地狱门的时候就扣血，经过砂石路移动速度变慢，判断是否经过，就是看英雄的坐标和障碍物是否重叠。
<h2 id="con6B">地图编辑器</h2>
种类是丰富了，但是我想做一个英雄联盟这样的地图，那不得写到宇宙二次爆炸？那该怎么做呢？
玩过魔兽争霸的朋友可能知道，有一个东西叫地图编辑器，从编辑器里诞生Dota，Dota衍生LOL，Lol变异成王者农药，农药里的三国的关羽能骑马砍战国末期的嬴政....
很久以前做了一个简单的地图编辑器，墙能够粉刷，其实还做了怪物来着，后面觉得实现方式有问题，给删了。
前半段演示画墙，后面演示走路
核心就是用可视化创建地图数据
<img src="https://img2024.cnblogs.com/blog/1049707/202504/1049707-20250423115515675-986115169.gif">

<h1 id="e2tKb">寻路</h1>
来到核心内容了，代码一大堆，网上搜的到，AI能生成，但都没那么容易理解。
要想写出代码，先要了解业务逻辑
<h2 id="cTfMw">寻路前的数据</h2>
寻路，至少要知道自己在哪儿，要去哪儿。
App导航需要先获取你的位置，再输入目的地，最后确认路线，这里也是如此，寻路前需要最基本的数据
<ul class="ne-ul">
<li id="uc2e56acb" data-lake-index-type="0">起点和终点【蓝色，粉色】</li>
<li id="u4ca663db" data-lake-index-type="0">将起点加入到已走过的路</li>
<li id="u4f97a293" data-lake-index-type="0">起点和终点不能相同【没写】</li>
<li id="uf9a4af5b" data-lake-index-type="0">还有不能出界，导航从广州到上海，想必你也不想从西藏方向出发，再从美国那边飞回来吧</li>
</ul>

 <img src="https://img2024.cnblogs.com/blog/1049707/202504/1049707-20250423115534936-1366235408.png">
所对应的代码如下，有了最基本的数据后才能寻路
<pre id="Pyfkp" class="ne-codeblock language-javascript highlighter-hljs" data-language="javascript" data-dark-theme="true"><code>/**
* @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}`);
//开始寻路
}</code></pre>
<h2 id="bkvPM">开始寻路</h2>
<ul class="ne-ul">
<li id="u135f9e55" data-lake-index-type="0">寻路</li>
</ul>
<ul class="ne-list-wrap">
<ul class="ne-ul">
<li id="u218a5813" data-lake-index-type="0">探索的过程只能一格一格的找，一次找很多步，容易错过终点</li>
<li id="u4523cca2" data-lake-index-type="0">如果没有找到终点，并且还有没走过的路，就要一直找，【核心驱动】</li>
</ul>
</ul>
<ul class="ne-ul">
<li id="u00ece555" data-lake-index-type="0">搜索：</li>
</ul>
<ul class="ne-list-wrap">
<ul class="ne-ul">
<li id="ue299d538" data-lake-index-type="0">每经过一个点，都要找一下上下左右有没有终点的坐标，如此循环</li>
</ul>
</ul>

图示寻路过程：
<ul class="ne-ul">
<li id="u97d22955" data-lake-index-type="0">蓝块是我们的本体，粉色是终点</li>
<li id="ubb0bd2e5" data-lake-index-type="0">旁边的色块是搜索的结果，</li>
</ul>
<ul class="ne-list-wrap">
<ul class="ne-ul">
<li id="uf39c004b" data-lake-index-type="0">红色代表出界或已走过，总之不能走的地方，且不会加入到队列</li>
<li id="u1be13eca" data-lake-index-type="0">深绿色代表优先走，会加入到队列，且下一次循环就要走到这个点【很重要】</li>
<li id="u6ef20f61" data-lake-index-type="0">浅绿色代表能走，且经过检测不是终点，但不会加入队列</li>
<li id="u2fd60866" data-lake-index-type="0">优先级取决于方向的顺序，可以根据情况调整，比如知道目标点在最下面，可以把去下面的方向调整到最前面来</li>
</ul>
</ul>

<img src="https://img2024.cnblogs.com/blog/1049707/202504/1049707-20250423115557765-1066930976.png"><img src="https://img2024.cnblogs.com/blog/1049707/202504/1049707-20250423115602245-1046497262.png"><img src="https://img2024.cnblogs.com/blog/1049707/202504/1049707-20250423115608054-530616827.png">
<h3 id="f5wRr">代码</h3>
<pre id="OPIgb" class="ne-codeblock language-javascript highlighter-hljs" data-language="javascript" data-dark-theme="true"><code>// 方向，下面有解释
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 [];
};</code></pre>

<h2 id="VtVYz">难点解析</h2>
<h3 id="pxcaJ">边界检测</h3>
普通地图，一般都是有边界的，且限定不能出界，所以需要准备相关条件进行判断，障碍物也是边界
所以地图有几个地方不能去，
<ul class="ne-ul">
<li id="uf7da91cd" data-lake-index-type="0">上下左右的边界不能走</li>
<li id="u3273dad8" data-lake-index-type="0">已经走过的路，不能走，否则就一直绕圈，完蛋啦。</li>
<li id="u25f776c8" data-lake-index-type="0">障碍物也不能走，穿墙了就到都处是路</li>
</ul>
<pre id="QRAPa" class="ne-codeblock language-javascript highlighter-hljs" data-language="javascript" data-dark-theme="true"><code>
/**
*@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
);
};</code></pre>
<h3 id="GLC1M"> 方向</h3>
以我们正常去移动用的方式去看，只要修改横轴纵轴坐标即可，如下
<ul class="ne-ul">
<li id="uc6f9fab0" data-lake-index-type="0">往右移动x+=1</li>
<li id="ud4b965b3" data-lake-index-type="0">往左移动x-=1</li>
<li id="uc1e97f47" data-lake-index-type="0">往上移动y-=1</li>
<li id="uc4379db2" data-lake-index-type="0">往下移动y+=1</li>
</ul>
但这里不相同，需要没走一步，就要四周观察，查看四次，所以被设计成了这样，当然坐标数组可以用对象代替，方便调整顺序
<pre id="tHHP9" class="ne-codeblock language-javascript highlighter-hljs" data-language="javascript" data-dark-theme="true"><code>const DIRECTIONS = [
, //上
, //下
[-1, 0], //左
, //右
];
//方向结合当前的坐标，就能检测周围了
let =current;//假设当前坐标为
for (const of DIRECTIONS) {
 /* 周围的坐标，上下左右 */
 const newX = dx + x;
 const newY = dy + y;
//循环次数方向新的坐标备注
// 1 DIRECTIONS= 出界了
// 2 DIRECTIONS= 往右走一格
}</code></pre>
<h3 id="hQu5P">队列</h3>
这可能是最难理解的一部分了,然而我也很难用一两张图去表达，这个过程是动态的，除非做成动画，可目前还没有加这个技能点,那只能大致说说了
<code class="ne-code">const queue = [];</code>
队列详解
队列初始化数据是queue=[[]],是一个三维数组，
<ol class="ne-ol">
<li id="u577e385f" data-lake-index-type="0">最里面一层是坐标</li>
<li id="uc7a6ed43" data-lake-index-type="0">中间一层是真正的路线</li>
<li id="u589f6d5d" data-lake-index-type="0">最外层是终止条件，始终只有一个数据，当四处都是障碍物，没有路线的时候，终止循环</li>
<li id="uf55ba667" data-lake-index-type="0">发现有可用的坐标的话，把坐标加入到路线中，再把路线加入到queue中</li>
</ol>
<img src="https://img2024.cnblogs.com/blog/1049707/202504/1049707-20250423115630402-696025569.png">
简单流程
(flag)发现可用的坐标，更新到路线和队列中，取出最新的坐标，继续寻找,回到前面的(flag)继续发现，直到找到目标
<h1 id="tkEVP">走路</h1>
执行完上面的findPath，我们就能找到路了,路长这个样子
<pre id="Q9FQg" class="ne-codeblock language-javascript highlighter-hljs" data-language="javascript" data-dark-theme="true"><code>[,,]</code></pre>
接下来该走路了。
有的同学可能肃然起敬，这个我熟，for循环，把路线中的每个点都赋值给英雄就好了。
好吧，你又中招了，for循环让整个寻路失去了意义
<pre id="F2hnU" class="ne-codeblock language-javascript highlighter-hljs" data-language="javascript" data-dark-theme="true"><code>//错误演示
const routes = findPath(stage, start.value, end.value);
// routes=[,,] 示例结构，非真实代码
routes.forEach((v) => {
const = v;
hero.value.x = x;
hero.value.y = y;
});</code></pre>
<h2 id="Ow8BP">看效果</h2>
可以看到，都是点哪里去哪里，全程闪现
<img src="https://img2024.cnblogs.com/blog/1049707/202504/1049707-20250423115640763-2123411952.gif" height="343" width="315">
核心原因是for计算没有延迟，中间的确经过了我们之前得到的路径，但由于太快，我们看不到
没有延迟，制造延迟，用定时器模拟for循环
创造一个变量i=0，相当于for的累加

<h2 id="onNRw">代码</h2>
<pre id="HtW6a" class="ne-codeblock language-javascript highlighter-hljs" data-language="javascript" data-dark-theme="true"><code>// 我们需要移动的目标英雄
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 = routes;
 hero.value.x = x;
 hero.value.y = y;
} else {
 start.value = [...end.value];
 i = 0;
 clearInterval(flag);
}
}, 50);
};</code></pre>
<h1 id="Tq4q3">完整代码</h1>
用vue实现，复制粘贴即可运行
<pre id="ieC3z" class="ne-codeblock language-javascript highlighter-hljs" data-language="javascript" data-dark-theme="true"><code><template>
<div class="parent">
<div class="grid">
 <div v-for="(item, k) in stage" :key="k" class="flex">
 <div
 v-for="(m, n) in item"
 :key="n"
 class="square"
 @click="setEnd(n, k)"
 :class=""
 ></div>
 </div>
</div>

<div
 class="hero"
 :style="{
 left: `${hero.x * 100}px`,
 top: `${hero.y * 100}px`,
 }"
></div>
</div>
</template>

<script setup lang="ts">
import { ref } from 'vue';

let flag: NodeJS.Timeout | undefined = undefined;

const stage = [
,
,
,
,
,
,
,
,
];

const hero = ref({
x: 0,
y: 0,
});
const end = ref([-1, -1]);
const start = ref();
const setEnd = (x: number, y: number) => {
end.value = ;
move();
};
const DIRECTIONS = [
,
,
[-1, 0],
,
];
/**
* @description 寻找路径
* @param grid 二维数组
* @param start 起始点
* @param end 终点
* @returns 路径数组
*/
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 是否已经过
*/
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
);
};

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 = routes;
 hero.value.x = x;
 hero.value.y = y;
} else {
 start.value = [...end.value];
 i = 0;
 clearInterval(flag);
}
}, 50);
};
</script>

<style scoped lang="scss">
.parent {
--wh: 100px;
position: relative;
.square {
border: 1px solid #000;
width: var(--wh);
height: var(--wh);
}
.hero {
position: absolute;
text-align: center;
width: var(--wh);
height: var(--wh);
background-color: red;
}
.black {
background-color: #000;
}
}
.grid {
display: grid;
}
.flex {
display: flex;
}
</style></code></pre>

</div> 
来源：https://www.cnblogs.com/blogin/p/18842499

頁: [1]

琼殿技术论坛's Archiver

最好懂的自动寻路-前端