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)
