Sign in to follow this  
Norman Barrows

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

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

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

Not necessarily.

 

 

An impassable route can never be a legitimate return from A*. A route with a stupid cost [i]can[/i] 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

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