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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Wed, 10 Apr 2002, Raimar Falke wrote:

> On Wed, Apr 10, 2002 at 04:30:23PM +0100, Gregory Berkolaiko wrote:
> > On Wed, 10 Apr 2002, Raimar Falke wrote:
> 
> > 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;
> }

doesn't work.
we start at the shore therefore it will always return FALSE.

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

not just that, but you cannot tell if the shore you found in the 
look-ahead is useful.


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

1. bool consider_waiting in the map structure to trigger it at all
2. push only safe locations, obviously ;)

> > > > 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?

I think the above is good solution.

G.