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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

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 (1 map)

Actual ferry finding:
 - U to all shore tiles around 1 (1 map)
 - all shore tiles around 1 to all shore tiles around 2 (1 map)
 - all shore tiles around 2 to Z (1 map)

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.

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

> >  - rest as usual (two maps required)

This proposal does min(t_1), min(t_w), min(t_2).

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Despite all the medical advances of the 20th century, the mortality 
  rate remains unchanged at 1 death per person."