a star - Understanding the AStar Algorithm -

from link: http://www.policyalmanac.org/games/astartutorial.htm

if adjacent square on open list, check see if path square is better one. in other words, check see if g score square lower if use current square there. if not, don’t anything.

example:

parent (already traversed): o
branches: a, b, c

parent (working on): a
branches: b, d

the open list contains, a, b, c , d.

now, bold statements in above quote comparing path with, path b? i.e. comparison of a b && o b or comparison of a b && a d

please clarify.

basic a* is:

while we're not close enough / destination     take point have now, lowest expected total cost (so known cost point plus estimated remaining cost).     calculate cost surrounding locations & add them priority queue expected total cost.  return route followed closest point 

in official a* terminology, g-score cost there. h-score estimate there want go.

extremes if h-score overestimates; new score (estimate + new cost) lower previous square's estimate + cost, you'll beeline target. if h-score underestimates (or 0, or whatever) you'll prefer squares closer point of departure, they'll have lower cost far, you'll floodfill position.

you can use a* theoretical point of view or practical point of view. theoretically, may never overestimate cost of link. means find efficient route, take longer finding you'll expand lot more nodes.

using practical point of view allows slightly-inadmissible heuristics (ones can overestimate slightly). route find unoptimal shouldn't bad game use. calculations way faster though, since don't expand anymore. 1 (slow) implementation had made took 6 minutes across 1k*1k map regular trig distance heuristic few seconds augmented times 3. routes weren't different. making heuristic times 5 made routes beeline & faster still, unusably so.

wrt direct question: it's second square evaluate. have roads o a,b,c planned (with given cost g each of routes). now, suppose there's highway o through b, instead of dirt road o b. means going through faster. when expanding looks @ surrounding squares , adds cost + heuristic open list if wasn't in there already. if in there, sees if new route faster (lower g square) , if so, replace it.

so in example, adds o->a->d list , checks if o->a->b faster o->b.

-- addendum

open list: 2 / (through o), 5 / b (through o), 7 / c (through o)

closed list: 0 / o (origin / through nothing)

take it's lowest cost far. then, each neighbor of calculate cost there.

• if there's entry , cost lower know far, replace entry.
• if there's no current entry, add it.

working on a, roads of cost 2 b , 3 d. going b through has cost of 4, current entry 5. replace it. d isn't in there, add it.

open list: 4 / b (through a), 5 / d (through a), 7 / c (through o)

closed list: 0 / o (origin / through nothing), 2 / (through o)

so compared b versus o b.