[freeciv-ai] Re: [RFC] Ferry code proposal v.2
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
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
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.
> > 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
> - 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,...).
[freeciv-ai] Re: [RFC] Ferry code proposal v.2, Jason Dorje Short, 2003/04/06