Directions ignore input_is_destination

[goblinJoel]

This addon is great! It's definitely going to save me a lot of hassle (and maybe avoid performance issues) compared to replacing A* on my own to handle displaying and checking movement options for players and AI.

There is something weird though: recalculate()'s input_is_destination flag doesn't seem to affect directions. When I use get_direction_map() and then check the direction from a cell, it's the same either way. The same is true if I just poll the specific cell with get_direction_at_point(). get_shortest_path_from_point() also moves from the given point to the nearest origin regardless of flag value.

(Cost, however, is affected as expected for connections with different weights in each direction. "input_is_destination": true uses weights going from inspected points to origins, while false uses weights going from origins to inspected points.)

---

The documentation could also be improved. It currently reads:

The get_*** methods documentation was written with the assumption that "input_is_destination" argument was set to true (the default behavior) in recalculate.

In this case, paths point towards the origin and inspected points are assumed to be destinations.

If the "input_is_destination" argument was set to false, paths point towards the destination and inspected points are assumed to be origins.

This is confusing because it appears to say that true makes paths point toward the origins, even though the inspected points are destinations. (Normally, an origin is where you come from and a destination is where you point to.) It also sounds like setting it to false makes paths go from inspected points ("assumed to be origins") to the recalculation origins, which become the destinations -- the opposite of how cost calculation works now.

If I understand the intent correctly, matching current behavior with connection weights, it should say,

The get_*** methods documentation was written with the assumption that "input_is_destination" argument was set to true (the default behavior) in recalculate.

In this case, the origins you input to recalculate are assumed to be destinations, and paths point from the get methods' inspected points to the origins.

If the "input_is_destination" argument was set to false, paths point from the origins you input to recalculate, and the get methods' inspected points are assumed to be destinations.

This can be worked around, but it looks like a bug, so I thought I should report it.

[astrale-sharp]

Hi! thank you for your interest!

Quick question about your first point : "recalculate()'s input_is_destination flag doesn't seem to affect directions."
is the map on which you're doing the testing connected in both ways? (if you can go from A->B you can also go from B->A ?)

if so, i think that is why you get the same result when you change the input_is_destination flag and i think it is intended behavior! Maybe test it with a one way map (if you can go from A->B you CANT go from B->A )

Let me know!

About your second point : it's been a while since i have been looking at this codebase so im confused with both version 🤣
I'll think about it (or maybe another contributor with bigger brain cells will come around).

[goblinJoel]

Thanks for the response! I was testing all this by messing with the scene included with the addon from the Godot asset library. This is the one that shows a grid where you can swap terrain types and show the colorful cost map or the directional arrows. The arrows stay the same even if you switch recalculate to set input_is_destination=false, but it seems like they should reverse. I believe all the default tiles are bidirectional.

I added a few off the lower-right edge to experiment with connecting points one direction at a time so costs could be different each way, and input_is_destination did change the costs for those tiles, but it did not affect their directions. I don't think I've tried with single-direction connections only; even the tiles I connected one direction at a time, I still connected both directions.

Part of the confusion with the documentation is that it's not clear what "origin", "destination", "input", and "inspected points" mean. I took them to mean "the points you give to recalculate()", "the points that paths end at", "the points you give to recalculate()", and "the point(s) you give to other functions".

[astrale-sharp]

Hey!

if you're using the testscene, i assure you each point is connected bidirectionally to its neighbours ! ;)
(if you look in gdscript and verify where the points are being connected you'll see it i'm sure )

I myself am confused about the meaning of these words since the beginning but i dont really see how to change that right now, we'll see what we can do ;)

[goblinJoel]

To help illustrate the issue I see, I've turned my modified gridmap.gd into a gist. On line 97, you can set input_is_destination.

When true, the relevant output is:

recalculated with input_is_destination=True
testing points A: (23, 16) and B: (24, 16)
costs of point A: 9 and B: 10
direction map at point A: (22, 16) and B: (23, 16)
direction at A: (22, 16)
direction at B: (23, 16)
shortest path from A: [435, 416, 397, 378, 359, 340, 339, 338, 337]
shortest path from B: [439, 435, 416, 397, 378, 359, 340, 339, 338, 337]

When false, it is:

recalculated with input_is_destination=False
testing points A: (23, 16) and B: (24, 16)
costs of point A: 10 and B: 11
direction map at point A: (22, 16) and B: (23, 16)
direction at A: (22, 16)
direction at B: (23, 16)
shortest path from A: [435, 416, 397, 378, 359, 340, 339, 338, 337]
shortest path from B: [439, 435, 416, 397, 378, 359, 340, 339, 338, 337]

The costs are higher with false because I connected 435 to 439 (point A) with cost 2.0, while the reverse is only 1.0: when moving from origin to inspected point, it costs 1 more than when moving from inspected point to origin.

However, the directions and paths always point from inspected points to origins, regardless of input_is_destination. This is the part that seems like it's a bug, unless that flag is only supposed to apply to costs.

These results can be visualized by clicking "cost map" and "direction map" while running the scene with the modified script.

Workaround
In my game, a tactical RPG, I'm using this addon to display all of the spaces within a unit's movement range and determine paths and costs when they mouseover or select a space to go to. To accomplish this, I set input_is_destination=false and recalculate from the unit's point so that costs are correct. For getting paths, this is not enough: I must also reverse the path I get from the Dijkstra map, then add the destination to the end of it. (Currently, the map always starts from the destination instead of the origin, and it leaves out the starting point of the path, even though that's where I'm trying to end up.)

[astrale-sharp]

sorry for the infinitely long delay, i think the name is just confusing, it reverses the cost but it does not make the the origin a "destination" the calculus always starts from your origin's points, that's what djikstra does, if you want info on other point you have to calculate again, changing the origin.
We will change the name to reverse to make it less confusing !

[goblinJoel]

Renaming it and updating documentation seems like a good route.

Reading over this thread again, I was under the impression that the directions the path points in (and the order of points on the path) would be reversed, when as you point out, it just changes cost calculation. If it's clear that it doesn't change the result of methods like get_direction_at_point() or reverse the order of get_shortest_path_from_point(), I think that would solve the issue.

[astrale-sharp]

Thanks for the input! I'll go with renaming it soon!

…

________________________________ From: Joel ***@***.***> Sent: Wednesday, December 7, 2022 11:47:52 PM To: MatejSloboda/Dijkstra_map_for_Godot ***@***.***> Cc: astrale-sharp ***@***.***>; Comment ***@***.***> Subject: Re: [MatejSloboda/Dijkstra_map_for_Godot] Directions ignore input_is_destination (Issue #110) Renaming it and updating documentation seems like a good route. Reading over this thread again, I was under the impression that the directions the path points in (and the order of points on the path) would be reversed, when as you point out, it just changes cost calculation. If it's clear that it doesn't change the result of methods like get_direction_at_point() or reverse the order of get_shortest_path_from_point(), I think that would solve the issue. — Reply to this email directly, view it on GitHub<#110 (comment)>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/AMZTDKTNLXHQMH64ETUYADDWMEHZRANCNFSM5WHAGNHQ>. You are receiving this because you commented.Message ID: ***@***.***>