Skip to content

Simple implementation of the a-star algorithm in Python ๐ŸŒŸ

License

Notifications You must be signed in to change notification settings

nealshan/python-astar

ย 
ย 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

ย 

History

62 Commits
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 

Repository files navigation

https://travis-ci.com/jrialland/python-astar.svg?branch=master https://coveralls.io/repos/github/jrialland/python-astar/badge.svg?branch=master https://img.shields.io/github/stars/jrialland/python-astar https://img.shields.io/github/forks/jrialland/python-astar

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 :

neighbors

@abstractmethod
def neighbors(self, node)

For a given node, returns (or yields) the list of its neighbors. this method must be implemented in a subclass

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.

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

About

Simple implementation of the a-star algorithm in Python ๐ŸŒŸ

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • Python 97.9%
  • Shell 2.1%