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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Sun, Jun 23, 2002 at 10:43:27PM +0100, Gregory Berkolaiko wrote:
> 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.

Looks familiar ;)

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

Can you make a test like 1. but with static allocation? This would be
similar to the current code.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 Q:  Do you know what the death rate around here is?
 A:  One per person.