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.<\/p>\n\n\n\n
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. <\/p>\n\n\n\n
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.<\/p>\n\n\n\n
Recursive Backtracking<\/a> is a very intuitive way of making a maze, it does however use recursion, which some languages (python<\/a>) 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. <\/p>\n\n\n\n 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. <\/p>\n\n\n\n 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:<\/p>\n\n\n\n\/\/Setup canvas\n<canvas id=\"Maze\" width=\"300\" height=\"300\" style=\"border:1px solid #000000;\"><\/canvas>\n<script>\n\/\/ 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\nfunction getValidMovesHelper(moves, tile){\n \/\/Assumes that it is a valid move, then proves otherwise\n let out = true;\n \/\/surrounding here is the surrounding moves\n let surrounding = [];\n \/\/If there is any surrounding tiles, we push back 1 to surrounding\n if(moves.includes(tile+20)){\n surrounding.push(1);\n }\n if(moves.includes(tile-20)){\n surrounding.push(1);\n }\n if(moves.includes(tile-1)){\n surrounding.push(1);\n }\n if(moves.includes(tile+1)){\n surrounding.push(1);\n }\n \/\/If there is any more than one item in the surrounding tiles, it is an invalid move, and we return false\n if(surrounding.length > 1){\n out = false;\n }\n return out;\n}\n\n\/\/ 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\nfunction getValidMoves(moves, tile, walls){\n \/\/ Out hereis the output moves\n let out = [];\n \n \/\/Check up\n if(!moves.includes(tile-1)){\n if(!walls.includes(tile-1)){\n if(getValidMovesHelper(moves, tile-1)){\n out.push(tile-1);\n }\n }\n }\n \/\/Check Down\n if(!moves.includes(tile+1)){\n if(!walls.includes(tile+1)){\n if(getValidMovesHelper(moves, tile+1)){\n out.push(tile+1);\n }\n }\n }\n \/\/Check Left\n if(!moves.includes(tile-20)){\n if(!walls.includes(tile-20)){\n if(getValidMovesHelper(moves, tile-20)){\n out.push(tile-20);\n }\n }\n }\n \/\/Check Right\n if(!moves.includes(tile+20)){\n if(!walls.includes(tile+20)){\n if(getValidMovesHelper(moves, tile+20)){\n out.push(tile+20);\n }\n }\n }\n return out;\n}\n\n\/\/gen Maze helper loops through the valid moves, and actually implements recursive back tracking\nfunction genMazeHelper(moves, walls){\n \/\/stacks is the stack of all moves\n var stacks = [];\n \/\/ copy all moves into the stack\n for(i = 0; i < moves.length; i++){\n stacks.push(moves[i]);\n }\n \/\/ declare variables so I don't do it a million times in a while loop\n var curTile = 0;\n var allMoves = [];\n var randNum = 0;\n var sizeStack = stacks.length;\n \/\/ 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. \n while(stacks.length > 0){\n sizeStack = stacks.length;\n curTile = stacks[sizeStack-1];\n allMoves = getValidMoves(moves, curTile, walls);\n if(allMoves.length == 0){\n stacks.pop();\n }\n else{\n randNum = Math.floor(Math.random() * allMoves.length);\n moves.push(allMoves[randNum]);\n stacks.push(allMoves[randNum]);\n }\n }\n return moves;\n}\n\nfunction genMaze(){\n \/\/ Arrays represents maze, size 20*20\n \/\/ first, fill out maze with Black. \n let out = [];\n for(let i = 0; i < 400; i++){\n out.push(1);\n }\n let walls = []\n \/\/Then fill out the maze. The edges are 0->19; 379->399; 20, 40, 60, 80 so ADD TO LIST\n for(let i = 0; i < 20; i++){\n walls.push(i);\n walls.push(i+379);\n walls.push(i*20);\n walls.push(i*20-1);\n }\n walls.push(399);\n \/\/Now draw out start moves\n let moves = [];\n moves.push(30);\n moves.push(31);\n moves.push(32);\n moves.push(33, 34, 29, 29);\n moves.push(51);\n \n \/\/Now, we need to generate the rest of the maze!\n moves = genMazeHelper(moves, walls);\n \/\/Add entrance\n moves.push(11);\n \/\/ Add the exit\n let validExits = [];\n for(let m = 360; m < 380; m++)\n {\n if(moves.includes(m)){\n validExits.push(m);\n }\n }\n let randNum = Math.floor(Math.random() * validExits.length);\n moves.push(validExits[randNum]+20);\n for(let n = 0; n < moves.length; n++){\n let cur2 = moves[n];\n out[cur2] = 0;\n }\n return out;\n}\n\n\/\/Init canvas and actually draw\nvar c = document.getElementById(\"Maze\");\nc.parentElement.style.textAlign = \"center\";\nvar ctx = c.getContext(\"2d\");\nlet curMaze = genMaze()\nvar total = 0;\nfor(let i = 0; i < 20; i++){\n for(let j = 0; j < 20; j++){\n var val = curMaze[total];\n if(val != 0){\n ctx.beginPath();\n ctx.fillRect(i*15, j*15, 15, 15);\n ctx.stroke();\n }\n total = total + 1;\n }\n}\n<\/script><\/code><\/pre>\n\n\n\n