The project in five facts.
Challenge, approach and results.
The diploma thesis presents a comparison of pathfinding algorithms and artificial intelligence in solving randomly generated mazes. The purpose of the diploma thesis is to determine the efficiency and speed of different approaches to solving paths in complex structures. The theoretical part discusses shortest path search algorithms, namely the A* algorithm, breadth-first search and Dijkstra's algorithm.
Solution and method
The diploma thesis presents a comparison of pathfinding algorithms and artificial intelligence in solving randomly generated mazes.
Results
The purpose of the diploma thesis is to determine the efficiency and speed of different approaches to solving paths in complex structures. The theoretical part discusses shortest path search algorithms, namely the A* algorithm, breadth-first search and Dijkstra's algorithm. The theory of graphs and networks and the role of heuristics in pathfinding is also presented.
A special chapter is dedicated to artificial intelligence and its significance in solving the pathfinding problem. For the 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 different sizes and visualisation of the operation of individual algorithms.
A deep Q-learning approach using the PyTorch library was implemented to simulate artificial intelligence. Testing was carried out on a thousand randomly generated mazes for the following sizes: 11×11, 21×21 and 31×31. Search time, number of visited nodes and successful reaching of the goal were measured.
Pathfinding algorithms showed 100% success rate for all maze sizes. The A* algorithm proved to be the most optimised with the smallest number of visited nodes, whilst Dijkstra's algorithm found the final node the fastest. Artificial intelligence achieved 60.3% success rate on mazes of size 11×11, but its efficiency decreased significantly with larger mazes: 8.1% success rate on mazes of size 21×21 and 2.8% success rate on mazes of size 31×31.
The results indicate that traditional pathfinding algorithms are more reliable and efficient for practical applications where 100% efficiency and success rate are required. Artificial intelligence offers potentially better results, but requires more extensive training on diverse data to achieve results comparable to pathfinding algorithms. The diploma thesis contributes to a better understanding of the advantages and limitations of different pathfinding approaches in complex structures.
In the future, it would be sensible to investigate other artificial intelligence methods and optimise learning processes to achieve greater success in solving more demanding mazes.
Module, programme and stories.
Your diploma project for a real company.
A diploma thesis at Academia solves a challenge from a company – often the one where you do your 800 hours of placement. Read about the Programsko inženirstvo module or book a consultation.