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 :(

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 :)

it runs then the walker only updates once it has been given a complete output path

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 =)

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?

i'll clarfiy, here is my level (w=wall, p=walker)

wwwwwwwwwwwwwwwwwwwwwwwwww                       ew                wwww   ww                       ww                       ww  f                    ww                  f    ww                       ww          wwwwwwwww    ww                       ww                       ww               h       ww                       ww                       ww   2f                 ww                       wwwwwwwwwwwwww           wwx                      ww                       ww                 f     ww                       ww                       ww                       wwp      f               wwwwwwwwwwwwwwwwwwwwwwwwww

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 :(

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?

yup when they route is passed out to the main program both lists are emptied

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

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