As suggested here, we could also limit the runtime by a maximum path length instead of just the number of iterations.

Hello,

I'd like to know if there is a way to get the closest cell to the destination in case there is no direct path to it.
if not, is there a way to implement it myself without spending too long working on it ?

Thanks.

Hi,
I'm trying to create a path finding method for the game brawlstars and I was wondering if it could be possible to find a path that does take a little longer route but avoid touch a neighbor cell that is non walkable. This would be helpful for my project since in brawlstars, there's some kind of "auto adjustment" when you go straight to a wall that makes the player move a little in order to avoid getting hit, but this feature is quite annoying for a bot and can make it loose the track of the player.

For example this :

instead of the current that is :

inspired by easystarjs

Hello, I thought I would use this python pathfinding algorithm to solve the advent of Code problem this year (https://adventofcode.com/2023/day/17)

unfortunately seems to have a bug:

The following code just sets up the Graph:

3215453535623
3255245654254
3446585845452
4546657867536
1438598798454
4457876987766
3637877979653
4654967986887
4564679986453
1224686865563
2546548887735
4322674655533'''

data = B.split("\n")
h = len(data)
w = len(data[0])
data = [[int(dd) for dd in d] for d in data]
data = list(map(list,zip(*data)))
from pathfinding.core.graph import Graph
from pathfinding.finder.dijkstra import DijkstraFinder

edges = []
for x in range(w-1):
    for y in range(h):
        for i in range(2):
            edges.append([f'x{x}_y{y}_r{i}',f'x{x+1}_y{y}_r{i+1}',data[x+1][y]])
        for i in range(3):
            edges.append([f'x{x}_y{y}_u{i}',f'x{x+1}_y{y}_r0',data[x+1][y]])
            edges.append([f'x{x}_y{y}_d{i}',f'x{x+1}_y{y}_r0',data[x+1][y]])
for x in range(w):
    for y in range(h-1):
        for i in range(2):
            edges.append([f'x{x}_y{y}_d{i}',f'x{x}_y{y+1}_d{i+1}',data[x][y+1]])
        for i in range(3):
            edges.append([f'x{x}_y{y}_r{i}',f'x{x}_y{y+1}_d0',data[x][y+1]])
            edges.append([f'x{x}_y{y}_l{i}',f'x{x}_y{y+1}_d0',data[x][y+1]])
for x in range(1,w):
    for y in range(h):
        for i in range(2):
            edges.append([f'x{x}_y{y}_l{i}',f'x{x-1}_y{y}_l{i+1}',data[x-1][y]])
        for i in range(3):
            edges.append([f'x{x}_y{y}_u{i}',f'x{x-1}_y{y}_l0',data[x-1][y]])
            edges.append([f'x{x}_y{y}_d{i}',f'x{x-1}_y{y}_l0',data[x-1][y]])
for x in range(w):
    for y in range(1,h):
        for i in range(2):
            edges.append([f'x{x}_y{y}_u{i}',f'x{x}_y{y-1}_u{i+1}',data[x][y-1]])
        for i in range(3):
            edges.append([f'x{x}_y{y}_r{i}',f'x{x}_y{y-1}_u0',data[x][y-1]])
            edges.append([f'x{x}_y{y}_l{i}',f'x{x}_y{y-1}_u0',data[x][y-1]])

edges.append(["start",f'x1_y0_r1',data[1][0]])
edges.append(["start",f'x0_y1_d1',data[0][1]])
edges.append([f'x{w-1}_y{h-1}_r0',"end",0])
edges.append([f'x{w-1}_y{h-1}_r1',"end",0])
edges.append([f'x{w-1}_y{h-1}_r2',"end",0])
edges.append([f'x{w-1}_y{h-1}_d0',"end",0])
edges.append([f'x{w-1}_y{h-1}_d1',"end",0])
edges.append([f'x{w-1}_y{h-1}_d2',"end",0])
graph = Graph(edges=edges, bi_directional=False)

where the aim is to find the shortest least-cost path from node "start" to node "end"
the pathfinding algorithm Dijkstra's can be implemented by:

finder = DijkstraFinder()
path, _ = finder.find_path(graph.node("start"), graph.node("end"), graph)
path_cost = sum([graph.calc_cost(path[i],path[i+1]) for i in range(len(path)-1)])

which gives incorrect result (of 138).
whereas a handcoded algorithm on the same graph gives correct result: (of 102)

for g in graph.nodes.values():
    g.f = float("inf")
open_list = [graph.node("start")]
open_list[0].f = 0
while len(open_list)!=0:
    node = open_list[0]
    if node==graph.node("end"):
        break
    neighbors = graph.neighbors(node)
    for n in neighbors:
        if not n.closed:
            m = node.f + graph.calc_cost(node,n)
            if m < n.f:
                n.parent = node
                n.f = m
            if n not in open_list:
                open_list.append(n)
    node.closed = True
    open_list = open_list[1:]
    open_list.sort()
path = []
while node is not None:
    path.append(node)
    node = node.parent
path = path[::-1]
path_cost = sum([graph.calc_cost(path[i],path[i+1]) for i in range(len(path)-1)])

I am not sure what is going on.
perhaps I have missed some warning about proper usage?

Hello, I am trying to use pathfinding but the output I get for the path from the find_path() method is not what I would expect. I would expect a simple list of tuples but instead it is fulled with <GridNode(0:0 0x104760110)> and I am not sure what is wrong with my setup.

My system is: MacOS Sonoma 14.2.1 (M1 Pro chip) and I am running Python 3.12.1 and pathfinding 1.0.9.

The code that I am using as a test is below:

from pathfinding.core.diagonal_movement import DiagonalMovement
from pathfinding.core.grid import Grid
from pathfinding.finder.a_star import AStarFinder
import random

blockpositions = []

def makegrid(x2, y2):
	grid = []
	for x in range(x2):
		grid.append([])
		for y in range(y2):
			if random.randint(1,5)==1:
				blockpositions.append((x, y))
				grid[x].append(0)
			else:
				grid[x].append(1)
	return grid

grid = makegrid(50, 50)
startpos = (0, 0)
endpos = (49, 49)

finder = AStarFinder(diagonal_movement=DiagonalMovement.always)
grid2 = Grid(matrix = grid)

start = grid2.node(startpos[0], startpos[1])
end = grid2.node(endpos[0], endpos[1])

path, runs = finder.find_path(start, end, grid2)
for x in path:
	if x in blockpositions:
		print("block in path!")
print(path)

The output is:
[<GridNode(0:0 0x104760110)>, <GridNode(1:1 0x104b46c90)>, <GridNode(2:1 0x104b46cc0)>, <GridNode(3:2 0x104b47650)>, <GridNode(3:3 0x104b47fb0)>, <GridNode(4:4 0x104b74980)>, <GridNode(5:5 0x104b75310)>, <GridNode(6:6 0x104b75ca0)>, <GridNode(7:7 0x104b76630)>, <GridNode(8:8 0x104b76fc0)>, <GridNode(9:9 0x104b77950)>, <GridNode(10:10 0x104b84320)>, <GridNode(11:10 0x104b84350)>, <GridNode(12:11 0x104b84ce0)>, <GridNode(13:12 0x104b85670)>, <GridNode(14:13 0x104b86000)>, <GridNode(15:14 0x104b86990)>, <GridNode(16:15 0x104b87320)>, <GridNode(17:16 0x104b87cb0)>, <GridNode(18:17 0x104b98680)>, <GridNode(19:18 0x104b99010)>, <GridNode(20:19 0x104b999a0)>, <GridNode(21:20 0x104b9a330)>, <GridNode(22:21 0x104b9acc0)>, <GridNode(23:22 0x104b9b650)>, <GridNode(24:23 0x104b9bfe0)>, <GridNode(25:24 0x104ba89b0)>, <GridNode(26:25 0x104ba9340)>, <GridNode(26:26 0x104ba9ca0)>, <GridNode(27:27 0x104baa630)>, <GridNode(28:28 0x104baafc0)>, <GridNode(29:29 0x104bab950)>, <GridNode(30:30 0x104bb8320)>, <GridNode(30:31 0x104bb8c80)>, <GridNode(31:32 0x104bb9610)>, <GridNode(32:33 0x104bb9fa0)>, <GridNode(33:34 0x104bba930)>, <GridNode(34:34 0x104bba960)>, <GridNode(35:35 0x104bbb2f0)>, <GridNode(36:36 0x104bbbc80)>, <GridNode(37:37 0x104bc8650)>, <GridNode(38:37 0x104bc8680)>, <GridNode(39:38 0x104bc9010)>, <GridNode(40:39 0x104bc99a0)>, <GridNode(41:40 0x104bca330)>, <GridNode(42:41 0x104bcacc0)>, <GridNode(43:41 0x104bcacf0)>, <GridNode(44:42 0x104bcb680)>, <GridNode(45:43 0x104bd8050)>, <GridNode(46:44 0x104bd89e0)>, <GridNode(47:45 0x104bd9370)>, <GridNode(48:46 0x104bd9d00)>, <GridNode(49:47 0x104bda690)>, <GridNode(49:48 0x104bdaff0)>, <GridNode(49:49 0x104bdb950)>]

Please let me figure out what is going wrong.

see qiao/PathFinding.js#28

Add Documentation and examples for bresenham, raytrace and smoothen_path

I was working on a project and my pytests errored out using Python 3.9.17. Is it possible to do the type hint on the function level to keep the 3.9 version working still?

Hey, I was looking to contribute and going through CONTRIBUTING.md, and noticed that under the Pull Requests section it says Gitlab instead of Github.

Add some big maps to test the algorithm & performance (based on https://harablog.wordpress.com/2011/09/07/jump-point-search/ )

• Baldurs gate (like)
• Adaptive Depth
• Rooms
• Generate mazes, that can be solved (with a python implementation of this: https://github.com/bestguy/generate-maze )

see qiao/PathFinding.js#109 (comment)

Hi, I would like to know if there is an option to split the path into either X-direction move, or Y-direction move, not X and Y at the same time (diagonal). Hope that makes sense for you. Thank you!

travis-ci is acting strangely and throws some errors, we might want to move to github actions (or another CI)

Hi, I need to set some fields on the 2D matrix that have a 'walk cost' of a quarter of a movement point (0.2)
But when doing so, the pathfinding algorithm starts to do some weird things.
If I instead use only integers the pathfinding works just great.

Is there any chance of using floats?

I'm using the A* algorithm.

Hello,
I just used the pathfinding with matrix with size of (227,304).
when i tried to get the node[222][268] i got this error:
File "C:\Users\...\Python\Python37\site-packages\pathfinding\core\grid.py", line 60, in node return self.nodes[y][x] IndexError: list index out of range

I changed the self.nodes[y][x] to - self.nodes[x][y] and it works like magic.

is there any reason you decided to make it self.nodes[y][x] ?

Not sure if this is useful for you, but I saw in #3 that you wanted an MSP algorithm in place. I needed one for my own purposes, and thought I'd share the code back with you in case you want to integrate it somehow. Cheers!

from collections import deque, namedtuple
from pathfinding.core import heuristic
from pathfinding.finder.finder import Finder
import heapq
import time


class MinimumSpanningTree(Finder):
    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)
        self.heuristic = heuristic.null

    def tree(self, grid, start):
        return list(self.itertree(grid, start))

    def itertree(self, grid, start):

        # Finder.process_node requires an end node, which we don't have. The following
        # value tricks the call to Finder.apply_heuristic. Though maybe we want to generate
        # a limited spanning tree that trends in a certain direction? In which case we'd
        # want a more nuanced solution.
        end = namedtuple("FakeNode", ["x", "y"])(-1, -1)

        self.start_time = time.time()  # execution time limitation
        self.runs = 0  # count number of iterations
        start.opened = True

        open_list = [start]

        while len(open_list) > 0:
            self.runs += 1
            self.keep_running()

            node = heapq.nsmallest(1, open_list)[0]
            open_list.remove(node)
            node.closed = True
            yield node

            neighbors = self.find_neighbors(grid, node)
            for neighbor in neighbors:
                if not neighbor.closed:
                    self.process_node(neighbor, node, end, open_list, open_value=True)

    def find_path(self, start, end_test, grid):
        for node in self.itertree(grid, start):
            if end_test(node):
                path = deque()
                step = node
                while step.parent:
                    path.appendleft(step)
                    step = step.parent
                path.appendleft(step)
                return path, self.runs
        else:
            return [], self.runs

Hi,
It is my first time to use python-pathfinding, it's nice but sth make me confused...
To be brief, I am writing a bot to play a game, this is what I try to do tonight:

   def ParseMap(map:List[Map]) -> (List[List[Map]], List[List[List[tuple]]], tuple):
    parsedMap = [[Map() for i in range(MapEdgeLength)] for j in range(MapEdgeLength)]
    paths = [[[] for i in range(MapEdgeLength)] for j in range(MapEdgeLength)]
    accessableNow = [[1 for i in range(MapEdgeLength)] for j in range(MapEdgeLength)]
    playerPosition = None
    for grid in map:
        parsedMap[grid.x][grid.y] = grid
        for obj in grid.objs:
            if obj.type == ObjType.Player and obj.property.player_id != gContext["playerID"] and playerPosition is None:
                playerPosition = (grid.x, grid.y)
            if obj.type == ObjType.Block or obj.type == ObjType.Bomb:
                accessableNow[grid.x][grid.y] = 0 # (a)
    # pfGrid: an abbreviation of pathfinding grid
    pfGrid = Grid(matrix=accessableNow)
    for grid in map:
        pfGrid.cleanup()
        finder = AStarFinder(diagonal_movement=DiagonalMovement.never)
        newPath, _ = finder.find_path(pfGrid.node(playerPosition[0], playerPosition[1]),
                                        pfGrid.node(grid.x, grid.y, pfGrid) #(b)
        myNewPath = [(newPath[i].x, newPath[i].y) for i in range(len(newPath))]
        paths[grid.x][grid.y] = myNewPath
    return parsedMap, paths, playerPosition

Some names of variables in the code above are provided by the organizer of the contest I am taking part in.
My code above failed to get correct answer until I rewite (a) as:

 accessableNow[grid.y][grid.x] = 0

or rewrite (b) as:

 newPath, _ = finder.find_path(pfGrid.node(playerPosition[1], playerPosition[0]),
                                        pfGrid.node(grid.y, grid.x, pfGrid) #(b)

Later, I refer to the docs but find nothing about parameter order.
As I look into the grid.py i found:

       def node(self, x, y) -> GridNode:
        """
            get node at position
            :param x: x pos
            :param y: y pos
            :return:
        """
        return self.nodes[y][x]

Below is what I suggest: Rearrangeing parameters x and y as the order they appear in the List indexes:

       def node(self, y, x) -> GridNode:
           return self.nodes[y][x]

or rename them to the form xi where i is the order they appear in the indexes:

       def node(self, x1, x2) -> GridNode:
           return self.nodes[x1][x2]

so that People who use the pathfinding can access a node not according to a specific name convention, but the order they pass parameters to these functions before.

In some instances, it may be helpful to (topologically) fuse opposite borders of the grid. Examples include maps where crossing the eastern grid border should result in arriving at the western grid border.
Adding this functionality should entail small modifications to /core/grid.py. Happy to take on this issue if needed.

I'm a user of the "pathfinding" Python module. It has greatly benefited my projects.
I've noticed the grid-to-string conversion function can be slow in some cases, especially with larger matrices like my 750x650 grid. On my laptop, it took around 29.89 seconds. I'm keen on optimizing this process.
(The algorithm i'm using is bi-directional a*, which takes 8.54 seconds)

Good afternoon,

I just realised that if a link is defined from the end of a path to be found, the DijkstraFinder seems to give absurd results:

from pathfinding.core.diagonal_movement import DiagonalMovement
from pathfinding.core.graph import Graph
from pathfinding.core.node import Node
from pathfinding.finder.a_star import AStarFinder

edges = [
    [0, 1, 1],
    [1, 0, 1],
    [1, 2, 1],
    [2, 1, 1],
]
graph = Graph(edges=edges, bi_directional=False)
finder = DijkstraFinder()
path, runs = finder.find_path(graph.node(0), graph.node(2), graph)
print(len(path), [n.node_id for n in path])

output: 1 [2]

Comment the last edge out, and all is right again.

currently euclidean and chebyshev heuristics are not tested (see
https://coveralls.io/builds/14862532/source?filename=pathfinding%2Fcore%2Fheuristic.py )

extend the examples to also use Puzzle Tunnel Discovery
(see https://github.com/xinyazhang/PuzzleTunnelDiscovery / https://xinyazhang.gitlab.io/puzzletunneldiscovery/ )

Create some examples that show and benchmark pathfinding in 3D

Implement an additional grid storing walls, similar to the javascript solution (and maybe an editor to easily create those walls):
qiao/PathFinding.js#185

Hi, using Python 3.7, I can't use the pathfinding module.

I've tried in an virtualenv and by installing it directly in the system packages.

Error is:

python.exe pathfinding.py
Traceback (most recent call last):
  File "pathfinding.py", line 1, in <module>
    from pathfinding.core.diagonal_movement import DiagonalMovement
  File "pathfinding.py", line 1, in <module>
    from pathfinding.core.diagonal_movement import DiagonalMovement
ModuleNotFoundError: No module named 'pathfinding.core'; 'pathfinding' is not a package

Process finished with exit code 1

Sample code used:

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

matrix = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
]
grid = Grid(matrix=matrix)

start = grid.node(0, 0)
end = grid.node(2, 2)

finder = AStarFinder(diagonal_movement=DiagonalMovement.always)
path, runs = finder.find_path(start, end, grid)

print('operations:', runs, 'path length:', len(path))
print(grid.grid_str(path=path, start=start, end=end))

Any idea how to make it work?

travis has not been run since 2021, coveralls shows a 404 and tox is barely used anymore.

implement the other algorithms from PathFinding.js

Grid-based

from Pathfinding.js

• Bi-directional A*
• Iterative Deeping A Star (IDA*)
• Jump Point Search
• Orthogonal Jump Point Search
• Breadth-First-Search
• Best-First
• Bi-directional Breadth-First-Search
• Bi-directional Best-First
• Bi-directional Dijkstra

other algorighms

• D*
• D* Lite (maybe based on this or this)
• Any-angle path planning (maybe needs another visualization?)
• Theta* ( see qiao/PathFinding.js#89 )
• Floyd-Warshall
• Minimum spanning trees
• rapidly exploring random tree (RRT).

also some more from the OpenGenus Cosmos like for example

Non-Grid-based (Navigation Meshes)

• Recast/Detrour
• PatrolJS

Implement a live demo/playground using Skulpt

also take a look at qiao/PathFinding.js#97

We should address the performance of different path finding algorithms, provide benchmarks on different PC systems as well as additional information on algorithm optimization.
Especially with the new teleport-feature it might be important for users to understand that it might be compute intense.

Provide simple jupyter notebook example

Create an example with multiple Agents

• see https://youtu.be/S-VAL7Epn3o?t=588

I created a matrix array in a CSV file as I needed to make the array for ~500 different points that may need to change on a bi-monthly basis, so csv file feels like the best way to maintain this as opposed to manually creating and updating it within my_pathfinding_file.py.

I used numpy and pandas to read the file and create the array, no problem; however when it spits out the array it looks like this:
matrix = [
[1 0 0 0 1]
]

instead of
matrix = [
[1, 0, 0, 0, 1]
]

Which returns an error when you try to run it through the grid.py portion of your script. As best as I can understand it the grid.py script requires the commas to be associated to a list type of format, not an array of numbers; or what maybe considered a tuple.

Would it be possible to add in this sort of functionality? I have looked into the articles below to best resolve the issue but my understanding of python is too limited to understand the greater problem nor how to implement it into the code you have already created.
Grid from counting points
CSV appending rows option

We tried running below code

"""Test path finding performance."""
import numpy
from pathfinding.core.diagonal_movement import DiagonalMovement
from pathfinding.core.grid import Grid
from pathfinding.finder.a_star import AStarFinder
import pytest
import logging


class TestPathFinding:
    """Path finding test."""

    def _add_block(self, g: numpy.ndarray, x: int, y: int, padding: int):
        for i in range(x - padding, x + padding):
            for j in range(y - padding, y + padding):
                g[j][i] = 0

    # @pytest.mark.skip(reason="Please uncomment to enable")
    def test_performance(self):
        """Test performance."""
        # Get a 500 x 500 grid
        grid = numpy.ones((500, 500), numpy.int32)

        # Add a block at the center
        self._add_block(grid, 250, 250, 50)

        finder_grid = Grid(matrix=grid)
        start = finder_grid.node(0, 0)
        end = finder_grid.node(400, 400)

        finder = AStarFinder(diagonal_movement=DiagonalMovement.never)
        path, runs = finder.find_path(start, end, finder_grid)

        assert len(path) == 801
        logging.info("found len(path)=%s", len(path))

and did some profiling and found below bottleneck

i.e. to find a single path for a relative small grid it takes 34 seconds with debugger and 24 seconds without.

If we added below fixes:

We get much faster performance as shown below with 9 seconds with debugger and 7 seconds without.

I am using AStarFinder. Don't know why it can find only one path when used in a loop. I have a list of starting and ending points, when I try to get the shortest path with AStarFinder it finds the path only for the first item in the list.

see here and here

see https://github.com/jbrown123/PathFinding.js/

Like qiao/PathFinding.js#196

Implement and describe ways to go from one grid to another, e.g. for different level of a building:

• elevators or ladders are going from one node on one grid to another node in another grid on the same position,
• steps are similar to ladders but can be connected to other nodes on the second grid
• portals are the same as steps or elevators but without a cost.

Also add a markdown-page with a description describing the problem and how to use it.

For the implementation you need to extend the Node to have a list of connecting nodes in other grids. Then you need to inherit the Grid class and extend the check_neighbors function to look for those connections after all other neighbors are checked. Because for the algorithm the path isn't stored as a grid but as a graph where all neighboring cells are seen as edges so you just need another edge in the other grid.

I'm wondering if it's possible to output the solution coordinates in order.

Current

operations: 61 path length: 43
+-----------+
|sxx  #xxx  |
|##x###x#x##|
|xxx#xxx#xxx|
|x###x#####x|
|x#xxx#xxxxx|
|x#x###x### |
|xxx#xxx# # |
| ###x### # |
| # #x#   # |
| # #x# ### |
| #  e#     |
+-----------+

Purposed

(0,0),(0,1)(0,2),(1,2) . . .