[Freeciv-Dev] (PR#9626) RFC: design for AI strategic road building

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=9626 >

(See also PR#8474.  This ticket should perhaps be merged in there, or 
vice versa.)

The current situation with AI stragic road building (connecting) is 
documented in PR#8474 and in road_bonus().  What it amounts to is that 
there is no overall strategy involved, just a consideration of a few of 
the nearby tiles when judging whether to build a road.  The result is 
that roads are built almost everywhere but no real connecting is done.

Greg and I discussed a design for a better system.  In this system each 
player has a network generated.  This network is just a boolean entry 
for each tile.  For marked tiles we want to build a road.  It is 
therefore easy to apply a suitable bonus in evaluate_improvements to 
make it more likely that a road is built here.

The next question is the designing of the network.  The most obvious 
solution is to generate a minimal spanning tree.  With roads this isn't 
necessarily optimal since it doesn't give you the fastest route across 
the empire.  But it's still pretty good.  The general algorithm is:

1.  Start with a single city (any city) in the network.
2.  Consider the distance to each other city.
3.  Add the city with shortest distance to the network.
4.  If any cities remain, go to 2.

This is something like O(n^2) (with n being the number of nodes, i.e., 
cities).

With PF this becomes:

1.  Take any city.
2.  Generate a PF map outward from this city with:
     - Move_cost = 0 for tiles with a road, 1 without.
     - extra_cost = 0 for tiles with a road, road build time without.
     (tiles that can't have roads built - like ocean - are unaccessible)
3.  Take the first city the PF map encounters; add all tiles on the path 
to the network.
4.  Goto 2.

This requires n different PF maps to be generated so is still something 
like O(n^2).  It gives a network with minimum distance of newly-built 
roads, with the tiebreaker being the minimum build time.  But note that 
we may not get the minimum distance in the end, since if existing roads 
take a non-optimal path we won't build a new path to replace them.  This 
can be fixed (for instance set move_cost to be 1 for all tiles), but 
this won't necessarily give better results.  Another alternative is to 
set the move_cost to be 0 for all tiles, so you get the road with 
minimum build time.  It's probably something best left until we can 
actually test the results before we worry too much about it.

This network can be cached but the cache becomes invalid when a 
non-networked road is built, a road is pillaged, a city is acquired or 
lost, etc.  In practice it should be quite sufficient to rebuild the 
cache each turn and probably sufficient to rebuild it every few turns. 
It might be a good idea to rebuild the cache when a new city is built so 
that roads to it can be started on immediately (building roads to a city 
taken by the enemy is probably not something to worry about, since 
settlers will avoid enemy units).

One thing we didn't discuss was different continents.  Obviously each 
continent will need a different network.  So the above must all be 
contained within some sort of loop to make continents work; I'm not sure 
how to make this most efficient.

We also didn't discuss railroads.  For the most part they work just the 
same as roads.  However here you have to consider the time for building 
road + railroad, if applicable.  And you may not be concerned with 
minimum distance at all (but it probably doesn't matter much).

Overall I think the design is quite nice.  However we briefly discussed 
disabling this for human players.  Human players may want to build their 
own connections and find it obnoxious to have the computer do this (as 
human players now find it obnoxious that autosettlers always build 
roads).  But other human players may like having the settlers do this 
automatically.

jason