Graph Pathfinder is a high-performance pathfinding library for the Defold game engine. It is developed by Selim Anaç, a developer and designer who creates native extensions for Defold. The library is written in C++ and is based on the A* pathfinding algorithm.
For those unfamiliar, the A* algorithm is used to find the shortest and most efficient route between two points. It helps characters, vehicles, and other game objects navigate around obstacles and terrain. It makes movement appear smooth and intelligent, supporting gameplay elements that include unit movement, enemy pursuit, projectile or ability targeting and AI decision planning.
After maintaining a tile-based A* extension for many years, the developer wanted to create a new solution that offered greater control over the underlying graph structure. An initial attempt to port an existing solution to C++ did not meet these expectations, which led to the decision to develop Graph Pathfinder as a new project.
The solution places a strong emphasis on performance, with the author stating that it is designed for real-time games and simulations that handle hundreds to thousands of moving objects.
The library, which is currently in a beta state, is divided into three main parts. The first is Pathfinder, the core library responsible for managing nodes and edges and performing pathfinding operations. It includes features such as projected pathfinding, a min-heap priority queue, path caching, and distance caching.
The second part is Path Smoothing, which focuses on refining paths using a variety of smoothing techniques. Available options include Quadratic Bézier, Adaptive Bézier, Catmull–Rom, Cubic Bézier, and Circular Arc smoothing. According to the author's tests, the quadratic option generally provides a good balance between quality and performance.
The final part is Navigation, which is still a work in progress and is intended to enable agents to move along calculated paths. Planned and in-progress features include path following, dynamic nodes and path invalidation for agents, group assignment, and group formation patterns.
The project has been recently updated and now includes polygon-based navmesh pathfinding support. This feature works alongside standard pathfinding, allowing both approaches to be used at the same time, although only static 2D navmeshes are currently supported.
Graph Pathfinder includes an example project called Tiny City, which demonstrates its capabilities. An interactive web build of the demo is also available and can be experienced directly in the browser. The project additionally contains a development version of a visual graph editor for Graph Pathfinder, designed to speed up the creation and editing of waypoints. The graph editor is not production ready and should be used at the user's own risk.
Graph Pathfinder is available for free for personal use, educational purposes, and entirely free games or applications. Commercial use requires a one-time payment of $10 USD.
For more information, visit the project's repository on GitHub.
