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

[Jason Dorje Short <vze49r5w@xxxxxxxxxxx>]

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.
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.
Also consider how a unit (explorer) might get *back* from an uncolonized 
island, or move from one uncolonized island to another.
-----

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.
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?
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?
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 *might* be possible to do on a boat-by-boat basis - here boat B1 
realizes that it can carry units U1, U2, and U3 all at once.  But how 
does it know that U1 isn't better off taking boat B2?  I think this 
would end up being better, but still not ideal.
Unfortunately, that's about the extent of my constructive ideas.

jason