Jump to content
  • Advertisement
Sign in to follow this  

A* with several possible endings

This topic is 4815 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 trying to draw a path from a node to any of several acceptable end nodes. Are there any good ways to adjust the heuristic for this case, other than the brute force of applying the single-end heuristic to each ending in turn, and choosing the lowest? Example : Draw a path from X to either A or B. Which one you end up at doesn't matter. oooooooooooooooooooooo oooooXoooooooooooooooo oooooooooooooooooooooo oooAoooooooooooooooooo ooooooooooooooooooBooo

Share this post


Link to post
Share on other sites
Advertisement
Might a solution be to have:

H(heuristic) = min(H to A, H to B)

Then the heuristic is always aimed at the closest target, but you still only do a single search.

Jim.

Share this post


Link to post
Share on other sites
JimPrice is right as long as you use the lower heuristic then you will be fine, you just need to keep exploring to you can see both nodes, not matter witch one you reach first. I would also consider how good each gaol is and use that to help decide witch node to go to along with the distance.

NodeA = Value(of gettig there)*A - Distance*B
NodeB = Value*A - Distance*B
if(NodeA < NodeB)
goto(NodeA);
else
goto(NodeB);

A and B are multipiers detirming how imortant distance is verus benfit of getting ther.

Share this post


Link to post
Share on other sites
I feel that using Dijkstra's is a really bad idea and will result in far more nodes being explored than necessary.

It seems reasonable to just find the min of the heuristics, as Jim says.

Mark

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!