Occupy Math is a member of the IEEE Computational Intelligence Society’s Technical Committee on Games. What this means is that now that games are a multi-billion dollar industry, Occupy Math can use the stuff he learned refereeing Dungeons and Dragons ™ in his academic research. While Occupy Math works on mathematical games like prisoner’s dilemma and rock-paper-scissors, he also has managed to build an automatic dungeon designer for simple role playing game modules. Here is a map built by one of Occupy Math’s algorithms. The algorithm assembles tiles according to a plan to make a really big map.
The key tool I use is Evolutionary Computation. My research is the design of structures that can efficiently evolve, in this case, maps or map fragments. All the tiles assembled to make the big map above were produced with an evolving AI. Let’s look at some different evolvable representations for maps. The first uses a grid of full-or-empty values. It makes maps that look like this:
The big innovation here is to have 20% full and 80% empty for the levels generated at the beginning of evolution. A 50% full maze is almost always impossible to traverse – but if evolution fills a few more squares in each generation then a slightly full maze rapidly fills up – at least if the breeding selection function encourages it. This is a technique invented by Occupy Math called sparse initialization.
The choice of how to represent the evolvable structures has a huge impact on the appearance of the maps that evolve.
The map above uses the negative representation invented by my student, Colin Lee, where we start with a full area. The evolving structures specify where to dig out material. Another way to go is to have the evolving structure specify where walls go and how long they are. We call this the positive representation. This gives you maps like the one below. The red dots are the beginning and end of the paths through the tile and the green dots are used to let the algorithm space things out.
Look at the three maps above. Don’t they look like they were done with different artistic techniques? This is one of the benefits of changing the representation used to evolve map tiles. Each representation is like a different painting tool. You can also impose symmetry – like the example below or all the tiles in the middle of the big map at the beginning of the post. This example is the full or empty representation again, but with imposed symmetry. Cool, isn’t it?
Once we have the positive representation, we can do interesting stuff with it – like give the walls material types. The map below has stone walls (black), water features (blue), and walls of fire (red). The map specifies a stone-fire maze that a non-fireproof player must traverse and a stone-water maze that a flaming denizen of the netherworld must traverse. The selection function tries to make it easier for the fireproof netherworlder to get around, challenging the flammable character run by a human player. This representation specifies two mazes that exist simultaneously in the same space. Isn’t this nifty?
A simple algorithm called dynamic programming figures out shortest paths between places and forms the basis of many different selection functions that drive the evolving AI.
What about the map for a role playing game module? This is joint work with my former student Cameron McGuinness. The map is first designed with the simple full-or-empty representation. We then locate rooms with a connected open space detector and number them. The selection function then tries to enforce designer-specified tactical properties like “the goblin lair is near the door” or “the necromancer is far from the door”. The following map puts the goblin lair, rooms 9-11, near the door (room 1).
This next map puts the goblin lair, rooms 7-9, far from the door (still room 1). A few of the rooms or sets of rooms, like the goblin lair, are pre-specified, placed first, and then the rest of the map is evolved to the users exacting specifications about the distance relationship between the different special, pre-specified areas.
An earlier post, Cookies or Calculus, Occupy Math advocated for an area of math called graph theory. Using a graph that captures room adjacencies in a dungeon map creates a much simpler domain for computing the selection function that drives the evolving AI. Here is a graph that not only shows the room adjacencies but specifies the special, pre-specified areas. This graph isn’t taken from either of the example maps above – this research project generated 180 maps.
One of the enormous advantages of evolutionary design is that, once the system is set up, you can make hundreds of variant gaming modules in a few minutes. This speaks to an issue that game designers call “replayability”. The evolving AI technique has the potential to eliminate, or at least massively reduce, the annoying delay while we wait for the next mission pack of our favorite game to come out.
Occupy Math will leave for another day the process of populating the dungeon with monsters and treasure – these are relatively easy once you have a map with the correct properties. The entire set-up for creating the modules uses a whole lot of math. The obvious math is the use of dynamic programming and graph theory, but designing the different representations for evolvable maps and, especially, the selection functions that encourage user-specified tactical properties, require a lot of mathematics. As always – Occupy Math hopes you will join those of us who see math as more of a paint brush than a torture device.
Interested in automated game design? Comment or tweet to let us know. Occupy Math also works on puzzle design, adult coloring books, automatic difficulty adjustment, and creating NPCs with predictable challenge level. All interesting areas and Occupy Math likes it when readers suggest topics.
I hope to see you here again,
University of Guelph,
Department of Mathematics and Statistics