Efficient Path finding algorithm avoiding zigzag&#

Question

This question already has an answer here:

• Pathfinding - A* with least turns 2 answers

I am developing a software which connects objects with wires. This wiring has a rule that these wires cannot pass on other objects and no diagonal move is accepted.

All of the shortest path algorithms that i know (A*, dijkstra etc.) find this type of paths:

I do not want the unnecessary zigzags in the second screenshot. How do i achive this goal?

Note: Anyone who want to try the algorithms can use this application.

Another Note: This is the exact situation that i do not want. It finds the zigzag path instead of the one "go to the right until the you reach x position of the target, go to the up until you reach the y position of the target" which has the same cost with the zigzagged one.

Answer 1

Internally, the algorithm evaluates many possible paths, and chooses the shortest one.

If you adjust the algorithm slightly, so it calculates an additional penalty for each change in direction, then it will choose the shortest path with the fewest changes in direction.

Answer 2

I'm not familiar with search algorithms specifically, but this would be the best programmatic approach, pseudoed out below.

Objects we use:

vertex { //generic x,y coordinate
    int x;
    int y;
}
vertices[3]; //3 vertices: 0, 1, 2 (0 is start, 1 is mid, 2 is end);

And our algorithm, which depends on the most efficient path already found not having weirdness like ¯|_|¯

boolean hasObstacles = false;

int increment = 0;
//there's some other ways to set this up, but this should make the most sense to explaining which way we need to go
if(vertices[0].x < vertices[2].x)
    increment = 1;
else
    increment = -1;

for(int i = vertices[0].x; i != vertices[2].x; i = i + increment) {
    //check for collision at coordinate (i, vertices[0].y), set hasObstacles to true if collision
}

if(vertices[0].y < vertices[2].y)
    increment = 1;
else
    increment = -1;

for(int i = vertices[0].y; i != vertices[2].y; i = i + increment) {
    //check for collision at coordinate (vertices[2].x, i), set hasObstacles to true if collision
}

if(!hasObstacles) {
    //we can remove these 3 vertices and add this point to our list of vertices.
    vertex corner = new vertex(vertices[2].x, vertices[0].y) // relocation of point
}

The scan should progress one vertex at a time. If the 3 vertices are replaced with a single vertex, the next scan should use that new vertex as 0.

Answer 3

Intuitively, you can do this by giving your agent a "momentum."

Specifically, increase the size of your state space by a factor of four; you keep track of whether the agent last moved up, right, left, or down. Scale up the costs in your network by some large factor and assign a small penalty to moves that change direction.

Answer 4

Use a pair of values (doubles, integers, whatever) for your distance calculation.

The first is the distance, the second the number of turns.

Sort lexically, so the first one matters more than the second one.

This is cleaner than "use a small penalty for turns" both mathematically and programmatically.

Each node is duplicated. The node "having entered vertically" and "having entered horizontally", as they make a difference to the number of turns.

The heuristic is Manhattan distance, with a turn if you aren't exactly horizontal or vertically aligned with the target.

As a down side, this technique gets in the way of the Jump Point optimization, as there are far fewer symmetric paths to a location (as some paths have more turns than others).

Answer 5

Your problem is non-trivial because e.g. if you greedily go as far as you can up or to the the right, then you might encounter a tight maze of objects that requires a crazy zig-zag path to finish, whereas if you stopped before the tight maze you might be able to change directions fewer times by essentially going around the maze. And you could encounter this dilemma anywhere along your path, not just in the beginning. One way to solve this problem is to use Dijkstra and define a grid of locations you can travel to, and then define a move to be 2 steps long instead of 1 step long. Define the distance between two connected grid points to be very small if the move is pure horizontal or pure vertical in one oriented direction, and very large if the move changes direction in the middle. Then, assuming the path length from start to finish is even, the shortest path from the start to the finish in this double-move framework will be the path that minimizes the amount of zig-zag. If the path length from start to finish is odd, then use the grid points one space away horizontally and vertically to start from and then the path length from start to finish will be even (although you'll have to run the path finding for both possible modified starting positions).

Answer 6

Right now your algorithm answers question "which squares does the optimal path go through?" Your graph has a node for every square and an edge for every pair of adjacent squares.

Change it to "where does the optimal path crosses borders between squares?"

Your graph will change:

• Graph nodes: middle of every edge between adjacent squares + start + finish.
• Graph edges: in every square they connect every pair of square edges.

And now you can price differently connections of opposite square edges and connections of adjacent square edges. Giving bigger weight to the second will reduce number of zig-zags.