+6 votes

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:

    1. What's the difference between these two?
    2. How do they interact with weight from add_point?
    3. Will they always be called on connected points?
    4. What should be valid return range?
  4. Which of functions are CPU expensive? Are there any caching/pre-computing going on? For example:

    1. 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?
    2. 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.

asked Sep 29, 2017 in Engine by koder (32 points)

1 Answer

+5 votes

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.

    1. _compute_cost is always called with neighboring points. _estimate_cost can be called on any two points.
    2. _compute_cost's output is multiplied by weight. _estimate_cost is used as is.
    3. only _compute_cost
    4. There does not seem to be an assumption there. To be safe use positive floats.
  4. Brief code analysis reveals:

    1. No caching is performed - there is a comment in code suggesting possible future upgrade. Route should be cached in gdscript.
    2. 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.
answered Sep 29, 2017 by koder (32 points)
Welcome to Godot Engine Q&A, where you can ask questions and receive answers from other members of the community.

Please make sure to read How to use this Q&A? before posting your first questions.