How to favor path with less turns? (A*)

[maximweb]

Thanks for this library. Being new to pathfinding, I used the A* basic example at it ran right away.

Is your feature request related to a problem? Please describe.
For my use-case, I set DiagonalMovement.never. I now was wondering, if it is possible to favor a path with less turns?

Describe the solution you'd like

• In the following simplified grid, I want to get from s to e.
• For the purpose of discussion, I drew to possible paths A (sxxAA..Axxe) and B (sxxBB..Bxxe).
• Without diagonal movement, Path B has the same length as path A. Is it possible to tune settings(neighbor weights?) so that path A (having less turns) is favored over path B?

+----------+
|        ##|
| AAAAAxxe#|
| A    B ##|
| xBBBBB ##|
| x        |
|#s##      |
|####      |
+----------+

Describe alternatives you've considered

• I was (naively) hoping that deliberately setting the start and endpoint in a recess of my blocked areas might help to favor path A, but I get B instead.

[brean]

Hi @maximweb,
If I understand correctly, you want to favor the y-direction in the heuristic of A* .
simple:

from pathfinding.finder.a_star import AStarFinder
from pathfinding.core.diagonal_movement import DiagonalMovement

def my_heuristic(dx, dy) -> float:
    return dx + dy * 1000

finder = AStarFinder(
    heuristic=my_heuristic,
    diagonal_movement=DiagonalMovement.never
)
path, runs = finder.find_path(start, end, grid)

(tested with https://brean.github.io/svelte-pyscript-pathfinding)

[brean]

Note that this is not a very nice solution because it might increase your search space.
A* is only suited to give you ONE best solution, not all possible paths and because the distance to the goal is the same A and B are both the correct best solutions.
However I have some ideas for alternatives:

1. using a weighted graph with special weights that are higher from left-to-right (but that's only working for moving right)
2. use Dijkstra instead of A* and rewrite the backtracking function to look at all possible paths and try to find the one with least amount of curvature, but this might be a compute intense and complex solution
3. use some raycasting-like algorithm on the path after A* found a solution to check if direct paths are also possible (maybe you need to re-run A* on parts of your path as well to make sure its still valid)
4. Take a look at Jump Point Search (thats actually on my feature-wishlist for python-pathfinding)
5. Take a look at Theta* (or a variation of it - its actually on my feature-wishlist as well)

https://news.movel.ai/theta-star
https://zerowidth.com/2013/a-visual-explanation-of-jump-point-search/

[maximweb]

Hi @brean ,

thank you for your reply. My goal was to reduce the amount of turns in general, not necessarily favoring one direction.

I looked at your example, but it kept getting more turns than necessary. I also not 100% sure I understand it. As far as I understand, the heuristic is a representation of the distance of the current node to the destination, and A* should favor nodes with a smaller heuristic. Hence, your dy * 1000 would punish any deviation from $y_{target}$ and resulting in vertical movement first. Yet your playground gave me paths, which always seem to prefer the x direction (horizontal).

In the meantime, I stumbled across a project, which uses a modification of your library, to do just what I want to achieve:

After the default cost calculation:

python-pathfinding/pathfinding/finder/finder.py

Lines 107 to 109 in a99f3c2

	# calculate cost from current node (parent) to the next node (neighbor)
	ng = parent.g + graph.calc_cost(parent, node, self.weighted)

They calculate the previous and current direction, and if these diverge, they add a penalty (Source).

        lastDirection = (
            None
            if parent.parent == None
            else (parent.x - parent.parent.x, parent.y - parent.parent.y)
        )
        turned = (
            0
            if lastDirection == None
            else (
                lastDirection[0] != node.x - parent.x
                or lastDirection[1] != node.y - parent.y
            )
        )

        ng += self.turnPenalty * turned

(I think in the original the sign was wrong, as they compared parent - grandparent == node - parent instead of parent - grandparent == parent - node, so I changed that.)

My first tests indicate, that this does exactly what I intended. I'll post an update, as soon as I find the time to test more.

[brean]

Hey,

yes, you understand correctly by punishing one direction it would favor straight paths in the other direction, not necessary change the amount of turns.
The turn-penalty is a very interesting idea, I think we can include that in python-pathfinding as well, of course only as optional parameter to not change the original A*s functionality, or inherit from AStarFinder and create it as own finder...

Looking forward to your tests.

[w9PcJLyb]

A* is only suited to give you ONE best solution, not all possible paths

The good news is that we have all necessary information in grid.nodes to extract all possible optimal paths. Therefore, we can traverse all the paths and find the one that has the minimum number of turns.

Here is my approach:

from pathfinding.core.grid import Grid, GridNode, DiagonalMovement
from pathfinding.finder.a_star import AStarFinder


class Solution:
    def __init__(self):
        self.num_turns = 0
        self.path = []
        self.last_action = None
    
    def add(self, p: GridNode):
        if len(self.path) == 0:
            self.path.append(p)
            return

        if len(self.path) == 1: 
            p0 = self.path[0]
            self.last_action = (p.x - p0.x, p.y - p0.y) 
            self.path.append(p)
            return

        p_last = self.path[-1]
        new_action = (p.x - p_last.x, p.y - p_last.y)

        if new_action != self.last_action:
            self.num_turns += 1
            self.last_action = new_action

        self.path.append(p)
    
    def pop(self):
        if len(self.path) == 0:
            raise ValueError()

        if len(self.path) <= 2:
            self.last_action = None
            self.path = self.path[:-1]
            return

        p2 = self.path[-2]
        p3 = self.path[-3]
        
        new_last_action = (p2.x - p3.x, p2.y - p3.y)
        if new_last_action != self.last_action:
            self.num_turns -= 1
            self.last_action = new_last_action

        self.path = self.path[:-1]


def traverse(grid: Grid, solution: Solution, best_solution: Solution):
    last_node = solution.path[-1]
    for n in grid.neighbors(last_node):
        if not n.closed:
            continue

        if last_node.g != n.g + grid.calc_cost(last_node, n, weighted=True):
            continue

        solution.add(n)
        if solution.num_turns < best_solution.num_turns:
            if n.g == 0:
                best_solution.path = solution.path
                best_solution.num_turns = solution.num_turns
            else:
                traverse(grid, solution, best_solution)
        solution.pop()


def find_path_with_less_turns(start, goal, grid):
    grid.cleanup()
    finder = AStarFinder(diagonal_movement=DiagonalMovement.never)
    path, _ = finder.find_path(start, goal, grid)
    if not path:
        return []

    best_solution = Solution()
    best_solution.num_turns = float("inf")

    solution = Solution()
    solution.add(goal)
    traverse(grid, solution, best_solution)

    return best_solution.path[::-1]

Edit: it is better to use Dijkstra or BFS instead of A*, because A* does not guarantee finding every optimal path.

[brean]

TODO: we should investigate to include in a new pathfinding-release

[maximweb]

I forgot to give an update. I am using the solution I linked earlier, using A* including looking at grandparents to get the direction. For my applications (including walls and weighted nodes) this works well. I have to mention tough, that I did neither test the performance nor other algorithms as @w9PcJLyb suggested, as my use-case is fairly small.

Not sure if I can help with any other implementation, but I would love to see such a feature builtin and am willing to help testing.