Home

Awesome

Dijkstra Algorithm for Godot

What it does

Howdy !

This is a GDNative project for Godot game engine, that introduces Dijkstra Map pathfinding node. It provides a much needed versatility currently absent from the build-in AStar pathfinding. Its main feature is the ability to populate the entire graph with shortest paths towards a given origin point. Total lengths of shortest paths and directions can then be easily looked up for any point in the graph.

Common use cases include: pre-computing pathfinding for tower-defense games, RTS games and roguelikes; listing available moves for turn-based games; aiding in movement-related AI behaviour. You can find more examples in this amazing article.

The library is written in Rust programming language and performance should be comparable to C/C++ (approximately 10-20x faster than GDScript).

Note that the API is now stable! Some features may be added over time.

Installing

Note: when installing pre-compiled libraries, we support

Method 1: from the asset store (recommended)

This will work for linux x64, macos x86 and windows x64 for godot 3.5.1 (for another godot version you'll probably have to use the second method):

  1. In the godot editor, go to the AssetLib tab

    And search for Dijkstra Map Pathfinding

  2. Download and install the files

    This will install the files in res://addons/dijkstra-map.

Method 2: from Github

Note: on linux x64, macos x86 or windows x64, you may skip steps 2-4 and use the pre-compiled libraries in addons/dijkstra-map/Dijkstra_map_library/bin/<os-name>. They may be slightly outdated though.

  1. Clone this repository

  2. Install the Rust compiler

  3. Install the dependencies for the GDNative bindings for Rust.

  4. Run cargo build --release. This will build the library in target/release (for example, on windows: target/release/dijkstra_map_gd.dll).

    Note that this might take some time as it compiles all the dependencies for the first time.

    Copy the resulting library to addons/dijkstra-map/Dijkstra_map_library/bin/<os-name>.

  5. Copy the addons/dijkstra-map directory into your project's res://addons directory.

  6. Open Godot and add path to the binary file into the res://addons/dijkstra-map/Dijkstra_map_library/dijkstra_map_library.tres GDNativeLibrary resource. This resource tells Godot which binary to use for which system. For more info see the GDNative C example in Godot's documentation.

Examples

There are 3 examples scenes in the github repository:

And heavily commented code in Project_Example/dependancy/.

Note: all examples need mono-based Godot to run.

You can also look at the unit tests in Tests/unit/*.

Features && How-To's

Basic Behaviour

In Godot project you start by creating a new DijkstraMap Node.

More recalculate flags

recalculate method has various optional arguments that modify its behavior. It is possible to:

Please, see the documentation for full explanation.

The usefulness of terrain

Points in the DijkstraMap have an optional terrain ID parameter. This feature makes it possible to re-use the same DijkstraMap node for units with different movement restrictions, without having to duplicate the entire DijkstraMap and manually modify all connection costs.

For example, let's say you have 3 unit types in your game: Footsoldier (which moves the same speed regardless of terrain), Cavalry (which moves half the speed through forests) and Wagon (which can only move on roads). First you decide on integer IDs you will use for different terrain types, for example:

const TERRAIN_ID_OTHER=-1 #Note: default terrain ID -1 is hard-coded in the DijkstraMap
const TERRAIN_ID_ROAD=0
const TERRAIN_ID_FOREST=1

Now you assign these terrain IDs to the points in your DijkstraMap. This can be done while adding the points (add_point method has optional second parameter for terrain ID) or even after they were added (via set_terrain_for_point method). By default (if not specified otherwise), points get terrain ID of -1.

When recalculating the DijkstraMap for the Cavalry, we specify "terrain_weights" optional argument as follows:

my_dijkstra_map.recalculate(origin_point, {"terrain_weights": {TERRAIN_ID_FOREST:2.0} } )

Now, during this recalculation, connection costs of forest points are doubled* (ie. movement speed is halved) and the shortest paths will try avoid forest points, to minimize travel time. Specifically, path segments will only lead trough forests, if they are half the length of alternative paths.

When recalculating the DijkstraMap for the Wagon, we specify "terrain weights" optional argument as follows:

my_dijkstra_map.recalculate(origin_point, {"terrain_weights": {TERRAIN_ID_FOREST:INF, TERRAIN_ID_OTHER:INF} } )

Now, during this recalculation, all points, except roads, are completely inaccessible, because their connections have infinite cost. The calculated paths will only follow roads.

C# Support

A wrapper located in addons/dijkstra-map/Dijkstra_map_library/DijkstraMap.cs can be used to interface with the library. Example use can be seen in addons/dijkstra-map/visualization demo/visualisation.tscn. The benefits of this wrapper:

Make sure your C# code can find the DijkstraMap.cs file and its class.

Notes

Careful ! If you pass arguments of the wrong signature to the Rust API, the game will not crash, if you're lucky and have a terminal open, it might print an error there but not in Godot! This issue can be avoided by using a gdscript wrapper But it can lead to non trivial bugs, consider yourselves warned. We're working on friendlier error at runtime.

Running the tests

If you're familiar with the gut API, you can launch the Gut.tscn and run some test

You can also run 'cargo test' and you're free to look at rust test or contribute to them.

Contributing

Open an issue before working on a feature, bugfix, unit tests, then we discuss it, then you can work on it (or let someone else) then do a pull request

Before doing that pull request, if you modified the rust code be sure you have build it "cargo build --release" and it still works!

TODO

Use in projects

Acknowledgments

KohuGaly Astrale EƤradrier