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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Sat, Jun 29, 2002 at 06:32:48PM +0100, Gregory Berkolaiko wrote:
> 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.

Ok here is the version 11 with a sample implementation. Changes to the
interface:
 - remove enum turn_index
 - rename the user data arguments
 - make the arrays turn and remaining_move_points scalar values

Changes in the implementation: 
 - exchange the hash with a 2D array
 - exchange the list with a heap
 - cache tile pointer
 - add ptile->move_cost2

The implementation still needs 7 times as much time as the gotohand.c
code. To be honest I don't know why my code is so much slower than
yours. But thats not the real problem. 

I would like that we agree upon an interface and let the two
implementations run in parallel to catch the remaining bugs. Parallel
to this I would implement the famous is_position_dangerous if I get
the time. I expect that this will require some work to get right.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "From what I am reading Win98 and NT5.0 will be getting rid of all that
  crap anyway. Seems that Microsoft has invented something called TCP/IP and
  another really revolutionary concept called DNS that eliminates the
  netbios crap too. All that arping from browsers is going to go away.
  I also hear rumors that they are on the verge of breakthrough discoveries
  called NFS, and LPD too. Given enough time and money, they might
  eventually invent Unix."
    -- George Bonser in linux-kernel

path_finding11.diff.gz
Description: GNU Zip compressed data