Sign in to follow this  
QuackCoder

A* Ambiguity problem and questions

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:
[img]https://lh5.googleusercontent.com/-0kAD42Idbew/Topq9h6UExI/AAAAAAAAAB4/W_VCYdelEZQ/Untitled.jpg[/img]

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 this post


Link to post
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 this post


Link to post
Share on other sites
You are confused about how A* works. Remember, A* calculates the [i]whole [/i]path before it starts to move. It doesn't do one step at a time. The [i]f,g,h[/i] 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 [i]did[/i] 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 [i]rest[/i] of the space (including the obstacle cell), it determined that going directly right was the shortest path.

Share this post


Link to post
Share on other sites
While writing my pathfind function, it got stuck on this statement, from [url="http://www.policyalmanac.org/games/aStarTutorial.htm"]here[/url]

[i][font="Arial"][size="2"][quote][/size][/font][/i]
[b][font="Arial"][size="2"]Summary of the A* Method : statement = 2.c.3
[/size][/font][/b]
[i][font="Arial"][size="2"][size="3"][b]"[/b]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.[b]"[/b][/size][/quote]

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

Share this post


Link to post
Share on other sites
[quote name='QuackCoder' timestamp='1317783772' post='4869193']
[font="Arial"][size="2"]Are they telling me to compare the new adjacent Node's [/size][/font][font="Arial"][size="2"](that is already on my openList)[/size][/font][font="Arial"][size="2"] G value with my current Node's?
[/size][/font][/quote]

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"][size="2"]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. "
[/size][/font]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this