Complete.Org: Mailing Lists: Archives: freeciv-dev: June 2002:
[Freeciv-Dev] Re: [RFC] Path finding implementation.
Home

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

[Top] [All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
To: Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>
Cc: Freeciv Development List <freeciv-dev@xxxxxxxxxxx>, "Ross W. Wetmore" <rwetmore@xxxxxxxxxxxx>
Subject: [Freeciv-Dev] Re: [RFC] Path finding implementation.
From: Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>
Date: Sat, 29 Jun 2002 12:35:37 +0200

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.


[Prev in Thread] Current Thread [Next in Thread]