Solving your maze

This is the third post on the subject of JavaScript mazes. the first post saw the creation of a random maze and the second looked at how such a maze could be transformed into JavaScript code ready to be used within a First Person Shooter style Ray casting project. This post looks at solving the maze with a general algorithm that should be able to find a valid path between any two locations within a maze.

The process is fairly simple and starts from a specified cell walking the maze until it reaches the specified end point. The process identifies the cells that the path could move to from any current cell. A random choice is then made and the path extended. If there is no valid way forward then the process moves backwards through the path until an alternative way forward is found. In this demonstration, the path is marked by green blocks of colour and any routes found to be invalid are marked in red. When the process reaches the end point then the number of steps from start to finish point is displayed. The path array holds the route. The badPath array holds all of the invalid cells and is only there in case anyone fancies resetting the relevant cell colours.

The solve() function is called from the initialise() function after a given random maze has been created.

solve({y:0, x: 0}, {y: maze.cellsHigh-1, x: maze.cellsWide - 1});

The solve() function follows:

function solve(from, to){ resetGrid(); let current = maze.map[from.y][from.x], end = maze.map[to.y][to.x]; current.visited = true; colourCell(current, "green"); let path = [current]; let badPath = []; while((current.x !== end.x) || (current.y !== end.y)){ possibles = getPossibles(current); if(possibles.length){ let next = possibles[Math.floor(maze.rand() * possibles.length)]; next.step = current.step + 1; next.visited = true; colourCell(next, "green"); path.push(next); } else { let bad = path.pop(); colourCell(bad, "red"); badPath.push(bad); } current = path[path.length-1]; } alert("Path has " + current.step + " steps"); }

That function calls resetGrid() which just resets the visited Boolean for each cell and initialises a new member called step.

function resetGrid() { for(let i = 0; i < maze.cellsHigh; i++){ for(let j = 0; j < maze.cellsWide; j++){ maze.map[i][j].visited = false; maze.map[i][j].step = 0; } } }

There is also a call to getPossibles() which returns an array of possible next steps from a given cell.

function getPossibles(current){ possibles = []; let x = current.x, y = current.y; if(!current.up && !maze.map[y-1][x].visited){ possibles.push(maze.map[y-1][x]); } if(!current.down && !maze.map[y+1][x].visited){ possibles.push(maze.map[y+1][x]); } if(!current.left && !maze.map[y][x-1].visited){ possibles.push(maze.map[y][x-1]); } if(!current.right && !maze.map[y][x+1].visited){ possibles.push(maze.map[y][x+1]); } return possibles; }

The final call is to colourCell() which highlights the search path.

function colourCell(cell, colour){ let x = (cell.x) * (maze.side + maze.wallWidth) + maze.wallWidth * 2; let y = (cell.y) * (maze.side + maze.wallWidth) + maze.wallWidth * 2; view.ctx.fillStyle = colour; view.ctx.fillRect(x,y,maze.side - maze.wallWidth * 2,maze.side- maze.wallWidth*2); }

There are other maze (and more general "shortest path") algorithms that you might like to explore. This one works fine for this maze type where all cells are connected so we did not have to consider the possibility of failing to find the required path.

The above example includes a very long path from top left to bottom right but it got there.