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

# [freeciv-ai] Re: [RFC] Ferry code

[Top] [All Lists]

 To: Freeciv AI development Subject: [freeciv-ai] Re: [RFC] Ferry code From: Gregory Berkolaiko Date: Sun, 6 Apr 2003 00:45:47 +0100 (BST)

```On Sat, 5 Apr 2003, Jason Dorje Short wrote:

> Gregory Berkolaiko wrote:
> > I thought lots about the ferry code (no, really!) and here is the outline
> > of my
> > proposal.
> >
> > Setup: unit U on continent 1 wants to move to Z on continent 2.
> >
> > We make a big map for U to go to all coastal towns T(i) on 1 where it will
> > spend
> > approx N(i) turns waiting, then from each town we calculate paths to all
> > coast
> > tiles of continent 2, from all coastal tiles we calculate all paths to Z.
> > This
> > calculation is not much costlier than normal map for one unit btw!
>
> I don't see why coastal towns should come into play.  There's no reason
> a ferry route should be related to them at all, and it will lead to some
> non-optimal routes.

I was actually thinking that a city will keep a tab on how well it can
serve the passengers and this info can be fed back into the
ferry-path-finding and, more importantly, crossing time estimation.  I
felt that finding a real boat each time you want a quick estimate of the
time to get from A to Z is a bit over the top.

Also, if there is no ferry in sight, a spot on the coast won't be able to
build it for you.

If you do it according to Per's initial proposal, you would know exactly
where would you get a boat and where not.  Unfortunately such extensive
information is costly to compute, and, being very exact, it doesn't remain
valid for too long.  Heisenberg principle, that sort of thing.

> Suppose U is on continent 1, right next to boat B1, and wants to go to Z
> on continent 2 right across the channel.  The only city on the continent
> is on the other side, and contains boat B2.  Now your algorithm will
> have B2 ferry U (probably after U crosses the continent), while the
> fastest way is just to have U board B1.

Such situations are theoretically possible, but I don't think they will
have much practical impact.  Units get built in the cities, they go to
other cities to conquer them, whole game is cities-based.  The only units
which do get far from settled area are explorers but I am willing to
ignore them to keep the code simpler.  Besides even explorers should
explore near the cities.

> Also consider how a unit (explorer) might get *back* from an uncolonized
> island, or move from one uncolonized island to another.

In the present state of the code, there would be no explorer on
an uncolonized island.

> -----
>
> If for U you consider every boat B(i) (i: [0,n)), then you can pick the
> optimal boat to get you where you want to go.  This is an O(n)
> operation, but probably no worse than having to look at every city on

Come to think of it, not much worse...

> Problem 1: How do you define optimal?  Is the only consideration how
> long it takes U to get to its destination?  Or do you consider how much
> of B(i)'s time you're taking up?  If B(i) can ferry other units while U
> is on the way, is this better?

Let's not let our imagination run away :)

> Problem 2: How do you get multiple units onto a boat?  If B(i) knows
> it's ferrying U, how does U2 go about employing the boat to carry it as
> well?

Short answer: I don't know how to do it.

> I think the only real solution to the ferry problem is a global one.
> You can't consider units on a case-by-case basis.  But if you look at
> all your units and where they need to go, you can assign boat B1 to
> ferry units U1, U2, and U3 from point A on continent 1 to point B on
> continent 2, while boat B2 ferries unit U4 from C on continent 1 to D on
> continent 2.  Then you just tell B1, U1, U2, and U3 to all meet up at A,
> while B2 and U4 meet up at C.

This is sci-fi, as far as I am concerned.  If you have any practical
ideas, please explain them in detail.  Mind you, very often you just need
an estimate of the time to get from A on cont 1 to Z on cont 2.

G.

```