Repository files navigation

This is a simple implementation of thea-star path findingalgorithm inpython

The astar module defines the AStar class, which has to be inherited fromand 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 becomparable for same-ness (i.e. implement __eq__).

The computation of the hash may be implemented by several means :

• base types like strings, floats, integers, tuples. already implement __hash__
• dataclasshttps://docs.python.org/3/library/dataclasses.html#dataclasses.dataclass ` objects declared with `@dataclass(frozen=True) directly implement __hash__ if possible.
• by overriding the __hash__()https://docs.python.org/3/reference/datamodel.html#object.__hash__ method as a combination of the fields that you consider relevant for your object.

@abstractmethoddefneighbors(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 thealgorithm the description of the graph to use during for computation.

Alternately, your override method may be named "path_neighbors". Instead ofyour node, this method receives a "SearchNode" object whose "came_from"attribute points to the previous node; your node is in its "data" attribute.You might want to use this if your path is directional, like the track of atrain that can't do 90° turns.

One of these methods must be implemented in a subclass.

@abstractmethoddefdistance_between(self,n1,n2)

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

Alternately, you may override "path_distance_between". The argumentswill be a "SearchNode", as in "path_neighbors". You might want to use thisif your distance measure should include the path's attainable speed, thekind and number of turns on it, or similar. You can use the nodes' "cache"attributes to store some data, to speed up calculation.

One of these methods must be implemented in a subclass.

@abstractmethoddefheuristic_cost_estimate(self,current,goal)

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

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

This method must be implemented in a subclass.

defis_goal_reached(self,current,goal)

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

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>

deffind_path(start,goal,neighbors_fnct,reversePath=False,heuristic_cost_estimate_fnct=lambdaa,b:Infinite,distance_between_fnct=lambdaa,b:1.0,is_goal_reached_fnct=lambdaa,b:a==b    )

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

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

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

CheshamChalfont & LatimerChorleywoodRickmansworthMoor ParkNorthwoodNorthwood HillsPinnerNorth HarrowHarrow-on-the-HillNorthwick ParkPreston RoadWembley ParkFinchley RoadBaker StreetBond StreetOxford CircusTottenham Court RoadHolbornChancery LaneSt. Paul'sBankShadwellLimehouseWestferryPoplarBlackwallEast IndiaCanning TownRoyal VictoriaCustom HousePrince RegentRoyal AlbertBeckton ParkCyprusGallions ReachBeckton

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 1testin 0.010sOK