a star algorithm not taking the visually ideal route [duplicate]

Question

This question already has answers here:

Pathfinding - A* with least turns (3 answers)

Closed 9 years ago.

I have implemented the A star algorithm to find a route between two nodes on a simple grid. I'm currently testing on a grid with no obstacles, and it seems to be finding a shortest path, but it isn't an 'ideal' shortest path, by that I mean one that doesn't keep randomly changing directions. Ideally I'd like it to keep going in one direction, meaning it only changes direction once.

How can I enforce this? I'm looking at the part of the code where I consider which node to expand in the open list, and I might be able to hack something in by keeping a note of the previous direction and choosing the same direction if the next tile has the same f value, but it isn't very elegant.

Answer 1

Given your graph G=(V,E) where each v in V stands for a cell, and each edge (u,v) is possible move, you can create a new (weighted) graph G'=(V',E') as follows:

V' = V_u U V_d U V_l U V_r - each group stands for the type of move you have done last, and V_u = { v_u | for each v in V }, similarly for V_d,V_l,V_r

Now, for each edge (u,v) in E:

• If (u,v) stands for 'left' move, add (u_l,v_l,1) and (u_r,v_l,1+eps),(u_u,v_l,1+eps),(u_d,v_l,1+eps). Intuitively - you give a small punishment (eps) for 'changing direction', and no penalty if keeping the same direction.
• If (u,v) stands for 'up' move, add (u_u,v_u,1) and (u_r,v_u,1+eps),(u_l,v_u,1+eps),(u_d,v_u,1+eps). (similarly)
• Repeat for 'right' and 'down' moves.

Make sure eps is small enough to only influence among paths of the same length. 1/(|V|+1) should do it.
Also make sure you have 4 targets now (t_u,t_d,t_l,t_r, where t is the original target).

This gives you a graph with 4*|V| vertices, that now favors keeping the same direction over changing it. You can stick with the heuristic you previously had - if it was admissible, it is going to stay this way.

Answer 2

You shouldn't have to enforce anything. Just looking at your path I can tell that there is a problem with you algorithm. Though without your code I cannot tell you where it is. The shortest path on an open grid is always going to be a straight line because of (a^2+b^2=c^2). A* will always return that. If you post your code I can give you some guidance on what you need to do. but right now your cost calculations are off for some reason, otherwise you would head straight from start to end. also bear in mind that A* find one of the shortest paths when /if there is a tie. In your case there won't be, but when you add obstacles visually evaluating the graph is not always a good indicator.

long answer short. check your cost functions and the way that you are identifying the path node's previous node. if you aren't utilizing the previous node for your path when you find that taking it to the current node is advantageous this will happen. it will also happen if your cost functions are wrong (typically the heuristic is messed up somehow).