Blobs in Games

I was drawing tile maps in Flash and found a cheap trick that improved the appearance of the maps, so I thought I'd share. Here's how I had been drawing the tile map:

In a bitmap-based graphics engine, you can smooth the edges of the tiles either by adding transition tiles (see this article or this article) or by using a blending mask between adjacent tiles.

Flash, OpenGL, and DirectX are vector-based engines. The bitmap techniques still work, but there are new possibilities available. I'm drawing each square tile by filling a square polygon with a bitmap texture. The engine doesn't care that it's square; it works on any polygon. I'm taking advantage of this with what I call “vertex displacement”:

I look at the four tiles touching each vertex. If three of them are the same and the fourth is different, I move the vertex to expand the area of the three common tiles and shrink the area of the uncommon one. It's easier to see the effect with the polygon borders:

It turns out there are other fun things you can do with this trick. For example, a little bit of random noise on each vertex makes for a map that looks a little more hand drawn:

I've also used it to animate the boundary between the ocean and the beach. I added vertex displacement to my simple map generator; see the demo (Flash). Try changing the corner setting to adjust how much the corners get moved when three tiles are the same, and the random setting to adjust how much vertices get randomly moved. I have a separate demo (also Flash) to show the animated coastline.

The technique has its limitations. Terrain boundaries that don't fall on a 45° angle look wavy (see example). Some terrain types shouldn't meet in this way. And the biggest limitation is that it only applies when the terrain texture has no major features (such as trees, rocks, etc.). But it's a cheap enough trick that it's worth keeping in my toolbox.

Edit: The feedback from comments is that the names “teleological” and “ontogenetic” aren't good fits. I agree. There's an interpretation in which the terms work but there are also other ways to interpret them where it doesn't make sense. I had gotten the terms from the procedural content wiki, but in the future I'll avoid using these terms. Thanks for the feedback.

Long ago, I spent years working on the terrain generation for a game I worked on. I used earthquake faults, volcanoes, soil erosion, lava, river erosion, sediment deposition, water flow, weather simulation, vegetation (affected soil, which affected erosion), forest fires, floods, continental uplift, and other physical processes. This is the teleological approach to making maps.

To make good maps, I'd change parameters and run it to see if the maps looked good. I'd go back and change parameters again and again. Ideally I'd write a search/evolutionary algorithm that explored the parameter space. To do that I need to write code to determine whether a map will look to my eye, and I never did figure that out. I knew it when I saw it.

The other approach to map making is ontogenetic. Start with what you want to see, and make algorithms produce that directly. This is what I did with last year's simple map generation project. I had seen Perlin Noise, and thought, hm, that looks vaguely like a map — let's see how much work it takes to turn it into a map. Not much, it turns out!

For the past month I've been working on a new map generation project. I wanted island/continent maps with rivers, and Perlin Noise wasn't a good fit for that. I tried making random mountains come out of the ocean, and then using water flow algorithms to carve out rivers. I've been tweaking and testing, tweaking and testing, tweaking and testing, and finally realized that I'm back to using teleological algorithms. It's incredibly addictive. It feels right: erosion, mountains, gravity, and all the other “realistic” things that form terrain.

The trouble is that I really don't need all of that. I'm working on 2D Flash games, and I don't need terrain; I need maps. It doesn't need to be completely realistic. It just has to be interesting. So I'm stepping back a bit and switching back to the ontogenetic approach. I'm drawing some maps that I like, and then I'll find algorithms that generate maps like those, instead of modeling physical processes that produce realistic terrain. I think this will lead to better maps with less work.