In A star, do I use the sum or the edge cost?

Question

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?

Answer 1

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.

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.