Tremaux Algorithm
The Tremaux algorithm is similar to actually walking through the maze. Only the immediate tiles visible to you can be followed.
It begins in a random direction and continues until it hits a wall. It then turns right, until a path is available to walk. Each time the algorithm takes a step, it marks the tile as visited.
The algorithm always tries to first visit an un-visited tile. However, if no new tiles are found, it will backtrack over a visited tile.
It will never visit the same tile more than twice (with the only exception being if the algorithm is stuck in a dead-end, in which case it will re-visit a tile it's already backtracked over, in order to exit the trap).
The maze solution is all tiles that have been visited once.
A* Search Algorithm
A* search is similar to having an aerial view of the maze before walking through it. It uses the maze end point to calculate a score from each neighboring tile. It intelligently walks down multiple paths, seemingly at the same time, until it reaches the end.
You would not be able to use this algorithm if you were physically traversing the maze. At least, not easily.
|
|
|
|
|
|
Build your own maze! This app supports query string url parameters! That means, with a little whizbang JSON, you can change the url and provide your very own maze for the algorithm to run through! Cool?
Examine the urls of the above example mazes to see how it works. Read below for the details.
Edit the url and append a string similar to the following:
?maze={"start": {"x": 1, "y": 0}, "end": {"x": 3, "y": 0}, "width": 5, "height": 6, "map": "*.*.**.*.**.*.**...******"}
| Property |
Description |
| start (x, y) |
Starting x,y coordinate to begin traversing the map |
| end (x, y) |
Exit x,y coordinate to indicate when you have exited the map |
| width |
Width of the map (dependent on the height). For example: *** equals a width of 3 |
| height |
Height of the map (dependent on the width). For example: **.*** with a width of 3, has a height of 2 |
| map |
Content of the maze. Use an asterik * to denote a wall. Use any other character to denote a walkable tile. |
Remove all linebreaks from the map when sending in url
{"start": {"x": 3, "y": 0},
"end": {"x": 6, "y": 0},
"width": 20,
"height": 10,
"map": "
***.**.*************
***....*************
**..****.........***
*..****..*******.***
*.****..********...*
*.****.***********.*
*.****........***..*
*.**************..**
*................***
********************"}