# The Cellular Automaton Method for Cave Generation

Dear reader, this post has an interactive simulation! We encourage you to play with it as you read the article below.

In our series of posts on cellular automata, we explored Conway’s classic Game of Life and discovered some interesting patterns therein. And then in our primers on computing theory, we built up a theoretical foundation for similar kinds of machines, including a discussion of Turing machines and the various computational complexity classes surrounding them. But cellular automata served us pretty exclusively as a toy. It was a basic model of computation, which we were interested in only for its theoretical universality. One wouldn’t expect too many immediately practical (and efficient) applications of something which needs a ridiculous scale to perform basic logic. In fact, it’s amazing that there are as many as there are.

In this post we’ll look at one particular application of cellular automata to procedural level generation in games.

An example of a non-randomly generated cave level from Bethesda’s The Elder Scrolls series.

## The Need for More Caves

Level design in video games is a time-consuming and difficult task. It’s extremely difficult for humans to hand-craft areas that both look natural and are simultaneously fun to play in. This is particularly true of the multitude of contemporary role-playing games modeled after Dungeons and Dragons, in which players move through a series of areas defeating enemies, collecting items, and developing their character. With a high demand for such games and so many levels in each game, it would save an unfathomable amount of money to have computers generate the levels on the fly. Perhaps more importantly, a game with randomly generated levels inherently has a much higher replay value.

The idea of randomized content generation (often called procedural generation) is not particularly new. It has been around at least since the 1980′s. Back then, computers simply didn’t have enough space to store large, complex levels in memory. To circumvent this problem, video game designers simply generated the world as the player moved through it. This opened up an infinitude of possible worlds for the user to play in, and the seminal example of this is a game called Rogue, which has since inspired series such as Diablo, Dwarf Fortress, and many many others. The techniques used to design these levels have since been refined and expanded into a toolbox of techniques which have become ubiquitous in computer graphics and game development.

We’ll explore more of these techniques in the future, but for now we’ll see how a cellular automaton can be used to procedurally generate two-dimensional cave-like maps.

## A Quick Review of Cellular Automata

While the interested reader can read more about cellular automata on this blog, we will give a quick refresher here.

For our purposes here, a 2-dimensional cellular automaton is a grid of cells $G$, where each cell $c \in G$ is in one of a fixed number of states, and has a pre-determined and fixed set of neighbors. Then $G$ is updated by applying a fixed rule to each cell simultaneously, and the process is repeated until something interesting happens or boredom strikes the observer. The most common kind of cellular automaton, called a ‘Life-like automaton,’ has only two states, ‘dead’ and ‘alive’ (for us, 0 and 1), and the rule applied to each cell is given as conditions to be ‘born’ or ‘survive’ based on the number of adjacent live cells. This is often denoted “Bx/Sy” where x and y are lists of single digit numbers. Furthermore, the choice of neighborhood is the eight nearest cells (i.e., including the diagonally-adjacent ones). For instance, B3/S23 is the cellular automaton rule where a cell is born if it has three living neighbors, and it survives if it has either two or three living neighbors, and dies otherwise. Technically, these are called ‘Life-like automata,’ because they are modest generalizations of Conway’s original Game of Life. We give an example of a B3/S23 cellular automaton initialized by a finite grid of randomly populated cells below. Note that each of the black (live) cells in the resulting stationary objects satisfy the S23 part of the rule, but none of the neighboring white (dead) cells satisfy the B3 condition.

A cellular automaton should really be defined for an arbitrary graph (or more generally, an arbitrary state space). There is really nothing special about a grid other than that it’s easy to visualize. Indeed, some cellular automata are designed for hexagonal grids, others are embedded on a torus, and still others are one- or three-dimensional. Of course, nothing stops automata from existing in arbitrary dimension, or from operating with arbitrary (albeit deterministic) rules, but to avoid pedantry we won’t delve into a general definition here. It would take us into a discussion of discrete dynamical systems (of which there are many, often with interesting pictures).

## It All Boils Down to a Simple Rule

Now the particular cellular automaton we will use for cave generation is simply B678/S345678, applied to a random initial grid with a fixed live border. We interpret the live cells as walls, and the dead cells as open space. This rule should intuitively work: walls will stay walls even if more cells are born nearby, but isolated or near-isolated cells will often be removed. In other words, this cellular automaton should ‘smooth out’ a grid arrangement to some extent. Here is an example animation quickly sketched up in Mathematica to witness the automaton in action:

An example cave generated via the automaton rule B678/S345678. The black cells are alive, and the white cells are dead.

As usual, the code to generate this animation (which is only a slight alteration to the code used in our post on cellular automata) is available on this blog’s Google Code page.

This map is already pretty great! It has a number of large open caverns, and they are connected by relatively small passageways. With a bit of imagination, it looks absolutely cavelike!

We should immediately note that there is no guarantee that the resulting regions of whitespace will be connected. We got lucky with this animation, in that there are only two disconnected components, and one is quite small. But in fact one can be left with multiple large caves which have no connecting paths.

Furthermore, we should note the automaton’s rapid convergence to a stable state. Unlike Conway’s Game of Life, in practice this automaton almost always converges within 15 steps, and this author has yet to see any oscillatory patterns. Indeed, they are unlikely to exist because the survival rate is so high, and our initial grid has an even proportion of live and dead cells. There is no overpopulation that causes cells to die off, so once a cell is born it will always survive. The only cells that do not survive are those that begin isolated. In a sense, B678/S345678 is designed to prune the sparse areas of the grid, and fill in the dense areas by patching up holes.

We should also note that the initial proportion of cells which are alive has a strong effect on the density of the resulting picture.  For the animation we displayed above, we initially chose that 45% of the cells would be live. If we increase that a mere 5%, we get a picture like the following.

A cave generated with the initial proportion of live cells equal to 0.5

As expected, there are many more disconnected caverns. Some game designers prefer a denser grid combined with heuristic methods to connect the caverns. Since our goal is just to explore the mathematical ideas, we will leave this as a parameter in our final program.

## Javascript Implementation, and Greater Resolution

One important thing to note is that B678/S345678 doesn’t scale well to fine grid sizes. For instance, if we increase the grid size to 200×200, we get something resembling an awkward camouflage pattern.

A 200×200 grid cave generation. Click the image to enlarge it.

What we really want is a way to achieve the major features of the low-resolution image on a larger grid. Since cellular automata are inherently local manipulations, we should not expect any modification of B678/S345678 to do this for us. Instead, we will use B678/345678 to create a low-resolution image, increase its resolution manually, and smooth it out with — you guessed it — another cellular automaton! We’ll design this automaton specifically for the purpose of smoothing out corners.

To increase the resolution, we may simply divide the cells into four pieces. The picture doesn’t change, but the total number of cells increases fourfold. There are a few ways to do this programmatically, but the way we chose simply uses the smallest resolution possible, and simulates higher resolution by doing block computations. The interested programmer can view our Javascript program available on this blog’s Google code page to see this directly (or view the page source of this post’s interactive simulator).

To design a “smoothing automaton,” we should investigate more closely what we need to improve on in the above examples. In particular, once we increase the resolution, we will have a lot of undesirable convex and concave corners. Since a “corner” is simply a block satisfying certain local properties, we can single those out to be removed by an automaton. It’s easy to see that convex corners have exactly 3 live neighbors, so we should not allow those cells to survive. Similarly, the white cell just outside a concave corner has 5 live neighbors, so we should allow that cell to be born. On the other hand, we still want the major properties of our old B678/S345678 to still apply, so we can simply add 5 to the B part and remove 3 from the S part. Lastly, for empirical reasons, we also decide to kill off cells with 4 live neighbors.

And so our final “smoothing automaton” is simply B5678/S5678.

We present this application as an interactive javascript program. Some basic instructions:

• The “Apply B678/S345678″ button does what you’d expect: it applies B678/S345678 to the currently displayed grid. It iterates the automaton 20 times in an animation.
• The “Apply B5678/S5678″ button applies the smoothing automaton, but it does so only once, allowing the user to control the degree of smoothing at the specific resolution level.
• The “Increase Resolution” button splits each cell into four, and may be applied until the cell size is down to a single pixel.
• The “Reset” button resets the entire application, creating a new random grid.

We used this program to generate a few interesting looking pictures by varying the order in which we pressed the various buttons (it sounds silly, but it’s an exploration!). First, a nice cave:

An example of a higher resolution cave created with our program. In order to achieve similar results, First apply B678/S345678, and then alternate increasing the resolution and applying B5678/S5678 1-3 times.

We note that this is not perfect. There are some obvious and awkward geometric artifacts lingering in this map, mostly in the form of awkwardly straight diagonal lines and awkwardly flawless circles. Perhaps one might imagine the circles are the bases of stalactites or stalagmites. But on the whole, in terms of keeping the major features of the original automaton present while smoothing out corners, this author thinks B5678/S5678 has done a phenomenal job. Further to the cellular automaton’s defense, when the local properties are applied uniformly across the entire grid, such regularities are bound to occur. That’s just another statement of the non-chaotic nature of B5678/S5678 (in stark contrast to Conway’s Game of Life).

There are various modifications one could perform (or choose not to, depending on the type of game) to make the result more accessible for the player. For instance, one could remove all regions which fit inside a sufficiently small circle, or add connections between the disconnected components at some level of resolution. This would require some sort of connected-component labeling, which is a nontrivial task; current research goes into optimizing connected-component algorithms for large-scale grids. We plan to cover such topics on this blog in the future.

Another example of a cool picture we created with this application might be considered a more “retro” style of cave.

Apply S678/B345678 once, and increase the resolution as much as possible before applying B5678/S5678 as many times as desired.

We encourage the reader to play around with the program to see what other sorts of creations one can make. As of the time of this writing, changing the initial proportion of live cells (50%) or changing the automaton rules cannot be done in the browser; it requires one to modify the source code. We may implement the ability to control these in the browser given popular demand, but (of course) it would be a wonderful exercise for the intermediate Javascript programmer.

## Caves in Three Dimensions

It’s clear that this same method can be extended to a three-dimensional model for generating caverns in a game like Minecraft. While we haven’t personally experimented with three-dimensional cellular automata here on this blog, it’s far from a new idea. Once we reach graphics programming on this blog (think: distant future) we plan to revisit the topic and see what we can do.

Until then!

# Blog Referral – Economics, Arbitrage Schemes, and Team Fortress 2

A sample of tradable items from Valve’s “Team Fortress 2.”

I don’t often put dedicated referrals to other blogs here. If I see blogs on relevant topics, I usually want to implement the ideas myself and write an original post that delves deeper into the mathematics involved. And more often than not, the post I’d refer to shies away from or completely ignores the mathematics (the best part!), so I feel justified in not referring to the original motivating article.

But I recently found an absolutely fascinating blog, and a topic, which is a novel exception. The blog is called Valve Economics, and it’s so intriguing precisely because I don’t know anything about economics, and because Valve keeps all their juicy raw data private. I’d like to take a moment to share it with you.

## Here’s Some Background

There’s an excellent video game company out there called Valve, which has made some of the (universally accepted) best video games of all time, including some I personally have enjoyed.

A scene from Portal 2, my personal favorite Valve game.

Valve also has a wonderful content distribution network called Steam, which doubles as a platform for their in-game economies. One prominent example of this is their popular online shooter Team Fortress 2. They have what’s known as a barter economy: goods are exchanged directly for other goods, without any universal intermediary currency.

Now the thing that makes this economy so fascinating is not what you’d expect. The guns, hats, and glasses and game mechanics are largely irrelevant. The astounding feature of the Team Fortress 2 economy, and that of all virtual economies, is that every single transaction is recorded and saved. Let me isolate that statement, because it deserves a the emphasis.

Valve has access to the data of every single transaction ever made in the Team Fortress 2 economy.

This opens up a dreamland of possibilities for economists, programmers, social scientists, and a whole host of businessmen.

Consider the current state of economics. The world has been experiencing befuddling economic woes. The “Fed”s of the world have been lowering interest rates to encourage lending to no avail. Governments have been spending to encourage a resistant job market to grow. Countries have been clawing through massive heaps of debt, and economists have been speculating about the collapse of the Euro, one of the world’s largest currencies.

In the midst of all this economists are more or less at a loss. Classical and contemporary economic models fail alike, and the usual tools to combat recession have been all but exhausted. And, not even considering the recent corruption scandals, banks have not contributed much.

One huge factor in the difficulty for economists to conduct a meaningful analysis is that there is simply not enough data. It’s an unavoidable fact of life that many transactions are not recorded. Migrant workers are hired under the table, big corporations reroute their income through circuitous digital pathways to avoid larger tax burdens, and a vast amount of exchanges are simply not available (recorded or not) for economists to use. They are forced to rely on macroscopic estimates and statistical simplifications to predict the future of an increasingly complex system. And so economists measure the growth of most goods-based markets by sampling a “basket” of commonly traded goods and measuring their value. But that doesn’t tell economists what people are buying, and most companies wouldn’t give up their sales data to an outsider anyway.

But Valve’s virtual economy suffers none of those ailments. Since every transaction goes through the Steam network (and through Valve servers), each one can be logged, stored, and retrieved at the flick of a SQL query. As an analogy to a real-world economy, imagine if every single container of milk that was ever bought, sold, traded, or given freely (even in, say, the last year) was recorded in a single spreadsheet. It’s ludicrous, right? And that’s just for one product! In the Team Fortress economy, Valve has this data for every one of their many goods.

But outside of Valve, and aside from being a euphoria-inducing, data-happy wonderland, what good is studying a virtual economy? I think the answer lies in economic knowledge itself. In the Team Fortress economy, the folks at Valve can perform experiments and measure the results. They can provide hard evidence that a particular technique will have a particular effect on their users, and this can provide valuable insight into real world economies. Because remember, these are real people making decisions on the value of various goods. Steam has about 90 million users. At peak hours, there are more than 5 million users playing games, about 60,000 of which are playing Team Fortress 2. Imagine the entire country of Singapore on Steam at the same time, or Ireland, or Costa Rica. Now imagine if the entire population of Flagstaff, Arizona was playing Team Fortress. And now consider the entire country of Germany having Steam accounts. In those reference frames, it’s not hard to imagine the relevance of this digital economy.

## Enter, Yanis Varoufakis

Valve recently hired a Greek economist by the name of Yanis Varoufakis to analyze their virtual economies, and he’s recording his insights and methods on his new blog, Valve Economics. He’s already shown some fascinating results on the fluctuation of potential for arbitrage schemes. That is, the opportunity for someone to buy cheap goods and immediately resell them for a higher price (a trader’s dream). Moreover, this represents the divergence of an economy from its equilibrium. Finally, it seems that the need for generalized statistical models evaporate once you have all the data. The mathematics and economics he explains is completely elementary, and the need for statistics largely evaporates in favor of large-scale computational techniques (which he only hints at in his posts). The resulting analysis is concise, clear, and elegant.

Varoufakis’s graph showing arbitrage potential in Team Fortress 2. Height represents potential for arbitrage, and thickness represents volume of transactions.

Varoufakis (a complete stranger to video games) has done a boatload of work in economics, been at the center of the debate over Greece’s debt problems, and now works full-time for Valve exploring virtual economies.

Varoufakis provides more details on the structure of the economy in this interview (starting about 33:00) on Left Business Observer radio, where he elaborates on content creation, bursting bubbles, philosophical economic debates, and economic regulation. I highly encourage the interested reader to listen, because he provides many details and analogies that are omitted on his blog.

Even with only two posts, I’m hooked. And as long as his posts are, I want more: more detail, more economic background, more history, more on his programmatic methods, more of it all! I’d love to learn more about economics from a mature point of view (and in particular mathematical and computational economics), and Varoufakis presents his work in an accessible, engaging way. But even more so, I’d love to get my hands on these awesome datasets.

If any readers know of a good text that would give an introduction to mathematical economics or computational economics, please let me know in the comments. More importantly, if anyone knows of freely available datasets from similarly isolated economies, please let me know! Without data to experiment with the analytic techniques is largely useless.

Until next time!

# Classic Nintendo Games are NP-Hard

The heroes and heroines of classic Nintendo games.

Problem: Prove that generalized versions of Mario Brothers, Metroid, Donkey Kong, Pokemon, and Legend of Zelda are NP-hard.

Solutionhttp://arxiv.org/pdf/1203.1895v1.pdf

Discussion: Three researchers (including Erik Demaine, a computer science professor at MIT famous for his work with the mathematics of origami) recently finished a paper giving the complexity of a number of classic Nintendo games (the ones I loved to play). All are proven NP-hard, some are shown to be NP-complete, and some are PSPACE-complete. Recall, a problem is NP-hard if an NP-complete problem reduces to it, and a problem is NP-complete if it’s NP-hard and also in NP. As we have just posted a primer on NP-completeness and reduction proofs, this paper is a fun next step for anyone looking for a more detailed reduction proof. A pre-print is available for free on arXiv, and it’s relatively short and easy to read. I’ll summarize his result here, and leave most of the details to the reader. Each game is “generalized” to the task of determining whether one can get from a “start” location to a “finish” location. So the decision problem becomes: given a finite level of a game, can the player move from the starting location to the finishing location? All of the reduction proofs are from 3-Sat, and they all rely on a common framework which can be applied to any platform game. Pictorially, the framework looks like this:

The framework for reducing 3-Sat to platform games.

The player starts in the “start” gadget, which allows one to set up initial state requirements. For instance, in Super Mario Brothers, the start provides you with a mushroom, and you cannot get to the finish without being able to break blocks by jumping under them, which requires the mushroom power-up. Each “variable” gadget requires the player to make a variable assignment in such a way that the player can never return to that gadget to make a different decision. Then each “clause” gadget can be “unlocked” in some way, and each clause gadget can only be visited by the player once the player has chosen a satisfying variable assignment for that clause. Once the player has visited all variable gadgets, he goes to the “check in” area, and can travel back through all of the clauses to the finish if and only if he unlocked every clause. The crossover of the paths in the picture above requires another gadget to ensure that the player cannot switch paths (the details of this are in the paper).

For example, here is the variable gadget described in the paper for The Legend of Zelda, a Link to the Past:

Note that here we require Link has the hookshot, which can grapple onto chests, but has limited reach. The configuration of the chests requires him to choose a path down one of the two columns at the bottom, and from there he may never return.

Here’s another example. In the classic Super Mario Brothers game, a possible clause gadget is as follows.

The clause gadget for the original Super Mario Brothers.

Note that if the player can only enter through one of the three columns at the top, then the only thing he can do is kick a red koopa shell down so that it breaks the blocks, unlocking the way for Mario to pass underneath at the end. Note that Mario cannot win if he falls from the top ledge (since must always remain large, he can’t fit through a one-tile-high entryway). Further details include the hole at the bottom, in which any stray koopa shell will necessarily fall, but which Mario can easily jump over. We recommend reading the entire paper, because it goes into all of the necessary details of the construction of the gadgets for all of the games.

## Future Work

We note that there are some parts of the paper that only got partial results, mostly due to the variation in the game play between the different titles. For instance, the original Super Mario Brothers is known to be NP-complete, but the added ability to pick up koopa shells in later Super Mario Brothers games potentially makes the decision problem more complex, and so it is unknown whether, say, Super Mario World is in NP. We will summarize exactly what is known in the table below. If readers have additions for newer games (for instance, it’s plausible that Super Mario Galaxy could be adapted to fit the same construction as the original Super Mario Bros.), please leave a comment with justification and we can update the table appropriately. I admit my own unfamiliarity with some of the more recent games.

Super Mario Brothers:

Game Title NP-hard in NP PSPACE-complete
Super Mario Bros.
Lost Levels
Super Mario Bros. 2
Super Mario Bros. 3
Super Mario Land
Super Mario World
Land 2: 6 Golden Coins
Super Mario Land 3
Yoshi’s Island
Super Mario 64
Sunshine
New Super Mario Bros.
Galaxy
New Super Mario Bros. Wii
Galaxy 2
Super Mario 3D Land

Legend of Zelda:

Game Title NP-hard in NP PSPACE-complete
The Legend of Zelda
Ocarina of Time
Oracle of Seasons
Oracle of Ages
The Wind Waker
The Minish Cap
Twilight Princess
Phantom Hourglass
Spirit Tracks
Skyward Sword

Donkey Kong:

Game Title NP-hard in NP PSPACE-complete
Donkey Kong
Donkey Kong Country
Donkey Kong Land
Country 2: Diddy’s Kong Quest
Land 2
Country 3: Dixie Kong’s Double trouble!
Land 3
Donkey Kong 64
Donkey Kong Country Returns

Metroid:

Game Title NP-hard in NP PSPACE-complete
Metroid
Metroid II: Return of Samus
Super Metroid
Fusion
Prime
Prime 2: Echoes
Prime Hunters
Prime 3: Corruption
Other M

Pokemon:

Game Title NP-hard in NP PSPACE-complete
All Games
Only trainers