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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Sat, 29 Jun 2002, Raimar Falke wrote:

> On Fri, Jun 28, 2002 at 10:28:49PM +0100, Gregory Berkolaiko wrote:
> > I put in priority queue instead of bucket list and got a very significant 
> > improvement, from around 11sec to 7.9sec.  I think it is mostly because of 
> > huge memory allocations that were necessary to do bucket list.
> 
> I have also restarted working on this. I also introduced a heap
> now. I'm currently fighting with a nice effect: the algo finds a
> shorter path to a tile. But this tile is in the heap and so the heap
> may become invalid. It has to be rebuilt. Took me quite some time to
> catch this.

That's the nasty one.  Causes a lot of problems.

> > Also, much to my surprise, when I put the lattice sizes to be the exact 
> > map sizes, as opposed to some power of 2, I also get good speed 
> > improvement.  Strange, I thought it is much faster to do x % 128 than to 
> > do x % 60...  Maybe my compiler does not optimize x % 128 to x | 127 ??
> 
> gcc -S is your friend. But I'm sure that it does.

Not a very friendly friend.  Last time I saw assembly code was about 10 
years ago on 80286...

But, by trial and error, I was able to deduce that yes, it optimizes 
ideed.  

> > Or the memory allocation is that expensive??
> 
> Could be. Maybe also cache trashing.
> 
> > > You can avoid the multiplication by using a 2D array.
> 
> I implemented this (and removed the hash). And it is quite painless:
> 
> struct pf_map {
>   struct cell **cells;
> ...
> };
> 
> build up:
> 
>   pf_map->cells = fc_malloc(sizeof(*pf_map->cells)*map.xsize);
>   for (x = 0; x < map.xsize; x++) {
>     pf_map->cells[x] = fc_malloc(sizeof(*pf_map->cells[x]) * map.ysize);
>     memset(pf_map->cells[x],0,sizeof(*pf_map->cells[x]) * map.ysize);
>   }

This is how it's done in generate_warmap.
I am not sure if the above for loop will be completely painless.

> accessing:
> 
> static struct cell *get_cell(pf_map_t pf_map, int x, int y)
> {
>   struct cell *result=&pf_map->cells[x][y];
> ...
> 
>       Raimar
> 
>