Sign in to follow this  

Pathfinding: Where do you apply the heuristics?

This topic is 402 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am currently in the progress of writing the Jump Sort Algorithm, which is basically A* with a massive skip function. But I am curious about something. Where do you apply the heuristic function? I've never written A* before, and the explination for it's pseudo code is rarely ever clear.

Do I add the Heuristic to the distance cost of the node when I submit the node to the open list and then sort? Or do I submit it with it's normal distance traveled, and search for a node with the best heuristic score?

Share this post


Link to post
Share on other sites

"Jump Point search"? http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/jump-point-search-fast-a-pathfinding-for-uniform-cost-grids-r4220

 

When adding nodes to the open list you add their heuristic to the cost of their path to the start node. That is, when you visit a node you add each of its successors to the open list with a tentative score "f"', where f = g + h. "g" is the true cost of the path you followed to reach the current node, plus the cost to enter the node you're adding to the open list. "h" is the heuristic value of the node being added. After you've processed all the successors you move the current node to the closed list and select the node with the lowest "f" from the open list.

Share this post


Link to post
Share on other sites

"Jump Point search"? http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/jump-point-search-fast-a-pathfinding-for-uniform-cost-grids-r4220

 

When adding nodes to the open list you add their heuristic to the cost of their path to the start node. That is, when you visit a node you add each of its successors to the open list with a tentative score "f"', where f = g + h. "g" is the true cost of the path you followed to reach the current node, plus the cost to enter the node you're adding to the open list. "h" is the heuristic value of the node being added. After you've processed all the successors you move the current node to the closed list and select the node with the lowest "f" from the open list.

 

Thank you! That cleared things up quickly enough. And yeah, Jump Point Search. Sorry about that. Been mentally burned out lately.

Share this post


Link to post
Share on other sites

This topic is 402 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this