“The more you learn, the more you know you don’t know” is one of the lessons I learned through doing this project so far.
Inspired by the Theseus and Minotaur maze recreated by computer programmers, I concluded my project proposal with the initiative to design (or let the computer design) game mazes using genetic algorithms. And since then I have looked through a myriad of online sources related to mazes, both in terms of how different genres of mazes affect the player and their navigation, and in terms of the processes and algorithms for generating different types of mazes. (There are more complex scenarios, such as the logic maze, where the navigable space is dependent on rules and variables, but these are far beyond the scope this project.)
The Design of Maze
Maze design is by no means new, and there are countless predecessors who have scrutinized mazes in much greater depth and breadth than I could ever achieve. Amongst the resources I came across, a computer programmer named Walter Pullen has put together a very detailed glossary of classifications and algorithms for maze: http://www.astrolog.org/labyrnth/algrithm.htm. I learned a lot from each sections of his posts, and the “Routing” section is particularly interesting and helpful in regard to the scope of my project.
He specified a few styles of routing on his website:
Search and Path Finding Algorithms for Evaluating the Maze
I looked into multiple path-finding algorithms because I think that in order evaluate each generation of maze, criterium such as total number of paths, dead ends and loops, and the length of paths are necessary when scoring each phenotype of the maze DNA.
I studied both depth-first search and breadth-first search and how they are demonstrated through code. However, both methods are good for picking one ideal path, as oppose to storing every single path of the maze. And in the recursive functions of the codes, there isn’t a mechanism for recording or keeping track of previous paths.
The “iterative depth-first search” is an approach that I found quite interesting but might not have time to explore in this project. It is a depth-bounding search approach, that repetitively does depth-first search to an increasingly deepening levels of a tree(search graph).
Graph Theory Related to Maze
Seeing the maze as a graph is an interesting idea because doing so prioritizes the abstracted interconnections between nodes(or vertices), and the visual form of these connections is only the secondary step.
The up side of this approach is that the designer (or the program) can observe and arrange the nodes at the conceptual level. The down side is that the maze geometry constrains the maximum number of edges each vertex can have.
My Approach So Far
Randomly generate the walls:
I want to represent the maze by creating a series of Cell objects displayed as columns and roles. Each Cell object(or instance?) is responsible for two walls (right and bottom), and stores attributes such as its index ([col][row]) and state (boolean visited), and the checkNeighbor() function asks that the current cell check its neighbor cells’s walls and it own walls to determine the accessible branches.
The first few generations of the maze should be made with randomly assigned walls.
Another way of indexing the cells that I though of but haven’t implemented yet is label the cells through their distance(number of necessary steps) to the origin. Maybe indexing cells this way can provide another sort of variable in the DNA array and product more efficient result genetic crossovers and mutations.
I’m currently stuck in the process of testing and scoring these generated mazes. I want to design a search algorithm that identifies and stores each path (from Start to a dead end or the exit). There’s some issues when working with stacks and recursions that I need to trouble shoot…
The current version of the code for Algorithmic Maze is here:
After using machine learning algorithms to generate the 2D maze, I want to extrude all the “walls” of the maze, and transform the maze into a game space that people can immediately play with,
This is a randomly generated 3D maze, made in Processing P3D and provides a more or less “immersive” navigation experience for the player. I envision the machine learning algorithms to be used, directly or indirectly, in game engines such as Unity, and help generate VR spaces in place of the traditional game designer.