A* algorithm in Python

A simple A* implementation using matplotlib to visualize the shortest path found from a point to another one. This implementation was made during the discipline of complexities of algorithms during Computer Science at La Salle university.

Implementation

• The implementation uses numpy array to store the representation of the terrain.
• The value -1 represents an obstacle on the terrain.
• Each coordinate may contain a specific weight.
  • The weight is considered by the implementation when searching for a path.

Running

Creating virtual environment and installing dependencies:

python -m venv .venv
source ./.venv/bin/activate

pip install -r requirements.txt

Generating a solution for a map:

python ./main.py --input "inputs/simple" --goal "1 13"

Example of solution

Input layout

The implementation expects the input map file to have the following layout:

<x_size> <y_size>
<start_x> <start_y>
<weight> <weight> <weight> <weight> <weight>
<weight> <weight> <weight> <weight> <weight>
<weight> <weight> <weight> <weight> <weight>
...

Example:

2 3
8 8
0 0 -1 0 0 0 0 0
0 -1 0 0 -1 0 0 0
-1 0 0 -1 -1 0 0 0
...

Running automated tests

The automated tests use mazelib to create random mazes with start and end coordinates to validate the implementation by comparing the shortest path found with the solution found by other algorithms.

python -m unittest ./tests/astar_test.py