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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Mon, 7 Apr 2003, Raimar Falke wrote:

> On Sun, Apr 06, 2003 at 10:32:31PM +0100, Gregory Berkolaiko wrote:
> > On Sun, 6 Apr 2003, Raimar Falke wrote:
> > 
> > > On Sun, Apr 06, 2003 at 07:53:16PM +0100, Gregory Berkolaiko wrote:
> > > > 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.
> 
> Let me see if I got this right
> 
> Update:
>  - all ferries to all shore tiles around 1 (map 1)
> 
> Actual ferry finding:
>  - U to all shore tiles around 1 (map A)
>  - all shore tiles around 1 to all shore tiles around 2 (map B)
>  - all shore tiles around 2 to Z (map C)

Yes, this is correct.  The above maps A, B and C complement each other.
(sorry I edited your text).

> I'm not sure what it does compute however. It is not min(t_1 + t_w +
> t_2) with t_1 time till pickup = max(time for U to go to the pickup
> point, time for the ferry to go to the pickup point), t_w = water
> travel time and t_2 is from the drop point till Z. for min(t_1 + t_w +
> t_2) you have AFAIK to calculate seperate water maps. It is hard to
> tell since you didn't said how the best path is choosen.

Yes it will calculate min(t_1 + t_w + t_2).
It will set up map B by initialising all shore tiles of 1 with their t_1
(by this time we have map A ready) and initialising shore tiles of 2 in 
map C with their t_1+t_w (which will be taken from map B).

> 
> > > I think the idea that you save a map for each idle ferryboat is
> > > better. Because they just don't change. In you proposal above you have
> > > to update the numbers everytime another unit booked a ferryboat. With
> > > Per's idea you just have to consider one unit/map less. So my proposal
> > > 2:
> > >  - update the map for each idle ferry and all coastal cities
> > >  - go over all costal/shore tiles of 1:
> > >    for each ferry or city:
> > >      calculate time to reach the tile (this is fast since the ferry
> > >      maps are "filled" out)
> > >  - choose best as pickup point
> > 
> > what if the pickup point you chose is on an internal sea?
> 
> You have to guard against this. For example by not producing ships in
> internal seas.

Internal sea is the limiting case of course.  Besides on some generators 
internal seas might be big enough to warrant boat construction.

Let me give you an example (map attached).  Alexander the Great wants to
travel from Babylon to Athens.  He has to get a ferry somewhere because
going around the Black Sea is out of question. There are two idle boats,
one at Umm Qasr another at Sidon.  Your algorithm will send him to Umm
Qasr, because it's just down the river (so it gives you min t_1). But the
boat from Umm Qasr would have to go around whole of Africa, since you
don't have Suez Canal!!!

G.

map.jpg
Description: JPEG image