a star algorithm not taking the visually ideal route

Question

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.