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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

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?

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

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

This is exactly one pf map: you start at Z and go backwards.

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

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

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  Tank: So what do you need? Besides a miracle.
  Neo: Guns. Lots of guns.
    -- From The Matrix