CHDR is a C++ library aiming to offer a comprehensive cross-platform solution for pathfinding in K-dimensions. It provides routing support for a variety of maze types including grid-based graph-based recursive and weighted (fields) using an extensive range of algorithms.
CHDR is designed to be fast and lightweight. Alongside data and algorithmic optimisations it utilises metaprogramming to resolve expensive code paths at compile time.
| Platform | Status |
|---|---|
| Linux | Tested ✔️ |
| Windows | Tested ✔️ |
| MacOS | Untested ❓ |
| Type | Status |
|---|---|
| A-Star (A*) | Completed ✔️ |
| Best-First Search (B*) | Completed ✔️ |
| Breadth-First Search (BFS) | Completed ✔️ |
| Depth-First Search (DFS) | Completed ✔️ |
| Dijkstra's Algorithm | Planned 📝 |
| Enhanced Iterative Deepening Search (EIDA*) | Planned 📝 |
| Enhanced Simple Memory Bounded A-Star (SMA*+) | Planned 📝 |
| Enhanced Simple Memory Bounded Graveyard Search (SMG*+) | In Progress 🏗️ |
| Graveyard Breadth-First Search (GBFS) | Completed ✔️ |
| Graveyard Depth-First Search (GDFS) | Completed ✔️ |
| Graveyard Jump-Point Search (GJPS) | Planned 📝 |
| Graveyard Search (G*) | Completed ✔️ |
| Jump-Point Search (JPS) | Completed ✔️️ |
| Type | Status |
|---|---|
| Fields | Completed ✔️ |
| Graphs | Completed ✔️ |
| Grids | Completed ✔️ |
| Recursive | Planned 📝 |
| Type | Status |
|---|---|
| Path Smoothing | Planned 📝 |
| Path Simplification | Planned 📝 |
| Type | Status |
|---|---|
| Jump Flooding Algorithm (JFA) | Planned 📝 |
| Feature | Status |
|---|---|
| Compile-Time K-dimensionality | Completed ✔️ |
| Compile-Time Routing | Planned 📝 |
| Concurrent Capabilities | In Progress 🏗️ |
| Dynamic Mazes and Obstacle-Avoidance | Planned 📝 |
| Maze Optimisation (Baking) | In Progress 🏗️ |
| Runtime K-dimensionality | In Progress 🏗️ |
| Architecture | Instruction Sets | Status | Vectorisation |
|---|---|---|---|
| x86 / x86-64 | MMX 3DNOW SSE SSE2 SSE3 SSSE3 SSE4.1 SSE4.2 AVX AVX2 AVX-512 |
Redundant 🦕 Redundant 🦕 Redundant 🦕 Completed ✔️ Completed ✔️ Completed ✔️ Completed ✔️ Completed ✔️ Completed ✔️ Completed ✔️ Planned 📝 |
- - - 128-bits 128-bits 128-bits 128-bits 128-bits 128-bits (Up to 256 planned) 128-bits (Up to 256 planned) Up to 512-bits |
| ARM | NEON SVE SVE2 |
Planned 📝 Planned 📝 Planned 📝 |
128-bits Up to 2048-bits Up to 2048-bits |
| RISC-V | P-Extension V-Extension |
Planned 📝 Planned 📝 |
128-bits Variable |
| POWER | AltiVec VSX |
Planned 📝 Planned 📝 |
128-bits 128-bits |
| MIPS | MSA | Planned 📝 | 128-bits |
As CHDR is a header-only library you can simply include the headers directly in your project or build and link using your preferred build system.
at present CHDR does not offer compatibility with languages other than C++. We prioritise consolidating and enhancing the set of features offered by our library before extending its support to other languages.
Each programming language has its unique characteristics and paradigms. With this in mind our strategy for supporting a specific language would be determined by its compatibility with C++ and the performance efficiency it offers. The support may be facilitated through language wrappers (interfaces to the library's compiled code) or ports (rewriting parts or all of the library in the target language), whichever is more suited.
CHDR is completely standalone and does not require the use of any third-party libraries.
However CHDR does require that your project is compatible with a C++17 environment and supports the following standard libraries:
Lovinger J. and Zhang X., 2017 Enhanced simplified memory-bounded a star (SMA*+). EPiC Series in Computing, 50, 202–212. Available at: https://doi.org/10.29007/v7zc. [Accessed 10 Aug. 2024].
Reinefeld, A. and Marsland, T. A., 1994. Enhanced iterative-deepening search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 16 (7), 701–710. Available at https://doi.org/10.1109/34.297950. [Accessed 3 Oct. 2024].