Document A* and reference implementation

explain

https://learn.unity.com/tutorial/graph-theory#5e0b72d3edbc2a144cf5cb47

Early exit

https://www.redblobgames.com/pathfinding/early-exit/

Region growth or procedural map

https://www.redblobgames.com/pathfinding/distance-to-any/#region-growth

Apply to towerdefense

https://www.redblobgames.com/pathfinding/tower-defense/

Movement cost and Infulence map for detect enemy or friendly unit

http://theory.stanford.edu/~amitp/GameProgramming/MovementCosts.html

 http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html

I go into a lot more detail here, with interactive diagrams.

⁽¹⁾ I’m skipping a small detail here. You do need to check to see if the node’s g value can be lowered, and if so, you re-open it.

OPEN = priority queue containing START
CLOSED = empty set
while lowest rank in OPEN is not the GOAL:
  current = remove lowest rank item from OPEN
  add current to CLOSED
  for neighbors of current:
    cost = g(current) + movementcost(current, neighbor)
    if neighbor in OPEN and cost less than g(neighbor):
      remove neighbor from OPEN, because new path is better
    if neighbor in CLOSED and cost less than g(neighbor): ⁽²⁾
      remove neighbor from CLOSED
    if neighbor not in OPEN and neighbor not in CLOSED:
      set g(neighbor) to cost
      add neighbor to OPEN
      set priority queue rank to g(neighbor) + h(neighbor)
      set neighbor's parent to current

reconstruct reverse path from goal to start
by following parent pointers

https://pavcreations.com/pathfinding-with-a-star-algorithm-in-unity-small-game-project/

We now have all the elements to start writing the main algorithm. Let’s get right to it!OPEN_LIST
CLOSED_LIST
ADD start_cell to OPEN_LIST

LOOP
    current_cell = cell in OPEN_LIST with the lowest F_COST
    REMOVE current_cell from OPEN_LIST
    ADD current_cell to CLOSED_LIST

IF current_cell is finish_cell
    RETURN

FOR EACH adjacent_cell to current_cell
    IF adjacent_cell is unwalkable OR adjacent_cell is in CLOSED_LIST
        SKIP to the next adjacent_cell

    IF new_path to adjacent_cell is shorter OR adjacent_cell is not in OPEN_LIST
        SET F_COST of adjacent_cell
        SET parent of adjacent_cell to current_cell
        IF adjacent_cell is not in OPEN_LIST
            ADD adjacent_cell to OPEN_LIST