Skip to main content
Join the official 2019 Python Developers SurveyStart the survey!

A* search algorithm implemented in Cython

Project description

Build Status

astarlib

astarlib is a Cython ("C-Extensions for Python") implementation of the A* search algorithm on a graph or a 2-dimensional polygon space packaged into a reusable library. It was originally implemented as my battlesnake.io bot's navigation system (e.g. finding minimum path around enemy bots).

Example

To find A* paths in a 2D polygon, you need to initialize an aStar() object with a "map" of the traversing space.

Note: all elements of a given array will be automatically normalized to boolean states. After normalization, elements that are True are considered traversable and False are treated as untraversable (e.g. obstacle).

>> from astarlib import aStar
>> area = aStar(array=[
  [1, 1, 1, 1, 1, 1],  # see `normalization`
  [0, 1, 0, 1, 1, 1],
  [0, 0, 0, 0, 0, 1],
  [1, 1, 1, 1, 1, 1],
  [0, 1, 0, 1, 0, 1],
  [0, 0, 1, 1, 1, 1],
])

And then simply set the start/destination information to find a valid path and cost of the path. In a snake game, "start" is the head of a snake and "end" is an apple.

>> area.find_path(start=(0, 0), end=(area.height-1, area.width-1))
(
  ((0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 5), (2, 5), (3, 5), (4, 5), (5, 5)),
  11
)

Since the initial "map" is preserved, you can also invoke .find_path() multiple times for different traversal paths.

>> area.find_path(start=(0, 0), end=(0, 1))
(
  ((0, 0), (0, 1)),
  2
)

If there is no path, PathNotFoundException will be raised.

>> area.find_path(start=(0, 0), end=(1, 0))  # `PathNotFoundException`

Build

Local build for development requires some dependencies to compile C extensions.

~$ make

Installation

For stable channel:

~$ pip install astarlib==1.0.0

For edge channel:

~$ # sudo apt install gcc python-dev
~$ pip install git+https://github.com/initbar/astarlib.git

Tests

~$ # pip install pytest
~$ make test

Documentations

See documentations.

License

astarlib is licensed under MIT License.

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for astarlib, version 1.0.5
Filename, size File type Python version Upload date Hashes
Filename, size astarlib-1.0.5.zip (10.4 kB) File type Source Python version None Upload date Hashes View hashes

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN SignalFx SignalFx Supporter DigiCert DigiCert EV certificate StatusPage StatusPage Status page