[Freeciv-Dev] Re: [RFC] Path finding interface

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Wed, Apr 10, 2002 at 11:38:55AM +0100, Gregory Berkolaiko wrote:
> On Wed, 10 Apr 2002, Raimar Falke wrote:
> 
> > On Tue, Apr 09, 2002 at 08:49:53PM +0100, Gregory Berkolaiko wrote:
> > > Sorry about the delay in replying.
> > > 
> > > I read your proposal.  It mostly deals with the path-finding, which is 
> > > the 
> > > structure above the map.  IMO path finding accounts for a quite small 
> > > percentage of the map-generation used by the AI.  So I think we should 
> > > start from the map.
> > 
> > I have only choosen the term "path finding" because warmap.[ch] is
> > only known to insiders and goto.[ch] was already gone.
> 
> I think move cost map is more general.
> A lot of warmap usage is about estimating distance, not calculating paths.

But you get the path for free as an extra. The distance eastimation is
easy, just take the turns.

> > > A comment:
> > > as you'll see from my map proposal I'd prefer to get the possibility of a 
> > > BMC-callback too.
> > 
> > What type of scenario could require this? You can even now adjust the
> > BMC with extra costs.
> 
> Yes, I thought about it, you are right.
> The "special" scenarios I had in mind are:
> 1. Finding the best route for a road from A to B:
> first minimize the length of the future road (equiv to BMC being igter), 
> than minimize over additional cost arising from the time required to build 
> the road.
> 2. Finding the shortest and safest path for a trireme (see anxious trireme 
> bug):
> first minimize over the lengths of all "safe" paths (the path is "safe" if 
> the unit ends its move next to the shore),
> than among these paths find the one which sticks to shore most of the time 
> (in case the trireme has to end the move early).
> Looking for safe paths would involve returning PF_IGNORE_COST as the 
> additional cost for the path which would end the turn away from shore.

An extra callback
 bool (*wait_test)(int x, int y, void *user_data);
which tells the core that the unit should wait a turn?

> This leads to the problem which is hardest to solve IMO:
> 3. Take into account the possibility to end move early to stay out of 
> trouble.
> 
> This would be very useful for military unit too.

We can declare a special return value (2*FC_INFINITY) of the callback
which will abort the calculation. And you may also use wait_test.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  reality.sys corrupt. Reboot Universe? (y,n,q)