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:

  1. AI must understand large-scale geography
  2. For good Military strategy AI must understand local geography
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: 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.

4.   Now do for regions what we did for contiguous areas, calculate: 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:

  1. floodfill algorithm
  2. Data structures that hold:
  3. shortest-path algorithm
  4. center-of mass algorithm
  5. 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)