Here's a question I have ...
Why doesn't the open list just contain the current working nodes (current node + adjacent nodes to current node) instead of all the nodes that all current nodes ever run into. There can never be a better path than an adjacent node near a current working node so why keep the history of all inspected nodes on the open list since they can't be a better path. Guess that means the open list would only ever contain about 8-9 nodes at most. Or am I leaving something out?
help calculating G cost of A* algorithm
Of course there can be a better path. Your program will start to greedily explore some path towards the goal, guided by the heuristic, and it may run into an alley with no exit. You would then have to pick one of the other nodes that the heuristic didn't favor the first time around and go from there.
Author
Ugh, my code works, it finds the target, but I know it's not right. I think I'll try to find another tutorial to see if it explains certain things differently that might clear things up for me.
I learned A* from one of Robert Sedgewick's books, and I really like the level of technicality (simple enough to understand, detailed enough to actually get things implemented). He has books in several programming languages, although I don't think the code is particularly idiomatic. The old editions were just one volume, but now apparently it has been divided into several parts: What you want is part 5, which deals with graphs. See if you can find it at the library of a local university.
EDIT: Never mind. I am looking through his website, and it doesn't look like there is much about A* there. I swear it was there in some older edition...
EDIT: Never mind. I am looking through his website, and it doesn't look like there is much about A* there. I swear it was there in some older edition...
Author
This is confusing me when my node runs into invalid terrain.
Lowest F score is 1675, so I drop it off of the open list and add to closed list.
Path is travelling downward (1575, 1625, 1675).
So now I search for a better path of nodes on open list by lowest G cost. G cost for each of these nodes is:
Current node is 1675.
398 + 10 = 408 for horiz/vert nodes, no better path found.
398 + 14 = 412 for diagonal nodes, no better path found.
Now I search all adjacent nodes to 1675 that are not already on the open list. This adds nodes 1724, 1725, and 1726 (the illegal terrain nodes). Because they're illegal, they DO NOT go on the open list.
So now I start a new iteration and its time to select the lowet F score on the open list and switch it to the closed list.
The problem is, my lowest F score on the open list is now like 10 rows up. And from here on out my nice clean path that I could see it traversing has just transported itself across my grid and things just get whacky.
Any ideas?
Lowest F score is 1675, so I drop it off of the open list and add to closed list.
1574 1575 1576
1624 1625 1626
1674 1675 1676
1724 1725 1726 (this row is a wall)
Path is travelling downward (1575, 1625, 1675).
So now I search for a better path of nodes on open list by lowest G cost. G cost for each of these nodes is:
382 378 382
392 388 392
402 398 402
X X X
Current node is 1675.
398 + 10 = 408 for horiz/vert nodes, no better path found.
398 + 14 = 412 for diagonal nodes, no better path found.
Now I search all adjacent nodes to 1675 that are not already on the open list. This adds nodes 1724, 1725, and 1726 (the illegal terrain nodes). Because they're illegal, they DO NOT go on the open list.
So now I start a new iteration and its time to select the lowet F score on the open list and switch it to the closed list.
The problem is, my lowest F score on the open list is now like 10 rows up. And from here on out my nice clean path that I could see it traversing has just transported itself across my grid and things just get whacky.
Any ideas?
This is expected behavior. You got to a point where the search cannot continue, so the search resumes elsewhere. What gets whacky?
Author
I guess that's good. Good that you think it should work like that, bad that I don't understand whats happening. Although now it just keeps running, it never finds a path. I had it working before, even though at some points the path solution before a wall looked like a christmas tree. But I'm thinking now that that was my fault in the way I was printing the nodes.
So at the point where I explained that it goes from node 1675 and seems to reset at 1174 (about ~10 rows back up) ... how can it continue to find a path if several of the nodes that it tried to find a solution with the first time are no longer on the open list. They're on the closed list now and unavailable to be traversed again.
I didn't read anything about resetting any lists in the tutorial.
So at the point where I explained that it goes from node 1675 and seems to reset at 1174 (about ~10 rows back up) ... how can it continue to find a path if several of the nodes that it tried to find a solution with the first time are no longer on the open list. They're on the closed list now and unavailable to be traversed again.
I didn't read anything about resetting any lists in the tutorial.
The path that A* finds is not the sequence of nodes expanded: That's just the procedure used to find the path, with attempts that don't work out included. The search ends whenever you pick the goal to be expanded. Whenever that happens, you need to reconstruct the path. The easiest way to do that is to store the parent of each node (the node we reached it from, when we updated its G cost), follow the sequence of parents from the goal to the start and then reverse the list. Alternatively, if you remember all the G costs, you can find the neighbor of the goal that minimizes the sum of G and the cost to move to the goal, then find the neighbor of that node that minimizes the sum of G and the cost to move to that node, etc.
Author
Ah, ok. So I think I'm starting to get it. When I had no obstacles in my path, The path was always the lowest F score and that's what I would store (and print) for my path. And it worked fine. Then once I started adding obstacles, I would see huge blotchy type areas and I wasn't using parents as I should, rather, I was still thinking like a path w/ no obstacles. I haven't fixed this yet, but at least now I think I understand what should be happening. Thanks for your help.
Author
I see my path taking shape, but trying to debug areas where the parent is wrong.
If a better path was found because it has a lower G cost, and then after G, H, and F scores along w/ its parent has been updated ... do I then drop it from the open list to closed list? Or does a better path found mean that better path node stays on the open list?
So far the only time I see that I ever drop a node from the open to closed list is when a node is checked for the low F score. And up until my path is screwed up, I can see when I backtrace for parent nodes, they're all on the closed list. So my path looks good from the start to point of screw-up and all those nodes are on the closed list. At the point of screwup, I see nodes on the open list.
If a better path was found because it has a lower G cost, and then after G, H, and F scores along w/ its parent has been updated ... do I then drop it from the open list to closed list? Or does a better path found mean that better path node stays on the open list?
So far the only time I see that I ever drop a node from the open to closed list is when a node is checked for the low F score. And up until my path is screwed up, I can see when I backtrace for parent nodes, they're all on the closed list. So my path looks good from the start to point of screw-up and all those nodes are on the closed list. At the point of screwup, I see nodes on the open list.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
