Mazerunner - Analysing AI Search Algorithms

The goal is to compare and analyse different search algorithms. I simulated an environment of obstacles and open squares as shown in the image.

• Red squares represent the source and destination. The agent starts from the top-left corner and has to find a path to the bottom-right corner.

• Black cells represent obstacles

• White cells represent open space.

I tried 3 different algorithms:

• Breadth-First Search

• Depth First Search

• A* Algorithm with the following heuristics

  • Euclidean Distance

  • Manhattan Distance

The project was divided into 4 stages:

1. Time Analysis and Comparison - A comparison of the above 4 algorithms in terms of the time taken to find optimal paths, the size of different mazes and which one perfoms better.

2. Generating Hard Mazes - For each algorithm, the task is to find the hardest possible maze based on

   1. how long the shortest path is

   2. how many nodes are expanded by the algorithm

   3. the maximum time taken to find the path.

3. Thinning A* - A variation of the A* algorithm

4. Maze on Fire - A variation of the above problem where now its a race against time since the maze is also set on fire. The algorithm needs to find a path which reaches the destination before the fire engulfs the maze!