在很多游戏中都有寻路的机制，就是从一个点走到另一个点，这个路径可以有很多种，但是我们要找到其中最短的路径。
其中最经典的问题就是迷宫，我们在本篇文章就一起来完成一个迷宫的小游戏。
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;
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 | 堆和堆排序：为什么说堆排序没有快速排序快？
评论