[freeciv-ai] [RFC] Ferry code proposal v.2

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

Here is another proposal for the ferry code.  It is influenced by Raimar's 
and Jason's insistence on considering all coastal tiles.

The suggested implementation goes back to Per's idea of the ferry
availability map (FAM) -- I convinced myself that I can do it in O(1),
where time is measured in units of creating one full PF map for 1
ferryboat.  I don't want to follow another idea of Per and keep a PF map
for each free boat and overlay them where possible.  In any case, the way
we create the FAM is not crucial now and can be disputed separately.

***********************************************************************
Problem 1: unit U at A on continent 1 wants to move to Z on continent 2.

1. We make sure we have an up-to-date FAM.  For each _coastal_ location
(x, y) the FAM contains the number of turns it will take the closest real
or virtual boat to get to (x, y).  For virtual boats we take into account
the building time.  Initially, we allow virtual boats at (x, y) only if
(x, y) is the city which will build it.

2. We make a big map for U to go to all coastal tiles T1 on 1 where it
will spend FAM(T1) - Walk_Time(T1) turns waiting, then from each T1 we
calculate paths to all coastal tiles of continent 2, from all coastal
tiles we calculate all paths to Z.  This calculation is also O(1).

3. Once a route has been decided,

* If the boat is real*, 
 it is booked, directed to the embarkation place and thereafter each turn 
both U and the boat check if the other is still alive and onit's way to 
the embarkation point.

* If the boat is virtual*
 the city is ordered to build a boat, the unit is directed to the city but 
each turn after that the search for a real boat is repeted.

Notes: 
1. This way, the real boat and the unit automatically meet at the 
optimal point.
2. If there are no willing cities and no boats to be seen, U presses the 
red "D" button :)  Well, considers it.


***********************************************************************
Problem 2: Unit U wants an estimate of time to get to various places Z.

Since U is possibly virtual we don't want to book anything so stage 3 is 
not needed.  Stage 2 remains the same, but instead of the actual FAM we 
use a clever mathematical average of the FAMs over last turns.


How does that sound?

G.

P.S. Per, I forgot how you called the map and so invented another acronym 
:)