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

[Justin Moore <justin@xxxxxxxxxxx>]

> 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