Understanding the AStar Algorithm

From this link: Link

If an adjacent square is already on the open list, check to see if this path to that square is a better one. In other words, check to see if the G score for that square is lower if we use the current square to get there. If not, don’t do anything.

Example:

parent (already traversed): O

branches: A, B, C

parent (working on): A

Branches: B, D

The open list contains, A, B, C and now D.

Now, the bold statements in the above quote 开发者_高级运维are comparing which path with, path A to B? i.e. Comparison of A to B && O to B OR Comparison of A to B && A to D

Please clarify.

---

Basic A* is:

While we're not close enough to the / a destination
    Take the point that we have now, with the lowest expected total cost (so known cost up to this point plus estimated remaining cost).
    Calculate cost for all surrounding locations & add them back to the priority queue with their expected total cost.

return route that we followed to the closest point

In the official A* terminology, G-score is the cost to get there. H-score is the estimate to get from there to where you want to go.

Extremes are if your H-score always overestimates; the new score (estimate + new cost) will then always be lower than the previous square's estimate + cost, so you'll beeline to the target. If your H-score always underestimates (or is 0, or whatever) you'll always prefer squares closer to your point of departure, as they'll have a lower cost so far, so you'll basically floodfill from that position.

You can use A* from a theoretical point of view or from a practical point of view. Theoretically, you may never overestimate the cost of any link. That means that you will always find the most efficient route, but will take longer finding it as you'll expand a lot more nodes.

Using it from the practical point of view allows slightly-inadmissible heuristics (ones that can overestimate slightly). The route you find will most likely be slightly unoptimal but shouldn't be too bad for game use. The calculations get way faster though, since you don't expand everything anymore. One (slow) implementation I had made took 6 minutes across a 1k*1k map with a regular trig distance heuristic but only a few seconds with that augmented times 3. The routes weren't too different. Making the heuristic times 5 made the routes basically a beeline & much faster still, but unusably so.

WRT your direct question: It's the second square you evaluate. You have the roads from O to A,B,C planned (with a given cost G for each of those routes). Now, suppose there's a highway from O through A to B, instead of a dirt road from O to B. That means that going through A is faster. When expanding A it looks at all surrounding squares and adds the cost + heuristic to the open list if it wasn't in there already. If it was in there, it sees if the new route is faster (lower G to get to that square) and only if so, does it replace it.

So in your example, it adds O->A->D to the list and then checks if O->A->B is faster than O->B.

-- addendum

Open list: 2 / A (through O), 5 / B (through O), 7 / C (through O)

Closed list: 0 / O (origin / through nothing)

Take A as it's the lowest cost so far. Then, for each neighbor of A calculate the cost to get there.

• If there's an entry for it already and the cost is lower than we know so far, replace the entry.
• If there's no current entry, add it.

Working on A, with roads of cost 2 to B and 3 to D. Going to B through A has a cost of 4, where the current entry is 5. So we replace it. D isn't in there, so we add it.

Open list: 4 / B (through A), 5 / D (through A), 7 / C (through O)

Closed list: 0 / O (origin / through nothing), 2 / A (through O)

So we compared A to B versus O to B.

---

Well, if we are working on the node A, we are considering its neighbours. Say we are considering the B node now (which is in the openList).

The definition given tells us to compare the G value of B (previously computed when it was first added to open list when the working node was O) and the sum of the cost of reaching A from the begining (O) and the cost of reaching B from A.