Efficient Path finding algorithm avoiding zigzag&#

问题:

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.

回答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.

回答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.

回答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).

回答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.

回答5:

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.

回答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.

回答7:

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).

回答8:

All you need is to modify heuristic of your A* algorithm a little bit. One the top of my head: if you do not like these turns you can just penalize each turn.

So your heuristic will depend on the number of turns and on the Manhattan distance to the target. One important thing is to not forget that it should not overestimate the distance to the goal. Read more how to select heuristic here.