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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

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.

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

> 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);
  }

accessing:

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

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  The trick is to keep breathing.