[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, 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
- 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
> > - rest as usual (two maps required)
This proposal does min(t_1), min(t_w), min(t_2).
"Despite all the medical advances of the 20th century, the mortality
rate remains unchanged at 1 death per person."
[freeciv-ai] Re: [RFC] Ferry code proposal v.2, Jason Dorje Short, 2003/04/06