How to use AStar

Archive
1
:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By koder
:warning: Old Version Published before Godot 3 was released.

I can’t find documentation on how AStar is supposed to be used. API reference does give some hints, but there is much guesswork. Is there a tutorial somewhere?

I assume the workflow is to initialize an AStar, supply it with points with (add_point), add connections (connect_points) between the points and then query paths with get_id_path or get_point_path. My specific questions are:

  1. Can I use any integer point id, or should I use get_available_pint_id to generate it?
  2. Basic A* algorithm works on nodes and has nothing to do with 3d space. Methods accept Vector3 pos; is this a convenience method that can be ignored, or do I need actual 3d representation of node map?
  3. I first assumed that I should extend AStar and implement my own _compute_cost and _estimate_cost, but with return signature of (int,int)=>void I am not sure what these should do. Shouldn’t these return a float? If so:
  4. What’s the difference between these two?
  5. How do they interact with weight from add_point?
  6. Will they always be called on connected points?
  7. What should be valid return range?
  8. Which of functions are CPU expensive? Are there any caching/pre-computing going on? For example:
  9. If I ask for a path (1,7) and I get [1,2,3,4,5,6,7], does querying later for path (2,7) re-use computation, or is it up to me to cache it?
  10. Is creating new AStar cheap enough to be re-created on every AI decision?

Apologies if these topics were covered somewhere and TIA for any answer.

4
:bust_in_silhouette: Reply From: koder

So I dug into it’s source code to answer my own questions:

  1. Points are stored as Map<int, Point *>, so any non-repeating integer should do - but get_available_point_id just gives id of last point + 1, so either use your own numbering, or get_available_point_id, don’t mix them.
  2. Vectors are mostly for convenience and to compute default _compute_cost and _estimate_cost - they default to distance between these.
  3. Both _compute_cost and _estimate_cost default to distance between vectors and can be implemented in gdscript. They both should return a float value (presumably positive), docs on them returning void seem to be incorrect.
  4. _compute_cost is always called with neighboring points. _estimate_cost can be called on any two points.
  5. _compute_cost’s output is multiplied by weight. _estimate_cost is used as is.
  6. only _compute_cost
  7. There does not seem to be an assumption there. To be safe use positive floats.
  8. Brief code analysis reveals:
  9. No caching is performed - there is a comment in code suggesting possible future upgrade. Route should be cached in gdscript.
  10. clear runs in O(n), and adding points obviously too, so it’s way better to re-use. Also, adding a point with previously used ID replaces previous one.