"remote" dijkstra map

[astrale-sharp]

Hey @MatejSloboda , you mentioned a few time that when you got time you'd like to implement a kind of "remote" dijkstra-map. I've never quite understood what you meant by that but i happen to have some time, so if you happen to provide some example from the gdscript size for instance, I'd like to try to implement it ;).

[MatejSloboda]

I've thought about a bit more afterwards and came to a conclusion, that it'd be a real bitch to implement. Here's a description of how I imagined it would work:

We would have a central DijkstraMapGraph object (probably a child of Reference class, as it is now). It only contains the graph (ie. it holds the points, connections, terrain, etc.) as well as all the methods for modifying the graph ( add_point, connect_points, add_*_grid etc.).
It also has a spawn_new_dijkstramap method which spawns DijkstraMap object. This object doesn't contain the graph (it merely has a reference to the DijkstraMapGraph object that spawned it). It does contain the direction_map and cost_map along with all the methods that access them. It also has the recalculate method.

You could have multiple DijkstraMap objects, that can be recalculated independently, with their own unique parameters. However, they are calculated based on the same shared DijkstraMapGraph.

The way it would work in GDScript is something like this:
In the main map node in the project you'd have the graph. This is the central spot where you can modify it.

#main map node
var dijkstramapgraph

func _ready():
    dijkstramapgraph = DijkstraMapGraph.new()
    #points and connections are added here

func get_dijkstra_map() -> DijkstraMap:
     return dijkstramapgraph.spawn_new_dijkstramap()

In places where you need the dijkstramap (for example in script of some unit)

#some unit elsewhere in the project
var dijkstra_map

func _ready():
    dijkstra_map = get_node("/root/../main_map_node").get_dijkstra_map()
    #set parameters here
    dijkstra_map.recalculate()

func _process(dt):
    if dijkstra_map.is_out_of_sync?():
         dijkstra_map.recalculate()

Now, if the DijkstraMapGraph in the main map node gets modified, then the next time the unit tries to recalculate() its DijkstraMap, it will use the the new modified graph instead of the old one (regardless of where in the project it might be).

The DijkstraMapGraph would also have a generational index, that increments every time the graph gets modified. It gets copied to DijkstraMap every time it recalculates. That way, it is possible for DijkstraMap to check, whether it is "out of sync" and needs new recalculation.

There are a couple of other things we might want to change. The optional parameters are rather inconvenient. We should make them fields of the DijkstraMap:

#old
dijkstramap.recalculate(target_point_id, {"terrain_weights": speed_modifiers, "input_is_destination": true})

#new
dijkstramap.set_target(target_point_id)
dijkstramap.set_terrain_weights( speed modifiers )
dijkstramap.target_is_destination( true )
dijkstramap.recalculate()

... #later in the code

dijkstramap.set_target(new_target_point_id)
dijkstramap.recalculate() #uses the same "terrain_weights" and "target_is_destination" as before, because they persist, unless changed

We also might want to add auto_sync field. When set to true, the DijkstraMap recalculates every time it is "out of sync" and you try to get results from it. That way you don't have to write this, every time you wish to get up-to-date result:

if dijkstra_map.is_out_of_sync?(): #if auto_sync is enabled, this is done automatically when get_cost_map() is called.
         dijkstra_map.recalculate()
var cost_map = dijkstra_map.get_cost_map()

We will also need to add meta_data for each point. It is no longer viable for the user to hold position_to_id and id_to_position dictionaries in a sensible place, because both the main map and the units (in the example above) need to have up to date copy of it. I'm not 100% sure how to handle this.
My gut feeling is that we should add the two dictionaries into the DijkstraMapGraph and provide "read only" access to them from the DijkstraMap. They would be HashMap<PointID , gdnative::prelude::Variant> and vice versa, to provide some versatility. The user might use Vector2 or Vector3 (or maybe even something completely custom) to identify the points (that's why Variant).

The reason I've said this will be a bitch to implement is because every DijkstraMap needs to hold a reference to the DijkstraMapGraph. We would have to make sure the reference is alive. We presumably would have to do it through Godot's references, because who the hell knowns how Godot would respond to Arc<RefCell<DijkstraMapGraph>>.

I have originally considered that DijkstraMapGraph should have some sort of update() function, to instantly recalculate all the DijkstraMaps that spawned from it. Maybe even queue_update() to perform the recalculation in idle frame, maybe multithreaded. But that would require circular references (both the graph and the map would need reference to each other) and the race conditions it would create look like Tour de France. The generational index (and the auto_sync functionality) is a more sensible alternative.

[astrale-sharp]

I'm starting to understand a little bit what you mean, there is at least two problems here :
I agree that the flags for recalculate aren't very nice to write here's what I propose :
having this sort of rust code:

struct RecalculateOptions {
        origins: &[PointID],
        read: Option<Read>,
        max_cost: Option<Cost>,
        initial_costs: Vec<Cost>,
        terrain_weights: FnvHashMap<TerrainType, Weight>,
        termination_points: FnvHashSet<PointID>,
}

pub fn recalculate(
        &mut self,
        options : &RecalculateOptions
    )

accessed in this manner via gdscript (by exporting the RecalculateOptions structure as well, via the interface (if think its best) or a second interface also exported (maybe a lot just for a little struct):

var map = DijkstraMap.new()
#setup of map
...
#map is setup
var options = map.get_default_options()
options.max_cost = 5.0
map.recalculate(options)

would already solve the problem of the interface

[MatejSloboda]

I don't think exporting it to godot is useful. We would still need to store the last RecalculateOptions in the DijkstraMap, to allow the "auto sync" functionality, I've mentioned. Also the user would have to store both the DijkstraMap and the RecalculateOptions on Godot's side if they wanted to easily reuse the same options.
It would be simpler if RecalculateOptions struct was a field in the DijkstraMap object, and we would expose setters and getters for the fields of RecalculateOptions on the DijkstraMap itself.
We would have something like this:

struct RecalculateOptions {
        origins: &[PointID],
        read: Option<Read>,
        max_cost: Option<Cost>,
        initial_costs: Vec<Cost>,
        terrain_weights: FnvHashMap<TerrainType, Weight>,
        termination_points: FnvHashSet<PointID>,
}

struct DijkstraMap {
       graph: Ref<DijkstraMapGraph , Shared>,
       cost_map: FnvHashSet<PointID,Cost>,
       direction_map: FnvHashSet<PointID,PointID>,
       parameters:  RecalculateOptions,
}

impl DijkstraMap {

pub fn set_terrain_weights(&mut self, terrain_weights: FnvHashMap<TerrainType, Weight>)
// etc. 
}

[astrale-sharp]

Okay I'm going to start working on this for funsies

let dmap = .... // your initialized DijkstraMap
let dmap1 = dmap.remote()
dmap1.disable_points(...)

//perform a search and get different results

// modify dmap

// perform same search on dmap1 and see that the result changed

Objectives :

• don't clone everything (interior mutability will probably be required), maybe CoW can play a nice role for disabling points but I'm not sure how yet
• Implemented nicely without duplication of code (DijkstraMap::remote() returns something that should act like a DijkstraMap, not reimplementing the same methods with additional logic)
• Change on an original DijkstraMap are propagated to it's remotes, change to a remote are not propagated to the DijkstraMap of origin
• Calculations that can be shared are shared?