[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 06:04:29PM +0100, Gregory Berkolaiko wrote:
> > 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.
> 
> The base version should use pf_parameter. There may be a wrapper which
> get punit and uses the base version.

Why so categorically, "should use"?  Why not pass all the parameters as 
the arguments?  Where is the advantage in having a spoof data structure 
which is never used?

You are probably right, but please give reasons.

> > > > 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).
> 
> I though we have agreed that user supplied zoc checking is useless?!

Let me think again (I actually don't remember ever thinking about it, I 
think it was you arguing with yourself and then reaching an agreement with 
yourself.  I was too afraid to interfere ;)...

Some goto-related code uses a rather esoteric function goto_zoc_ok...

There is no need to have an end-user-specified function, but maybe some
service code could specify it.  It really depends if we want to convert
find_the_shortest_path to use PF module.  That'd be a messy job though.

G.