Maze

Maze is a visual demonstration of 3 search algorithms:

1. Breadth First Search

BFS is a search algorithm, in which closer places are searched before farther ones. Read more: Breadth-first search

2. Depth First Search

DFS is a search algorithm, in which a chosen path is searched until a dead-end is reached. Then, previous possible ways are searched. Read more: Depth-first search

3. A-Star

A-Star uses a heuristic to determine which places should be searched first. Read more: A* search algorithm

How to use?

1. Download the folder, run Main.java (it's inside src folder).
2. Tell the system which maze you want to use. You can give it the name of one of the existing mazes (e.g., "maze4" or "smiley", see in the folder). You can also type "random" or leave it empty, which will lead to a randomly generated maze.
3. Tell the system which search algorithm you want: BFS, DFS or AStar. The default is AStar.

What am I looking at, exactly?

Given an agent (in red), a goal (in blue) - Is there a way to get from the agent to the goal? The three algorithms share a common idea:

1. Starting from the agent, decide which next square you want to explore. Color this square light-green.
2. From all the squares you wanted to explore, choose one (which one? Depends on the specific algorithm. AStar, for example, chooses the one with the lowest Eucledian distance to the goal) and repeat until you find the goal.

The expanding paths you see when you run the program are the expanding search- this is where the algorithm is currently looking to find the goal.

If a path is found, the algorithm will back track, ignoring the errors it did along the way, and show you the actual best path available to it, note that there might be better ways to get from the agent to the destination. No algorithm is perfect, right? If the shortest path is found, it often comes at a higher searching time (like in BFS). The highlighted path is guaranteed to be the shortest one only by using BFS (it is also likely to take a long time to find). Using DFS and AStar might give different results. Have fun playing with it.

You can also use the maze constructor attached as an excel file.

Example