GameDev.net Posting Guidelines (please read before posting)
Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.
Posted 30 October 2011 - 01:49 AM
Posted 30 October 2011 - 06:19 AM
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI
Posted 30 October 2011 - 07:27 AM
Posted 31 October 2011 - 08:05 AM
In a grid world without diagonal move, Manhattan distance is more accurate than Euclidean distance.If I have two admissible heuristics (less than the true cost), does using the more detailed heuristic (absolute distance) provide any benefit over the coarser heuristic (manhattan distance)? The more detailed heuristic returns different results when the coarser heuristic returns the same results.
Posted 31 October 2011 - 05:06 PM
The better is your heuristic, the less node you may expect to visit.
An other thing with heuristic is how it breaks tie which can favour some (equivalent) path from other.
Euclidean Distance will favour path along the straight line.
Posted 31 October 2011 - 11:36 PM
If I have two admissible heuristics (less than the true cost), does using the more detailed heuristic (absolute distance) provide any benefit over the coarser heuristic (manhattan distance)? The more detailed heuristic returns different results when the coarser heuristic returns the same results.
Posted 01 November 2011 - 07:08 AM
This is actually a useful point. People rarely bother with climbing that asymptotic curve to perfection. Eventually we get to "good enough". If you overestimate a little and speed up your search, not too many people are going to notice a slightly sub-optimal result.You can also overestimate on purpose to get a result faster, but once your heuristic overestimates, you might not get the shortest path. That's not always a real problem, because personally, I had 3 options to walk to work every day and no, I never bothered to find out which one might be a few steps longer. So in some cases overestimating a little can even be a good thing.
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI
Posted 03 November 2011 - 09:27 PM
This is my thread. There are many threads like it, but this one is mine.
Posted 03 November 2011 - 09:33 PM
Directionality is taken into account when you compare the other values of the potential squares you want to search next. If you move away from the goal, your cost goes up. If you move toward, the cost goes down. All the heuristic represents is a starting point from which to compare the total distances of your future selections. And for distance, no direction is needed.When I did the overestimating it made things much faster, but while most paths were fine when I had irregular geometry it could do strange things like hug a wall that was curving AROUND the goal.
For heuristing I was wondering if there's something that takes directionality into account more as I still don't always get the most obvious path for straight line.
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI
Posted 04 November 2011 - 08:48 PM
Posted 04 November 2011 - 11:49 PM
Directionality is taken into account when you compare the other values of the potential squares you want to search next. If you move away from the goal, your cost goes up. If you move toward, the cost goes down. All the heuristic represents is a starting point from which to compare the total distances of your future selections. And for distance, no direction is needed.When I did the overestimating it made things much faster, but while most paths were fine when I had irregular geometry it could do strange things like hug a wall that was curving AROUND the goal.
For heuristing I was wondering if there's something that takes directionality into account more as I still don't always get the most obvious path for straight line.
This is my thread. There are many threads like it, but this one is mine.
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.
GameDev.net™, the GameDev.net logo, and GDNet™ are trademarks of GameDev.net, LLC.