本篇将尝使用 canvas + wasm 画一个迷宫,生成算法主要用到连通集算法,使用 wasm 主要是为了提升运行效率。然后再用一个最短路径算法找到迷宫的出路,最后的效果如下:
生成迷宫的算法其实很简单,假设迷宫的大小是 10 * 10,即这个迷宫有 100 个格子,通过不断地随机拆掉这 100 个格子中间的墙,直到可以从第一个格子走到最后一个格子,也就是说第一个格子和最后一个格子处于同一个连通集。具体如下操作:
(1)生成 100 个格子,每个格子都不相通
(2)随机选取相邻的两个格子,可以是左右相邻或者是上下相邻,判断这两个格子是不是处于同一个连通集,即能否从其中一个格子走到另外一个格子,如果不能,就拆掉它们中间的墙,让它们相连,处于同一个连通集。
(3)重复第二步,直到第一个格子和最后一个格子相连。
那这个连通集应该怎么表示呢?我们用一个一维数组来表示不同的已连通的集合,初始化的时候每个格子的值都为 - 1,如下图所示,假设迷宫为 3 * 3,即有 9 个格子:
每个索引在迷宫的位置:
负数表示它们是不同的连通集,因为我们还没开始拆墙,所以一开始它们都是独立的。
现在把 3、4 中间的墙拆掉,也就是说让 3 和 4 连通,把 4 的值置成 3,表示 4 在 3 这个连通集,3 是它们的根,如下图所示:
再把 5、8 给拆了:
再把 4、5 给拆了:
这个时候 3、4、5、8 就处于同一个连通集了,但是 0 和 8 依旧是两个不同的连通集,这个时候再把 3 和 0 中间的墙给拆了:
由于 0 的连通集是 3,而 8 的连通集也是 3,即它们处于同一个连通集,因此这个时候从第一个格子到最后一个格子的路是相通的,就生成了一个迷宫。
我们用 UnionSet 的类表示连通集,如下代码所示:
- class UnionSet { constructor(size) { this.set = new Array(size);
- for (var i = this.set.length - 1; i >= 0; i--) { this.set[i] = -1;
- }
- } union(root1, root2) { this.set[root1] = root2;
- } findSet(x) {
- while (this.set[x] >= 0) { x = this.set[x];
- }
- return x;
- } sameSet(x, y) {
- return this.findSet(x) === this.findSet(y);
- } unionElement(x, y) { this.union(this.findSet(x), this.findSet(y));
- }
- }
我们总共用了 22 行代码就实现了一个连通集。上面的代码应该比较好理解,对照上面的示意图。如 findSet 函数得到某个元素所在的 set 的根元素,而根元素存放的是负数,只要存放的值是正数那么它就是指向另一个结点,通过 while 循环一层层的往上找直到负数。unionElement 可以连通两个元素,先找到它们所在的 set,然后把它们的 set union 一下变成同一个连通集。
现在写一个 Maze,用来控制画迷宫的操作,它组合一个 UnionSet 的实例,如下代码所示:
- class Maze { constructor(columns, rows, cavans) { this.columns = columns; this.rows = rows; this.cells = columns * rows; //存放是连通的格子,{1: [2, 11]}表示第1个格子和第2、11个格子是相通的
- this.linkedMap = {}; this.unionSets = new UnionSet(this.cells); this.canvas = canvas;
- }
- }
Maze 构造函数传三个参数,前两个是迷宫的列数和行数,最后一个是 canvas 元素。在构造函数里面初始化一个连通集,作为这个 Maze 的核心模型,还初始化了一个 linkedMap,用来存放拆掉的墙,进而提供给 canvas 绘图。
Maze 类再添加一个生成迷宫的函数,如下代码所示:
- //生成迷宫
- generate() { //每次任意取两个相邻的格子,如果它们不在同一个连通集,
- //则拆掉中间的墙,让它们连在一起成为一个连通集
- while (!this.firstLastLinked()) {
- var cellPairs = this.pickRandomCellPairs();
- if (!this.unionSets.sameSet(cellPairs[0], cellPairs[1])) { this.unionSets.unionElement(cellPairs[0], cellPairs[1]); this.addLinkedMap(cellPairs[0], cellPairs[1]);
- }
- }
- }
生成迷宫的核心逻辑很简单,在 while 循环里面判断第一个是否与最后一个格子连通,如果不是的话,则每次随机选取两个相邻的格子,如果它们不在同一个连通集,则把它们连通一下,同时记录一下拆掉的墙到 linkedMap 里面。
怎么随机选取两个相邻的格子呢?这个虽然没什么技术难点,但是实现起来需要动一番脑筋,因为在边上的格子没有完整的上下左右四个相邻格子,有些只有两个,有些有三个。笔者是这么实现的,相对来说比较简单:
- //取出随机的两个挨着的格子
- pickRandomCellPairs() {
- var cell = (Math.random() * this.cells) >> 0; //再取一个相邻格子,0 = 上,1 = 右,2 = 下,3 = 左
- var neiborCells = [];
- var row = (cell / this.columns) >> 0,
- column = cell % this.rows; //不是第一排的有上方的相邻元素
- if (row !== 0) { neiborCells.push(cell - this.columns);
- } //不是最后一排的有下面的相邻元素
- if (row !== this.rows - 1) { neiborCells.push(cell + this.columns);
- }
- if (column !== 0) { neiborCells.push(cell - 1);
- }
- if (column !== this.columns - 1) { neiborCells.push(cell + 1);
- }
- var index = (Math.random() * neiborCells.length) >> 0;
- return [cell, neiborCells[index]];
- }
首先随机选一个格子,然后得到它的行数和列数,接着依次判断它的边界情况。如果它不是处于第一排,那么它就有上面一排的相邻格子,如果不是最后一排则有下面一排的相邻格子,同理,如果不是在第一列则有左边的,不是最后一列则有右边的。把符合条件的格子放到一个数组里面,然后再随机取这个数组里的一个元素。这样就得到了两个随机的相邻元素。
另一个 addLinkedMap 函数的实现较为简单,如下代码所示:
- addLinkedMap(x, y) {
- if (!this.linkedMap[x]) this.linkedMap[x] = [];
- if (!this.linkedMap[y]) this.linkedMap[y] = [];
- if (this.linkedMap[x].indexOf(y) < 0) { this.linkedMap[x].push(y);
- }
- if (this.linkedMap[y].indexOf(x) < 0) { this.linkedMap[y].push(x);
- }
- }
这样生成迷宫的核心逻辑基本完成,但是上面连通集的代码可以优化, 一个是 findSet 函数,可以在 findSet 的时候把当前连通集里的元素的存放值直接改成根元素,这样就不用形成一条很长的查找链,或者说形成一棵很高的树,可直接一步到位,如下代码所示:
- findSet(x) {
- if (this.set[x] < 0) return x;
- return this.set[x] = this.findSet(this.set[x]);
- }
这段代码使用了一个递归,在查找的同时改变值。
union 函数也可以做一个优化,findSet 可以把树的高度改小,但是在没有改小前的 union 操作也可以做优化,如下代码所示:
- union(root1, root2) {
- if (this.set[root1] < this.set[root2]) { this.set[root2] = root1;
- } else {
- if (this.set[root1] === this.set[root2]) { this.set[root2]--;
- } this.set[root1] = root2;
- }
- }
这段代码的目的也是为了减少查找链的长度或者说减少树的高度,方法是把一棵比较矮的连通集成为另外一棵比较高的连通集的子树,这样两个连通集,合并起来的高度还是那棵高的。如果两个连通集的高度一样,则选取其中一个作为根,另外一棵树的结点在查找的时候无疑这些结点的查找长度要加上 1 ,因为多了一个新的 root,也就是说树的高度要加 1,由于存放的是负数,所以进行减减操作。在判断树高度的时候也是一样的,越小就说明越高。
经验证,这样改过之后,代码执行效率快了一半以上。
迷宫生成好之后,现在开始来画。
先写一个 canvas 的 html 元素,如下代码所示:
- <canvas id="maze" width="800" height="600">
- </canvas>
注意 canvas 的宽高要用 width 和 height 的属性写,如果用 style 的话就是拉伸了,会出现模糊的情况。
怎么用 canvas 画线呢?如下代码所示:
- var canvas = document.getElementById("maze");
- var ctx = canvas.getContext("2d");
- ctx.moveTo(0, 0);
- ctx.lineTo(100, 100);
- ctx.stroke();
这段代码画了一条线,从 (0, 0) 到(100, 100),这也是本篇将用到的 canvas 的 3 个基础的 api。
上面已经得到了一个 linkedMap,对于一个 3 * 3 的表格,把 linkedMap 打印一下,可得到以下表格。
通过上面的表格可知道,0 和 3 中间是没有墙,所以在画的时候 0 和 3 中间就不要画横线了,3 和 4 也是相连的,它们中间就不要画竖线了。对每个普通的格子都画它右边的竖线和下面的横线,而对于被拆掉的就不要画,所以得到以下代码:
- draw() {
- var linkedMap = this.linkedMap;
- var cellWidth = this.canvas.width / this.columns,
- cellHeight = this.canvas.height / this.rows;
- var ctx = this.canvas.getContext("2d"); //translate 0.5个像素,避免模糊
- ctx.translate(0.5, 0.5);
- for (var i = 0; i < this.cells; i++) {
- var row = i / this.columns >> 0,
- column = i % this.columns; //画右边的竖线
- if (column !== this.columns - 1 && (!linkedMap[i] || linkedMap[i].indexOf(i + 1) < 0)) { ctx.moveTo((column + 1) * cellWidth >> 0, row * cellHeight >> 0); ctx.lineTo((column + 1) * cellWidth >> 0, (row + 1) * cellHeight >> 0);
- } //画下面的横线
- if (row !== this.rows - 1 && (!linkedMap[i] || linkedMap[i].indexOf(i + this.columns) < 0)) { ctx.moveTo(column * cellWidth >> 0, (row + 1) * cellHeight >> 0); ctx.lineTo((column + 1) * cellWidth >> 0, (row + 1) * cellHeight >> 0);
- }
- } //最后再一次性stroke,提高性能
- ctx.stroke(); //画迷宫的四条边框
- this.drawBorder(ctx, cellWidth, cellHeight);
- }
上面的代码也比较好理解,在画右边的竖线的时候,先判断它和右边的格子是否相通,即 linkMap[i] 里面有没有 i + 1 元素,如果没有,并且它不是最后一列,就画右边的竖线。因为迷宫的边框放到后面再画,它比较特殊,最后一个格子的竖线是不要画的,因为它是迷宫的出口。每次 moveTo 和 lineTo 的位置需要计算一下。
注意上面的代码做了两个优化,一个是先 translate 0.5 个像素,为了让 canvas 画线的位置刚好在像素上面,因为我们的 lineWidth 是 1,如果不 translate,那么它画的位置如下图中间所示,相邻两个像素占了半个像素,显示器显示的时候变会变虚,而 translate 0.5 个像素之后,它就会刚好画在像在像素点上。详见: HTML5 Canvas – Crisp lines every time 。
第二个优化是所有的 moveTo 和 lineTo 都完成之后再 stroke,这样它就是一条线,可以极大地提高画图的效率。这个很重要,刚开始的时候没这么做,导致格子数稍多的时候就画不了了,改成这样之后,绘制的效率提升很多。
我们还可以再做一个优化,就是使用双缓存技术,在画的时候别直接画到屏幕上,而是先在内存的画布里面完成绘制,最后再一次性地 Paint 绘制到屏幕上,这样也可以提高性能。如下代码所示:
- draw() {
- var canvasBuffer = document.createElement("canvas"); canvasBuffer.width = this.canvas.width; canvasBuffer.height = this.canvas.height;
- var ctx = canvasBuffer.getContext("2d"); ctx.translate(0.5, 0.5);
- for (var i = 0; i < this.cells; i++) {
- } ctx.stroke(); this.drawBorder(ctx, cellWidth, cellHeight); console.log("draw"); this.canvas.getContext("2d").drawImage(canvasBuffer, 0, 0);
- }
先动态创建一个 canvas 节点,获取它的 context,在上面画图,画好之后再用原先的 canvas 的 context 的 drawImage 把它画到屏幕上去。
然后就可以写驱动代码了,如下画一个 50 * 50 的迷宫,并统计一下时间:
- const column = 50,
- row = 50;
- var canvas = document.getElementById("maze");
- var maze = new Maze(column, row, canvas); console.time("generate maze");
- maze.generate();
- console.timeEnd("generate maze");
- console.time("draw maze");
- maze.draw();
- console.timeEnd("draw maze");
画出的迷宫:
运行时间:
可以看到画一个 2500 规模的迷宫,draw 的时间还是很少的,而生成的时间也不长,但是我们发现一个问题,就是迷宫的有些格子是封闭的:
这些不能够进去的格子就没用了,这不太符合迷宫的特点。所以不能存在自我封闭的格子,由于生成的时候是判断第一个格子有没有和最后一个连通,现在改成第一个格子和所有的格子都是连通的,也就是说可以从第一个格子到达任意一个格子,这样迷宫的误导性才比较强,如下代码所示:
- linkedToFirstCell() {
- for (var i = 1; i < this.cells; i++) {
- if (!this.unionSets.sameSet(0, i))
- return false;
- }
- return true;
- }
把 while 的判断也改一下,这样改完之后,生成的迷宫变成了这样:
这样生成的迷宫看起来就正常多了,生成迷宫的时间也相应地变长:
但是我们发现还是有一些比较奇怪的格子布局,如下图所示:
因为这样布局的其实没太大的意义,如果让你手动设计一个迷宫,你肯定也不会设计这样的布局。所以我们的算法还可以再改进,由于上面是随机选取两个相邻格子,可以把它改成随机选取 4 个相邻的格子,这样生成的迷宫通道就会比较长,像上图这种比较奇芭的情况就会比较少。读者可以亲自动手试验一下。
这个模型更为常见的场景是,现在我在 A 城镇,准备去 Z 城镇,中间要绕道 B、C、D 等城镇,并且有多条路线可选,并且知道每个城镇和它连通的城镇以及两两之间距离,现在要求解一条 A 到 Z 的最短的路,如下图所示:
在迷宫的模型里面也是类似的,要求解从第一个格子到最后一个格子的最短路径,并且已经知道格子之间的连通情况。不一样的是相邻格子之间的距离是无权的,都为 1,所以这个处理起来会更加简单。
用一个贪婪算法可以解决这个问题,假设从 A 到 Z 的最短路径为 A->C->G->Z,那么这条路径也是 A 到 G、A 到 C 的最短路径,因为如果 A 到 G 还有更短的路径,那么 A 到 Z 的距离就还可以更短了,即这条路径不是最短的。因此我们从 A 开始延伸,一步步地确定 A 到其它地点的最短路径,直到扩散到 Z。
在无权的情况下,如上面任意相邻城镇的距离相等,和 A 直接相连的节点必定是 A 到这个节点的最短路径,如上图 A 到 B、C、F 的最短路径为 A->B、A->C、A->F,这三个点的最短路径可标记为已知。和 C 直接相邻的是 G 和 D,C 是最短的,所以 A->C-G 和 A->C->D 也是最短的,再往下一层,和 G、D 直接相连的分别是 E 和 Z,所以 A->C->G->Z 和 A->C->D->E 是到 Z 和 E 的一条最短路径,到此就找到了 A->Z 的最短路线。E 也可以到 Z,但是由于 Z 已经被标为已知最短了,所以通过 E 的这条路径就被放弃了。
和 A 直接相连的做为第一层,而和第一层直接相连的做为第二层,由第一层到第二层一直延伸目标结点,先被找到的节点就会被标记为已知。这是一个广度优先搜索。
而在有权的情况下,刚开始的时候 A 被标记为已知,由于 A 和 C 是最短的,所以 C 也被标记为已知,B 和 F 不会标记,但是它们和 A 的距离会受到更新,由初始化的无穷大更新为 A->B 和 A->F 的距离。在已查找到但未标记的两个点里面,A->F 的距离是最短的,所以 F 被标记为已知,这是因为如果存在另外一条更短的未知的路到 F,它必定得先经过已经查找到的点(因为已经查找过的点是 A 的必经之路),这里面已经是最短的了,所以不可能还有更短的了。F 被标记为已知之后和 F 直接相连的 E 的距离得到更新,同样地,在已查找到但未标记的点里面 B 的距离最短,所以 B 被标记为已知,然后再更新和 B 相连的点的距离。重复这个过程,直到 Z 被标记为已知。
标记起始点为已知,更新表的距离,再标记表里最短的距离为已知,再更新表的距离,重复直到目的点被标记,这个算法也叫 Dijkstra 算法。
现在来实现一个无权的最短路径,如下代码所示:
- calPath() {
- var pathTable = new Array(this.cells);
- for (var i = 0; i < pathTable.length; i++) { pathTable[i] = {
- known: false,
- prevCell: -1
- };
- } pathTable[0].known = true;
- var map = this.linkedMap; //用一个队列存储当前层的节点,先进队列的结点优先处理
- var unSearchCells = [0];
- var j = 0;
- while (!pathTable[pathTable.length - 1].known) {
- while (unSearchCells.length) {
- var cell = unSearchCells.pop();
- for (var i = 0; i < map[cell].length; i++) {
- if (pathTable[map[cell][i]].known) continue; pathTable[map[cell][i]].known = true; pathTable[map[cell][i]].prevCell = cell; unSearchCells.unshift(map[cell][i]);
- if (pathTable[pathTable.length - 1].known) break;
- }
- }
- }
- var cell = this.cells - 1;
- var path = [cell];
- while (cell !== 0) {
- var cell = pathTable[cell].prevCell; path.push(cell);
- }
- return path;
- }
这个算法实现的关键在于用一个队列存储未处理的结点,每处理一个结点时,就把和这个结点相连的点入队,这样新入队的结点就会排到当前层的结点的后面,当把第一层的结点处理完了,就会把第二层的结点都 push 到队尾,同理当把第二层的结点都出队了,就会把第三层的结点推到队尾。这样就实现了一个广度优先搜索。
在处理每个结点需要需要先判断一下当前结点是否已被标记为 known,如果是的话就不用处理了。
在 pathTable 表格里面用一个 prevCell 记录到这个结点的上一个结点是哪个,为了能够从目的结点一直往前找到到达第一个结点的路径。最后找到这个 path 返回。
只要有这个 path,就能够计算位置画出路径的图,如下图所示:
这个算法的速度还是很快的,如下图所示:
当把迷宫的规模提高到 200 * 200 时:
生成迷宫的时间就很耗时了,花费了 10 秒:
于是想着用 WASM 提高生成迷宫的效率,看看能提升多少。我在《 WebAssembly 与程序编译 》这篇里已经介绍了 WASM 的一些基础知识,本篇我将用它来生成迷宫。
我在《 WebAssembly 与程序编译 》提过用 JS 写很难编译,所以本篇也直接用 C 来写。上面是用的 class,但是 WASM 用 C 写没有 class 的类型,只支持基本的操作。但是可以用一个 struct 存放数据,函数名也相应地做修改,如下代码所示:
- struct Data { int * set; int columns; int rows; int cells; int * *linkedMap;
- }
- data; void Set_union(int root1, int root2) { int * set = data.set;
- if (set[root1] < set[root2]) { set[root2] = root1;
- } else {
- if (set[root1] == set[root2]) { set[root2]--;
- } set[root1] = root2;
- }
- } int Set_findSet(int x) {
- if (data.set[x] < 0) return x;
- else return data.set[x] = Set_findSet(data.set[x]);
- }
数据类型都是强类型的,函数名以类名 Set_开头,类的数据放在一个 struct 结构里面。主要导出函数为:
- #include < emscripten.h > EMSCRIPTEN_KEEPALIVE //这个宏表示这个函数要作为导出的函数
- int * *Maze_generate(int columns, int rows) { Maze_init(columns, rows); Maze_doGenerate();
- return data.linkedMap; //return Maze_getJSONStr();
- }
传进来列数和行数,返回一个二维数组。其它代码相应地改成 C 代码,这里不再放出来。需要注意的是,由于这里用到了一些 C 内置的库,如使用随机数函数 rand(),所以不能用上文提到的生成 wasm 的方法,不然会报 rand 等库函数没有定义。
把生成 wasm 的命令改成:
emcc maze.c -Os -s WASM=1 -o maze-wasm.html
这样它会生成一个 maze-wasm.js 和 maze-wasm.wasm(生成的 html 文件不需要用到),生成的 JS 文件是用来自动加载和导入 wasm 文件的,在 html 里面引入这个 JS:
- <script src="maze-wasm.js">
- </script>
- <script src="maze.js">
- </script>
它就会自动去加载 maze-wasm.wasm 文件,同时会定义一个全局的 Module 对象,在 wasm 文件加载好之后会触发 onInit,所以调它的 api 添加一个监听函数,如下代码所示:
- var maze = new Maze(column, row, canvas);
- Module.addOnInit(function() {
- var ptr = Module._Maze_generate(column, row); maze.linkedMap = readInt32Array(ptr, column * row); maze.draw();
- });
有两种方法可以得到导出的函数,一种是在函数名前面加_,如 Module._Maze_generate,第二种是使用它提供的 ccall 或 cwrap 函数,如 ccall:
- var linkedMapPtr = Module.ccall("Maze_generate", "number", ["number", "number"], [column, row]);
第一个参数表示函数名,第二个返回类型,第三个参数类型,第四个传参,或者用 cwrap:
- var mazeGenerate = Module.cwrap("Maze_generate", "number", ["number", "number"]);
- var linkedMapPtr = mazeGenerate(column, row);
三种方法都会返回 linkedMap 的指针地址,可通过 Module.get 得到地址里面的值,如下代码所示:
- function readInt32Array(ptr, length) {
- var linkedMap = new Array(length);
- for (var i = 0; i < length; i++) {
- var subptr = Module.getValue(ptr + (i * 4), 'i32');
- var neiborcells = [];
- for (var j = 0; j < 4; j++) {
- var value = Module.getValue(subptr + (j * 4), 'i32');
- if (value !== -1) { neiborcells.push(value, 'i32');
- }
- } linkedMap[i] = neiborcells;
- }
- return linkedMap;
- }
由于它是一个二维数组,所以数组里面存放的是指向数组的指针,因此需要再对这些指针再做一次 get 操作,就可以拿到具体的值了。如果取出的值是 - 1 则表示不是有效的相邻元素,因为 C 里面数组的长度是固定的,无法随便动态 push,因此我在 C 里面都初始化了 4 个,因为相邻元素最多只有 4 个,初始时用 - 1 填充。取出非 - 1 的值 push 到 JS 的数组里面,得到一个用 WASM 计算的 linkedMap. 然后再用同样的方法去画地图。
最后再比较一下 WASM 和 JS 生成迷宫的时间。如下代码所示,运行 50 次:
- var count = 50;
- console.time("JS generate maze");
- for (var i = 0; i < count; i++) {
- var maze = new Maze(column, row, canvas); maze.generate();
- }
- console.timeEnd("JS generate maze"); Module.addOnInit(function() { console.time("WASM generate maze");
- for (var i = 0; i < count; i++) {
- var maze = new Maze(column, row, canvas);
- var ptr = Module._Maze_generate(column, row);
- var linkedMap = readInt32Array(ptr, column * row);
- } console.timeEnd("WASM generate maze");
- })
迷宫的规模为 50 * 50,结果如下:
可以看到,WASM 的时间大概快了 25%,并且有时候会观察到 WASM 的时间甚至要比 JS 的时间要长,这时因为算法是随机的,有时候拆掉的墙可能会比较多,所以偏差会比较大。但是大部份情况下的 25% 还是可信的,因为如果把随机选取的墙保存起来,然后让 JS 和 WASM 用同样的数据,这个时间差就会固定在 25%,如下图所示:
这个时间要比上面的大,因为保存了一个需要拆的墙比较多的数组。理论上不用产生随机数,时间会更少,不过我们的重点是比较它们的时间差,结果是不管运行多少次,时间差都比较稳定。
所以在这个例子里面 WASM 节省了 25% 的时间,虽然提升不是很明显,但还是有效果,很多个 25% 累积起来还是挺长的。
综上,本文用 JS 和 WASM 使用连通集算法生成迷宫,并用最短路径算法求解迷宫的路径。使用 WASM 在生成迷宫的例子里面可以提升 25% 的速度。
虽然迷宫小时候就已经在玩了,不是什么高大上的东西,但是通过这个例子讨论到了一些算法,还用到了很出名的最短路径算法,还把 WASM 实际地应用了一遍,作为学习的的模型还是挺好的。更多的算法可参考这篇《 我接触过的前端数据结构与算法 》。
浏览量: 19
来源: http://www.tuicool.com/articles/QbUNVvz