ANALYSIS AND COMPARISON OF EXISTING MAZE GENERATION METHODS IN COMPUTER GAMES

Abstract

In the era of the information society, where the visualization of game and simulation spaces is becoming increasingly important, the development of algorithms for generating mazes is becoming more and more relevant. Interactive games, virtual reality, educational platforms, and other areas require the generation of mazes of various complexities and configurations to provide variety and an engaging experience for players and users. Traditional maze generation methods, such as the Wilson algorithm or the Prim’s algorithm, may be limited in their flexibility and ability to create mazes with specified characteristics. Procedural maze generation methods offer a more flexible and powerful approach. These methods allow generating mazes with different parameters, such as size, complexity, branching type, presence of dead ends, and other elements. As a result, procedural methods are becoming increasingly popular for maze generation in a wide range of applications. This research aims to compare different maze generation algorithms. The paper investigates and compares five algorithms: Recursive Backtracker, Kruskal’s Algorithm, Aldous-Broder Algorithm, Hunt-and-Kill Algorithm, and Binary Tree Algorithm. There is a need to determine the efficiency of different methods in terms of structural complexity and variability of the generated mazes. Analyzing the impact of different methods on computational resources and generation time is also a key aspect, especially in demanding applications such as video games or simulations. Such analysis will help identify optimal and efficient approaches to maze generation for different applications.The research results may be useful for game developers, for researchers in artificial intelligence who want to develop algorithms for solving routing problems, and so on. This research will help developers better understand the capabilities and limitations of each algorithm to make an informed choice.