Synopsis: This project originally started out as a quick and snappy comparison of Dijkstra and A*. This however proved difficult, as I had nothing to test it on. As such, I then had to figure out many many other things, starting with, building a maze. I used mazes because I think that they are fascinating, the classic myth of the Minotaur in the labyrinth has always enticed me. So, to test Dijkstra and A*, I learned how to build a maze. Then, after building mazes, I learned to solve them, and then how to apply other methods of solving, like A* and Dijkstra.
Introduction
While at university, the discussion of various path finding and solving algorithms was often discussed, and like most things in university, we used a cookie cutter version of these algorithms to solve problems. I like to understand problems and solutions, and so I decided to see if I could use these algorithms to solve a problem of my own design and creation. Cursory google searching revealed that mazes are a great path finding problem.
Making Mazes
The first challenge to solve when solving a maze is having a maze to solve. So instead of just googling mazes and solving something someone else built, I wanted to solve any arbitrary maze. The best way to solve something arbitrary, is to build an arbitrary something generator. And that is exactly what I did. Research through google showed many different algorithms to generate mazes. I wanted mazes that were difficult for humans to solve, with long paths that spiral out of control. I wanted a maze that mirrored real life – one where you could spend quite some time on the wrong path before realizing that there was a mistake. As such, I settled on the recursive back tracking algorithm.
Recursive Backtracking is a very intuitive way of making a maze, it does however use recursion, which some languages (python) are not very good at. My first ever course at uni was all about recursive programming, so I am very familiar with the principal, but I have very distinct memories of pulling my hair at maximum recursion depth errors in python. So, I had to re-adapt the algorithm to no longer be recursive, and instead have it nested in a loop. This was clunkier and less elegant than the recursive solution, but it still worked.
The recursive back tracking algorithm starts at a certain point (the entrance) and then looks for every possible move around it. It then makes that move, and pushes the move made onto a stack. It then repeats (recursively), until it can’t make any more moves. Then it pops moves off the stack until it finds one that can make moves, and starts again, making moves until it is stuck. Then, pops until it can make moves again, and so on. When it has no moves left in the stack, the game is done. This however, does not add an exit, so we then look for every white square in the last column, and then randomly pick one, then turn it white, to give us an exit. This can all be seen in the following code block, which generates mazes on the home page.
//Setup canvas
<canvas id="Maze" width="300" height="300" style="border:1px solid #000000;"></canvas>
<script>
// Function includes all moves made and current tile, is to check to see if there are any white squares around a tile, and is a helper function to get valid moves
function getValidMovesHelper(moves, tile){
//Assumes that it is a valid move, then proves otherwise
let out = true;
//surrounding here is the surrounding moves
let surrounding = [];
//If there is any surrounding tiles, we push back 1 to surrounding
if(moves.includes(tile+20)){
surrounding.push(1);
}
if(moves.includes(tile-20)){
surrounding.push(1);
}
if(moves.includes(tile-1)){
surrounding.push(1);
}
if(moves.includes(tile+1)){
surrounding.push(1);
}
//If there is any more than one item in the surrounding tiles, it is an invalid move, and we return false
if(surrounding.length > 1){
out = false;
}
return out;
}
// getValid moves, takes a list of all moves, a tile, and a list of all walls and returns all surrounding tiles that it can move to
function getValidMoves(moves, tile, walls){
// Out hereis the output moves
let out = [];
//Check up
if(!moves.includes(tile-1)){
if(!walls.includes(tile-1)){
if(getValidMovesHelper(moves, tile-1)){
out.push(tile-1);
}
}
}
//Check Down
if(!moves.includes(tile+1)){
if(!walls.includes(tile+1)){
if(getValidMovesHelper(moves, tile+1)){
out.push(tile+1);
}
}
}
//Check Left
if(!moves.includes(tile-20)){
if(!walls.includes(tile-20)){
if(getValidMovesHelper(moves, tile-20)){
out.push(tile-20);
}
}
}
//Check Right
if(!moves.includes(tile+20)){
if(!walls.includes(tile+20)){
if(getValidMovesHelper(moves, tile+20)){
out.push(tile+20);
}
}
}
return out;
}
//gen Maze helper loops through the valid moves, and actually implements recursive back tracking
function genMazeHelper(moves, walls){
//stacks is the stack of all moves
var stacks = [];
// copy all moves into the stack
for(i = 0; i < moves.length; i++){
stacks.push(moves[i]);
}
// declare variables so I don't do it a million times in a while loop
var curTile = 0;
var allMoves = [];
var randNum = 0;
var sizeStack = stacks.length;
// While there are moves in the stack, see if there are any valid moves from the top, if there is, make moves until you can't and push to stack and allMoves, then pop until 0.
while(stacks.length > 0){
sizeStack = stacks.length;
curTile = stacks[sizeStack-1];
allMoves = getValidMoves(moves, curTile, walls);
if(allMoves.length == 0){
stacks.pop();
}
else{
randNum = Math.floor(Math.random() * allMoves.length);
moves.push(allMoves[randNum]);
stacks.push(allMoves[randNum]);
}
}
return moves;
}
function genMaze(){
// Arrays represents maze, size 20*20
// first, fill out maze with Black.
let out = [];
for(let i = 0; i < 400; i++){
out.push(1);
}
let walls = []
//Then fill out the maze. The edges are 0->19; 379->399; 20, 40, 60, 80 so ADD TO LIST
for(let i = 0; i < 20; i++){
walls.push(i);
walls.push(i+379);
walls.push(i*20);
walls.push(i*20-1);
}
walls.push(399);
//Now draw out start moves
let moves = [];
moves.push(30);
moves.push(31);
moves.push(32);
moves.push(33, 34, 29, 29);
moves.push(51);
//Now, we need to generate the rest of the maze!
moves = genMazeHelper(moves, walls);
//Add entrance
moves.push(11);
// Add the exit
let validExits = [];
for(let m = 360; m < 380; m++)
{
if(moves.includes(m)){
validExits.push(m);
}
}
let randNum = Math.floor(Math.random() * validExits.length);
moves.push(validExits[randNum]+20);
for(let n = 0; n < moves.length; n++){
let cur2 = moves[n];
out[cur2] = 0;
}
return out;
}
//Init canvas and actually draw
var c = document.getElementById("Maze");
c.parentElement.style.textAlign = "center";
var ctx = c.getContext("2d");
let curMaze = genMaze()
var total = 0;
for(let i = 0; i < 20; i++){
for(let j = 0; j < 20; j++){
var val = curMaze[total];
if(val != 0){
ctx.beginPath();
ctx.fillRect(i*15, j*15, 15, 15);
ctx.stroke();
}
total = total + 1;
}
}
</script>That is a teeny tiny 20*20 maze. So, for a bigger one, see below, this is a dynamically generated maze, new every time, guaranteed to have a solution:
So now, we have a maze generated that looks pretty, we need to solve it.
My Solution
As any good Scientist or Engineer knows, you should always try and come up with your own conclusion/ solutions before realizing your idea is slow and garbage and some crazy person like Dijkstra has come up with a near perfect mathematical solution to the problem. So, in that spirit, here is the brief explanation of my solution.
Check through every tile of the maze, and check if we are on a dead end square (one surrounding tile). Then check the surrounding tile and see if it is a dead end as well, then mark it as a dead end as well. Then keep going until we can get through the whole maze without finding any dead ends, and we have our path through the maze. It is reminiscent of when I solved mazes as a kid and would colour in all the dead ends red until the maze was solved.
This is not a very good solution. It requires many iterations through the maze, and, in the worst case it could take quite some time. However, it was my own solution before I stole someone elses idea and it is fun because of that. So, without further ado, see my solution below, stepping through and looking pretty, using the maze from above.
Now, the question becomes, how to make this faster? The above solver is deliberately slowed because I like how it looks, however, it is not very efficient. It needs to look through the whole maze, and finds any dead end it can, then it starts again. To speed this up, there are two options. We can store the earliest square found, and the oldest square found with each iteration, and then only search in that zone. This means that we will reduce the search space with each successive loop, and we can cut out big chunks of the maze that do not need to be checked. This can further be optimized, by keeping a track of the white squares, and only checking them. This way, we are skipping checks for any of the black squares that sit in our maze, and we can improve performance accordingly.
In addition to this, when we find a dead end, we can then search all the surrounding tiles and see if they are now dead ends as well. This means, that some of the longer paths will be almost the same computation time as the shorter paths, and we can stop stepping through the whole maze so quickly. It is difficult to quantify how much time this will save our algorithm, but there is a comparison of all the times in the end section.
Dijkstra
Dijkstra's algorithm finds the shortest path from a root node to every other node, until a target is reached. It is often considered to be one of the most useful graph theory algorithms and it can be modified easily to solve many different problems. It is useful because it does not require searching every possible path, unlike some other algorithms. It is used in network routing, believed to be used in mapping, such as google maps, etc. Much like recursive back tracking mentioned before, it is a multi-tool of an algorithm and can be used to solve a variety of different problems.
How does it work? Well, it is quite simply, we have a start node and a list of surrounding candidate nodes. They are all assigned a value of infinity, assuming they are infinitely far away, except for our origin point. Then, find the closest node, and repeat until we find destination. If we can't find the destination, we back track through our list, and try again with previous nodes.