Incursion was my second game for BYOND, the first being a concept called "Goop" with multi-tiled mobs that never got off the ground. But the concept of pushing the engine appealed to me, and I wanted to see if I could develop something like Lords of Conquest, a game I used to play where maps were generated on the fly. It started out as a project called Land War, and evolved from there.

A lot of people have asked how I made Incursion, and I think it's time to share how the whole thing works under the hood.

Map generation phase 0: Preparation

Let's talk terminology for a minute. When Incursion was made, BYOND didn't handle auto-scaling maps. Maps were displayed either big (32×32) or small (16×16). To get a detailed map, I needed to break turfs up into smaller units. The map was 17×13 turfs, with each turf being broken into four sub-tiles that I'll call cells. The cell map, therefore, is 34×26. The cells at the edges of the map are marked as off-limits for creating land.

Because Incursion was first developed before pixel offsets or HUDs were available, I had to get really creative. Images were used for all items (including the unit movement interface) that would be shown to a single player, and items were shown in the cells by using icons that had four directions: one for each corner. Eventually I did make use of the new upgrades, but Incursion really pushed the engine hard in its day.

Anyway, where were we? The map is made up of cells. The game cares about territories, each of which basically is a collection of cells. Each territory keeps track of its neighbors and is represented by a datum.

Map generation phase 1: Continents and territories

First off, the territories need to be generated. I wanted there to be large contiguous land masses, so my goal was to form continents. To do this, I split the map into nine regions (3×3). This grid starts about 1/6 of the way in from any edge.

For each continent, pick a region at random from the list, of those that haven't been used yet. Then look for a random cell in that region. If one is found that's already been used for land, the region goes back on the list and we pick again. Otherwise, the cell we found is the seed for a new territory.

Each territory is grown outward to a predetermined size: 8 to 11 cells. When a territory grows, it looks for any water cells adjacent to its land cells, and then one of the water cells is picked at random. This is a weighted pick; a water cell is more likely to be picked the more land cells are next to it, which helps keep the shape from getting too far out of control. If a territory can't expand to the minimum size, it fails. If this territory started from a continent seed, the seed doesn't go back onto the list to try again; the engine just fails the entire continent.

Seven continents are started in this way. Each of their seed territories is called a breadbasket, the heart of a continent, by the info page in the game. They're great places to gather resources and terrible places to keep units, because they're surrounded by other territories.

That's what comes next: Each breadbasket tries to become landlocked. A water cell next to it is picked at random, and that becomes the seed for a new territory, which expands. This process continues. If any water cell fails to become a territory because of size constraints, it's marked as off-limits. Once the center territory is surrounded by neighbors or unusable water, the continent is finished.

Continents tend to run together because of the size of the map and the way the territories are chosen.

Map generation phase 2: Water routes

For the game to work, every territory has to be able to reach, indirectly, every other territory. Because there can often be two or three land masses, that means water routes are needed.

First, a little explanation of how water routes work: Every water route consists of a line that starts in one of the eight compass directions, can turn by at most 45°, and can only turn once. Water routes are allowed to cross the west and east edges of the map, but only when headed directly east or west. And finally, no water route cell can be next to the cells of any other water route, so there's always a buffer between them.

Basic connectivity: Connecting land masses

The first step is to identify land masses that stand alone, and build water routes between them. This will ensure there is always some level of connectivity. Pick a territory at random, and build a list that includes it and all its neighbors, and so on until there are no more neighbors. If the list contains all of the territories, then minimal connectivity has been reached--and it's time to skip to advanced connectivity (below).

When connecting land masses, we need to find another land mass to connect to. Pick one of the territories at random that isn't part of land mass A, and gather it into a land mass also: land mass B. Find the land cells in each land mass that are adjacent to water. Now, it's time to radiate.

Water routes are built by "radiating" outward from land. Each land cell traverses a straight line along the water cells, until it hits another land cell or water that hasn't been marked as invalid. (Invalid water would be anything at the poles, or anything within 1 cell of an existing water route. Also when radiating diagonally, the sides of the map can't be crossed.) Each water cell keeps tracks of the territories that radiated to it: what direction they're in, and how far away they are.

Any water cell that can reach both land mass A and B, such that A and B are either 180° or 135° apart, can be the inflection point of a valid route. (Math people: I know it's a stretch to call it an inflection point if the route is actually straight, but screw it.) All of these water cells are gathered up, and their total distances are checked. There may be more than one route available for any given inflection point, but only the shortest distance counts. All longer routes are discarded. (In distance, each diagonal step counts as sqrt(2), while cardinal directions count as 1.)

Once all longer routes are eliminated, choose an inflection point at random from what's left. If it has multiple routes that are still viable, pick one of those at random as well. (If no route can be found, the route failed. This should never happen at the land mass stage.) Now draw a path from the inflection point to both land masses. This is a new water route. Mark the two territories it connects as neighbors, and any water cell within 1 cell's distance of the route should be marked as off-limits.

Continue until all land masses have been connected. Now it's time for advanced connectivity.

Advanced connectivity: Shortcuts

Now it's time to improve the map's connectivity by building in some shortcuts. The basic form ensures that all territories can reach one another, but it's best for gameplay to have more than one way to do it. Incursion avoids the "Australia scenario" as best it can.

Every territory that has coastline, and does not already have a water route, radiates outward into the water, just like the land masses did. But instead of saying we want one from side A and one from side B, the goal now is to determine whether each potential route will improve connectivity.

Here are the rules: Each path is as short as possible, and connects two territories whose distance in hops is as large as possible. (Neighbors are 1 hop away. Neighbors of neighbors are at most 2 hops away. And so on.) A water cell obviously can't be used as an inflection point if it only points to one territory, or was already marked as invalid.

At this point the map generator uses some heuristics. The two territories that might be connected, A and B, should be at least 4 hops away from each other. If not, there's no point connecting them by water. The "fitness" of any inflection point is measured by the number of hops between A and B, minus the distance of the water route. If fitness is less than -6, it isn't considered. (With a bigger map size, that heuristic might need to be renegotiated.) The fittest water route, if any, is chosen.

Once a route is found, if any, the water route is created, A and B no longer are used for connections, and of course cells next to the water route are marked as off limits. Hop distances need to be be recalculated. Then we can look for another route.

Advanced connectivity ends when there are no routes left to place that are deemed fit.

Map generation phase 3: Prettification

Straight lines don't make for good-looking borders. Incursion uses specialized icons that give territories a more organic look, although they're not as organic as they really ought to be. At this point let's talk about corners, where four cells meet. At least one of those cells has to be a land cell, and if all four are land then they can't all belong to the same territory--otherwise the corner isn't actually on a border, and is therefore not interesting. This is all about borders, after all.

Corners come in four flavors, described by the way their borders look: Straight, curve, T, or 4-way. Incursion comes with three visually distinct "forms" for each of these, and then rotates the icons as needed so that all possible combinations of borders are available. Each set of border icons breaks down like so:

• Territory in the northwest cell
• ...and its border
• Territory in the northeast cell
• ...and its border
• Territory in the southeast cell
• ...and its border
• Territory in the southwest cell
• ...and its border

When the same territory is used by two cells--such as when the corner is straight--some of these icons can be omitted. The corner icons are 16×16, the same size as each cell.

Now, the icons are created for each territory. For each corner it touches, the appropriate icon is chosen, shifted, and blended into place. This is done twice: once for the territory's land area icon, and once for the border icon. Borderless corners, i.e. interior space, are obviously solid for the land area and not used at all for the border.

(And this, friends, is a major reason why the /icon datum was born. Incursion's icon operations were major stressors on the server back when icon operations were only meant to be simple affairs like adding colors. The /icon datum allows multiple operations to be done before committing the result to the cache.)

Once the icons are created, the territories need names. There are many ways to generate names: I've always been partial to Werd, which is kind of a pattern engine, but I decided it wasn't enough for my purposes and expanded on the syntax to create sWerd. There's a limitation placed on the generator in that no two territories can have the same name--it will try again if it has to.

Bonus: The water icon

The animated water icons were something I whipped up on my own. They're designed so that they repeat every 2 tiles east, 1 south, which makes five of them forming a skewed square.

The water within that square is made up of many waves. These waves have a period that makes them repeat an integral (but random) number of times in the X and Y directions. One wave for instance might repeat five times to the right and two times up, forming a steep angle. The speed of each wave, the number of cycles it advances during the whole animation, is also an integer. The wave's amplitude and phase are random--they don't need to be integers.

Once all the waves are made, they're added up and the result is plugged into a little algorithm similar to a ray tracer to figure out how much light they should get from the "sun", and how much shadow, based on the height of the wave at each pixel. This was done over 16 frames of animation, and finally the result was ported into Dream Maker to create a .dmi file.

What I'd do differently

Now that BYOND is much more advanced, I'd probably change a few things. If I had to start from scratch--and the idea is sometimes tempting--I would probably use a map with a much larger number of cells, possibly even hexagonal cells for more interesting shapes. (I'd love to lose the cell concept entirely, but it's harder to manage things like figuring out where to place icons for units, resources, etc.) The prettified borders wouldn't be chosen from a set of three options, but would be custom-drawn. I'd even like to get in a little simple shading to provide some sense of terrain, which could hopefully be made to look like mountains and rivers along the borders.

Many of the colored icons I'd redo in a simpler way with atom.color. (Units maybe not so much, for various reasons including the fact that they use highlights.) Territory icons at least would be very interesting this way, because animation could be used to change their colors instead of abrupt transitions. As you can probably guess, the current game keeps track of a basic white territory icon, and only creates colored versions as needed.

Skin advances mean that the interface could be simpler too. A couple of bar controls could handle the basic troop and resource movements.

Animation means that the game could be visually a lot more interesting, and maptext would allow for more clarity in the gameplay.

Hopefully this post inspires you to take up the challenge of procedurally designing interesting maps, and making them beautiful. Procedural generation is fun, and in my case I was able to turn it into a good game--all because I wanted to know if I could. Go forth and strike the earth!