[Freeciv-Dev] Re: Path finding: dijkstra vs a*
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
> 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
|
|