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?

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!

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.

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?

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.