The Clash of Civilizations
Map AI
Here's my take on how to give AI players a functional grasp of geography.
Its written with world-scale geography in mind, but others might find the
same ideas useful for battle-scale terrain evaluation. I have coded
none of this yet, so although I think its correct, keep in mind that it
may be worth what you paid for it ;)
Issues:
-
AI must understand large-scale geography
-
Which features are contiguous on either land or water
-
In the absence of enemy forces what is the most efficient way to get from
A to B
-
If the best route is blocked, decide alternates and be able to decide whether
to capture the blocked waypoint, or go some other way
-
Use large-scale geographic knowledge to determine good defensive lines,
reasonable limits of expansion. Hopefully this will help limit strategic
over-extension
-
For good Military strategy AI must understand local geography
-
Identify road and rail junctions, mountain passes etc.
-
Assess how quickly enemy and friendly force can be applied to a given point
Proposed Method:
Use a background thread to perform detailed map analysis. This
first pass to promote geographical understanding by the AI will see the
whole map. The Idea is that in using it only AI players that can
see selected portions of the map get the background information.
For instance using the Americas as an example, an AI player that only sees
only South America will not know the importance of the isthmus of
Panama. An AI player that can see all of the Americas up to and including
Mexico will know that Panama is an important bridge between South and North
America, and in fact is the only land path between the two. It still
won't know just how important since it doesn't yet know the complete size
of the American landmass. The exact amount of background information
needed to reach this understanding is undetermined, but will be heavily
dependent on seeing the isthmus or waypoint clearly, and also having knowledge
of substantial geography on each side of it.
The details for obtaining geographic knowledge for an arbitrarily designed
world are given below
1. Determine all contiguous map regions using a floodfill algorithm.
Keep going until all the map is covered. Label the edges of each
region. Each feature is assigned a unique identifier (One-square
features are assigned 0 and get no further processing since the label one-square
(=0) plus the terrain type tells all.) In the rare occasion when
you might want to label a one-square feature it can be labeled as larger
ones are. Can use a Byte variable for the identifier, with + numbers
indicating land features, and - water features.
2. For each contiguous map region calculate:
-
its size in squares
-
its "center of gravity" (this need not actually be in the feature)
-
other regions that abut it (using edges recorded above)
3. Sub-divide each large contiguous feature into regions. This is
difficult to do in a "human" way but I think it can be done reasonably.
The key idea is to use a shortest path algorithm e.g. A*...
on a moderately large number of pairs of randomly chosen points.
The number of paths for which a square is on or very near the shortest
path will tell you where the "hotspots" are.


The figure above left shows a sample continental landmass. It
is divided into two large pieces separated by an isthmus (the red region
at top right). The dark lines indicate the best paths between four
pairs of points. (terrain features other than major rivers aren't shown)
If we did 100 paths instead, a very large proportion of them would run
through the neck. If we take the area fraction of part A to be a,
and B b we get trivially that the fraction of paths staying in A
is a2 . Assuming the neck is small those running through
the neck will be ~ 1 - a2 - b2 = 2a(1-a).
If a ~ 50% the neck "path intensity" will be almost 50% of all paths, decreasing
to about 20% of paths if a ~ 10% of the area.
I will use the areas with very high path intensity
as dividers between the large, more uniform continental regions.
In the case of the figure above the AI can, after this procedure, recognize
that the continent is divided by the neck into regions A and B. Further
the peninsula beneath the letter B in the figure cannot confuse the issue
using this procedure. Since the peninsula is at most 5% of the total
area of continent A-B the path weighting of it will be less than 2(.05)(.95)
~ 10% so that the values at the base of the peninsula will be less
than 1/5 that on the main A-B neck.
Here's how to do the A, B... division of the continent into regions:
1) Identify the N most important necks by their value. And mark
them as neck 1-N
(for a small continent maybe only a few are needed, for a Asia-Europe-Africa
type
continent probably 5 or 6 would not be unreasonable.)
2) Select a non-neck point and arbitrarily define it as in region A.
3) Any point that can be reached from A without going through one of
the necks is also part of A
(use a simple floodfill algorithm)
4) do 2-3 again but for points that do not lie in A or a neck, call
this B
5) Keep doing above until all land belongs either to a "region" (A,
B, C...) or a neck 1-N
In this way the algorithm will produce the areas of necks and labelled
regions.
Note: you could also do the neck and region membership as fuzzy sets
to not make the neck-region distinction so abrupt.
A few more details.
-
In addition to large weights at necks, this method will also give large
values at the edges of interior features, for instance inland seas.
Since such bands of large numbers of shortest path crossings aren't generally
strategically significant (you can just move around the sea at a distance
from the shore, for instance) we want to give "pretty good" paths equal
weights with shortest paths. Pretty good paths can be obtained by using
a weighted A* algorithm. With an evaluation function f = g + xh where
x >= 1 we change from shortest paths to simply pretty good ones.
With this modification with x maybe 2 or so we'll get a random good path
rather than the shortest one.
-
Another way to accomplish this (suggested by Tim Smith) is to use previous
"path intensity" (from previous paths crossing a square) as an additional
cost of moving into the square. This will spread out "path intensity"
across necks without significantly changing anything, and yet prevent shores
of interior seas from racking up huge scores. This type of treatment
will give results like those shown in the figure above on the right side.
-
We'll need to do some consistency checks on the regions (like A and B)
that the algorithm has divided large landmasses and oceans into.
These sub-regions should now be able to meet some reasonable constraints
if we are to be able to really trust them. I'll need to experiment
around but an obvious one is that the continent sections should be fairly
compact. At any rate they must be more compact than the whole original
landmass. Something like a best-fit rectangle or circle overlay of
the same area as the region should get 70% of the region's squares within
it. I'll just have to experiment.
-
The choke points for the main body of ocean, if there is one, will be a
little more difficult. Need to experiment around with it. We
may get several possibilities at to what makes sense for the major oceans.
The bullet point immediately above will help in that a body of water with
reasonably good compactness will satisfy most practical definitions of
an ocean
4. Now do for regions what we did for contiguous areas, calculate:
-
its size in squares, figure edge squares for each region
-
its "center of gravity" (this will now most likely be in the feature)
-
other regions that abut it including necks (using edges recorded above)
-
Figure additional very-close contacts, e.g. islands within a 2-square sea
voyage. Nearby landmasses will be indicated by necks in the ocean
and vice versa. For nearby ones we'll also need to record the distance.
I plan to use 100 as the movement cost for the "opposite" type, so when
considering moving over a narrow sea bridge the cost will usually be multiples
of 100. For instance Pas de Calais to southern England might be recorded
as 100 since it requires a one-square sea voyage. This value will
be modified by friendly and enemy seapower effects when an AI player actually
uses it.
The upshot of all this work will, I think, allow the AI to look at a map
in a way that is relatively similar to the way we do. For instance,
when the AI plans an attack from continent A to continent B in the map
above it will know that there are 3 basic choices: thru the neck, via the
"North Sea"or the "South Sea". These three choices come out of the
list of geographic pointers that tell it what features are adjacent to
region A and B. The AI can then assess enemy strength along the 3 different
paths in a simplified way like you or I would. In other words if
the neck is defensible and the enemy controls it the AI should look to
either of the amphibious attack options. The results of these quick
calculations will, of course, have to be checked in detail using finer-scale
algorithms. But I think that giving the AI a chance to prune the
possible solutions down to a few cases for detailed investigation will
help alot.
My apologies, but I've only written down the ideas for the first half
of the "Issues" list at the top of this page. Eventually I'll get
the rest written up.
To do list for implementation:
-
floodfill algorithm
-
Data structures that hold:
-
feature number (each mapsquare) and sub-features, eg A or the neck
-
feature number of adjacent region for edges (each mapsquare)
-
pointers to all adjacent land an sea regions
-
shortest-path algorithm
-
center-of mass algorithm
-
algorithm to decide if an AI Player knows about a certain geographic feature
Home Civilization
Advances Chart (133K) Map AI
Screen Shot
Economy Screen Economic
Development Gaming/AI
Links
Coming soon... Clash's RealPolitik AI (calculated using Genetic Algorithms
in a background thread)
