Efficient Path finding algorithm avoiding zigzag's [duplicate]

Question

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

Your current algorithm finds a shortest path, Pmin, but the improved algorithm should find a shortest path that takes minimum number of turns (Pmin, Tmin). General solution requires that you work with pair of numbers instead of a single number. If newly found Pnew is smaller than current Pmin OR if it is equal but Tnew is smaller than Tmin then take (Pnew, Tnew) as new minimal path.

If the board is small enough you could still use a single number as you currently use, but this number must be a compound number C = P * N + T, where N is sufficiently large and sufficiently small constant number. It must be larger than largest possible T for that board, which is almost the total number of tiles in the board. It must be also small enough so that there is no integer overflow when algorithm happens to handle the largest path in the board, which is also the total number of tiles in the board. So N must satisfy these two terms (B is total number of tiles in the board):

N > B
B * N < INT_MAX

If B is larger than SQRT(INT_MAX) then this system is unsolvable, and you should go with pair of values. N should be SQRT(INT_MAX), which for 2³² is 2¹⁶.

Main problem now is how to count all the turns, but that depends on the algorithm that you have. It shouldn't be too difficult to add that part.

Answer 2

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 3

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 4

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.