Threading... can we? and should we?

[MatejSloboda]

The current implementation is build around Dijkstra algorithm. The algorithm works by visiting all points in graph in order of increasing distance from origin point(s). It's inherently linear and non-thread-able. We could switch to some tread-able/concurrent algorithm, but it might come at a cost of having to pre-process the graph every time it changes and at a cost of cutting features (using Dijkstra as fallback in those cases). To me, this doesn't seem like viable option and might be superfluous in the first place. I think a regular user should understand that calculating shortest paths to all points on the map is probably not something you should be triggering every frame.

Where I do see a room for multithreading is bulk processing. We might split the structure into two. One that holds the graph (let's call it Graph object) and one that holds the calculated results (let's call it Dmap object). This way user can provide multiple 'recalculate' queries in one go, that get processed in parallel. The function returns the Dmap objects that can be passed around (ie. assigned to particular units in game) and accessed. Meanwhile the Graph can be stored in central location.

The Dmap object may even hold all the settings that normally get passed to the recalculate method and it may be synced up the Graph object. When the Graph is modified (points/connections added/removed) all the Dmap objects get recalculated remotely. Similarly, you could just modify the settings (such as source and target position or movement type) of a particular Dmap object to recalculate it in place, without having to pass it to the Graph object. These "updates" may also be optionally queued, to be batch processed when convenient and in bulk, when possible.

This might improve functionality a lot. At the moment, if you wish to keep multiple Dijkstra maps all calculated from the same graph (a very common situation), you either: a) need to dump the results into Dicts (the get_cost_map and get_direction_map methods) and manually make sure everyone has an up-to-date version of them. or b) duplicate the DijkstraMap object itself and manually make sure, that every instance has an up-to-date graph.

[astrale-sharp]

We can, as the crate pathfinding https://docs.rs/pathfinding/2.0.4/pathfinding/index.html already does so. I don't understand how it would improve functionality because i don't see the difference between -"a) need to dump the results into Dicts (the get_cost_map and get_direction_map methods) and manually make sure everyone has an up-to-date version of them. or"

• however a multithreaded version of this algorithm would work

We can and it would definitely improve performance BUT i don't have the need for more performance right now (if it ain't broken don't fix it). So I'm not interested in doing the work. If you're interested in doing so i advise to use the crate rayon for multithreading

[MatejSloboda]

I agree. It would be another major refactor, that I'm not looking forward to. Multi-threading is also like one of those common tropes in movies, where the character says "What could possibly go wrong?!" and the movie jump cuts to them screaming while driving a burning car from T-rex riding cannibals. May be something for v2.0

[realkotob]

I've worked with multi-threading in godot, and it's not something you can tack on without considerations about the desired interaction points with the scene tree (basically you need to be very aware of your real-world usage).

Additionally, threading is an optimization feature, and unless someone opens an issue complaining about the performance then we definitely should stay away from it.

Multi-threading in godot is not hard and actually fun to use (I've used it for AI calculations for 3D boids as well as for calculating geometry for realtime 3D trails) but adding the gotchas of godot threading to the gotchas of gdnative to the inherent complexity of Rust... Just no, not without reason.

[astrale-sharp]

Agreed