Godot 3.6 compatibility?

[goblinJoel]

I've updated to the recently-released Godot 3.6 and now get these warnings in the editor (constantly) and in the debugger while running the game (on start):

W 0:00:01.155   <unset>: This godot-rust version is only compatible with Godot >= 3.5.1 and < 3.6; detected version 3.6-stable (official).
GDNative mismatches may lead to subtle bugs, undefined behavior or crashes at runtime.
Apply the 'custom-godot' feature if you want to use current godot-rust with another Godot engine version.
  <C++ Source>  dijkstra-map-gd\src\lib.rs:1204 @ <unset>()

So far, the game hasn't crashed when using this plugin to pathfind.
If I understand correctly, this is because godot-rust's latest release, 0.11.3, which I custom-compiled this plugin against in order to fix #123, is marked as not supporting 3.6. Their repo has a note from a few hours before the 3.6 release saying they are no longer actively maintaining Godot Rust for 3.x, so I'm not optimistic about getting a release of their 90 unreleased commits or 3.6 compatibility any time soon.

What is the best approach to using this plugin on 3.6? Is there any reason to think changes from 3.5.3 to 3.6 would be incompatible with this plugin? (I assume it doesn't really call engine APIs much.) I don't see any other Dijkstra map plugins, and since even this one is fairly slow at calculating paths on larger maps (ex: 80x80), I'm concerned reimplementing myself in GDScript (I don't know much C++ or Rust) would be challenging in terms of performance.

---

My attempts to resolve. Skip to the end if you just want to see how I made the warning go away, but I know basically nothing about Rust and could have done something unstable, so my question above is still open:

When I compiled it, I think I used custom-godot already, unless I need to change something else. My Cargo.toml line was:
gdnative = { git = "https://github.com/godot-rust/godot-rust.git", tag = "0.11.3", features = ["custom-godot"] }
I have tried updating my GODOT_BIN env var to the 3.6 exe and rebuilding, but it didn't change the dll. I tried deleting the target folder and rebuilding, but the resulting dll is the same number of bytes as the old one and doesn't make the warnings stop when used in my project.

I tried removing the 0.11.3 tag so that it uses master, which appears to suppress the warning when using custom-godot, but then building fails to find a non-conflicting version for quote. (It said it was locked to another version.) I took an educated guess and saw Cargo.lock was in .gitignore, so I deleted it and tried again.

Then I got errors because the deprecation warnings for Int32Array and Float32Array, "use of deprecated type alias gdnative::prelude::Int32Array: Specialized pool array aliases will be removed in a future godot-rust version. Use PoolArray instead," are now errors.

I noticed this quote from the issue about the warnings occurring even with custom-godot, godot-rust/gdnative#1023 :

In effect, it only silences the warning message if there is a custom-godot feature in the user crate and it's enabled.

It's a shame that fix was done just 3 days after 0.11.3, but I took a guess that this meant I could add a dummy feature to the Dijkstra map crate... and it worked!

[goblinJoel]

For reference, this is what my hack looks like to make this work (so far?) on Godot 3.6 without version mismatch warnings. I don't know if there are any bugs lurking due to the mismatch, so I'm still interested in hearing if this was a good way to handle it.

--- a/dijkstra-map-gd/Cargo.toml
+++ b/dijkstra-map-gd/Cargo.toml
@@ -4,12 +4,16 @@ version = "0.1.0"
 authors = ["Astrale", "Matej Sloboda"]
 edition = "2018"

+[features]
+default = ["custom-godot"]
+custom-godot = []
+
 [lib]
 crate-type = ["cdylib"]

 [dependencies]
 fnv = "1.0.7"
-gdnative = "0.11.0"
+gdnative = { git = "https://github.com/godot-rust/godot-rust.git", tag = "0.11.3", features = ["custom-godot"] }
 dijkstra_map = { path = "../dijkstra-map" }

I have this on a branch and can push it if desired. (I don't know if this repo lets me do that or if I need to fork it first?)

In case this is the right answer, and anyone else comes by who wants to try it (Windows only), here's the dll that goes in addons\dijkstra-map\Dijkstra_map_library\bin\windows: dijkstra_map_gd.zip

[astrale-sharp]

Thanks for your comments and experiments 😄

your educated guesses were quite good

Our implementation should be pretty performant, if it struggles on map as slow as 80x80 there could be a few reasons, namely we probably convert from Vec to PoolArray which might be costly

It's a bit of a pain using a tool and realizing it doesn't support latest versions of the engine, I can relate, unfortunately I'm not willing to invest the time to make the situation better

Some would stay on the latest supported godot version, some would go godot 4.0, some would ditch the plugin or use your hack, all answers seem valid to me, i moved to godot 4.X for all my current projects and it's quite good so far, better than 3.X anyway even though some feature disappeared here and there.

[astrale-sharp]

If you have any other question feel free to reopen the issue!

[goblinJoel]

@astrale-sharp Thanks for your response! I do have some questions, actually.

I haven't upgraded to Godot 4 because dependencies like Dijkstra map and Dialogic don't have releases for 4 yet. (And at this point, the project is far enough along I'd hesitate to even if they did!) So my main question, not knowing how rust or gdnative work, is:

Is there any reason to think that using this addon for Godot 3.6 with a godot-rust version made for 3.5 would have a problem?

Side question: I saw in other issue threads that maybe there was a version of this Dijkstra map addon that works with Godot 4, but I also saw comments saying a Godot 4 version wasn't releasable yet. What is going on there?

As for performance, it looks like my notes (with measurements using the profiler, running on an older desktop processor) were that an 80x80 square grid map with 8 connections (4 edges, 4 corners) per space took 275ms on average to set up. Some of that time is in GDScript as it figures out what points to connect with what weights. Fortunately, setup was something that was natural to do once and save instead of recreate every frame.

On the 80x80 test, it took 4.8ms on average in recalculate() whenever I needed to run that. That is more performance-sensitive since it has to happen during play rather than when loading things, and it has to fit along with everything else that might be happening on any given frame in under 17ms. But it may be fast enough. However, I should try profiling it again on my current version of my pathfinding code, since I've changed some things since then and have a new processor now. (Although some players may have slower machines.)

Performance in all the parts I measured seems to scale linearly with the number of points on the map.

[astrale-sharp]

Is there any reason to think that using this addon for Godot 3.6 with a godot-rust version made for 3.5 would have a problem?

I would say probably, there is subtle interop between the C++ and Rust and if any details of how things are handled, defined changed in the C++, you have yourself undefined behavior, do try though maybe nothing that matter to your project changed

Side question: I saw in other issue threads that maybe there was a version of this Dijkstra map addon that works with Godot 4, but I also saw comments saying a Godot 4 version wasn't releasable yet. What is going on there?

I care about optional arguments in our gdscript API which are not yet possible to express in GDext which is the only blocker, i have hacked together a version where the api has been updated to gdext and the optional parts are not optional, i don't want to release it but it's usable

Perf

Do you have a reason to think this is slow? another lib to compare it to? Have you been using the provided bin or recompiling?

[arnaudgolfouse]

Hm indeed, we seem to perform about 2x slower than petgraph (based on a quick test on my machine). That being said, this could be explained in part by the fact that we compute a bit more information during the algorithm.

Here is the code I used in dijkstra_map:

fn perf() {
    let now = Instant::now();
    let size = 80;
    let mut map = DijkstraMap::new();
    let points = map.add_square_grid(size, size, None, TerrainType::DefaultTerrain, None, None);
    for _ in 0..1000 {
        map.recalculate(
            &[points[&Vector2D::zero()]],
            None,
            None,
            Vec::new(),
            Default::default(),
            Default::default(),
        );
    }
    println!("{}", now.elapsed().as_millis());
}

And here is the one for petgraph:

use std::{collections::HashMap, time::Instant};
use petgraph::{
    graph::{DefaultIx, NodeIndex},
    Undirected,
};

type Graph = petgraph::Graph<i32, i32, Undirected, DefaultIx>;

#[inline(never)]
fn fill_graph(graph: &mut Graph, n: i32) -> Vec<NodeIndex> {
    let mut node_idx = Vec::new();
    for i in 0..n * n {
        node_idx.push(graph.add_node(i));
    }
    for i in 0..n * n {
        for j in 0..4 {
            if i + j < n * n {
                graph.add_edge(node_idx[i as usize], node_idx[j as usize], 0);
            }
        }
    }
    node_idx
}

#[inline(never)]
fn fill_terrains(terrains: &mut HashMap<i32, f32>) {
    terrains.insert(0, 1.0);
}

fn main() {
    let mut graph = Graph::default();
    let mut terrains = HashMap::new();

    let node_idx = fill_graph(&mut graph, 80);
    fill_terrains(&mut terrains);

    let now = Instant::now();
    for _ in 0..1000 {
        let _ = petgraph::algo::dijkstra(&graph, node_idx[0], None, |e| terrains[e.weight()]);
    }
    println!("{}", now.elapsed().as_millis());
}

Change the 80 to other values as needed.

[arnaudgolfouse]

Wait nevermind I was tired, the graphs are not the same
I’ll try again tomorrow 😅

[goblinJoel]

Thanks for responding.

Sounds like I should keep an eye on godot-rust and hope they release a 3.6 update. So far no problems though. I'm guessing this addon doesn't interact much with Godot other than to let GDScript call the Dijkstra map functions.

For performance, I'm talking in purely utilitarian terms. I don't know if it's faster or slower than alternatives. (I actually couldn't find any alternatives for Godot.) I've been avoiding the complication of making my project multithreaded, so that means that to keep consistent frame rates and physics tick rates, the pathfind call has to complete quickly enough to fit with all of the other idle and physics processing the game does that frame. So 5ms is about 1/3 of the time available at 60fps, which is probably fine in my context.

The worst I'm seeing is around 12ms occasionally when using recalculate() followed by get_all_points_with_cost_between() with a higher max cost equivalent to about 20 points/hops, although I might be able to find a way to use get_shortest_path_from_point() instead for that particular check. (Context is clicking on a space to walk there outside of battle, where your movement range isn't limited by your per-turn movement speed, so I used a high cost limit when I check that the space is one of the reachable ones.)

[arnaudgolfouse]

Ok, now with the right test for petgraph:

use petgraph::{
    graph::{DefaultIx, NodeIndex},
    Undirected,
};
use std::{collections::HashMap, time::Instant};

type Graph = petgraph::Graph<i32, i32, Undirected, DefaultIx>;

#[inline(never)]
fn fill_graph(graph: &mut Graph, n: i32) -> Vec<NodeIndex> {
    let mut node_idx = Vec::new();
    for i in 0..n * n {
        node_idx.push(graph.add_node(i));
    }
    for i in 0..n * n {
        if i % n != 0 {
            graph.add_edge(node_idx[i as usize], node_idx[i as usize - 1], 0);
        }
        if i % n != n - 1 {
            graph.add_edge(node_idx[i as usize], node_idx[i as usize + 1], 0);
        }
        for j in [i + n, i - n] {
            if 0 <= j && j < n * n {
                graph.add_edge(node_idx[i as usize], node_idx[j as usize], 0);
            }
        }
    }
    node_idx
}

#[inline(never)]
fn fill_terrains(terrains: &mut HashMap<i32, f32>) {
    terrains.insert(0, 1.0);
}

const SIZE: i32 = 80;

fn main() {
    let mut graph = Graph::default();
    let mut terrains = HashMap::new();

    let node_idx = fill_graph(&mut graph, SIZE);
    fill_terrains(&mut terrains);

    let now = Instant::now();
    for _ in 0..1000 {
        let _ = petgraph::algo::dijkstra(&graph, node_idx[0], None, |e| terrains[e.weight()]);
    }
    println!("{}", now.elapsed().as_millis());
}

We are about ~40% slower than this (with varying graph sizes), so not too bad I'd say 😅

The worst I'm seeing is around 12ms occasionally when using recalculate() followed by get_all_points_with_cost_between() with a higher max cost equivalent to about 20 points/hops, although I might be able to find a way to use get_shortest_path_from_point() instead for that particular check. (Context is clicking on a space to walk there outside of battle, where your movement range isn't limited by your per-turn movement speed, so I used a high cost limit when I check that the space is one of the reachable ones.)

get_all_points_with_cost_between is supposed to be quite fast (especially with respect to recalculate), although maybe the conversion to Godot is costly... do you have an idea of the time taken by recalculate vs get_all_points_with_cost_between in your case?

[goblinJoel]

I realized I never answered whether I was using the provided bin or recompiling. I have been recompiling to get it to work on Godot 3.5.3 and then on Godot 3.6.

Trying some manual time logging to answer @arnaudgolfouse question and satisfy my curiosity. (It's too bad the Godot profiler doesn't tally uses of functions across multiple frames or let me see the timing of calls to the Dijkstra map addon.) Samples are the number of times the function was run in the test gameplay. Times are in microseconds.

This one was accidentally 160x160 (with 8-direction, sometimes asymmetric connections) because I scaled the level by the wrong factor:

function	average	min	max	samples
recalculate with no max cost	12,406.19	10,783	23,176	395
get_shortest_path_from_point	8.77	4	212	394
recalculate with max cost 100.1	704.11	631	927	9
get_all_points_with_cost_between 0.0 and 100.1	11.00	8	15	9
recalculate with smaller max costs (3.1-15.1)	46.28	16	65	11
get_all_points_with_cost_between 0.0 and smaller max costs (3.1-15.1)	5.20	3	7	10

I tried again with 80x80 but didn't wrangle all the data to spreadsheets to make a table.

• Recalculates with no max cost were pretty consistently around 1/4 of that, which makes sense if it's O(n).
• Getting shortest path from point was still higher the first time (12 micros) than later times (mostly 4-8 micros, with occasional hiccups up to 18 micros), usually taking around 2/3 the time as on the larger map.
• Recalculating with max cost 100.1 were 240-397 micros, so roughly 1/2 the larger map.
• Getting all points with cost between 0 and 100.1 took 6-8 micros, around 2/3 the larger map's time.
• Recalculating with smaller max costs took 14-44 micros, slightly faster than the larger map.
• Getting points with smaller max costs took 2-6, slightly faster than the larger map.

So pretty much all the time involved with the way I'm using it is creating the maps in the first place (when loading the level) and recalculating them when before querying. (Units change position, the unit that's pathfinding could change how far they can move or how high they can jump, the unit I'm pathfinding for changes... it's safest to just update the map and recalculate using current info every time I need to pathfind.) I was wrong about there being a meaningful difference between get_shortest_path_from_point() and get_all_points_with_cost_between(). That's good to know!