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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

I experimented a bit with the lattice management model in my path finding 
implementation.

notation: lattice = map = 2D array of nodes,
node = location = position contains data about costs of getting to it etc.

I used 3 methods:

1. allocate the whole lattice at once and fill (a potentially 
small part in).

2. allocate each node of the map as I reach it.  there is however a 
preallocated array of pointers to the nodes

3. fully dynamic allocation: the nodes are allocated as they are reached 
and are stored in a hash table (mostly copied from Raimar's 
implementation, introduced a few bugs, corrected them, in working order 
now it seems). 

Then I made 1000 repeats of making full maps for about 6 units.
The results (in secs, using clock()/CLOCKS_PER_SEC), averaged over 3 or 
more tries:

1:  9.6
2:  11.84
3:  21.89

Also the original generate_warmap:

2.73

There is some optimization that could be done to the code, but it won't 
reduce the time 4-fold.

Draw your own conclusions, I'm too tired and hungry today.

G.