A* Pathfinding

Okay, I'm definitely missing something and it's really bothering me, haha. So I guess it's time to take it to the forums!

So this is my general summary of how I understand A* Pathfinding. Note that I'm only looking at horizontal/vertical surrounding tiles, therefore eliminating the need for G.

That means, I'm working with the formula: F=H, where H is the estimated distance from the current tile being looked at to the destination tile without taking into consideration impassible tiles.



So lets take a simple example:
http://devworld.ca/map1.jpg

The blue tile represents the current on tile, and for right now is the starting tile (or character location). The red tile represents the destination tile, and the black ones are impassible tiles.



Examining the surrounding tiles of the current tile, we see the following H values of each:
http://devworld.ca/map2.jpg


We then take the shortest one, that is, the closest tile to the destination and add it to an array we can call pathHold. So now we repeat the process from this now new current tile:
http://devworld.ca/map3.jpg



This is where my issue begins. We now see that we have a matching H value, but visually it's obvious that the lower tile is the best route to take to the destination.

However, how do you determine which is the best one via code? And what generally happens is this result:
http://devworld.ca/map4.jpg


Sometimes it'll just take the wrong path, and because it made that bad choice at the 'fork in the road', it'll start going the long way around basically going through each tile.


What exactly am I not doing, or taking into consideration?

I haven't personally implemented A* before but my understanding is you should be calculating the cost for the entire path and then moving along it, not calculating it for one step at a time. It sounds like that is what you are doing.

you need a G cost for vertical horizontal tiles as well. The G cost for those tiles is 1, the G for a diagonal tile is roughly 1.4. So in your second image, the cost of the tiles should be 6, 5 + 1 or F = H + G

as a search continues the g cost raises for a certain tile based on the path to get there. If you keep a list of all open tiles and sort it based on the F cost, then your other tile (in fig2) will be selected.

Hm.

I just assumed that since there are no diagonal movements allowed, you could remove the g cost entirely, since both vertical and horizontal movements will be a cost of one. So you don't need to add it.



Also, the above images are in a sense the process of calculating the path to the destination. Once that's reached, then it begins the actual movement. So what you're suggesting in other words is to calculate all the potential routes to the location and then select the quickest one?

Although, I don't think that's how A* deals with pathfinding. Ahh, I'm so confused.

My understanding is that you would keep sorting the open tiles (ones that are adjacent to tiles you have 'checked', ones that have H values) from least to greatest and looking at them. So when you reach your fork in the road, and have the two 5 options, if your code takes one step north, the next open tile would be a 6, but it would not check that 6 first, it would check the other 5 first... You definately still want G, as that is what makes A* better than a purely greedy pathfinding, and what makes it better at things just like what you have shown here.

It has been awhile since I read A* Wikipedia has all the pseudo code steps for it and I recall it being a pretty reasonable read.

Found a great site for A* visualization:
http://www.policyalmanac.org/games/aStarTutorial.htm

Your dropping of G is your problem. G is not 1 for all your squares, G is +1 for all your squares.

Your sorting of open tiles should sort them by the SUM of G and H. G being the total cost to get there (from the start, not just the cost of that one square), H being the guess for how far is left to target.

So as your example takes a step north, G keeps growing by 1, and H will get larger as well. It will quickly notice that the southern route is the better route to target.

I attached a quick excel sheet of an example similar to yours.

At cell F5, A* has no way of knowing if north or south is the better choice, they have the same G+H value of 9.

In fact, looking around, there are several values of 9 to choose from. A* will sort open nodes by G+H and pick the top one. In this case it could be any of the 9 values.

I assumed it picked F4, as that was the case that concerned you. Once it picks F4, it checks surrounding cells. It even re-calculates E4, but since the value of E4 coming from F4 is larger than what is already stored there, that value is neglected. F3 gets a value of 11.

So A* goes and sorts the open tiles again and it will again pick one of the 9s. When it gets to F6, it will see that G6 will be G=4, H=5, Total=9 In fact, everything along that path till the end will be 9, if A* picks any of the other open nodes that are 9, they will all have neighbors that are more than 9 and will fall lower in the sorted list.

Hope this helps.

I don't know if it is part of A*, but I personally like to sort A* as G+H primary and then G secondary, so it picks the longest path with the lowest estimated distance. That keeps it from ever picking B5 in my example. That might even be part of A* as far as I know, or maybe sorting is computationally more expensive than the node check so my 'enhancement' might actually slow it down a little.

Wow, I'm incredibly impressed!

You ever experience a mental block because you thought you understood something, knew it was wrong, but just couldn't think outside the box in understanding it? Then someone simply explains it in the most simplest of ways, and it just blows the top off that box.

Thank you so much!


Now I understand why, what I was doing was wrong. You're right, I was assuming that the G Cost was either a 1 or a 1.4 for diagonals. And because I wasn't using diagonals, adding a 1 to all the totals would be the same thing as not.

But it was all about the distance from the start point.


Also, it makes a lot of sense now. Checking the surrounding tiles, and then comparing them with the open list first to determine if there is an already existing total cost that is better.

Phew ... relief. Thanks so much, I'm jotting down your name for some recognition in what I'm making, it's the least I can do. :)