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.
JimC has coded up a demonstration to show how these path intensity ideas work in practice. Here is a link to the
MapAI demo, and
the thread that discusses it is Map AI so far. I have used the demo to construct a continent that looks somewhat like the one shown in the figures above. The results of the tests are shown in the two figures below. In the first plot, blue is water and green is land. The small numbers, if you can make them out, show the path intensity values that come out of the demo. By far the highest intensity occurs on the neck between the A and B regions of the continent. Note: The values are smoothed a little bit to remove some artifacts that originate because of using relatively few points. That results in there being some intensity on a few sea squares. The second picture just shows in red-tones the path intensity itself that comes out of the demo. You can see that the area around the neck by far has the highest values.
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
(To learn more about this
topic, click here)
|
