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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

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.

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/

Best wishes,
G.

path_finding10.h
Description: Text document

path_finding10.c
Description: Text document

dynamic_pf.diff
Description: Text document