Visualising and Solving a Maze Using an Artificial Intelligence Technique
Marcel Sagming, Reolyn Heymann, Evan Hurwitz · 2019
This paper describes the implementation of an artificial intelligence (AI) technique known as Genetic Algorithm (GA), used to solve randomly generated mazes that are of varying sizes and complexity. To evaluate the effectiveness of the GA, several non-AI techniques are implemented such as Depth-First Search (DFS), Breadth-First Search (BFS), A-Star Algorithm (A*), Dijkstra Algorithm (DA), and Greedy Best-First Search (GBFS). Genetic algorithm is a method for solving both constrained and unconstrained problems based on a natural selection process that mimics biological evolution. The non-AI algorithms make use of graph concepts together with underlying data structures to solve randomly generated mazes. This paper also shows the results obtained from five different experiments after implementing the complete system and executing each of the non-AI algorithms as well as the GA. The strongest results after executing each algorithm, that is, the number of steps and the time taken to solve the maze were recorded and graphs were plotted to compare the performance of the GA compared to the non-AI algorithms. The GA always found the shortest path but becomes slower than the non-AI algorithms for dimensions greater than 10x 10.