DOCSEARCHbyAlgolia
Submit Docs

PyAstar2D

repository·master·Indexed 41 days ago

https://github.com/hjweide/pyastar2d

A high-performance C++ implementation of the A* algorithm for 2D grid pathfinding wrapped for Python. It optimizes large grids by representing the graph as a 1D array. The core API, pyastar2d.astar_path(), supports 4-connectivity and 8-connectivity (via allow_diagonal=True) using numpy float32 weights arrays.

Tokens
1.4K
Snippets
7
Records
7
Agent score
50%

What's inside PyAstar2D

  1. Install pyastar2d

    master

    You can install pyastar2d using several methods depending on your environment.

    From PyPI

    pip install pyastar2d

    From source

    Clone the repository and build it locally.

    • Linux/MacOS: Run pip install . from the root directory.
    • Windows: You may need to install Cython first:
    pip install Cython
pip install .

    As a dependency

    Add the following line to your requirements.txt to install directly from the master branch of the GitHub repository:

    pyastar2d @ git+git://github.com/hjweide/pyastar2d.git@master#egg=pyastar2d
    pip install pyastar2d

  3. Run the maze solver example CLI

    master

    The examples/maze_solver.py script can be used to solve mazes provided as images. It treats white pixels as open space (cost 1) and black pixels as walls (cost INF).

    Use the --input and --output flags to specify the source image and the destination for the solved path image.

    Example command:

    python examples/maze_solver.py --input mazes/maze_small.png --output solns/maze_small.png
    python examples/maze_solver.py --input mazes/maze_small.png --output solns/maze_small.png

  4. Use pyastar2d.astar_path() for grid pathfinding

    master

    The core API is pyastar2d.astar_path(), which finds the shortest path on a 2D grid using the A* algorithm.

    Requirements for inputs:

    • Weights Array: Must be a 2D numpy array with dtype=np.float32.
    • Minimum Cost: The minimum value in the weights array must be at least 1 for the heuristic to remain valid.
    • Coordinates: Both the start and goal coordinates must be provided as matrix coordinates in (i, j) format.

    Connectivity Options:

    • 4-connectivity: The default behavior (up, down, left, right).
    • 8-connectivity: Enable by setting allow_diagonal=True to allow diagonal moves.

    Returns: A numpy array of (i, j) coordinates representing the path.

    import numpy as np
import pyastar2d

# The weights array must have np.float32 dtype
# The minimum cost must be 1 for the heuristic to be valid.
weights = np.array([[1, 3, 3, 3, 3],
                    [2, 1, 3, 3, 3],
                    [2, 2, 1, 3, 3],
                    [2, 2, 2, 1, 3],
                    [2, 2, 2, 2, 1]], dtype=np.float32)

# Start and goal are (i, j) matrix coordinates
path = pyastar2d.astar_path(weights, (0, 0), (4, 4), allow_diagonal=True)
print(path)

  5. Calculate a path using astar_path()

    master

    The astar_path function computes the shortest path through a 2D grid of weights using the A* algorithm.

    Requirements:

    • Weights Dtype: The weights array must have a np.float32 data type.
    • Minimum Cost: For the heuristic to be valid, every value in the weights array must be at least 1.0. If any value is less than 1, a ValueError is raised.
    • Coordinates: The start and goal parameters must be provided as (i, j) tuples representing matrix coordinates.
    • Bounds: Both start and goal must lie within the dimensions of the weights grid.
    import numpy as np
from pyastar2d.astar_wrapper import astar_path, Heuristic

# Create a 10x10 grid of weights (all 1.0)
weights = np.ones((10, 10), dtype=np.float32)

# Define start and goal as (i, j) coordinates
start = (0, 0)
goal = (9, 9)

# Compute the path
path = astar_path(
    weights=weights,
    start=start,
    goal=goal,
    allow_diagonal=False,
    heuristic_override=Heuristic.DEFAULT
)

# path is returned as a numpy array of (i, j) coordinates or None if no path exists
print(path)

  6. Configure the heuristic using Heuristic enum

    master

    The heuristic_override parameter in astar_path allows you to specify which heuristic to use for the A* search. This is controlled via the Heuristic enum.

    from pyastar2d.astar_wrapper import Heuristic

# Available heuristic options:
# Heuristic.DEFAULT: Default heuristic
# Heuristic.ORTHOGONAL_X: Orthogonal X heuristic
# Heuristic.ORTHOGONAL_Y: Orthogonal Y heuristic