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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

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.
> 
> Aeehhmmmm. You have to create C pf maps every time something changes
> (here a ferryboat is book, a ferryboat is finished with its job and is
> free to take another, a ferryboat is build and some minor events). C
> here is the number of coastal tiles of the island 1. I would guess C
> is about 50-100. And "every time something changes" is 1-3 turns but
> can also be 1-3 times one turn. How can you say that this is CPU
> friendly?

Can be done O(1), see my reply to Jason.

> > 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,
> 
> And this are another C pf maps.

Still O(1).

> > from all coastal tiles we calculate all paths to Z.

[...]

> 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?

>  - rest as usual (two maps required)
> 
> So this would need 3 maps plus one map if somethings changes (ferry
> book, ferry finished, new ferry, new city,...).

G.