MatejSloboda
commented
3 years ago 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 changedWe 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
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 ;).