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: https://github.com/brean/python-pathfinding/blob/a99f3c2728c62aa5107c000b93c9c2295749c390/pathfinding/finder/finder.py#L107-L109

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.