This article is part technical documentation, part feature list and also
part FAQ. It intends to explain why Diorama was written the way it was,
why `it takes so long' and what it can do that would be extremely hard
for other random map generators to achieve.

Diorama aims to create maps that are both strategically appealing and
visually appealing. Both aspects are important to a good map, and Diorama
treats both properties roughly equal. The approach used to create a map
can be described as a top-down approach. First an abstract representation
of a map is generated, and then it is fleshed out and refined in stages.

Compare this to a bottom-up approach where the you start with random
detail (such as a height map) and then infer overall structure. This
approach is much faster, but a significant downside is that it is
very hard to guarantee in a natural way certain properties (such as
reachability) of the final result - or even to request certain
properties.

The main problem with a top-down approach is not coming up with a good
abstract map representation (a simple 2d maze will work), but to create
said maze in the first place so that it is interesting
*strategically*.

Something that is significant in a map is your starting location. It would
be easy to randomly assign a position on the map (and for oil wells as
well) and hope it works out. But that won't make for an interesting game
necessarily. For instance you might be unlucky and be stuck on a tiny
random mountain with no way to do anything. Or very lucky and have all
the oil on the map be next to your starting position.

Generally it would be desirable if the player bases are as far apart from
each other as possible. For two player bases the solution to this problem
is trivial: Opposite corners - if they are both free and not taken up by
randomly generated impassable terrain. For four players it might seem
obvious that its the four corners -- but what about non-square maps?
Eight player maps are even more complicated, and a good solution is
non-obvious.

Let's complicate the matters further: Free oil wells are oil wells which
do not belong to a player's starting oil wells, i.e. oil wells that are
up for grabs. These free oil wells should also be as far apart from each
other and each player base as possible. (But this constraint is not
quite as important as player bases being as far from each other as
possible.)

If we assume we can place things anywhere on the map, then we can lay
out the players bases and oil wells in a regular grid and then draw bits
around. But this would give boring maps, as they are always more or less
the same. On the other hand if we try and put a regular grid over the
existing random terrain, we may not be able to get the location we want.
Simply not placing the feature is unacceptable, nor is placing it
somewhere random.

We could however try every possible combination, measure the minimum
distance between each feature, and then pick the one that has the
largest minimum distance. However this quickly becomes impractical.
On a 12 x 12 map (very small) with 8 player bases and 4 random oil wells
we are looking at 103619293824707388 possible combinations to choose 12
locations from a possible 144. Given we can check 10000 of those each
second we'd still be looking at roughly 328574 exciting years of
computation.

Genetic algorithms do help, but they tend to favour a local minimum and
its impossible to know if the solution found is actually the best there
is. At this point you could reasonably argue that *"who **** cares,
its just a warzone map!"*, but that would lame and we *can* do
better.

This is one of the problems we are attacking with answer set
programming (ASP). ASP is a declarative approach to solving search
problems, so you write a description of the problem (in a
logic like language) and then give this description to a
solver (kind of like a theorem prover) which will come up
with valid model (solution) of the problem. But not
just any solution, we will arrive at the *optimal* solution, and
we can *prove* that the solution is optimal. The down
side is that generating this can take exponential time (this
is why requesting very large maps can take a while) but it
allows both local ("a base must have a given number of
entrances") and global ("every base must be able to reach
every other base") conditions on the map to be expressed
simply, cleanly and efficiently. Critically we don't have to
change any of the algorithms when the conditions on the map
change, we just change the description that gets input into
the solver.

Another problem is coming up with good random terrain where
every significant point of interest is reachable (by walking or
driving). Assigning each point a random height and then blurring
will give a reasonable result, but it will be uniform in its randomness
and won't make for a strategically interesting game.

Terrain should not be flat, but not just random either. There should be
clear features, such as (to name a few) winded ramps up to player's bases,
hills, canyons, causeways, lakes, and so on. Since warzone only offers
us 256 hight levels we can't just draw what we want either. Also, if
we start making mountains in one area of the map, we may end up with
an stupidly high cliff with no way to connect the two areas of the map.

The entire map is generated from an abstract representation; the main
hard part is coming up with a good one. The format is as follows:

3@121232

33333123

32011322

32133223

33132333

200223@3

i3221232

Each number represents a cell. (The parameters map cell width and map
cell height in diorama influence how large this initial map
representation is. The
parameter cell scale influences to how many tiles squared (roughly) each
cell expands to on the final map.) The numbers represent a cells height
with 0 being the lowest and 3 being the highest in this case. The
@ symbols indicate a player's starting
base, although each player's base also has a height value like any other
cell (but it is not shown here). The blue
i's indicate the locations where free
oil wells should be placed (like player bases, they also have a height
value which is not shown in the above diagram).

Cliffs are drawn along edges where there is a difference in height numbers
of at least 2. So for example in the first row, there is a cliff between
the second and third cell.

This is actually enough to draw a map, but it would end up very blocky:

Figure 1: Map with only straight cliffs.

If we simply jitter each point on the grid a draw cliffs between them
we will get a much more natural layout.

Figure 2: Map with jittered cliffs.

This is one example of how the abstract map gets more and more refined.

Another high level feature of a map is roads. There is two approaches to
this, roads on urban maps (grid pattern) and roads on arizona and rockies
maps (random). Urban roads are much simpler: We simply arrange the roads
in a grid, double up some of them (for dual carriage ways) and poke holes
into the grid (for the nuclear wasteland look and feel).

Roads on arizona and rockies maps are a bit more interesting. We first
decide where to draw roads: Each player base should be connected to a
road somehow (as that way you immediately notice the roads and you think
'hey, this is kinda nifty'). We then decided that each oil well cluster
should also be connected to a road as they also represent interesting
points on the map. Finally, we pick a few (maybe 3) of totally random
points on the map and also make sure they are connected to the road
network somehow.

We then construct a minimum spanning tree between each of those points and
draw a road between them. However, if we apply a standard path-finding
algorithm which assumes the cost to go from any one square to an
adjacent square is equal, we get a pretty ugly result as shown below:

Figure 3: Standard equal cost path-finding. Roads are highlighted in blue for illustration purposes.

You will notice immediately that roads criss-cross each other, are fairly
"square" and generally... quite messy. Not how a civilisation would
construct them. If we already have a road somewhere, its better to
re-use it as much as possible. Adjusting the path-finding algorithm
so that going to any road tile already on the map is significantly
cheaper will give a result as shown below:

Figure 4: Re-used roads.

However, just finding the shortest distance
does not give a realistic result, so will be slightly more random in
how we compute the `shortest' path. Thus in our path-finding
algorithm we have a very low cost associated with going to a tile
that already contains a road, and we have a high (and a little bit random)
cost associated for choosing a non-road tile.
The result is a fairly natural looking network of paths, twisting and
turning but ultimately reaching each target in a fairly efficient manner,
as shown below:

Figure 5: Jittered roads.

By default the map will just be covered in the same texture (red sand for
example). We then further refine the map by splatting random textures
across it.

There are technical difficulties, such as correctly
drawing all the transitions between one terrain style and another (and not
all transitions are possible), but these are implementation details.

This is another area we use ASP. We have a model of a good player base,
which is basically: Buildings should be aligned in a grid, there must be
a gap between them, the base overall should leave as many rows and
columns free (i.e. lots of straights with empty tiles without
buildings on them).

Around the base a wall is drawn and a hole is poked in it to give you an
entrance.

The reason we don't just have a pre-defined model of a base and just place
it on the map is that we don't really know what kind of terrain will
be around a player base: There may be cliffs in inconvenient places. The
ASP will work around those and will give us a good model regardless.

Finally, we place neutral features on the map: Buildings on the urban maps,
rocks and scavenger villages for arizona maps, and trees and huts on
rockies maps.

We're slightly more clever in how to place them by making use of all the
information we have generated in earlier stages: For example on urban
maps, buildings are placed next to roads; on arizona maps we place
the scavenger towns in a circle around any of the roads; on rockies maps
we place trees on non-snow terrain and snowy trees on snowy terrain.