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

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

[Top] [All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
To: freeciv-ai@xxxxxxxxxxx
Subject: [freeciv-ai] Re: [RFC] Ferry code
From: Jason Dorje Short <vze49r5w@xxxxxxxxxxx>
Date: Sat, 05 Apr 2003 17:34:55 -0500
Reply-to: jdorje@xxxxxxxxxxxxxxxxxxxxx

Gregory Berkolaiko wrote:
I thought lots about the ferry code (no, really!) and here is the outline of my

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.


[Prev in Thread] Current Thread [Next in Thread]