Search code examples
algorithmshortest-pathpath-finding

Efficient Path finding algorithm avoiding zigzag's

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. like in this screenshot

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. enter image description here

Solution

  • 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 232 is 216.

    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.