This paper will try to use Canvas + WASM to draw a maze. The generation algorithm mainly uses the connected set algorithm, and wASM is mainly used to improve operation efficiency. Then a shortest path algorithm is used to find the way out of the maze, and the final result is as follows:
1. Use connected set algorithm to generate maze
The algorithm to generate a maze is actually very simple, assuming the size of the maze is 10 * 10, that is, the maze has 100 cells, by repeatedly randomly removing the walls in the middle of the 100 cells, until you can walk from the first cell to the last cell, that is, the first cell and the last cell are in the same connected set. The specific operations are as follows:
(1) Generate 100 cells, each cell is not connected
(2) Randomly select two adjacent cells, which can be left and right or upper and lower adjacent, and judge whether these two cells are in the same connected set, that is, whether they can go from one cell to another. If not, remove the wall between them and make them connected and in the same connected set.
(3) Repeat step 2 until the first cell is connected to the last cell.
So how do we represent this connected set? We use a one-dimensional array to represent the different connected sets. When initialized, the value of each cell is -1, as shown in the figure below. Suppose the maze is 3 * 3, that is, there are 9 cells:
Location of each index in the maze:
Negative numbers mean they’re different connected sets, because we haven’t started tearing down the walls yet, so they’re all independent at first.
Now remove the wall between 3 and 4, that is to say, make 3 and 4 connected. Set the value of 4 to 3, indicating that 4 is in the connected set of 3, and 3 is their root, as shown in the figure below:
Then take down 5 and 8:
Then take down 4 and 5:
At this time, 3, 4, 5 and 8 are in the same connected set, but 0 and 8 are still two different connected sets. At this time, the wall between 3 and 0 is removed:
Since the connected set of 0 is 3, and the connected set of 8 is also 3, that is, they are in the same connected set, so at this time the road from the first cell to the last cell is connected, and a maze is generated.
We use the UnionSet class to represent the connected set, as shown in the following code:
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)); }}Copy the codeWe implemented a connected set in 22 lines of code. The code above should be easier to understand, as illustrated above. If the findSet function finds the root of a set that contains a negative number, as long as the root is a positive number, it points to another node and goes up through the while loop until it reaches a negative number. UnionElement can connect two elements, find their set, and then union their set into the same connected set.
Now write a Maze that controls the creation of a Maze and combines an instance of UnionSet, as shown below:
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; }}Copy the codeThe Maze constructor takes three arguments, the first two being the number of columns and rows of the Maze, and the last being the Canvas element. Initialize a connected set in the constructor, which is the core model of Maze, as well as a linkedMap that holds the removed walls for the Canvas drawing.
The Maze class adds another function to generate the Maze, as shown in the following code:
// Generate a maze
generate(){
// Every time I take two adjacent cells, if they are not in the same connected set,
// Remove the middle wall and connect them together to form a connected set
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]); }}}Copy the codeThe core logic for generating a maze is simple: in the while loop, determine whether the first cell is connected to the last cell, if not, randomly select two adjacent cells at a time, connect them if they are not in the same connected set, and record the removed walls into the linkedMap.
How do I pick two adjacent cells at random? There is no technical difficulty with this, but it takes some thinking to implement it, because there are no complete four adjacent cells on the edge of the grid, some have only two, some have three. The author implemented it in this way, which is relatively simple:
// Pick two random adjacent cells
pickRandomCellPairs(){
var cell = (Math.random() * this.cells) >> 0;
0 = up, 1 = right, 2 = down, 3 = left
var neiborCells = [];
var row = (cell / this.columns) >> 0,
column = cell % this.rows;
// Not the first row with adjacent elements above
if(row ! = =0){
neiborCells.push(cell - this.columns);
}
// Not the last row has the following adjacent elements
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]];
}Copy the codeFirst, choose a random cell, then get its number of rows and columns, and then judge its boundary case in turn. If it’s not in the first row, it has an adjacent cell in the top row, if it’s not in the last row it has an adjacent cell in the bottom row, and similarly, if it’s not in the first column it has an adjacent cell in the left, if it’s not in the last column it has an adjacent cell in the right. Place the eligible cells in an array, and then pick a random element from that array. So you have two random adjacent elements.
The other addLinkedMap function is simpler to implement as follows:
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); }}Copy the codeGenerated a maze of core logic basically completed, but the above connected set of code can be optimized, and one is findSet function, can the current in findSet connected set of elements to store values directly into the root element, so you need not to find the chain to form a long, or form a high tree, can be directly one pace reachs the designated position, The following code looks like this:
findSet(x){
if(this.set[x] < 0) return x;
return this.set[x] = this.findSet(this.set[x]);
}Copy the codeThis code uses a recursion that changes the value as it looks up.
The union function can also make an optimization. FindSet can make the height of the tree smaller, but the union operation before it is smaller can also be optimized, as shown in the following code:
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; }}Copy the codeThe purpose of this code is also to reduce the length of the search chain or the height of the tree, by integrating a shorter connected set into a subtree of a higher connected set, so that the combined height of the two connected sets is the same height as that connected set. If the height of two connected sets is the same, one of them will be selected as the root, and the search length of the nodes of the other tree will undoubtedly be increased by 1, because there is a new root, that is to say, the height of the tree will be increased by 1. As the storage is negative, the subtraction operation will be carried out. The same is true when judging the height of a tree, smaller means higher.
As it turns out, code execution is more than half as fast after this change.
Now that the maze is generated, start drawing.
2. Draw mazes on Canvas
Write a Canvas HTML element as follows:
<canvas id="maze" width="800" height="600"></canvas>Copy the codeNote that the width and height of canvas should be written with the properties of width and height. If style is used, it will be stretched, and there will be ambiguity.
How do I draw a line on a canvas? The following code looks like this:
var canvas = document.getElementById("maze");
var ctx = canvas.getContext("2d");
ctx.moveTo(0.0);
ctx.lineTo(100.100);
ctx.stroke();Copy the codeThis code draws a line from (0, 0) to (100, 100), which are the three base canvas apis we’ll use in this article.
We already have a linkedMap, and for a 3 by 3 table, print the linkedMap to get the following table.
As you can see from the table above, there is no wall between 0 and 3, so when you draw a line between 0 and 3, you don’t draw a line between 3 and 4, you don’t draw a line between them. Draw a vertical line to the right and a horizontal line to the bottom of each normal cell, but not the one that has been removed, so you get the following code:
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 pixels to avoid blur
ctx.translate(0.5.0.5);
for(var i = 0; i < this.cells; i++){
var row = i / this.columns >> 0,
column = i % this.columns;
// Draw a vertical line on the right
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);
}
// Draw the line below
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); }}// Last stroke to improve performance
ctx.stroke();
// Draw the four borders of the maze
this.drawBorder(ctx, cellWidth, cellHeight);
}Copy the codeLinkMap [I] = linkMap[I] = linkMap[I] = linkMap[I] = linkMap Because the border of the maze is drawn at the back, it is special, the vertical line of the last grid is not drawn, because it is the exit of the maze. The positions of moveTo and lineTo need to be calculated each time.
Note that the above code has two optimizations: first translate 0.5 pixels, in order to make the position of the canvas line just above the pixel, because our lineWidth is 1, if it does not translate, it will draw the position as shown in the middle of the picture below, with two adjacent pixels taking up half a pixel. The display will change to virtual, but after 0.5 pixels translate, it will be drawn exactly at the pixel. See: HTML5 Canvas — Crisp Lines every time.
The second optimization is to stroke after all moveTo and lineTo have been completed, so that it is a line, which can greatly improve the efficiency of drawing. This is very important, because I didn’t do this at the beginning, so I couldn’t draw when I had a little bit more lattice, but when I changed it to this, it made it a lot more efficient.
Another optimization we can make is to use the dual-cache technique. Instead of drawing directly on the screen, we will first Paint the canvas in memory and then Paint it on the screen at the end of the process. This will also improve performance. The following code looks like this:
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);
}Copy the codeFirst create a canvas node dynamically, get its context, draw a picture on it, and then use the drawImage of the original Canvas context to draw it on the screen.
Then you can write the driver code, as follows draw a 50 * 50 maze, and count the time:
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");Copy the codeThe maze:
Running time:
It can be seen that drawing a 2500 scale maze, draw time is still very small, and the generation time is not long, but we found a problem, is that some of the maze cells are closed:
These impenetrable cells are useless, which is not very characteristic of a maze. So can’t exist self-enclosed grid, due to the generated when did is the first grid and the last connected, now change to the first grid and all of the grid are connected, that is to say, can from the first grid to any a grid, so a maze of misleading, as shown in the following code:
linkedToFirstCell(){
for(var i = 1; i < this.cells; i++){
if(!this.unionSets.sameSet(0, i))
return false;
}
return true;
}Copy the codeChange the while judgment, too, and the resulting maze looks something like this:
The resulting maze looks much more normal and takes a correspondingly longer time to generate:
However, we found some strange grid layouts, as shown below:
It doesn’t make a lot of sense, and if you were to design a maze by hand, you wouldn’t do it either. Therefore, our algorithm can be further improved. Since the above is a random selection of two adjacent grids, it can be changed to a random selection of four adjacent grids, so that the maze channels generated will be longer, and there will be fewer cases of comparison like the above. Readers can try it out for themselves.
3. Use the shortest path algorithm to find a way out of the maze
The more common scenario of this model is that NOW I am in town A and am going to town Z. I need to bypass towns B, C and D in the middle, and I have multiple routes to choose from, and I know each town and its connected towns as well as the distance between them. Now I need to solve A shortest road from town A to Z, as shown in the following figure:
Similarly, in the maze model, the shortest path from the first cell to the last cell is required, and the connectivity between the cells is already known. The difference is that the distance between the adjacent cells is not authorized, it’s all equal to 1, so it’s a little bit easier to deal with.
A greedy algorithm can solve this problem, assuming that the shortest path from A to Z is A->C->G->Z, then this path is also the shortest path from A to G and from A to C, because if there are shorter paths from A to G, then the distance from A to Z can be even shorter, i.e. this path is not the shortest. So we start at A and work our way down the shortest path from A to other locations until we get to Z.
In the case of no right, if the distance between any neighboring towns above is equal, the node directly connected to A must be the shortest path from A to this node. For example, the shortest path from A to B, C and F in the figure above is A->B, A->C and A->F, and the shortest path of these three points can be marked as known. A->C->G->Z and A->C->D->E are the shortest paths to Z and E. E could also go to Z, but since Z is already labeled as the shortest known path, the path through E is abandoned.
The node directly connected to A is the first layer, and the node directly connected to the first layer is the second layer, extending from the first layer to the second layer, and the node found first will be marked as known. This is a breadth-first search.
In the entitled case, A is initially marked as known, and since A and C are the shortest, C is also marked as known. B and F are not marked, but their distances from A are updated from the initialized infinity to A->B and A->F. To have but not mark to find the two points, A – > F is the shortest distance, so F is marked as known, this is because if there is another less unknown road to F, it will have to pass already find points (because have been looking for is A part of the route), which is the shortest, it is not possible and shorter. After F is marked as known, the distance of E directly connected to F is updated. Similarly, B has the shortest distance among the points that have been found but not marked, so B is marked as known, and then the distance of the points connected to B is updated. Repeat this process until Z is marked as known.
Mark the starting point as known, update the table distance, then mark the shortest distance in the table as known, then update the table distance, repeat until the destination point is marked, this algorithm is also called Dijkstra algorithm.
Now implement an unauthorized shortest path as shown in the following code:
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;
// Use a queue to store the nodes of the current layer. The nodes of the advanced queue are processed first
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;
}Copy the codeThis algorithm is the key to use a queue to store unprocessed node, each dealing with a node, and the nodes connected to the team, the new node squad will row at the back of the current layer node, when the first layer of the node processing done, and will push the second layer of the node to a party, must be with the second floor of the nodes are out of the team, It pushes the third tier of nodes to the back of the queue. This enables a breadth-first search.
Before processing each node, check whether the current node is marked as known. If so, skip the processing.
Use a prevCell in the pathTable to record which node is the previous one, in order to find the path to the first node all the way from the destination node. Finally find the path and return.
As long as you have this path, you can calculate the position and draw a graph of the path, as shown below:
The speed of this algorithm is still very fast, as shown in the figure below:
When increasing the maze size to 200 * 200:
The maze takes a long time to generate, taking 10 seconds:
So I thought about using WASM to improve my maze-generation efficiency and see how much I could improve it. I’ve covered some of the basics of WASM in WebAssembly and Program Compilation, and in this article I’ll use it to generate mazes.
4. Create mazes with WASM
I mentioned in WebAssembly and Programming that writing in JS is difficult to compile, so THIS article will be written directly in C. WASM uses C to write classes without classes and supports only basic operations. However, you can use a struct to store data and change the function name accordingly, as shown in the following code:
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]);
}Copy the codeData types are strongly typed, function names start with the class name Set_, and the class’s data is stored in a struct structure. The main derived function is:
#include <emscripten.h>
EMSCRIPTEN_KEEPALIVE // This macro indicates that the function is to be exported
int **Maze_generate(int columns, int rows){
Maze_init(columns, rows);
Maze_doGenerate();
return data.linkedMap;
//return Maze_getJSONStr();
}Copy the codePass in the number of columns and rows and return a two-dimensional array. The rest of the code will be C code, and I won’t show it here. Rand () is a random number function used by wASM. The rand() function is a random number function used by WASM.
Change the command to generate wASM to:
emcc maze.c -Os -s WASM=1 -o maze-wasm.html
This generates a maze-wasm.js and maze-wasm.wasm (the generated HTML file is not needed). The generated JS file is used to automatically load and import the WASM file.
<script src="maze-wasm.js"></script>
<script src="maze.js"></script>Copy the codeIt will automatically load the maze-wasm.wasm file and define a global Module object that will trigger onInit when the wASM file is loaded, so call its API and add a listener like this:
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();
});Copy the codeThere are two ways to get an exported function. One is to prefix the function name with _, such as module._maze_generate, or the other is to use the ccall or cwrap function it provides, such as ccall:
var linkedMapPtr = Module.ccall("Maze_generate"."number"["number"."number"], [column, row]);Copy the codeThe first argument represents the function name, the second return type, the third argument type, the fourth argument type, or cwrap:
var mazeGenerate = Module.cwrap("Maze_generate"."number"["number"."number"]);
var linkedMapPtr = mazeGenerate(column, row);Copy the codeAll three methods return the linkedMap pointer address, which can be obtained from module. get, as shown in the following code:
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;
}Copy the codeBecause it’s a two-dimensional array, the array contains Pointers to the array, so you need to do another get on those Pointers to get the value. If I take out a value of -1, it means that it’s not a valid neighboring element, because the length of the array in C is fixed, so I can’t push it dynamically, so I initialize 4 elements in C, because there are only 4 adjacent elements at most, and I start with -1. Take the non-1 value and push it into the JS array to get a linkedMap calculated with WASM. Then use the same method to draw the map.
Finally, compare the maze-generation times of WASM and JS. Run 50 times as shown in the following code:
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");
})Copy the codeThe maze is 50 by 50, and the result is as follows:
It can be seen that the time of WASM is about 25% faster, and sometimes it can be observed that the time of WASM is even longer than that of JS. At this time, because the algorithm is random, sometimes there may be more walls removed, so the deviation will be relatively large. But 25% is still reliable in most cases, because if you save a randomly selected wall and then use the same data for JS and WASM, the time difference will be fixed at 25%, as shown in the following figure:
This takes longer than the above because it keeps an array with more walls to tear down. Theoretically, without generating random numbers, the time would be less, but our point is to compare the time difference between them, and it turns out that no matter how many times we run them, the time difference is stable.
So in this example, WASM saves 25% of the time. It’s not a huge improvement, but it works, and a lot of 25% adds up.
To sum up, this paper uses JS and WASM to generate the maze using the connected set algorithm, and uses the shortest path algorithm to solve the maze path. Using WASM increases the speed of mazes by 25%.
Although the maze has been playing since childhood, is not what high things, but through this example to discuss some algorithms, but also used the famous shortest path algorithm, but also the WASM practical application again, as a learning model or very good. For more algorithms, see this article “Front-end Data Structures and Algorithms I’ve worked with.”