Feature: Custom Origin Point Size

[SimonasLetukas]

Hello,

This is an amazing project which really makes it quick to develop any tactical strategy game, thank you guys so much for the effort!

I have a suggestion for a relatively small-scale feature which I wish I'd be able to commit myself, but I have no experience with developing in Rust environment. Basically the feature is about setting the size of the origin point and checking it when the recalculation process is running, based on this question.

From what I can see, the additional conditions could be added here, line 266/267: dijkstra-map/src/lib.rs. As for API, I think it should work fine as an additional parameter in "optional_params" dictionary in "recalculate" method. Something like:

• "origin_size"->int: Specifies size of the origin point. For example, setting this as 2 would expect an origin point which should find path as a 2x2 entity. Default value: 1

Please tell me if this is something you'd have plans implementing or should I try building a work-around?

Thank you so much for your time!

[arnaudgolfouse]

Hi, thank you for using our project ! 😄

If I understand correctly, I think it should be already possible to solve this in user code :

using the same conventions as your link :

. . . . o . . .
. a a . o . . .
. a a . o . g .
. . . . . . . .
. . . . o . . .
. . . . . . . .
. . . . . . . .
. . . . o . . .

We can apply the 'kernel' technique described in one of the answers :

var dijkstra_map
var pos_to_id = {}
# 2x2 kernel
var kernel = [Vector2(0, 0), Vector2.LEFT, Vector2.UP, Vector2.LEFT + Vector2.UP]
var bounds = Rect2(0, 0, 8, 8)

func _ready():
    dijkstra_map = DijkstraMap.new()
    pos_to_id = dijkstra_map.add_square_grid(bounds)
    add_obstacle(Vector2(4, 0))
    add_obstacle(Vector2(4, 1))
    add_obstacle(Vector2(4, 2))
    add_obstacle(Vector2(4, 4))
    add_obstacle(Vector2(4, 7))
    
    var target = []
    for kernel_point in kernel:
        var id = pos_to_id.get(kernel_point + Vector2(6, 2))
        if id != null:
            target.append(id)
    dijkstra_map.recalculate(target)

func add_obstacle(obstable_pos: Vector2):
    for kernel_point in kernel:
        dijkstra_map.remove_point(pos_to_id.get(obstable_pos + kernel_point, -1))

Are you suggesting to add this functionality to the library itself ? I am not sure how it will work for non-square maps then...

[SimonasLetukas]

Hey, thanks for the reply!

I haven't considered the non-square maps, implementing this for hexes would be a bit weird, as it is not quite clear how the "size 2" blob would look in hexes.

Yes, the kernel approach would work if I searched for a concrete target. What about when I search for available paths? Could I just have a separate "diluted" dijkstra_map in which all obstacles have these kernels added and when recalculating I could use the top-left point of the 2x2 unit? In theory, sounds like it could work, so I'll definitely try it. Could be a bit too fiddly though.

Anyway, thanks a lot for your time :)

[MatejSloboda]

This Dijkstra map library is for navigating general weighted graphs (ie. not just grids). The algorithm is completely oblivious to actual geometry of the level. The grid-adding methods are there just for convenience (they literally just add points and connections in bulk), because they are such a common use case.

As arnaudgolfouse pointed out, the feature you request is intended to be implemented in user's code on the godot side. You will simply have to create separate dijkstramap objects, one for each "unit size", and manually keep them in sync.

[astrale-sharp]

That raises interesting questions though...
how would we go about implementing this? what if the kernel is L shaped indeed and we have to get account of rotations? currently our library cant support that at all, does that mean it shouldn't?
maybe its outside the scope of this library (if someone does it, it could go into a "helper node" containing misc utilities like this), even if it is, theses questions entertain me.

[MatejSloboda]

how would we go about implementing this?

We would need to add a separate storage for the original full graph and a separate storage for a Option<"filtered" graph>. You could apply "filtering" to the original graph to remove unwanted points (such as the kernel algorithm above). The recalculate method would then work on filtered graph if Some, or original if filtered graph is None. This is the easy part.
We would also need to store additional information about the graph, to know how to "filter" it. Such as, point positions; which parts of graph are a grid; what kind of grid; etc. Currently, the only "extra" information we store is the "terrain type" of points for the terrain weighting feature.
However, this would be incremental change that'd only bite us in the ass in the long run.

Alternatively, this could be implemented using terrain. Tiles, that are "blocked" for large entities by an nearby obstacle, can have a bitflag in their terrain indicating how far the obstacle is. The bitflag would be ANDed away for smaller entities (resulting in normal terrain evaluation), but would be taken into account for larger entities (resulting in default infinite cost for these tiles).

What I plan to do for v2.0 (in unspecified future) is to separate graph from map calculation and storage. You can then have one central graph and spawn Dijktsramaps from it, that remain synced. Each Dijkstramap will have its own storage for costmap, directionmap and the last used parameters for recalculation. When you modify the central graph, you could just call apply_changes() and it will update all the Dijkstramaps it spawned, remotely (and possibly multithreaded).
This "filtering" feature could then be easily implemented by storing the "filtered" versions in respective Dijkstramaps (which we would probably do anyway to avoid the circular reference between central graph and Dijkstramaps).

[SimonasLetukas]

Interesting discussion, thanks guys!

maybe its outside the scope of this library (if someone does it, it could go into a "helper node" containing misc utilities like this), even if it is, theses questions entertain me.

I'm planning on implementing this in my own project so when it's done I could definitely try and extract the it and post here again to discuss best approach to add this functionality to the "helper node".

[MatejSloboda]

There's another potential issue. For "multi-tile" entities, it is not entirely clear which terrain should they be using. Imagine a 2x2 entity walking down a 2-wide corridor, where half the corridor is swampy and other half is paved. Should the entity get movement penalty from swampy terrain or boost from paved terrain? The answer is clearly game-specific.

Maybe instead of "helper node" we should include "wrapper nodes" written in GDScript for some of the most common game scenarios.

[astrale-sharp]

There's another potential issue. For "multi-tile" entities, it is not entirely clear which terrain should they be using. Imagine a 2x2 entity walking down a 2-wide corridor, where half the corridor is swampy and other half is paved. Should the entity get movement penalty from swampy terrain or boost from paved terrain? The answer is clearly game-specific.

Maybe instead of "helper node" we should include "wrapper nodes" written in GDScript for some of the most common game scenarios.

Ah yes, I see what you mean... This is to be decided by user code ( i would probably take the mean but someone could choose to do otherwise : the most advantageous for instance)