Complete.Org: Mailing Lists: Archives: freeciv-dev: September 2001:
[Freeciv-Dev] Re: Path finding: dijkstra vs a*
Home

[Freeciv-Dev] Re: Path finding: dijkstra vs a*

[Top] [All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
To: Freeciv Developers <freeciv-dev@xxxxxxxxxxx>
Subject: [Freeciv-Dev] Re: Path finding: dijkstra vs a*
From: Justin Moore <justin@xxxxxxxxxxx>
Date: Tue, 4 Sep 2001 11:35:09 -0400 (EDT)

> Has anybody considered implementing A* instead of the Dijkstra
> algorithm (which is AFAIK currently used)? Since I'm unfamiliar with
> A* can this result in a performance gain? AFAIK the method
> really_generate_warmap has top spot on the profile.

   From what I know of the really_generate_warmap function, A* won't be a
big help.  A* is a gain if you're actually searching for something
(AFAIK).  It looks like the function *has* to visit all the nodes since it
needs a value for each.  I know there are better ways to do the warmap
(dynamic programming methods come to mind) but I forget the best way to
implement them.

   If anyone wants to take a look around the 'net for it, there was an ACM
programming contest question like this.  You were put in a burning room
and had to figure out the distance to all the exits.  This basically
involved finding the distance to each tile in the room based on a per-tile
movement cost (fx, moving around chairs cost more).  Sound familiar? :)

-jdm

Department of Computer Science, Duke University, Durham, NC 27708-0129
Email:  justin@xxxxxxxxxxx



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