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

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.