This program solves 2D maze using various uninformed and informed (heuristic) search strategies. It takes the maze structure as input file and performs selected search algorithm. The cost of the solution found, the solution path itself and the list of expanded nodes are given as output. Thus, the results and differences of algorithms can be compared. Also, a GUI is implemented that visualizes the search steps.
The first line of the input file consists of 2 numbers, that are mapped to row and column indexes, representing the dimensions of the maze. The remaining lines consist of 1 letter and 2 numbers. The letter indicates the expression in the line(the type of wall or square), while the numbers indicate the row and column indexes, respectively.
| Maze Structure | Input Letter |
|---|---|
 |
v: vertical walls h: horizontal walls s: the starting square t: trap squares g: goal squares |
When the program is run, the algorithm must be selected. The program consists of following algorithms:
- Depth First Search
- Breadth First Search
- Iterative Deepening
- Uniform Cost Search
- Greedy Best First Search
- A* Heuristic Search
For Greedy Best First Search and A* Heuristic Search,city block distance (Manhattan distance) is used as an admissible heuristic.
