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

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Wed, Apr 10, 2002 at 04:30:23PM +0100, Gregory Berkolaiko wrote:
> On Wed, 10 Apr 2002, Raimar Falke wrote:
> > On Wed, Apr 10, 2002 at 11:38:55AM +0100, Gregory Berkolaiko wrote:
> > > 
> > > 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?
> 
> no, too complicated.  What do you do inside wait_test?

It is basically a look-ahead.

> imagine: trireme is at point A, needs to go to B, the only path 
> A -> D2 -> D1 -> B (three moves, both Ds are dangerous).  You start with 
> only 2 moves.

Lets assume that the prototype is changed to
  bool (*wait_test)(int x, int y, int moves_left, void *user_data);

wait_test(a_x, a_y, 2, NULL) is called.

wait_test will look like
{
  square_iterate(x,y,moves_left,x1,y1) {
    if(is_shore(x1,y1)) return FALSE;
  }
  return TRUE;
}

But this will not always work. Since there is no guaranty that the
path this this one shore isn't blocked by any other means.

> One solution is to push the current point into the queue twice, with cost 
> 0 (corresponding to setting off at once) and with cost 2 (corresponding to 
> waiting for 2 moves).

Possible but this will be expensive since it would double the elements
we have to consider. So it has to be selective.

> The problem is, as before, the randomness of movement across terrain.  
> It'd be ok with triremes, but not with land units.
> 
> > > 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.
> 
> abortion is not a solution in this case

So what do you want?

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "There are three ways to get something done. Do it yourself, hire someone
  to do it for you or forbid your kids to do it."