Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 7 down vote favorite

What heuristics do programmers use in A* pathfinding for NavMeshes?

NavMesh = Navigation Mesh, its a type of pathfinding that uses meshes instead of waypoints.

share|improve this question
Please clarify your question. I don't know what you mean when you say "NavMeshes" (capitalized as if it's a Product Name™). Are you asking for alternative algorithms to A* which produce more approximate paths but in faster time? – Ricket♦ Jan 25 '11 at 18:37
1  
@Ricket ai-blog.net/archives/000152.html – Shawn Mclean Jan 25 '11 at 18:47
Gotcha, thanks! I've heard of them but never done anything with them so I didn't recognize the condensed name :) – Ricket♦ Jan 25 '11 at 19:21

2 Answers

up vote 9 down vote accepted

Take your pick:

http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

There's a load of heuristics described in that link, either for speed or accuracy. There's always a trade-off, so I would assume that developers would use the most accurate heuristic that would cause minimal impact to their game's performance.

share|improve this answer
These are for grid maps. Nav meshes I assume would use a different heuristics to move from one poly to the other. Probably some form of geometry heuristic to select the next best poly based on the size of the edge or something. – Shawn Mclean Jan 25 '11 at 20:40
3  
Agreed, but heuristics are used to estimate the shortest path to the final absolute destination to help with the cost to the next poly. They should underestimate the distance to be an "admissable heuristic". A navigation mesh is still a graph, just like a grid map is a graph. So I reckon most of those heuristics are applicable, it's down to the developer to see which is most applicable. – Ray Dey Jan 25 '11 at 21:55
up vote 1 down vote

A very, very rough (but very speedy) heuristic to use is: (Manhattan distance)

vec1 = start vector
vec2 = end vector

heuristic = abs(vec2.x - vec1.x) + abs(vec2.y - vec1.y))

This avoids any square rooting, which could be costly (Pythagorean distance).

share|improve this answer
Manhattan distance, no? – Ray Dey Jan 25 '11 at 20:16
I thought it was, then edited it out since I though it might not have been. – The Communist Duck Jan 25 '11 at 21:07
You could also use the squared length (Pythagorean distance without taking the square root). It's fast and most likely a better heuristic than Manhattan distance (unless your character can only move horizontally and vertically) – bummzack Jan 26 '11 at 8:42
@bummzack: Please read the "Euclidean distance, squared" section of Amit's heuristic page. Distance squared is not an admissible heuristic, and will result in suboptimal pathing. – Joe Wreschnig Jan 27 '11 at 9:24
1  
Squared distances are too small for short distances (A* wastes time) and too large for long distances (A* finds worse paths). There are good reasons to have the heuristic overestimate distances, but avoiding sqrt isn't one of them. Either use a fast sqrt approximation, or use a diagonal distance, or if your navigation graph is explicit, compute the Euclidean/Pythagorean distance once and store it with the edge between nodes. – amitp Jan 27 '11 at 18:29
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.