Sign in to follow this  
Mantrid

A* queries

Recommended Posts

i'm studying off Patrick Lester's A* guide on gamedev (http://www.gamedev.net/reference/articles/article2003.asp) his algorithm for the A* planning process is as follows:
Quote:
1. Add the starting square (or node) to the open list. 2. Repeat the following: a) Look for the lowest F cost square on the open list. We refer to this as the current square. b) Switch it to the closed list. c) For each of the 8 squares adjacent to this current square … * If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following. * If it isn't on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square. * If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change. d) Stop when you: * Add the target square to the closed list, in which case the path has been found (see note below), or * Fail to find the target square, and the open list is empty. In this case, there is no path. 3. Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path.
when i implement this i'm having certain problems which i think i've narrowed down to these questions: 1-if it never re-opens closed nodes, then can't it box itself into a corner for a reasonably complicated route? (coupled with the manhattan heuristic my walker will go the wrong way when it meets a wall head-on and eventually get trapped in the corner to the perpendicular wall it joins - and never attempts to backtrack the other way) 2-if it does box itself in, and there are nodes still left open with a lower cost than it may be at, what's to stop it jumping to one of these open nodes even though they're not connected to the active node? (as far as i can tell there's no rules stopping this from happening when you search the entire open list for the lowest 'f' value, as soon as it finds somewhere in the open list with a lower f it'll go there) i'm probably reading a lot of this wrong but can't figure any better way :-/ this is a totally silly question i know, but i'm very new to AI programming.. as in last night new :(

Share this post


Link to post
Share on other sites
I haven't read the algorithm you posted thoroughly, but it sounds like you've misinterpreted the point of A*; it's not to be run as your walker is traversing the landscape, it's to be run before it starts to move. It searches for the optimal path, and to do this it may need to explore potentially wrong routes. Hope that helps :)

Share this post


Link to post
Share on other sites
I studied the A* last year, so apologies if my answers are a little rusty. Hopefully they aren't entirely incorrect at least :)

Quote:
1-if it never re-opens closed nodes, then can't it box itself into a corner for a reasonably complicated route? (coupled with the manhattan heuristic my walker will go the wrong way when it meets a wall head-on and eventually get trapped in the corner to the perpendicular wall it joins - and never attempts to backtrack the other way)


If all nodes end up closed then there is no route. It always chooses the node with the lowest F value (I think its F, F = G+H is it?) which might be right near the beginning or on an incorrect path.

In your example, it may fully explore the whole area which is wrong. Once every node has entered the closed list, A* will choose the node with the lowest f value, which will hopefully put it back on track. A* itself may be a bit slower if it can easily get stuck like this, but it should still return the correct path.

Quote:
2-if it does box itself in, and there are nodes still left open with a lower cost than it may be at, what's to stop it jumping to one of these open nodes even though they're not connected to the active node? (as far as i can tell there's no rules stopping this from happening when you search the entire open list for the lowest 'f' value, as soon as it finds somewhere in the open list with a lower f it'll go there)


If I remember this correctly, then that is what it should do. The final path is taken by traversing each parent of each node, so all of the exploring in the wrong direction will not be used.

I hope that makes some sense =)

Share this post


Link to post
Share on other sites
hey man! appreciate your reply.. but what if an agent goes up a narrow tunnel but can't turn backwards cos he can never come the way he came, because any point he has already been in is closed?(although thatd be ok, but he just groups himself into a corner which is less explanatory)

it's pretty weird, i'm sure im not reading between the lines in that algorithm somewhere?

Share this post


Link to post
Share on other sites
i'll clarfiy, here is my level (w=wall, p=walker)

wwwwwwwwwwwwwwwwwwwwwwwww
w e
w wwww w
w w
w w
w f w
w f w
w w
w wwwwwwwww w
w w
w w
w h w
w w
w w
w 2f w
w w
wwwwwwwwwwwww w
wx w
w w
w f w
w w
w w
w w
wp f w
wwwwwwwwwwwwwwwwwwwwwwwww


he gets the closest f ok, but cos of manhattan he goes for what i've stated as '2f'
but cos manhattan says he should go left from the first 'f', he gos top-left too much and can't backtrack so gets stuck at 'x' in a room of closed nodes :(

Share this post


Link to post
Share on other sites
I'm not sure if I'm following where you're getting confused here, but it sounds like you might be keeping the same closed list every time the algorithm is ran, maybe? You do understand that every time you run a query, the closed list should be empty and the open list should only have the agent's current node, right?

Share this post


Link to post
Share on other sites
Quote:
Original post by Mantrid
he gets the closest f ok, but cos of manhattan he goes for what i've stated as '2f' but cos manhattan says he should go left from the first 'f', he gos top-left too much and can't backtrack so gets stuck at 'x' in a room of closed nodes :(

The backtracking should occur when those nodes that have a low cost because of the manhattan estimate are checked and found invalid. At that point, all other nodes that are neighbours of the visited nodes should be in the open list. Thus, A* should look in the open list and find one of the nodes at the right end of the wall and continue looking there...

Sounds to me like you're clearing the open list when you shouldn't, or not adding all neigbouring nodes to the open list when you should...

Share this post


Link to post
Share on other sites
i think it might have sorted itself out now (as programs tend to do).. a few pointer errors when going from target->child->parent to send back the path might be to blame so far, i'm having a look through it. it's gonna be one of them days where it's something niggly...

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