home
last update: March 8, 2006

AI design considerations

History teaches us that wars are won based on a strong economy and working supply lines to the troops in the field.  Battles are won with strong troops and the proper timing.   In the battle of Waterloo Wellington is quoted saying " I wish it was night and the Prussians were here", if I remember correctly.  Well, in the evening the Prussians came and Napoleon was beaten.  For our game that means that troops of all  three domains have to be coordinated to be at the same place and the same time for attack and better not be at a undefendable place when the counter-attack comes.  For a strong economy the settlers should do their job as efficient as possible, much running about is counter-productive. 

If some units of my AI do not seem to follow this philosophy,  it is simply due to bad implementation and will be fixed ASAP.   So what is need is a good

Path Finding Algorithm

Although the server offers a path finding algorithm, it soon becomes obvious that for the job at hand you will need your own brand.

Assume you have 20 settlers and you want to send one of them to a certain tile to build a road.  Obviously you want to pick the settler which is closest by.
With the server's GetMoveAdvice you will have to find the path for each of the settlers and then pick the best one.  That is not a very appealing notion.
What  you really want is an algorithm  that takes a list of those settlers  for input  and returns  the path of the unit suited best.

The above is just one example of the design problems encountered over and over again.  So here comes the need your own path finding algorithm (PFA).

A very simple PFA for finding that path from a start point to a target works like this:  the start point is labeled "0".  All points surrounding the start point are labeled "1".
Put these points into a list.  Sort the list by label.  Take the point with the lowest label from the list and label all surrounding points with "n+1", adding them to the list (except already labeled points).  Repeat till you hit the target point.  From the target point you trace back your way going from higher label to lower label till you hit the start point and you are done.

The above holds for equal cost moving from point to point, which is not the case here.  So you just modify the above procedure by labeling the points with the cost to reach them.  The search wave will expand with the points of lowest cost first and the path found will be cheapest in terms of movement points.

Now, who says that you can have only one start point and one attack point?  Indeed,  you can have multiple start points and also multiple target points.

So to find the best path for the unit closest by just run the described procedure with 20 start points simultaneously.  The search wave from the closest start point to the target  automatically blocks out search waves from other, farther start points. You could also exchange target and start point, but beware, for ground units the cost from start point to target may not be the same as the cost from target to start point, and therefore the path forward may differ from the path  backward.
 
You can picture the procedure as a "search wave" moving outward from the start point  till it hits the target.  This  picture leads immediately to the solution  of the  problem  of bringing two units together, e.g.  ground unit and ship.  Just start  two search waves simultaneously.  Where they meet will be the optimal boarding point.

A problem comes up with the Shinkansen wonder (cost to next point = 0 !) or attacking  an enemy just outside a city with ship or aircraft from inside this city ( they may not attack directly !) .   The problem is easily solved if  you store for each point the point ( or the direction !) it was reached from.  That information also eases the trace back from target point to start point as you do not have to search for the lowest cost of the points adjacent.

The actual algorithm is the search wave mechanism with three exchangeable subroutines:  the valid-routine, which checks the validity of the point moved to,  the cost-routine, which generates the cost incurred for each step, and finally the the target-routine, which check whether a target has been reached and handles whatever should be done once target/s is/are reached.   The  necessary trace-back routine is best  left separate,  as trace-back is not always required (e.g. when you plan railroad routes).  The exchangeablity of the subroutines different handling of the various problems that can be solved with the PFA. E.g. when planning for a railroad, one would replace move cost with building costs, etc.  In C++ that would be a template with the three subroutines as an argument.

The important feature of your own PFA is the versatility for the solution of all kinds of problems.  E.g if you want to know how hard a distant enemy can hit your unit, just use the PFA with the enemy location as the start point, your unit as the target, change the cost subroutine as required, and look at the result to see how much MP the enemy has left when attacking your unit. 

Please note that the compute time for the search wave goes with the square of  the radius of the search wave.  Therefore hundreds of units sitting on railroad tracks with the Shinkansen wonder available can really be a compute time killer.

PFA Implementation History


I first started with the GMA available from the server.  But soon I found that some problems could not be dealt with appropriately or where simply to time intensive. 

Then, with my own PFA, I could cut the PFA runs to one per target and settler, at least for settlers going to their jobs.  Even for those attack targets that a single unit could win against several PFA runs where required till a winning unit was found.  One PFA run per each attacker would be required if the one closest by was to be chosen. This also  holds for attack targets which required more than one unit to attack, as you have to collect the available units (then simulate the attack, check for success, attack or forget it).

The next step was was the idea to first find all eligible units before doing a search  wave for each of them.  This is done by doing a PFA first with the target as the start point and limiting the search wave radius appropriately.  Then all units outside the search radius obviously cannot attack this turn and do not need their own search wave.   Although this gained quite a bit of speed,  that was not  really helpful with the advent of aircraft with their very large movement radius.

Aircraft obviously had to be treated separately.  For aircraft it is possible to simply calculate the distance/movement points  to the target, so a searchwave is only necessary to find a path for the aircraft being truly moved.  This is not quite exact, as there might be enemy interference in the path, such that the eligibility found by calculation does not always hold. 

The next idea was to do a search wave for each unit at the the beginning of each turn and keep that information ( I call it path map) with each unit.  For each target it was then possible without a further searchwave to determine immerdiately which unit would be eligible for attack and the attack simulation could be done immediately ( for settlers the approriate goes). Also, the path to the target is directly available from the stored information.  Then, after the enemy is killed, only those units which could reach the enemy need new searchwave.  Obviously a path map makes only sense for one turn.

As it turns out,  there is a way to repair search wave results/ path maps when a tile changes.  So there is no need for a completely new search wave for to each unit in question, a search wave for a sector only will do.  Only the moved units will need a complete new search wave, but only if they are to be moved.  

Then I observed that very often like units are clustered at one location, therefore the search wave information is the same for all those units.  So it was sufficient to do the search wave for just one unit of each cluster.  The information is then not stored anymore with each unit,  but in a separate  list, with the units just having a pointer to that list.

Now Shinkansen comes along.  The time required for doing the search waves explodes.  So I took the above idea a step further.  I treat the Shinkasen railroad net as a fictious unit located at some base point, usually the city of the Shinkansen wonder.  Then I do the the search wave for a fictious unit at the base point.  For any other unit on the net but not at the base point, all relevant path information can be derived directly from the information the fictious unit holds.  Obviously, the fictious unit knows both the path to the real unit and also the path to the target, so one simply has to concatenate the two paths and low and behold, there is the path from the real unit somewhere on the net to the target.  The beauty is that a unit moved on the net needs no repair. If a repair is needed,
just repairing the the Shinkansen net is sufficient for all units that are on the net.

As it turns out, even all units that can reach the net in one turn can be included in this scheme.       

         

(to be continued)

home
top