Help the Python Software Foundation raise \$60,000 USD by December 31st!

A* search algorithm implemented in Cython

## Project description # 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.

## Project details

This version 1.0.5 1.0.0