astar heuristics and heuristic weight
-
What exactly does the heuristic weight do?
I'm familiar with the astar algorithm itself. It's the Dijkstra algorithm plus a heuristic function (typically the manhattan or diagonal distance). In this case does the "heuristic weight" replace the heuristic function, or does it just add a modifier to the heuristic?
It would be great if we could just see the source, but you've got it a bit obfuscated.
-
I thought this was a good read. It won't get you details on the specific implementation for findPath... commands but helpful I think at least for me.
http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html
-
That's the set of articles that prompted me to ask this question
-
The current implementation uses PathFinding.js library so you can study its source to gain some insight. heuristicWeight is just a multiplicative factor in the formula:
F = G + weight*H
You can start from this line in the sources.
-
So, using a value < 1 makes the creeps stick more to roads, and > 1 less to roads and more cross country than by default, favoring straight lines - right?
-
@Amadox- You're technically write but I think it'll help to understand why you are right and what the tradeoffs are
A value less than 1 turns the AStar algorithm into Dijkstra's algorithm. This is guaranteed to find the shortest path, so it will in theory favor roads (if the shortest path is along a road). However, performance is going to *suck* for this.
A value that is really high turns AStar into a greedy best search first algorithm. This will favor direct lines to the destination, but has a chance of getting "caught" by obstacles and making a path that is not ideal.
Those are the two extremes, which are easier to get to with the modifier. To really understand what's doing on you need to understand the heuristic itself. It is just a calculation describing the distance remaining in a naive (straight line) sense. Typically this is the diagonal distance (Math.max(dx, dy)) or the Manhattan distance (dx+dy).
If your heuristic is completely accurate (it guesses the exact distance) then you will get the best performance out of the algorithm. This is only likely to occur on areas that are completed paved and have a lot of straight lines.
If your heuristic is slightly under the real number you will always find the shortest path, but you'll expand more nodes and have less performance.
If your heuristic is slightly over the real number then your paths will be mostly short, occasionally a little longer, but your performance will be the best.
After some testing you should set the modifier to 1.5. This gives a larger bias to moving towards the goal (improving performance) but slow enough that G still matters (thus preventing some of the more dumb path decisions that could show up).
-
.
