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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Wed, Jun 05, 2002 at 04:36:09PM +0100, Gregory Berkolaiko wrote:
> I now have a working implementation of the new path-finding.  
> Unfortunately it isn't yet fitted into the "interface", but the core is 
> fully working and extendable.
> 
> The queue is implemented as a bucket list.  The bucket list is implemented 
> as Ross Wetmore sketched in his warmap.c.  Major change: the list is 
> doubly-linked, this is quite necessary.  Proposed change: there is no 
> real need to remember both head and tail of each bucket: each bucket can 
> be implemented as LIFO not FIFO, this cutes the size of the whole 
> construct by two.

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

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

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 A life? Cool! Where can I download one?