[Freeciv-Dev] Re: [RFC] Path finding implementation.

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Wed, 5 Jun 2002, Raimar Falke wrote:

> On Wed, Jun 05, 2002 at 04:36:09PM +0100, Gregory Berkolaiko wrote:
> > BMCs are provided as call-backs.  Once we've identified all necessary BMCs 
> > and done some performance tests, they can be hard-wired inside the main 
> > loop.
> > 
> > pf_parameter is not used.  And I don't really see a point in using it: 
> > user'd have to allocate it, fill it in, give it to map initialization 
> > routine for processing, which seems a waste of time.  Just give the map 
> > initializator the unit or, if you are doing something exotic, full 
> > details.  An intermediate case (unit_type + initial_position) can also be 
> > done.
> 
> The path_finding must be able to cope with virtual units. This is one
> of the reason for pf_parameter. From the move_type you can also deduce
> the BMC type.

Of course.  But to use pf_parameter, the user has to set 5 (!) parameters
relating to the type of the unit.  To cope with virtual units it is easier
to have a wrapper which you supply with the unit_type and the initial
positions, which I already mentioned above.

> > Lifting the paths from a ready map is not implemented.  That shouldn't be 
> > a problem though.
> > 
> > The definition of the best path is simplified.  We can include more 
> > information, but I don't yet see any examples which are both doable and 
> > useful.
> > 
> > As a working example I include a patch to ai_manage_explorer.  It becomes 
> > trireme-safe, but the drawback is that triremes lack imagination (_always_ 
> > keep to the shore). 
> > 
> > Files:
> > path_finding10.[ch]  --- to go into server/ although they should really 
> >                      migrate to client
> > dynamic_pf.diff --- patch to manage_explorer against today's CVS, assumes 
> >                      path_finding10.[ch] are in server/
> 
> Extra cost doesn't have to fit into a char. You have no ZOC handling.

You can increase the extra cost limit.  But that will increase the size of 
the bucket list...

I will write an alternative implementation with a priority queue instead 
of the bucket list --- there you can have any extra cost.

ZOC, yes, I forgot about it.  It can be done via (maybe even 
user-supplied) function is_enemy_zoc(int x, int y, struct player).

G.