Nature of Code: Intelligence and Learning – Final Project Update

“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:

The perfect routing maze, also known as “simply-connected maze”, is an maze without loops or inaccessible area. Each cell is connected to at least one other cell, and connections is analogues to a spanning tree.
The braid routing method is similar to perfect routing in that it doesn’t leave any dead end of undefined area in the maze. The difference is that it has multiple paths that connects the Start to the End. Also called a “purely multiply connected” maze, the maze with braid routing can involve loops and can be more difficult to navigate than the perfect routing maze.
The unicursal maze is a maze with one continuous path that connects the Start and the End, leaving no dead-end, loop, or undefined area in the maze. If we see each grid of the maze as a vertices, then each vertices of the maze has exactly two edges (except Start and End).
Image result for unicursal maze
 The partial braid maze involve both loops and dead ends. The “braid” can be quantitative measure that counts how much looping and how many isolated walls there are.
download.png
Current Maze Generating Algorithm
Recursive Backtracking is a popular algorithm for generating perfect routing mazes and is used in the course example of Nature of Code. I wanted to implement the idea of defining and deleting walls in my project.

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.

Screen Shot 2017-05-13 at 11.13.59 PM.png

My Approach So Far

Randomly generate the walls:

Screen Shot 2017-05-03 at 10.29.30 AM.png

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.

diagram003.png

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:

http://alpha.editor.p5js.org/yuepingwang/sketches/Sy35SVLlZ

 

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.