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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

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 
> your continent.

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.