jrialland / python-astar Goto Github PK

View Code? Open in Web Editor NEW

191.0 6.0 59.0 1.21 MB

Simple implementation of the a-star algorithm in Python 🌟

License: BSD 3-Clause "New" or "Revised" License

Python 96.12% Shell 3.88%

pathfinding graph-theory-algorithms shortest-path-algorithm

python-astar's Introduction

python-astar

This is a simple implementation of the a-star path finding algorithm in python

Documentation

The astar module defines the AStar class, which has to be inherited from and completed with the implementation of several methods.

The functions take/return _node objects. The astar library only requires the following property from these objects:

They must be hashable (i.e. implement __hash__).

For the default implementation of is_goal_reached, the objects must be comparable for same-ness (i.e. implement __eq__).

A simple way to achieve this, is to use simple objects based on strings, floats, integers, tuples. [dataclass](https://docs.python.org/3/library/dataclasses.html#dataclasses.dataclass) objects declared with @dataclass(frozen=True) directly implement __hash__ if possible.

neighbors

@abstractmethod
def neighbors(self, node)

For a given node, returns (or yields) the list of its neighbors.

This is the method that one would provide in order to give to the algorithm the description of the graph to use during for computation.

This method must be implemented in a subclass.

distance_between

@abstractmethod
def distance_between(self, n1, n2)

Gives the real distance/cost between two adjacent nodes n1 and n2 (i.e n2 belongs to the list of n1's neighbors). n2 is guaranteed to belong to the list returned by a call to neighbors(n1).

This method must be implemented in a subclass.

heuristic_cost_estimate

@abstractmethod
def heuristic_cost_estimate(self, current, goal)

Computes the estimated (rough) distance/cost between a node and the goal. The first argument is the start node, or any node that have been returned by a call to the neighbors() method.

This method is used to give to the algorithm an hint about the node he may try next during search.

This method must be implemented in a subclass.

is_goal_reached

def is_goal_reached(self, current, goal)

This method shall return a truthy value when the goal is 'reached'. By default it checks that current == goal.

"Functional" API.

If you dislike to have to inherit from the AStar class and create an instance in order to run the algorithm, the module also provides a "find_path" function, which takes functions as parameters and provides reasonnable defaults for some of them.

See <https://github.com/jrialland/python-astar/blob/master/tests/basic/test_basic.py>

def find_path(
    start,
    goal,
    neighbors_fnct,
    reversePath=False,
    heuristic_cost_estimate_fnct = lambda a, b: Infinite,
    distance_between_fnct = lambda a, b: 1.0,
    is_goal_reached_fnct = lambda a, b: a == b
    )

Examples

Maze solver

This script generates an ascii maze, and finds the path between the upper left corner and the bottom right

PYTHONPATH=. python tests/maze/test_maze.py

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|####    |     |              |        |              |     |
+--+# +  +  +  +  +--+--+--+  +  +--+  +--+--+--+  +--+  +  +
| ### |  |  |  |  |        |  |     |     |        |     |  |
+ #+--+--+  +  +  +--+  +--+  +  +--+--+  +  +--+--+  +--+  +
| #|        |  |  |     |     |  |        |  |     |  |     |
+ #+  +--+--+  +  +  +--+  +--+  +  +--+--+  +  +  +  +  +--+
| #|        |  |  |     |     |  |     |        |     |     |
+ #+--+--+  +  +  +--+  +--+  +  +--+--+  +--+--+--+--+--+  +
| #      |  |  |  |        |     | ### |  |     |        |  |
+ #+--+--+  +  +  +  +--+--+--+--+ #+# +  +--+  +  +--+  +  +
| #         |     |       ####| ####|# |  |     |     |  |  |
+ #+--+--+--+--+--+--+--+ #+ #+ #+--+# +  +  +  +--+  +  +  +
| #|    ####|       #######| ####| ### |     |     |  |     |
+ #+--+ #+ #+--+--+ #+--+--+--+--+ #+--+  +--+--+--+  +--+--+
| ####| #| ##########|           | ### |  | ###### |        |
+--+ #+ #+--+--+--+--+  +--+--+  +--+# +--+ #+--+# +--+--+  +
|  | ####|        |     |           |########|  |##| ### |  |
+  +--+--+  +--+  +  +--+  +--+--+  +--+--+--+  + #+ #+# +  +
|        |     |  |  |     |                    | ####|#### |
+  +--+--+--+  +  +  +  +--+  +--+--+--+--+--+  +--+--+--+# +
|  |           |     |     |     | ####|     |     | ###### |
+  +  +--+--+--+--+--+  +  +--+--+##+ #+--+  +--+  + #+--+--+
|     |  |           |  |  | ###### | ####|        | ### |  |
+  +--+  +  +--+--+  +--+  + #+--+--+--+ #+--+--+--+--+# +  +
|        |  |     |        | ###### |  | ############ |# |  |
+--+--+--+  +  +  +--+--+  +--+--+# +  +--+--+--+--+# +# +  +
|           |  |  |        | ###### | ##########|  |#### |  |
+  +--+  +--+--+  +  +--+--+ #+--+--+ #+--+--+ #+  +--+--+  +
|  |     |     |        | ####|     | #######| ############ |
+  +--+--+  +  +--+  +--+ #+--+--+  +  +--+ #+--+--+--+--+# +
|        |  |     |  | ####| ####|        | #| ### |     |##|
+--+--+  +  +--+  +  + #+--+ #+ #+--+--+  + #+ #+# +  +  + #+
|        |  |     |  | #######| ####|     | #| #|# |  |  | #|
+  +--+  +  +  +--+--+--+--+--+--+ #+--+--+ #+ #+# +--+  + #+
|  |     |  |  |                 | #| ####| ####|# |     | #|
+  +  +--+  +  +  +--+--+--+--+  + #+ #+ #+--+--+# +  +  + #+
|  |  |     |  |        |     |  | ####| ######### |  |  | #|
+  +--+  +--+  +--+--+  +  +  +  +--+--+--+--+--+--+  +--+ #+
|           |              |  |                            #|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

London Underground

This script finds the shortest path between two underground stations, based on a list of London's stations

PYTHONPATH=. python tests/london/test_london_underground.py Chesham Beckton

Chesham
Chalfont & Latimer
Chorleywood
Rickmansworth
Moor Park
Northwood
Northwood Hills
Pinner
North Harrow
Harrow-on-the-Hill
Northwick Park
Preston Road
Wembley Park
Finchley Road
Baker Street
Bond Street
Oxford Circus
Tottenham Court Road
Holborn
Chancery Lane
St. Paul's
Bank
Shadwell
Limehouse
Westferry
Poplar
Blackwall
East India
Canning Town
Royal Victoria
Custom House
Prince Regent
Royal Albert
Beckton Park
Cyprus
Gallions Reach
Beckton

TAN Network

A solution for a codingame's puzzle (https://www.codingame.com/training/hard/tan-network)

PYTHONPATH=. python tests/tan_network/test_tan_network_5.py

.
----------------------------------------------------------------------
Ran 1 test in 0.010s

OK

python-astar's People

Contributors

Stargazers

Watchers

python-astar's Issues

Suggestion: add a functional interface

Thanks for the great library! I suggest to allow a fuctional interface. That is, instead of creating a class for each problem, allow to pass the functions neighbors, is_final etc. as direct arguments to the solver. This may be simpler for some users.

"pop index out of range" error since version 0.96

Hello,

I have the following error when using python astar since 0.96 while it is working with version 0.95 and below :

File "/usr/local/lib/python3.11/site-packages/astar/__init__.py", line 57, in pop
    item = self.sortedlist.pop(0)

 File "/usr/local/lib/python3.11/site-packages/sortedcontainers/sortedlist.py", line 1343, in pop
     raise IndexError('pop index out of range')

I use the following code :

def neighbors(neighbor):
    for node, distance in nodes[neighbor]:
        yield node

def distance(node_1, node_2):
    for node, distance in nodes[node_1]:
        if node == node_2:
            return distance

def cost(node, goal):
    return 1

best_path = astar.find_path(start_node_name, goal_node_name,
                            neighbors_fnct=neighbors,
                            heuristic_cost_estimate_fnct=cost, distance_between_fnct=distance)`

What is special in my case is that I have an incomplete set of nodes.
Start node : A
Goal node : D
I.e. I have the following nodes :
{'A': [('B', 200000)],
'C': [('D', 200000)],
'D': [('E', 200000)],
'E': [('F', 200000)],
'B': [],
'F': []}
As you can see, I have no path to go from B to C.
I expect in this case that astar.find_path() returns None (meaning no path found).
This was okay before 0.95 but it's not anymore.
From what I saw, it happens since the refactoring to use sortedcontainers : 71bd3c7

Do you have any suggestion/solution for that except using version 0.95 to not use sortedcontainers (which is now defined as a mandatory requirement by your module) ?

Thanks in advance,
Valentin

Performance drop on unreachable tile

I notice a performance bottleneck when trying to reach unreachable node. Any suggestions of how to mitigate it?

depth limited a*

i am looking for a depth-limited version of the algorithm, where depth is counted as the number of nodes in the path (never mind the distance)

Incorrect implementation

It may happen that you need to update a node with lower g-value. In this case you need to update the heap as well. You are not doing this correctly, which may lead in a suboptimal plan.

A quick fix (not optimal) is to sort the heap in case the node is already in the openlist:

 103:           if neighbor.out_openset:
                    neighbor.out_openset = False
                    heappush(openSet, neighbor)
                else:
 >>>                heapify(openSet)

heuristic_cost_estimate affects results

I was under the impression that the implementation of heuristic_cost_estimate should only affect performance, not results. But in this case, I'm seeing one implementation causes the result to be wrong:

from astar import AStar

M = 8
n = 15
A = [1, 4, 3, 6, 7, 1, 2, 2, 5, 2, 3, 3, 2, 1, 7]
B = [3, 7, 2, 1, 1, 8, 6, 5, 5, 4, 1, 2, 4, 8, 2]

class MyAstar(AStar):
    def neighbors(self, node):
        return [i for i in range(1, n+1) if i != node]

    def distance_between(self, n1, n2):
        return (A[n1-1] + B[n2-1]) % M

    def heuristic_cost_estimate(self, current, goal):
        return goal - current
        #return self.distance_between(current, goal)

    def is_goal_reached(self, current, goal):
        return current == goal

a = MyAstar()
print(list(a.astar(1, 15)))

This would print [1, 15] which has a cost of 3. If I use the actual implementation of distance_between for heuristic_cost_estimate (the commented line), I get [1, 4, 15] which with a cost of 2 is the correct result.

Add `py.typed` maker?

I'm using this astar successfully in my code, but when I try to check typing with mypy I get this error:

error: Skipping analyzing "astar": module is installed, but missing library stubs or py.typed marker  [import]
note: See https://mypy.readthedocs.io/en/stable/running_mypy.html#missing-imports

... so for now I'm ignoring this line:

from astar import AStar  # type: ignore

I think the fix may just be to add an empty astar/py.typed file, but I'm fairly new to python typing, so there may be more to it than just that.

(Looking at ci configuration, I'm not sure your type definitions are being checked now. I haven't run mypy on this package.)

Thanks, this saved me an hour or so

Surely this was the best way for me to solve that first puzzle in Castlevania: Lords of Shadow.

Incorrect implementation

118:    if neighbor.out_openset:
            neighbor.out_openset = False
            heappush(openSet, neighbor)
        else:
            # re-add the node in order to re-sort the heap
            openSet.remove(neighbor)
            heappush(openSet, neighbor)

The problem occurs inside the else branch. Remove and heappush may not re-sort the heap completely. The heap is a complete binary tree, the value of the parent node must be less(or greater) than or equal to the child node, so remove operation will destroy the structure of the heap. Heappush will only fix one path(from a leaf node to root), other problematic paths will not be fixed。

I wrote a unit test to reproduce the problem。
heap_unit_test.txt

jrialland / python-astar Goto Github PK

python-astar's Introduction

python-astar

Documentation

neighbors

distance_between

heuristic_cost_estimate

is_goal_reached

"Functional" API.

Examples

Maze solver

London Underground

TAN Network

python-astar's People

Contributors

Stargazers

Watchers

Forkers

python-astar's Issues

Recommend Projects

Recommend Topics

Recommend Org