Screen Shot 2017-07-25 at 7.11.17 PM.png

Algorithmic Maze

Algorithmic Maze

Design game space with machine-learning algorithms. (On-going)


* Link to the project site

In spring 2017, I took Nature of Code: Intelligence and Learning with Daniel Shiffman at ITP, a class in which we learned about different machine-learning algorithms - from various search and path-finding algorithms to the currently popular convoluted neural networks.

I was particularly drawn to the genetic algorithms - the idea that the behaviors of a program can be abstracted to a DNA-like data sequence, and by cross-mating the DNA of well-performed programs, the computer can evolve better programs over time.



Can Machine-Learning Be Used to Design Game Spaces?


Specifically, I'm curious about how generic algorithms can be used to design the navigable space in video games. On one hand, because game design concerns with chances and rules that affect the player's behavior and the task's difficulty, it is possible to (at least partially) abstract the gaming mechanisms to mathematical expressions. 

So while the blueprints of video game space is defined by game designers, based on their skills, experiences and user tests, I wonder if genetic algorithms can help create a controlled blend of geographical complexity, number of challenges(enemies), rewards, and over difficulty in the design of a “navigable space”. What’s more, algorithms can also be used to “test” the generated game space, allowing rapid iterations.

On the other hand, thinking about real-world strategies by abstracting them as games has been a fruitful way for cultural theorists of the 20th century to better extrapolate the essences of real-world event. Guy Debord, for example, has famously designed the Game of War at the late stage of his career (1987), turning the military theories of Napoleonic era into the rules of maneuvers on a customized chessboard. As Alex Galloway describes it: 

“He (Debord) positions chess firmly in the classical period of kings and corporal fiat, while the Game of War belongs to a time of systems, logistical routes, and lines of communication... In the Game of War, Debord maintained this attention to spatial relationships, but added a degree of complexity. The ‘liaisons’ in the Game of War are not simply the projections of possible troop maneuvers, but a communicative apparatus linking together far-flung fighting divisions. If chess’s king is an intensive node, one that must be fortified through the protection of its allied footmen, then Debord’s arsenals are extensive nodes.”


Maze Design: The New Approach

Game spaces can get exponentially complex as rules and actors change. So I narrowed down the scope to designing (or, letting the machine to design) mazes.

Maze design is by-no-means new, and there are many precedents of computer-generated maze. So I did a survey of existing algorithms, with a focus on the routing methods.

Search Algorithms, Data Structure and Graph Theory

In order to product better-performing mazes over time, each previous generation of mazes need to be scored, according to such criterium as total number of paths, dead ends and loops, and the length of paths are necessary.

I studied different path-finding algorithms, in order to gather information about each maze and effectively evaluate its performance.

*To be continued...