Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

When you add a new node to the closed list, you need to check all the adjacent nodes. If you find any adjacent nodes on the open list, you have to check if G would be lower if you went through the current node to get there.

My questions is, when checking if the G would be lower if you went through the current node, do you add up from the last node or start from 0?

Say you're using G = 14 for diagonal and G = 10 for horizontal. Last one on the closed list's G was 20. Your current node is one block lower from the last one on the closed list, and has an adjacent one that's on the open list with G = 34. Are you supposed to check if the G would be lower if you went through your current node by doing 20 + 10 + 14 = 44, 44 !< 34. Or, are you supposed to start from 0, so 0 + 10 + 14 = 24, 24 < 34?

I'm pretty sure it's the latter as with the former, the number is never going to be lower. But if it's the latter, wouldn't the number be lower every single time after a certain point?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

TL;DR : Yes, the adjacent nodes inherit the G cost from the current node PLUS the directional cost to the adjacent node.


When you check adjacent nodes, do you not already calculate the costs? The nodes you add to the open list should have some costs calculated and assigned to them. When the adjacent is already in the open list( aka already had its turn as "adjacent node") you compare those values with the values that are calculated from the current path. If the new one is cheaper you reassign the parent of the node in the open list to the current node.

Basically your "current node" is the node with the lowest costs in your open list/tree. And each time a tile/node has been processed it will be put in the closed list and the next one with the lowest costs will be processed. It keeps going until the goal has been reached or no solution is found. You are checking the adjacent nodes, calculate their costs and set their parent. So when you come across an adjacent node that is also already in the open list/tree the costs from that node is already calculated by a different potential path. That's when you compare values and see which path is superior and switch their parent ( or not if the other path deems to be faster ).

At the end you trace back through each parent node which eventually leads back to your starting point.

Note: A* can be achieved in different ways. I am assuming you are using some sort of uniform grid and iterate trough your tiles.

enter image description here

If you look at the third panel you can see that we check the adjacent tiles of the tile right from the starting point. The already checked tile above it ( top right adjacent from the start) has already a calculated cost. This cost was assigned to it when it was checked from the start ( note that I left H costs out for simplicity ). It appears that the new calculated cost actually takes 20 G to walk from the start point to this adjacent tile. But since the existing node in the open list has a G value of 10, which is lower, we let this one be. If the outcome were reversed where the new cost is cheaper we would set the parent of this adjacent tile in the open list to the current node and set the G value to the value that deems to be cheaper.

The cost of each adjacent node is :

currAdjNode.G = currentNode.G + directionCost; // 14 or 10 in your case
currAdjNode.H = //your manhatten distance function from currAdjNode;
currAdjNode.F = currAdjNode.G + currAdjNode.H;

If you keep iterating through each adjacent node this way the costs will logically add up. And thus also give you an easy solution for comparing open nodes with new nodes and determine whether or not to swap parents.

share|improve this answer
    
Thank you very much for the long and detailed answer. However, I'm aware of how the basics for A* pathfinding work. This line of yours confused me, however: "If the new one is cheaper you reassign the parent of the node in the closed list to the current node." I must have learned a different type of A* because from my understanding, the the node in the closed list usually IS the parent. Also what do you mean by this : "So when you come across an adjacent node that is also already in the closed list/tree the costs from that node is already calculated by a different potential path. –  Mastrolinie Sep 6 '13 at 4:21
    
Sorry I made a major mistake in my answer im trying to fix it now –  Sidar Sep 6 '13 at 4:22
    
That's when you compare values and see which path is superior and switch their parent ( or not if the other path deems to be faster )." Don't you compare values and see which is the better path when there's an adjacent square that was already on the open list? –  Mastrolinie Sep 6 '13 at 4:22
    
Either way, I'm not sure why someone edited my question as I don't believe it accurately portrays what I'm actually asking. My question is, when you calculate the cost to see if it would've been better to go through the current node to an adjacent square, rather than going directly, do you add up from the last node or start from 0? Read my example above to better understand what I'm trying to understand. –  Mastrolinie Sep 6 '13 at 4:27
    
Its late and i'm really tired, I only meant to talk about the open list. Does it make sense now? And I do believe I am answering your question. I explicitly say that the costs are precalculated when the adjacent nodes are checked. Each adjacent node "inherits" the cost from the parent node. –  Sidar Sep 6 '13 at 4:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.