Complete.Org: Mailing Lists: Archives: freeciv-ai: April 2003: [freeciv-ai] Re: [RFC] Ferry code proposal v.2

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

[Top] [All Lists]

 To: Gregory Berkolaiko Cc: Freeciv AI development Subject: [freeciv-ai] Re: [RFC] Ferry code proposal v.2 From: Raimar Falke Date: Sun, 6 Apr 2003 22:47:45 +0200

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

```