Site Stability Read more... ×

# A* Ambiguity problem and questions

This topic is 2937 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

So far I know that:
Open list = The adjacent tiles that I am looking into.
Closed list = The parent tile whose adjacent tiles are already explored.

If i am mistaken please clear it up.

My problem is in this:

From the start tile, there were 2 adjacent tile which equal F value, and again 2 of their adjacent tiles also had the same F values.
So why didnt it first move down once and move 3 tiles right (to hit the wall) and move back up and then 2 tile right and then down?
I am asking what made it think smart?

##### Share on other sites
.. it hit the wall, why don't it go up? The above tile from this tile would then have F:8 G:5, H:3. The F value is higher than other tiles in the open list so it will not be chosen.

##### Share on other sites
You are confused about how A* works. Remember, A* calculates the whole path before it starts to move. It doesn't do one step at a time. The f,g,h values you see there are what it is keeping track of as it is calculating in order to determine what it attempts to look at. It did attempt to look at the squares you mention which is why the bottom row is also calculated just as the square to the left is calculated as well. However, upon exploring the rest of the space (including the obstacle cell), it determined that going directly right was the shortest path.

##### Share on other sites
There was a good article in the articles section explaining HOW A* works. One step at a time. Read it and you will understand why it behaves that way. I think that will clear several questions.

##### Share on other sites
While writing my pathfind function, it got stuck on this statement, from here

[font="Arial"]
[/font]
[font="Arial"]Summary of the A* Method : statement = 2.c.3
[/font]

[font="Arial"]"If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change."[/quote]

[/font]
[font="Arial"]Are they telling me to compare the new adjacent Node's [/font][font="Arial"](that is already on my openList)[/font][font="Arial"] G value with my current Node's?
[/font]

##### Share on other sites

[font="Arial"]Are they telling me to compare the new adjacent Node's [/font][font="Arial"](that is already on my openList)[/font][font="Arial"] G value with my current Node's?
[/font]

Of course not. That would be meaningless and redundant with what they are saying.

You're supposed to check if that node is ALREADY in the open list and if your new path to get there is SHORTER than the one you found previously. That means your current nodes G PLUS the cost to actually get to the other node.

You might be able to skip that part if you are sure your heuristic will never overestimate the actual cost to the goal (and if searching/modifying the open list is more expensive than just pointlessly adding and processing the node twice with different Gs).

Edit: uhm... that link you posted even explicitely explains that:

"[font="Arial"]The other four squares are already on the open list, so we need to check if the paths to those squares are any better using this square to get there, using G scores as our point of reference. Let’s look at the square right above our selected square. Its current G score is 14. If we instead went through the current square to get there, the G score would be equal to 20 (10, which is the G score to get to the current square, plus 10 more to go vertically to the one just above it). A G score of 20 is higher than 14, so this is not a better path. That should make sense if you look at the diagram. It’s more direct to get to that square from the starting square by simply moving one square diagonally to get there, rather than moving horizontally one square, and then vertically one square. "
[/font]

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 15
• 21
• 25
• 11
• 25