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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Mon, Apr 07, 2003 at 01:23:29PM +0100, Gregory Berkolaiko wrote:
> 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).

Looks like you know how to use pf in some create ways.

So I agree with your proposal.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 checking for the vaidity of the Maxwell laws on this machine... ok
 checking if e=mc^2... ok
 checking if we can safely swap on /dev/fd0... yes
    -- kvirc 2.0.0's configure