The Map Placement Graph: Cities, Terrain Slopes & Brigades

The last week has revolved around the following things:

1. A new water rendering engine was introduced. The world oceans now have real waves, and coastlines have real foam.
2. The originally planned 1949 game start date has been changed to 1946.
3. I wrote a new engine for placing objects on the map.

This dev diary is going to be about item #3: figuring out how to place things on the map, in a good way. This is going to get a bit technical, so if you're just interested in gameplay writeups, I recommend skipping this one.

There's really just one thing that has to be placed on the map, and that's military units. Players need to be able to read, at a glance, whether a location has or does not have military units in it, and ideally, whether those units are friendly or hostile. Where do we put those? So far, in the province centers.

A grand strategy map is built out of thousands of small, irregularly shaped provinces. Each province has a province center, which is supposed to be the population center of the province, but sometimes it might end up just being the geographical center of the province.

But what if you want to have more than one thing in a province? Say, if you want a marker in the capital of a country, so that it's clear that this province is a bit more consequential than the other provinces of the country, because this is where the government has its seat.

Until now, it was enough to have just one point inside a province where you put things, military units, and that was fine. Ever since I added markers for capital cities, they've been clipping into the marker for military units. Looked awful.

So what can you do? You need to find more places in provinces to put things.

Easier said than done, because provinces are irregularly shaped, so you cannot really assume, well, anything about them. Some provinces have rivers crossing through them, some are forested (and we don't want trees clipping into our map objects), some have roads and railroads going through them.

Here's the solution I ended up pursuing: the placement graph.

The Placement Graph

The placement graph is a merged graph combining several things: province borders, rivers, roads, railroads, and "buildable areas". What are buildable areas? I took the topography map (the heightmap) and made steep slopes non-buildable, because human settlements are generally built on flat areas.

Above, you can see the current province map of the central Mediterranean, with non-buildable areas overlaid in black. This is a work in progress, so the final game might not have exactly this setup - most importantly, all of the Alps are non-buildable, which means that I will have to figure out a solution for Alpine countries, but it illustrates the point: we now have a map of where, and where not, we can place buildings and units.

The next step is to combine the buildable areas map with the province map and the rivers map.

By combining those things into one single graph, and subdividing edges whenever they intersect, we get many, many edges and many, many faces. Each one of those faces carries data: is it inside a river/road/railroad, is it buildable, which province does it belong to.

This means that I can take the province centers that I used to have, and ask the placement graph: which are the buildable areas near this province center, that also belong to this province, and aren't inside a river/road/railroad?

This opens the door to so many things.

For one thing, it becomes trivial to take a province and figure out the flat areas to put the city marker in, and to find another flat area to put the military units in. But that's not the best part, the best part is that we can now generate mini cities on the map using this graph, and figure out where to place them without the buildings ending up in water, clipping into steep slopes, etc.

I'm ever so slightly tempted to use this to start building a grand strategy-scale city builder.

What it means in practice, is that we can have dynamically growing cities, expanding their on-map footprint as their population expands in the simulation, rendered with hundreds of tiny on-map buildings (mostly houses, for now).

I want to use this to show mini cities: American suburbs, British townhouses, and massive, brutalist Eastern Bloc apartment complexes.

The placement graph in action

I didn't have time this week to finish this, but here you can see the principle in action:

There are some artifacts; most of these tiny flecks of color will be removed once the algorithm matures. What matters is the comparison to the province map:

The provine map is the map that decides the shapes of the smallest units on the map: provinces. Each unique color corresponds to one province. White is water. As you can see, the provinces along the southwestern coast of Sicily in these images have been subdivided more granularly than the province map itself, allowing me to place map objects such as military units and city buildings.

Atomic Dawn uses brigades of 5 000 men each as the standard military unit. Brigades can be infantry, militia, armored, artillery, etc. There are also air units (naval units are planned but TBD).

The above regions ensure that the land is flat enough, and is a reasonable distance from rivers, that things can be placed on it, and gives a proper shape that allows for intuitive placement inside it. That means proper cities with buildings, and it means that each brigade present in a province can get its own, individual 3D object on the map.

I think this is going to be wonderful: before the start of the Korean War, you will be able to see the North Korean tanks lining up along the 38th parallel north, an ominous sign of the storm to come.

Hopefully, I'll be able to set that up for a screenshot next week.