astar-algorithm

Summary

An efficient implementation in C++ of the A* algorithm, designed to be used in high performance realtime applications (video games) and includes an optional pool memory allocator.

It accompanies this A* tutorial: https://www.heyes-jones.com/astar.php

The A* algorithm is due to Hart, Nillson and Raphael. See https://ieeexplore.ieee.org/document/4082128.

This repository is dedicated to the memory of Nils Nilsson who sadly passed away in 2019.

Looking for a C# version? Checkout the companion repository astar-algorithm-csharp for a port by @scaryg

Star History

Release notes

v1.3.1 Bug fixes, safety hardening, and codebase modernization:

• Fixed use-after-erase iterator bug in SearchStep() when reopening nodes from the closed list.
• Guarded FreeSolutionNodes() against failed or uninitialized searches to eliminate potential use-after-free.
• Updated ~FixedSizeAllocator to properly invoke destructors on live objects, avoiding resource leaks when states hold non-trivial members.
• Added double-free, alignment, and bounds validation to FixedSizeAllocator::free().
• Fixed 64-bit pointer format specifiers (%p) in fsa.h Debug().
• Ensured goal node heuristic (h) and total cost (f) are properly populated upon search success.
• Replaced legacy NULL and 0 pointer literals with C++11 nullptr across all headers.
• Removed unused AStarState dead code and retired .travis.yml.
• Secured doctest download with SHA256 URL_HASH in CMake.

v1.3 Performance optimizations for the open list and addition of a reproducible benchmark suite:

• Open list state membership lookup is now O(1) using an unordered_set, eliminating the previous O(N) linear search per successor.
• The open list binary heap is now an indexed heap with each node tracking its heap_index, replacing O(N) std::make_heap operations on decrease-key with O(log N) sift-up operations.
• Added a 1,000,000-search reproducible 2D grid benchmark (bench.cpp) and modernized unit testing with doctest.

v1.2 Breaking changes! C++ 11 is now the minimum required C++ standard. User is now required to provide a Hash function for their Node type. Thanks to a contribution from @btdubs the closed list is now an unordered_set and this greatly speeds up the execution time of the algorithm. Check the included demo code for examples of the Hash implementation for various Node types.

v1.1 Code cleanup and final version that does not require C++11

v1.0 Initial release once API stable.

License

This software is released under the MIT License, see license.txt

Commercial Use

This software has been used in a number of AAA video games, which is an area of software that relies on efficiency and reliability. In addition it has been used in a number of academic and personal projects that require efficient search. Please

Commercial users of the code are encouraged to make a donation to http://www.unicef.org/ if they find this project useful.

Projects using this code

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 (various versions), 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

Building

Generally you can just include the stlastar.h and, optionally, the fsa.h header files and use it directly. The build instructions below are purely for the test suite and example executables.

Using CMake

Some examples:

** Use make and make a debug build ** bash cmake -S . -B builddebug -DCMAKE_BUILD_TYPE=debug

** Use Ninja and make a Release build ** bash cmake -S . -B ninjabuildrelease -DCMAKE_BUILD_TYPE=release

In both cases you can execute the build using make -C [build folder] or ninja -C [build folder].

Command line

8puzzle with no arguments runs with one of the boards in the cpp file, you can select the one you want changing the conditional compiliation instructions. Or if you prefer pass in a board on the command line using digits for the tile positions, where zero is the space. The board runs from left to right, each row at a time:

8puzzle 013824765

For path finder

• findpath.cpp
• stlastar.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.

Benchmark

The bench executable benchmarks search performance across a large 2D grid:

• What it does:

  • Generates a 1000 x 1000 grid from a deterministic, hardcoded random seed (12345), placing 20% obstacles (impassable cells) and 80% passable terrain.
  • Executes 1,000,000 searches between pseudo-randomly selected passable start and goal coordinates.
  • Measures the total elapsed search time with std::chrono::steady_clock and calculates the average time per search (total time divided by 1,000,000).
  • Because the random seed is fixed, the grid and the sequence of searches are completely reproducible across runs, making it an accurate baseline to benchmark optimizations to the stlastar.h implementation.
  • Key parameters (MAP_WIDTH, MAP_HEIGHT, RANDOM_SEED, NUM_SEARCHES, and OBSTACLE_PERCENTAGE) are configured as module constants in bench.cpp.

• How to run:

  • Build the benchmark target:

    cmake --build [build folder] --target bench

  • Run the default benchmark (1,000,000 searches):

    ./[build folder]/bench

  • Run with an optional argument to specify fewer searches for quick iterations during development:

    # Run 10,000 searches instead of 1,000,000
    ./[build folder]/bench 10000

Fixed size allocator

FSA is just a simple memory pool that uses a doubly linked list of available nodes in an array. This is a very efficient way to manage memory. It has no automatic resizing, so you must account for the fact it will use a fixed block of memory per instance and will report an error when memory is exhausted.

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.

Compatibility notes:

This version of the code requires any standards compliant C++ using std C++11. To build it requires a minimum cmake version you can find in the CMakeLists.txt file.