I’ve been playing a lot of a game called Dragon, Fly! recently. One of the cool things about Dragon, Fly! is that each day the levels are a little different. Not that there’s much to distinguish one level from another—each is basically a series of hills of varying width and height. Still, once I’ve played the game three or four times in a day I begin to recognize when a particularly sweet (or nasty) spot is about to show up, and I find myself planning ahead accordingly. Over the course of a day, I get a little better at whatever level happened to be generated that day. The daily learning curve isn’t steep, but it’s noticeable, and it serves two related purposes. First, it keeps the game fresh by surprising you—it’s way more interesting to pick up the app and be surprised by what you find than to encounter the same map over and over, day after day. Second, it provides you with a fresh set of content to learn each day. One of the main sources of fun in a game is the achievement of mastery—not having the mastery once you’ve gained it, but the process of gaining it. Dragon, Fly! lets you repeat that learning process over and over, day after day.

As a sole designer / programmer, procedurally generated content works well for a number of reasons. Most selfishly, it means that I don’t have to spend a lot of time designing a bunch of levels. Once I’ve written a satisfactory generation algorithm, I can generate a practically infinite number of distinct levels. This is good for the user, too—by sheer volume of content, the user will (hopefully) never be bored with the level design. Or if they are, it will at least be because of repetitive patterns between levels, which can be fixed in the generation algorithm, and not with the levels themselves. This freshness also helps keep me, as the game designer, interested in the game. It’s easy to get bored while spending days and days developing new features on the same set of levels. By keeping myself surprised by each new generated level as I’m developing, I keep up my motivation and enthusiasm for the project, which hopefully will lead to a more engaging game for the end user. The best way to make a game fun for your users is to make it fun for yourself.

One of the key mechanics of Mechasaur is that each unit type is capable of traveling over a different set of terrain types. Another key feature is that some unit types have a corresponding home terrain type, which gives a boost to their defenses. One of the key problems in developing a level-generation algorithm, then, is to balance these two mechanics. Home terrains should be close enough together so that a unit can travel around a significant portion of the map without ever leaving their home territory. On the other hand, terrain types should not be so densely intermingled that a unit is prevented from traveling across the map at all.

The key to this solution lies in the grass terrain. Grass is distinct because of its plainness: all units may travel over it, and it is no unit’s home terrain. It’s the vanilla of terrain types.

Broadly, the generation algorithm is as follows: I initialize each map by covering it in grass. I add a base location for each player, mark a small amount of grass around it as un-changeable (it must stay grass), add place units on some of those cells. I place a seed location for each non-grass terrain type somewhere randomly on the map. Then, I repeatedly randomly select one non-grass terrain cell on the map and change a nearby grass cell to that type. If this results in cutting off one section of grass from the rest of the map, I undo that change and mark the corresponding grass cell as un-changeable. Because all units can travel over grass, this guarantees that each unit can travel to every grass cell on the map.

Each time a terrain is duplicated, it becomes more likely to be selected to be duplicated in the future. This feedback cycle produces maps that disproportionately contain (or don’t contain) particular terrain. This is a desirable quality because it gives each map a sense of character (this map is a foresty map, this other map is a watery map).

This algorithm has two interesting parameters: How far away to place a new terrain cell from its parent cell (spawning distance), and when to decide that the map is finished. For small values of the spawning distance (say 1 or 2 in manhattan distance), you end up with more or less contiguous sections of terrain. For larger values, you end up with a more heterogeneous mixture of terrain types. I hand-tune a random distribution of this parameter for each terrain type in order for the resulting map to feel like it was hand-designed; water has a small spawning distance to produce lakes, whereas mountains have a larger spawning distance to produce individual mountains. In addition, by keeping the spawning distance less than or equal to the moving speed of the unit that gets a defensive boost in that terrain, I can guarantee that such units can traverse the entire portion of the map that contains their home terrain, without ever leaving their home terrain.

I haven’t yet found a satisfactory stopping criterion. For now, I count the number of times I have to undo a step to preserve grass’s continuity, and halt after the nth undo. I can vary n to produce sparser or denser maps.

While I’m generally happy with each individual map this algorithm produces, I would like to be able to produce a wider variety of maps. For example, in most of the maps I’ve designed by hand I border the map almost entirely with some particular terrain type in order for the player to feel immersed in the level. In the level generation algorithm, if I seed a level with a border of some particular terrain type, that terrain type would dominate the map to the point of making it unplayable. On the other hand, I don’t want to simply prohibit the duplication of border terrains, because the inner contents of the map should reflect the border to a certain extent. One possible solution would be to associate a weight with each terrain cell and weight the selection of the next terrain to duplicate by their weights. By weighting the center “seed” terrains more heavily than the border terrains, the border of the map could creep into the center just a little without dominating it, which would add some authenticity to the theme of the map, without disrupting gameplay.