# A* with several possible endings

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

## 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 on other sites
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 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 on other sites
Or you can use Dikstra's

##### 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

1. 1
Rutin
69
2. 2
3. 3
4. 4
5. 5

• 21
• 10
• 33
• 20
• 9
• ### Forum Statistics

• Total Topics
633430
• Total Posts
3011831
• ### Who's Online (See full list)

There are no registered users currently online

×