This is a customized version of astar-algorithm-cpp. Given a map and a set of starts and goals, this algorithm can return an optimal path. This repo has very easy-to-build-and-use C++ implementation and Python wrapper.
The following contents starting from Summary have been revised such that they fit this forked repo. I really appreciate all the contributors' effort such that I can use this C++ implement of A* algorithm!
Zehui
This repo has been tested with:
- GCC 13.3.0, CMake 3.28.3, Ubuntu 24.04.3 LTS
- GCC 10.2.0, CMake 3.16.3, Ubuntu 20.04.2 LTS
- GCC 9.3.0, CMake 3.16.3, Ubuntu 20.04.1 LTS
- Clang 15.0.0, CMake 3.27.7, macOS 13.6.6
- Clang 13.0.0, CMake 3.22.1, macOS 11.4
- Clang 12.0.0, CMake 3.18.3, macOS 10.15.7
For Python:
- pybind11 If you only install
pybind11bypip, it's possible that CMake can't find it. But you can install it byaptorbrew. - numpy.
- matplotlib.
$ sudo apt install gcc g++ cmake libtbb-dev # For macOS: brew install tbb
$ sudo apt install python3-pybind11 # For macOS: brew install pybind11
$ pip3 install numpy matplotlib
$ git clone https://github.com/zehuilu/astar-algorithm-cpp.git
$ cd <MAIN_DIRECTORY>
$ cd build
$ cmake .. # For debug mode, run: cmake .. -DCMAKE_BUILD_TYPE=Debug
$ makeIf you want to use conda to manage environment:
$ conda create --name astar python numpy matplotlib
$ conda activate astar
$ conda install conda-forge::pybind11
$ git clone https://github.com/zehuilu/astar-algorithm-cpp.git
$ cd <MAIN_DIRECTORY>
$ cd build
$ cmake .. # For debug mode, run: cmake .. -DCMAKE_BUILD_TYPE=Debug
$ makeNote: If you are using conda, make sure you are in the right env astar before you use cmake and make to compile.
Otherwise, conda will link to the Python associated with the base environment or other environments, which are wrong.
For C++, the usage is shown in src/main_sing_path.cpp.
$ cd <MAIN_DIRECTORY>
$ build/main_single
For Python, the usage is shown in example/run_PathFind.py.
$ cd <MAIN_DIRECTORY>
$ python3 example/run_PathFind.py
For Python, to run AStarPython.FindPathAll() with openMP (multi-threading), see example/run_FindPathAllMP.py.
The function AStarPython.FindPathAllMP() is used in line 36, and the usage is the same as AStarPython.FindPathAll().
$ cd <MAIN_DIRECTORY>
$ python3 example/run_FindPathAllMP.py
Python
To call A* Solver in Python, a simple example is shown below. More details are in example/run_PathFind.py.
import AStarPython
map_width = 20
map_height = 20
# world_map is a 1D list (row-major), 0 means no obstacles, 255 means blocked by obstacles
start = [0, 0] # start position is a list of intergers which indicates the position [px, py]
goal = [35, 18] # goal position
# solve
path, distance = AStarPython.FindPath(start, end, world_map, Simulator.map_width, Simulator.map_height)Run example/run_PathFind.py, the result is shown below. Time used is 0.362 ms.
C++
To call the A Star solver in C++, a simple example is shown below. More details are in src/main_single_path.cpp.
// ignore all the headers, see more details in src/main_single_path.cpp
int map_width = 20;
int map_height = 20;
int start[2] = {0, 0}; // Create a start state
int end[2] = {18, 14}; // Define the goal state
struct MapInfo Map;
Map.world_map = world_map;
Map.map_width = map_width;
Map.map_height = map_height;
// world_map is a std::vector<int>, 0 means no obstacles, 255 means blocked by obstacles
// solve
auto [path, distance] = find_path(start, end, Map);Run src/main_single_path.cpp, the path result is shown on the console. Time used is 0.135 ms.
This is the short path. Steps used:34
0,0
19,0
19,10
18,10
18,14
===================================================================================
This code is an efficient implementation in C++ and C# of the A* algorithm, designed to be used from high performance realtime applications (video games) and with an optional fast memory allocation scheme.
It accompanies this A* tutorial: http://www.heyes-jones.com/astar.html
The A* algorithm was described in the paper https://ieeexplore.ieee.org/document/4082128 by Hart, Nillson and Raphael. Sadly Nils Nillson passed away in 2019, his work is much appreciated.
Contributions:
- @justinhj Original code and tutorial
- @ScaryG C# port
- @Rasoul for submitting the path to Bucharest. Sample from Artificial Intelligence: A Modern Approach
- @sergiosota For fixing a number of issues related to memory management
This software is released under the MIT License, see license.txt
This software has been used in AAA video games and is well tested in the wild. Please let me know if you use this code in you games, studies or hobby projects.
If you feel the need to pay money for this code, it is not required by the license, but you could contribute to Unicef, a charity which helps children worldwide, http://www.unicef.org/ that would be awesome.
If you wish to be added to the list of known products/educational projects using the code please contact me.
- Gun, Activision
- Company of Heroes and Company of Heroes Online, Relic Entertainment
- Angel Engine, a game prototyping engine http://code.google.com/p/angel-engine/
- War of Sonria, a strategy war game on PSP and Playstation 3 by Playground Squad
- Lighthouses AI contest https://github.com/marcan/lighthouses_aicontest
- Self-Driving Car Engineer Nanodegree Program https://github.com/vanAken/CarND-Path-Planning-Project
This implementation is intended to be simple to read yet fairly efficient. To build it you can compile, with any recent C++ compiler, the following files :
For path finder
- findpath.cpp
- stlastar.h
- MapSearchNode.h
- MapInfo.h
- optionally fsa.h
pathfind has no arguments. You can edit the simple map in pathfind.cpp and the start and goal co-ordinates to experiement with the pathfinder.
Fixed size allocator notes: As mentioned briefly in the tutorial you can enable and disable the faster memory allocation. This allocates a fixed size block of memory, so you have to specify this size with the astar constructor. You need to enlarge it if you hit an out of memory assert during the search.
Please let me know if it doesn't work for you and I will try to help. I cannot help if you are using an old compiler such as Turbo C++, since I update the code to meet Ansi Standard C++ as required.
Cheers!
Justin