[freecivai] 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 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 uptodate 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 50100. And "every time something changes" is 13 turns but
can also be 13 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
 [freecivai] Re: [RFC] Ferry code, (continued)

