Databases
StackOverflow2013
Postsdbo
POA* path finding: backed into a corner, now what?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POA* path finding: backed into a corner, now what?
    text
    copied!<p>I'm writing a tower defense game, and I'm implementing the A* path finding algorithm from tutorials and what not, but I've encountered a situation I can't code out of as of yet! Consider the graphic below. The cyan nodes represent the shortest path found so far, the violet nodes represent inspected nodes, and the dark gray nodes represent a wall.</p> <p>From what I know of the A* algorithm, to calculate a path for the situation below, it...</p> <ol> <li>Starts at "start" and checks if the upper node is available. It is. It calculates its G and H scores. It does the same to the right, lower, and left nodes.</li> <li>Finds that the right node has the lowest F score (F = G + H). It then repeats the same method as step #1 to find the next node, marking the "start" node as the parent.</li> <li>Continues this pattern and lands on the node in the center of the "C trap," as this node has the lowest F score so far.</li> <li>Discovers that the upper, right, lower, and left nodes are all closed. A* then marks this node as closed and starts over, understanding to leave this node alone.</li> </ol> <p><strong>What happens immediately after #4?</strong> Would A* re-examine the G and H scores along the same path, skipping that newly-closed node? Also, when drawing this scenario with <a href="http://theory.stanford.edu/~amitp/game-programming/a-star-flash/main-square.swf" rel="nofollow noreferrer">this SWF</a>, it indicates that more nodes are discovered to make up for the trap, as <a href="http://8bitboobs.com/stuff/situation1_solution.png" rel="nofollow noreferrer">suggested here</a>. Why?</p> <p><img src="https://8bitboobs.com/stuff/a-star/situation1.png" alt="Graphic of an A* problem"></p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload