Why does A* path finding sometimes go in straight lines and sometimes diagonals? (Java)

Question

I'm in the process of developing a simple 2d grid based sim game, and have fully functional path finding.

I used the answer found in my previous question as my basis for implementing A* path finding. (Pathfinding 2D Java game?).

To show you really what I'm asking, I need to show you this video screen capture that I made. I was just testing to see how the person would move to a location and back again, and this was the result...

http://www.screenjelly.com/watch/Bd7d7pObyFo

Different choice of path depending on the direction, an unexpected result. Any ideas?

Answer 1

If you're looking for a simple-ish solution, may I suggest a bit of randomization?

What I mean is this: in the cokeandcode code example, there is the nested-for-loops that generate the "successor states" (to use the AI term). I refer to the point where it loops over the 3x3 square around the "current" state, adding new locations on the pile to consider.

A relatively simple fix would (should :)) be isolate that code a bit, and have it, say, generated a linkedlist of nodes before the rest of the processing step. Then Containers.Shuffle (or is it Generics.Shuffle?) that linked list, and continue the processing there. Basically, have a routine say, "createNaiveNeighbors(node)" that returns a LinkedList = {(node.x-1,node.y), (node.x, node.y-1)... } (please pardon the pidgin Java, I'm trying (and always failing) to be brief.

Once you build the linked list, however, you should just be able to do a "for (Node n : myNewLinkedList)" instead of the

for (int x=-1;x<2;x++) {

    for (int y=-1;y<2;y++) {

And still use the exact same body code!

What this would do, ideally, is sort of "shake up" the order of nodes considered, and create paths closer to the diagonal, but without having to change the heuristic. The paths will still be the most efficient, but usually closer to the diagonal.

The downside is, of course, if you go from A to B multiple times, a different path may be taken. If that is unnacceptable, you may need to consider a more drastic modification.

Hope this helps! -Agor

Answer 2

The reason why is actually pretty simple: the path will always try to have the lowest heuristic possible because it searches in a greedy manner. Going closer to the goal is an optimal path.

If you allowed diagonal movement, this wouldn't happen.

Answer 3

The reason is the path you want the algorithm to go.
I don't know the heuristic your A* uses but in the first case it has to go to the end of the tunnel first and then plans the way from the end of the tunnel to the target.

In the second case the simplest moves to the targets are going down till it hits the wall and then it plans the way from the wall to the target.

Most A* I know work with a line of sight heuristic or a Manhattan Distance in the case of a block world. This heuristics give you the shortest way but in case of obstacles that force to go a way that is different from the line of sight the ways depend on your starting point.
The algorithm will go the line of sight as long as possible.

Answer 4

Both of the paths are of the same length, so the algorithm is doing its job just fine - it's finding a shortest path. However the A* algorithm doesn't specify WHICH shortest path it will take. Implementations normally take the "first" shortest path. Without seeing yours, it's impossible to know exactly why, but if you want the same results each time you're going to have to add priority rules of some sort (so that you're desired path comes up first in the search).