Godot: Improved AStar

[supagu]

Hi,

I've improved the usability of the AStar class to be able to handle delegate to calculate distances between nodes.
I found the stock implementation too limited to straight lines where my project is using a custom method to compute distance between nodes, I am actually using splines instead of straight lines, so my changes allow for this by adding a delegate which then calls "compute_cost" on the delegate, or "estimate_cost" for cost estimation.

I've also added support for exhaustive AStar searching, flags and bindings for nodes.

If you just diff the files against the stock astar you will see my changes. I would like to see them merged in if you deem the changes suitable.

astar2.zip

[akien-mga]

Thanks, but it would be much easier to review your patches if you made a pull request directly from a GitHub fork.

[ghost]

@supagu What's the use of bindings and flags exactly?

[supagu]

these get sent path to the callback function so they are up to the callback
function what they do.

in my case, i pass through a game object that represents my track or path,
which has a spline and then i query that class for the spline length
instead of using the built in distance function.

thanks for making that a push request!
let me know if that is clear or not.

ta,
Fabian

On 3 Mar 2017 9:39 AM, "Ferenc Arn" [e-mail] wrote:

@supagu https://github.com/supagu What's the use of bindings and flags
exactly?

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/godotengine/godot/issues/7823#issuecomment-283812364,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AKovUAJx4wZ5mp91_rI7q0uMeLer7dpyks5rh0wTgaJpZM4MC5EB
.

[ghost]

these get sent path to the callback function so they are up to the callback
function what they do.

I'm not sure such having application specific parameters is a good idea in the core. I think you can simply pass a single context object which will contain all implementation specific details rather than hard-coded "binds" and "flags".

[ghost]

BTW, I just created that PR such that others can see the diff, and I will eventually close it without doing any revisions to it myself.
It probably requires revision so if you're still interested in getting it merged, you should create a new PR.

[supagu]

I was just following the closest example i could think of which is binding
to signals.

I'm happy for that to be changed.

On 3 Mar 2017 11:07 AM, "Ferenc Arn" [e-mail] wrote:

these get sent path to the callback function so they are up to the callback
function what they do.

I'm not sure such having application specific parameters is a good idea in
the core. I think you can simply pass a single context object which will
contain all implementation specific details rather than hard-coded "binds"
and "flags".

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/godotengine/godot/issues/7823#issuecomment-283828922,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AKovUGzxwdQQfrUyKVwClNwVrTjKIDOuks5rh2DUgaJpZM4MC5EB
.

[ghost]

@supagu Could you maybe post a GDScript snippet to show how this auxiliary data is used? Since A* doesn't make any use of that, I'm not sure if it's necessary at all: only GDScript has, and only GDScript uses that data, right?

[supagu]

https://github.com/bit-shift-io/trains-and-things/blob/master/Script/AStarMgr.gd

in _init i set the delegate, so the astar calls:
estimate_cost and compute_cost.

you will see in compute_cost the use of getRouteWeight which will get the length of the spline + any dynamic weighting of the AStar

[bojidar-bg]

Well, can't we add the following to AStar instead:

virtual float _estimate_cost(Vector3 from, Vector3 to); // or (int from, int to)
virtual float _compute_cost(Vector3 from, Vector3 to); // or (int from, int to)

And then have GDScript users do this:

class MyAStar extends AStar:
  const PORTAL_TRAVERSE_COST = 1
  var portal_a; var portal_b
  func _estimate_cost(a, b):
    var portal_a_distance = a.distance_to(portal_a) + b.distance_to(portal_b)
    var portal_b_distance = a.distance_to(portal_b) + b.distance_to(portal_a)
    return min( a.distance_to(b), min(portal_a_distance, portal_b_distance))
  func _compute_cost(a, b):
    if (a == portal_a and b == portal_b) or (a == portal_b and b == portal_a):
      return PORTAL_TRAVERSE_COST
    else:
      return a.distance_to(b)

var astar
func _ready():
  astar = MyAStar.new()
  add_child(astar)
  astar.portal_a = Vector3(0, 0, 0)
  astar.portal_b = Vector3(100, 100, 0)
  astar.add_point(0, astar.portal_a)
  astar.add_point(1, astar.portal_b)
  astar.connect_points(0, 1)
  # Connect points, set portal, do everything as usual with "astar"

[supagu]

Vector is not sufficient. There needs to be some way for the user to map back to the node IDs so I can atleast keep my user data outside of the astar class. Passing vectors back to gdscript is useless.

[bojidar-bg]

Then, we would have

virtual float _estimate_cost(int from, int to);
virtual float _compute_cost(int from, int to);

[ghost]

I believe @bojidar-bg means working purely with IDs, which seems to be the cleanest way to me too. Since GDScript has the mapping from ID to objects, both compute_cost and estimate_cost callbacks can access any relevant data they need.

[ghost]

Also, I believe it is possible to remove delegate altogether, provide a default compute_cost and estimate_cost, and let user override these functions by extending the class as @bojidar-bg did?

[supagu]

Inheritance sounds better than a delegate if that is possible, that should be better performance wise as well for those who do not need a modified AStar impl.

[bojidar-bg]

.. that should be better performance wise as well ..

Not really, as it would still use Object.call under the hood, though we might do some has_method checking if needed.

@tagcup And yeah, you were totally able to decipher (and repost) what I said above. :wink:

[supagu]

Please refer to PR https://github.com/godotengine/godot/pull/8146 for further info