写点什么

编程能力 —— 寻路问题

用户头像
wendraw
关注
发布于: 2020 年 07 月 10 日

在很多游戏中都有寻路的机制,就是从一个点走到另一个点,这个路径可以有很多种,但是我们要找到其中最短的路径。



其中最经典的问题就是迷宫,我们在本篇文章就一起来完成一个迷宫的小游戏。



1. 画迷宫

为了让寻路的过程更加直观,我们需要将这个过程可视化。先画一个 100 x 100 的矩阵,每一个格子表示一个位置。

<style></style>
<div id="container"></div>
<script>
let container = document.getElementById('container');
for (let y = 0; y < 100; y++) {
for (let x = 0; x < 100; x++) {
let cell = document.createElement('div');
cell.classList.add("cell");
container.appendChild(cell);
}
}
</script>



image.png



鼠标绘制

得到了矩阵地图之后我们还需要给一些障碍物,我们当然可以给这 10000 个格子一个个的设置,但是这样效率太低。我们希望可以像画图软件一样用鼠标就能画出一个迷宫。



<script>
const map = new Array(10000).fill(0);
const container = document.getElementById('container');
function show(map) {
let move = false;
let clear = false;
container.addEventListener('mousedown', e => {
move = true;
clear = e.button === 2; // 鼠标右键
})
container.addEventListener("mouseup", e => {
move = false;
})
// 取消浏览器右键弹出菜单
container.addEventListener("contextmenu", e => e.preventDefault());
for (let y = 0; y < 100; y++) {
for (let x = 0; x < 100; x++) {
let cell = document.createElement('div');
cell.classList.add("cell");
cell.addEventListener("mousemove", () => {
if (move) {
if (clear) {
cell.style.backgroundColor = "";
map[y * 100 + x] = 0;
} else {
cell.style.backgroundColor = "black";
map[y * 100 + x] = 1;
}
}
});
container.appendChild(cell);
if (map[y * 100 + x] === 1) {
cell.style.backgroundColor = "black";
}
}
}
}
show(map);
</script>

我们选择用一个数组来存储迷宫的数据,没有障碍物用 0 表示,有障碍物用 1 来表示。



我们首先需要监听 container 的 mousedown 事件,当鼠标有按键按下时,就表示接下来是 move 事件了,就将全局的 move 赋值为 true,如果按下的是右键,那么就认为是要擦除,就将 全局的 clear 赋值为 true。



然后就是监听 mouseup 事件,当按键被抬起就说明已经画完了,将 move 赋值为 false,表示不再管 move 事件了。



这里还有一个需要注意的是,浏览器已经占用了鼠标的右键每次都会弹出菜单,我们需要将其取消。



最后就是每一个格子都要监听 mousemove 事件,当触发了 mousemove 事件时,就是想要将当前的格子画成障碍物。因此每个格子在触发 mousemove 事件时,都去检查 move 跟 clear 来选择是擦除还是绘制。



持久化

现在我们就可以用鼠标绘制自己的地图了。但是还有一个小问题,就是我们可能花了很长时间画了一个非常漂亮的地图,但是刷新了一下页面全部心血就都白费了。



因此我们需要将我们的迷宫持久化的存储起来,每次进入页面就去取这部分的数据即可。在我们前端持久化最简单的就是用 localStorage 了。



我们给页面添加 save 和 clear 按钮,代码非常简单,要注意的是 clear 的时候需要重新加载页面,不然 map 的数据在内存还是存在的。

<style></style>
<div id="container"></div>
<button onclick="localStorage.map = JSON.stringify(map);">save</button>
<button onclick="delete localStorage.map;location.reload();">clear</button>
<script>
let map = localStorage.map ? JSON.parse(localStorage.map) : new Array(10000).fill(0);
// ......
</script>

下面就是我画的一个简单的迷宫,并且选择左上角为入口,右下角为出口。

const start = [0, 0];
const end = [99, 99];
function show() {
// ......
for (let y = 0; y < 100; y++) {
// ......
for (let x = 0; x < 100; x++) {
if (y === 0 && x === 0) {
if (x === start[0] && y === start[1]) {
cell.style.backgroundColor = "yellow";
}
if (x === end[0] && y === end[1]) {
cell.style.backgroundColor = "red";
}
}
}
}



image.png



我这里只随便画了一些障碍,你可以发挥你的聪明才智画一个更好看的迷宫。

2. BFS

有了迷宫,接下来就是寻路了。搜索算法最常用的就是 DFS(深度优先搜索)和 BFS(广度优先搜索)。DFS 就是一条路走到黑,直到找到目标或者没有路可走了。BFS 就是会尝试周围所有的可能,然后向外扩散,就像一个涟漪一样一圈一圈的向外扩散开。DFS 就是能确定一定能找到答案,而 BFS 就能找到最佳路径。



所以我们这里用 BFS 来完成这个寻路,先只考虑可以走上、下、左、右 4 个方向。



image.png



function findPath(map, start, end) {
let _map = map.slice();
let queue = [start];
while (queue.length) {
let [x, y] = queue.shift();
console.log(x, y);
if (x === end[0] && y === end[1]) {
return true;
}
await insert([x - 1, y]); // 左
await insert([x + 1, y]); // 右
await insert([x, y - 1]); // 上
await insert([x, y + 1]); // 下
}
return false;
function insert([x, y]) {
if (_map[y * 100 + x] !== 0) return;
if (x < 0 || y < 0 || x >= 100 || y >= 100) return;
_map[y * 100 + x] = 2;
queue.push([x, y]);
}
}

我们先将 map copy 一份就不会污染地图数据。



BFS 的代码其实非常简单,需要借助队列的特性先入先出,每次出队一个坐标,先判断当前的坐标是不是终点,如果是,就直接结束了。如果不是,就依次将上、下、左、右的坐标入队。当然入队前先要判断是不是障碍物和边界条件,然后再将当前的点标记为 2 表示已经访问过了。这样就会像涟漪一样一圈一圈的往外扩散式的搜索。



我们在控制台手动执行 findPath(map, [0,0], [99,99]),稍等一段时间就能返回 true,告诉我们能找到终点。



image.png



3. 可视化

上面的过程非常单调,我们只能看到坐标一直在变,对于我们人类来说非常不直观。因此我们就要将这个搜索的过程可视化,其实也非常简单就是将访问过的格子染个色。



这里我们需要用到异步编程的内容了,用 async await 将 findPath 改成一个异步函数,并且配合 Promise 封装的 sleep 函数,来完成可视化。就是在访问每个格子(将格子对应的值赋值为 2)时,将格子改成淡绿色,再等待 5ms。在进行下一步。



async function findPath(map, start, end) {
let _map = map.slice();
let queue = [start];
while (queue.length) {
let [x, y] = queue.shift();
if (x === end[0] && y === end[1]) {
return true;
}
await insert([x - 1, y]); // 左
await insert([x + 1, y]); // 右
await insert([x, y - 1]); // 上
await insert([x, y + 1]); // 下
}
return false;
async function insert([x, y]) {
if (_map[y * 100 + x] !== 0) return;
if (x < 0 || y < 0 || x >= 100 || y >= 100) return;
_map[y * 100 + x] = 2;
container.children[y * 100 + x].style.backgroundColor = "lightgreen";
await sleep(5);
queue.push([x, y]);
}
}
function sleep(ms) {
return new Promise((resolve, reject) => {
setTimeout(resolve, ms);
})
}

最后的运行效果就是下图这样了。



image.png



image.png



4. 寻路 -- 8 个方向

上面我们已经实现了从起始点走到结束点,但是还没有找出最佳路径。为了要找出最佳路径,我们还需要修改一下 _map 的数据结构,当格子被访问过时,不能只是将对应的数据存储成 2,而是要存储上一步的坐标。



这部分的代码如下,就是每次 insert 的时候都带上上一步的坐标。然后在找到终点时,从终点根据存储的上一个坐标反推到起点,就得到了最终的路径。

async function findPath(map, start, end) {
let _map = map.slice();
let queue = [start];
while (queue.length) {
let [x, y] = queue.shift();
if (x === end[0] && y === end[1]) {
let path = [];
while (x !== start[0] || y !== start[1]) {
path.push([x, y]);
container.children[y * 100 + x].style.backgroundColor = "pink";
[x, y] = _map[y * 100 + x];
}
return path;
}
// ...
}
return null;
async function insert([x, y], pre) {
// ......
_map[y * 100 + x] = pre;
// ......
}
}

最后找到的最佳路径就是下面这样:



image.png



在前面只考虑上、下、左、右 4 个方向,如果我们规定可以斜着走,那么就还有左上、右上、左下、右下,一共有 8 个方向了。



其实这部分的代码也非常简单,就是上面 4 个方向代码基础之上加上斜向的 4 个方向。

async function findPath(map, start, end) {
// ......
while (queue.length) {
// ......
await insert([x - 1, y]); // 左
await insert([x + 1, y]); // 右
await insert([x, y - 1]); // 上
await insert([x, y + 1]); // 下
await insert([x - 1, y - 1]); // 左下
await insert([x - 1, y + 1]); // 左上
await insert([x + 1, y - 1]); // 右下
await insert([x + 1, y + 1]); // 右上
}
// ......
}



image.png



image.png



这样简单的加上斜线的逻辑就会存在一个问题,我们的墙如果只有一层,就会被直接穿透。因此我们还需要在走斜线的时候加上一点逻辑,如果想要走斜线,那么在水平或者垂直方向上不能有障碍物。如,要走当前位置的「右下」位置,就先要确保当前位置的「右」或者「下」位置没有障碍物。



我们在每个位置加上对应的判断条件即可:

(map[y * 100 + (x - 1)] === 0 || map[(y - 1) * 100 + x] === 0) && await insert([x - 1, y - 1], [x, y]); // 左下
(map[y * 100 + (x - 1)] === 0 || map[(y + 1) * 100 + x] === 0) && await insert([x - 1, y + 1], [x, y]); // 左上
(map[y * 100 + (x + 1)] === 0 || map[(y - 1) * 100 + x] === 0) && await insert([x + 1, y - 1], [x, y]); // 右下
(map[y * 100 + (x + 1)] === 0 || map[(y + 1) * 100 + x] === 0) && await insert([x + 1, y + 1], [x, y]); // 右上

这样问题就解决了。



image.png



image.png



5. 寻路(优化)-- A*

在上一小节,我们完成了寻路的算法,利用 BFS 找到了最优的路径。但其实还有很多地方可以优化的,比如,我们这里将整个地图都遍历了一遍效率非常低。路径也不是最短路径,还有很多可以优化的空间。



寻找两点之间的最短路径这个问题,其实数学家们已经帮我们找到了最优解,就是 A* 搜索算法





简单来说就是,根据当前点与终点之间的距离不断进行剪枝。我们之前是依次遍历 8 个方向的每一个方向,没有优先级,直到找到终点。而 A* 算法就是要在所有可以走的坐标点中间,选择一个与终点距离最近的点来走。不断调整方向,最后就能得到最优路径。这个是数学家在数学上给我们证明过的。



因此我们要修改数据的「待访问点」的数据结构,不能用一个队列来存储。而是要用一个新的数据结构,它要满足我们每次都可以取到最小的值。



class SortedArray {
constructor(data, compare) {
this.data = data;
this.compare = compare;
}
take() {
let min = this.data[0];
let minIndex = 0;
for (let i = 1; i < this.data.length; i++) {
if (this.compare(min, this.data[i]) > 0) {
min = this.data[i];
minIndex = i;
}
}
this.data[minIndex] = this.data[this.data.length - 1];
this.data.pop();
return min;
}
insert(v) {
this.data.push(v);
}
get length() {
return this.data.length;
}
}

我们这个 SortedArray 类的构造函数接受一个 data(所有的数据)和一个 compare(数据的大小比较我们把接口放到调用者去实现,我们只要求,前一个数比后一个数大是返回正数,反之给我们返回负数即可)。



take() 方法也非常简单,每次都在 data 中取最小的那个数据。最小的数被取出之后,就有一个空位,然后我们的数组是无序的,所以只需要将最后一个数填到当前的最小值的空位即可。最后将这个最小值返回。



insert() 方法只需要将数据插入到数组的末尾。length 是一个 get 方法,这是是为了 BFS 的代码而加上的。



有了新的数据结构 SortedArray,我们接下来就是修改 BFS 部分涉及到 queue 的代码。都要改成 SortedArray 结构。

async function findPath(map, start, end) {
let _map = map.slice();
let collection = new SortedArray([start], (a, b) => distance(a) - distance(b));
while (collection.length) {
let [x, y] = collection.take();
// ......
}
return null;
async function insert([x, y], pre) {
// ......
collection.insert([x, y]);
}
function distance([x, y]) {
return (x - end[0]) ** 2 + (y - end[1]) ** 2;
}
}

compare() 算法就使用两点间距离公式来比较,并且我们只涉及大小比较,就可以省去开根号这个耗时的运算。



最后 A* 就给我们找到了最优的解,并且遍历的位置也非常非常少。



image.png



6. 寻路(优化)-- 二叉小顶堆

我们上面用的 A* 算法看起来像是完美的解决了问题,但其实还有优化的空间。如果你的算法功底还算不错,应该能发现一些端倪。问题就出在我们的 SortedArray 类的 take() 方法,这里找到最小值的时间复杂度是 O(n)。



当然我们知道在无序数组中找最小值,时间复杂度 O(n) 已经是极限了(如果是一个有序数组,取最小值的操作可以达到 O(1),但是要维护数组的有序,就要进行数据搬运最后时间复杂度还是 O(n))。



那么我们有没有一种数据结构可以更快的找到最小值,同时维护的成本更低一些。还真有这样的数据结构,它就是「小顶堆」,堆是一种树形结构从根节点遍历到叶子节点的时间复杂度只要 O(logn),然后小顶堆就是所有的根节点一定比它的左、右子树的所有元素都小的堆。



image.png



在 JS 中没有现成的小顶堆的数据结构,所以我们需要自己实现一个。

class BinaryHeap {
constructor(data, compare) {
this.data = data;
this.compare = compare;
}
take() {
if (this.data.length === 0) return;
let min = this.data[0];
let i = 0;
// fix heap
while (i < this.data.length) {
// 没有左子节点
if (i * 2 + 1 >= this.data.length) break;
// 没有右子节点
if (i * 2 + 2 >= this.data.length) {
this.data[i] = this.data[i * 2 + 1];
i = i * 2 + 1;
break;
}
// 比较左右子节点的大小,更小的补到父节点
if (this.compare(this.data[i * 2 + 1], this.data[i * 2 + 2]) < 0) {
this.data[i] = this.data[i * 2 + 1];
i = i * 2 + 1;
} else {
this.data[i] = this.data[i * 2 + 2];
i = i * 2 + 2;
}
}
if (i < this.data.length - 1) {
this.insertAt(i, this.data.pop());
} else {
this.data.pop();
}
return min;
}
insertAt(i, v) {
this.data[i] = v;
// 对比当前节点与其子节点,如果子节点更小就交换它们
while (this.compare(v, this.data[Math.floor((i - 1) / 2)]) < 0) {
this.data[i] = this.data[Math.floor((i - 1) / 2)];
this.data[Math.floor((i - 1) / 2)] = v;
i = Math.floor((i - 1) / 2);
}
}
insert(v) {
this.insertAt(this.data.length, v);
}
get length() {
return this.data.length;
}
}



二叉树的节点可以用一个对象来存储,但是对象的内存消耗太大,还要存储左右子针。其实如果是一个完全二叉树,我们可以用基于数组的顺序存储法。我们把根节点存储在下标 i = 0 的位置,那左子节点存储在下标 2 * i + 1 = 1 的位置,右子节点存储在 2 * i + 2 = 2 的位置。以此类推,最后整个小顶堆就存储到一个数组中了。



image.png



我们的 BinaryHeap 类跟 SortedArray 一样接受 data 和 compare 作为构造函数。不同的就是 take() 和 insert() 方法。



insert() 方法就是每次在数组的末尾 insertAt 一位数据。



insertAt() 方法就是将数值放到指定的位置,但同时还要保证最小堆的特性。就是要与左右子节点比较,如果子节点更小就交换它们的值。一直循环这个过程,直到子节点都比它大,或者没有子节点(下沉到了叶子节点)。



take() 每次都会从堆顶取出最小值,这时候堆顶就会产生空位,需要从它的左右子节点选出最小的值来作为根节点(这里不需要在左右子树中找最小节点,因为最小堆的定义就是根节点要比左右子树的所有节点都小),然后左右子节点最小的那个又会有空位,因此就在其左右子节点继续找最小值来填充。循环这个过程,直到空位是在叶子节点就跳出循环。这个时候就判断是不是最后一个叶子节点是空位,如果是,就直接删除即可。如果不是,就将最后一位叶子节点拿出来补上这个空位。



使用的方法只需要将 SortedArray 替换成 BinaryHeap 即可,因此它们的接口都是一样的。

let collection = new SortedArray([start], (a, b) => distance(a) - distance(b));
// 换成
let collection = new BinaryHeap([start], (a, b) => distance(a) - distance(b));





跟前面 SortedArray 的结果一致,不过访问的速度有明显的提升。



7. 寻路(优化)-- 距离权重

如果观察比较细致,这个路径其实还不是最优的,我们都知道两点之间直线距离最短。而我们这个 A* 算法找出来的路径还有一些瑕疵,最后算出来的路径会贴着障碍物走,有时候就会有一些冤枉路。



image.png



产生这个结果的原因是,我们没有给斜线和直线不同的权重。



我们用一个新的数组 table 来记录「当前点」与「起始点」的之间的距离,每次往上、下、左、右移动一位就将其距离 fromStart 加 1。往左上、左下、右上、右下移动一步就将距离 fromStart 加 1.4。然后每次 insert 的时候,要判断如果 fromStart 比 table 中记录的距离更长,就不要走这一步了。

async function findPath(map, start, end) {
// ......
// 记录到起点的长度
let table = new Array(10000).fill(Infinity);
table[start[1] * 100 + start[0]] = 0;
while (collection.length) {
let [x, y] = collection.take();
let fromStart = table[y * 100 + x];
// ......
await insert([x - 1, y], [x, y], fromStart + 1); // 左
await insert([x + 1, y], [x, y], fromStart + 1); // 右
await insert([x, y - 1], [x, y], fromStart + 1); // 上
await insert([x, y + 1], [x, y], fromStart + 1); // 下
(map[y * 100 + (x - 1)] === 0 || map[(y - 1) * 100 + x] === 0) && await insert([x - 1, y - 1], [x, y], fromStart + 1.4); // 左下
(map[y * 100 + (x - 1)] === 0 || map[(y + 1) * 100 + x] === 0) && await insert([x - 1, y + 1], [x, y], fromStart + 1.4); // 左上
(map[y * 100 + (x + 1)] === 0 || map[(y - 1) * 100 + x] === 0) && await insert([x + 1, y - 1], [x, y], fromStart + 1.4); // 右下
(map[y * 100 + (x + 1)] === 0 || map[(y + 1) * 100 + x] === 0) && await insert([x + 1, y + 1], [x, y], fromStart + 1.4); // 右上
}
return null;
async function insert([x, y], pre, fromStart) {
if (_map[y * 100 + x] === 1) return;
if (x < 0 || y < 0 || x >= 100 || y >= 100) return;
if (fromStart >= table[y * 100 + x]) return;
_map[y * 100 + x] = pre;
table[y * 100 + x] = fromStart;
container.children[y * 100 + x].style.backgroundColor = "lightgreen";
await sleep(1);
collection.insert([x, y]);
}
// ......
}

最后的效果就是这样:



image.png



总结

今天我们完成了一个寻路问题,这是一个在游戏领域应用非常广泛的问题。我们通过一步步拆解,最终解决了问题,最后还优化了一些明显存在的缺陷。最后整体的代码已经上传到 GayHub find-path 上了。



最大的收获就是可视化了,作为前端工程师页面展示与交互是我们的职责。那么将一些困难的问题可视化,对最终发现问题解决问题、找到最优解是非常有帮助的。



可视化应该是我们的神兵利器,后续我会尝试将算法的学习过程可视化。敬请期待。。。



参考

winter 前端进阶训练营

两点间距离公式

A* search algorithm

28 | 堆和堆排序:为什么说堆排序没有快速排序快?



发布于: 2020 年 07 月 10 日阅读数: 65
用户头像

wendraw

关注

还未添加个人签名 2018.05.07 加入

还未添加个人简介

评论

发布
暂无评论
编程能力 —— 寻路问题