Yet another pathfinding extension with a stupid name (I know every A* uses graphs 
). Feel free to recommend a new, creative, shocking name 
After maintaining another tile based A* extension for many years, I wanted to develop a new one where we could have more control over the graph. My initial idea was to port @dev-masih’s Defgraph to C++. I started working on it sometime in April 2025. I completed it after a few weeks (don’t remember the exact timeframe). But in the end, I realized that porting Lua to C one-to-one is a bad idea. I scrapped everything and started from scratch.
So this is not a port anymore. This was developed from the ground up (3 times). No other major dependencies were used (actually only dmArray and dmHashtable). I tried to build it with a focus on performance as much as I could (I’m not going to say it’s fast as hell ).
In the end, I believe it turned out to be new toy to play with, even just for fun😊
First beta is here:
If your map is tile based, I recommend using the A* extension or @rybeusz’s new Def-windward-jps.
Library Components
The library consists of three parts:
Pathfinder
Responsible for managing nodes, edges, and performing pathfinding. I’ve been testing this for a long time with various types of (dense) graphs. I consider this complete now for the first beta.
There are 4 kinds of pathfinding options:
- Start Node to Goal Node: Classic node-to-node pathfinding on the graph
- Projected to Goal Node: From an arbitrary position to a goal node
- Start Node to Projected: From a start node to an arbitrary position
- Projected to Projected: From an arbitrary position to another arbitrary position
You should consider that projected paths are more expensive. From cheapest to most expensive: node to node → projected to node/node to projected → projected to projected.
Path Smoothing
Responsible for path smoothing. I’m not very good at math, so I mostly adapted these algorithms from various sources (presentations, videos, etc.). In general, Bézier curves are hard to handle. I tried to simplify them to be usable with minimal settings.
It’s almost impossible to cover every use case. Requirements can vary from game to game. So feel free to add requests on GitHub.
These smoothing methods can also be used for any path, or anything you want to smooth (it’s enough to just pass the table with points ).
Currently available smoothing options:
- Quadratic Bézier
- Adaptive Bézier
- Catmull–Rom
- Cubic Bézier
- Circular Arc
These operations are relatively expensive. They are not perfect for every scenario. They might fail on tight nodes with aggressive curvatures etc. In general, quadratic offers a good balance between quality and performance in my tests.
Navigation
This is a work in progress and is not available in this release. It will be responsible for enabling agents to navigate along the path.
What is planned so far:
- Basic path following: Started to working on this but not finished yet
- Dynamic(moving) nodes handling for agents
- Group Assignment: Agent to red group, blue group, etc.
- Group Formation Patterns: Classic formations
I’m also considering adding collision avoidance, but it’s too early to say for sure.
Examples
I have many test projects, but they are mostly in terrible shape. There are just two basic examples in the main repo right now. I’m planning to do more when I get time.
To test this solution, I needed some kind of editor to add/edit waypoints faster. It has some issues while loading and saving, but I hope to fix them and share it as soon as possible.
Technical Stuff
I tried to follow Defold Engine’s principles with my limited knowledge.
- Flat Arrays: Cache-friendly memory layout using dmArray
- Path Caching: LRU cache with version based invalidation for frequently reused paths
- Spatial Index for Large Graphs: Grid based spatial indexing for projections (activated over 100 nodes, no benefits under 100). You may expect performance gains when the graph is larger (> 500 nodes)
- Dynamic Graph Updates: Add or remove nodes and edges at runtime with automatic cache invalidation
- Min-Heap Priority Queue: Custom implementation with zero-copy memory pooling and bulk operations
- Distance Caching: Spatial hashing for fast approximate distance lookups
- No STL Containers: Uses dmArray and dmHashTable for all data structures
- Memory Pre-allocation: All arrays are pre-allocated at initialization; pathfinding uses only pre-allocated memory
- No Exceptions: Uses explicit error codes instead of C++ exceptions
About the License
Here comes the fun part. I would like to try a different approach this time (I have my reasons).
- Free for personal, educational, and completely free games or apps
- Commercial use (any monetized game/app) requires at least a one-time payment of $10 USD (monthly sponsorships are also welcome) via GitHub Sponsors
- Free releases are welcome to share project info (name, genre, date, links)
- Library is closed-source; source access may be granted upon request (trusted developers, contributors, or verified sponsors)
So basically, if your released project is completely free and non-monetized, no payment or permission is required.
See License for details.