You've woken up at the beginning of a maze. You have no memory of how it happened. You only know that you need to escape.
Wait, something's coming back to you... You were studying... graph search algorithms?
Yes, that's right... Wait, who are these other characters in the maze with you?!
It can't be... your old nemeses: DFS, BFS, and A*!!! You must try to beat them to the exit!
Use the arrow keys or WASD to navigate. Select your difficulty below. Change settings by clicking the gear icon.
In the ultimate battle of human vs. computer, you are competing against three classic graph search algorithms in a race to the end of the maze. They key to victory is to know thy enemy. Therefore, this section will be of the utmost importance to you as you navigate through the maze.
Depth First Search is the most intuitive way of traversing a maze, and is likely the approach you as a human player will take. In DFS, you follow a single path as far as it will lead until you either hit a dead end or exit the maze, taking care not to revisit areas you've already visited. If you hit a dead end, you must backtrack to the last junction where you could have taken a different path, and then recursively repeat the procedure.
This implementation of DFS makes a random decision at each junction. This means that on small mazes with few junctions, it may actually perform quite well. However, it will perform asymptotically poorly on larger mazes as the number of possible routes increases. You should expect to beat DFS on any large maze, unless you are very unlucky.
While DFS is akin to a human navigating a maze, Breadth First Search can be thought of as a team of humans navigating the maze and communicating with walkie-talkies. Imagine that, at each junction, a pack of explorers splits: one subpack wanders out in each possible direction that has not yet been visited. One by one, these subpacks advance outwards, splitting again at future junctions. The first subpack to reach the goal reports their path back to the entire group.
This is why BFS appears to be hopping around, as subpacks alternate their moves. You may say: that's not fair! I only get one explorer and BFS gets as many as it wants! True, but remember that BFS will explore all possible paths, even those that are clearly in the wrong direction. So even though it has more explorers, each explorer is quite unintelligent. For this reason, BFS will typically outperform a blind DFS on larger mazes, but may lose to a human, even given its multi-explorer advantages.
A*, a form of Best First Search, is a hybrid of DFS and BFS. It can be thought of as a team of humans with walkie-talkies and periscopes to see over the maze walls. A* will wander out in packs like BFS, but rather than all packs advancing in turn, only the subpack closest to the goal (as estimated via the periscope) will advance. This approach is similar to that of a human with prior knowledge of the maze, always trying to move in approximately the right direction.
How is this "periscope" idea implemented? With what's called a heuristic, essentially an educated guess about the distance to the goal without knowing the landscape of unvisited terrain. This implementation uses the popular and simple Manhattan Distance heuristic, which calculates the number of "city blocks" to the goal assuming no obstacles. A* is one of the most powerful graph search algorithms currently known. You are unlikely to beat A* on any large maze.
It's here, in disguise! This graph is unweighted, meaning that all paths are equally difficult to traverse. Dijkstra's algorithm on an unweighted graph is just BFS! Future versions of this project may include different terrain (tarpits, turbo boosts, etc.) that would change the graph representation of the maze from unweighted to weighted. In this case, Dijkstra's algorithm will be a separate player and will almost certainly outperform BFS.
Ancient Ruins
Galaxia
Ocean's Deep
World 1-1
App Academy
Knife
Sniper
Ray Gun
CTCI