Comparison of path finding algorithms and artificial intelligence in a randomly generated maze
Software Computing
This thesis presents a comparison of pathfinding algorithms and artificial intelligence in solving randomly generated mazes. The purpose of the thesis is to determine the effectiveness and speed of different approaches to solving paths in complex structures.
The theoretical part deals with algorithms for finding the shortest path, namely the A* algorithm, breadth-first search, and Dijkstra’s algorithm. Graph and network theory and the role of heuristics in pathfinding are also presented. A special chapter is devoted to artificial intelligence and its importance in solving the pathfinding problem.
For empirical research, an application was developed in the Python programming language with a graphical user interface. The application enables the generation of random mazes of various sizes and the visualization of the operation of individual algorithms. To simulate artificial intelligence, a deep Q-learning approach was implemented using the PyTorch library.
The testing was conducted on a thousand randomly generated mazes of the following sizes: 11×11, 21×21, and 31×31. The search time, number of visited nodes, and successful goal achievement were measured. The pathfinding algorithms showed 100% success for all maze sizes.
The A* algorithm proved to be the most optimized with the fewest node visits, while Dijkstra’s algorithm found the final node the fastest. Artificial intelligence achieved 60.3% success on 11×11 mazes, but its efficiency decreased significantly in larger mazes, with 8.1% success in 21×21 mazes and 2.8% success in 31×31 mazes.
The results indicate that traditional pathfinding algorithms are more reliable and effective for practical applications where 100% efficiency and success are required. Artificial intelligence offers potentially better results but requires more extensive learning on diverse data to achieve comparable results with pathfinding algorithms.
This thesis contributes to a better understanding of the advantages and limitations of different approaches to pathfinding in complex structures.
