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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Sun, 6 Apr 2003, Jason Dorje Short wrote:

> 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.
> 
> > 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.  This calculation is also O(1).
> 
> I don't think this is O(1).  If you have to calculate the PF map from 
> every coastal tile of 1 to every coastal tile of 2, that should be O(n) 
> (n == # of coastal tiles of 1).  Unless you cache this information?

Can be done O(1).  Instead of having 1 initial position, push n initial 
positions into the priority queue at the start of the algorithm and 
calculate 1 map.

G.

P.S. Why do we have to approve Jason's posts?  Isn't he subscribed to 
freeciv-ai?