• Advertisement
Sign in to follow this  

A*, A Star: impassable nodes can just go on the closed list?

This topic is 744 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

A*, A Star: impassable nodes can just go on the closed list?

 

grid map.  nodes are either passable with uniform cost (IE 1), or impassable (insanely high cost, IE 1000000).

 

when visiting neighbor nodes, impassable nodes that are neither open nor closed will go on the open list with a very high cost. and there they will just sit more or less until the end, unless a shorter path to it is found, and then it will be closed. but it will never be part of the solution, so why bother putting it in the open list? am i missing something? 

 

i'm using the algo from Amit's A* pages.

 

if they can just go on the closed list with a high cost (f), you could put them all on the closed list before you started A*.  this could speed up the search / sort for lowest_open_node.

 

yes?  no?   maybe?

Share this post


Link to post
Share on other sites
Advertisement


If a node is literally impassable, it shouldn't even be considered part of the graph. I wouldn't count them as even neighboring anything.

 

so don't even visit / expand them then, eh?

 

sounds good. thanks!

Share this post


Link to post
Share on other sites

Unless you have an infinite map, you have to do some kind of test to make sure you don't go outside the map bounds when looking for neighbours at the edges of the map. If you treat impassable terrain the same way, it will never be processed. 

 

Also, remember, high cost is not the same as impassable. If the numbers align, that node may be considered a viable route.

Share this post


Link to post
Share on other sites


Also, remember, high cost is not the same as impassable. If the numbers align, that node may be considered a viable route.

 

but an insanely high cost will give you the same result, just with more work, right?

Share this post


Link to post
Share on other sites

Not necessarily.

 

 

An impassable route can never be a legitimate return from A*. A route with a stupid cost can be. Unless your agents are rejecting paths based on their cost outside of A*, you will eventually get an agent trying to travel an impassable route.

Share this post


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

  • Advertisement