Review Note

Description

A* (A star) is a computer algorithm used in pathfinding and graph traversal, the process of plotting short paths among vertices (points), passing through a given set of edges (segments). It enjoys widespread use due to its performance and accuracy. Godot's A* implementation uses points in 3D space and Euclidean distances by default.

You must add points manually with add_point and create segments manually with connect_points . Once done, you can test if there is a path between two points with the are_points_connected function, get a path containing indices by get_id_path , or one containing actual coordinates with get_point_path .

It is also possible to use non-Euclidean distances. To do so, create a class that extends AStar3D and override methods _compute_cost and _estimate_cost . Both take two indices and return a length, as is shown in the following example.

class MyAStar:    
extends AStar3D    
func _compute_cost(u, v):        return 
abs(u - v)    
func _estimate_cost(u, v):        return 
min(0, 
abs(u - v) - 1)

public 
partial 
class MyAStar : AStar3D{    
public 
override float _ComputeCost(long fromId, long toId)    {        
return Mathf.Abs((int)(fromId - toId));    }    
public 
override float _EstimateCost(long fromId, long toId)    {        
return Mathf.Min(0, Mathf.Abs((int)(fromId - toId)) - 1);    }}

_estimate_cost should return a lower bound of the distance, i.e. _estimate_cost(u, v) <= _compute_cost(u, v) . This serves as a hint to the algorithm because the custom _compute_cost might be computation-heavy. If this is not the case, make _estimate_cost return the same value as _compute_cost to provide the algorithm with the most accurate information.

If the default _estimate_cost and _compute_cost methods are used, or if the supplied _estimate_cost method returns a lower bound of the cost, then the paths returned by A* will be the lowest-cost paths. Here, the cost of a path equals the sum of the _compute_cost results of all segments in the path multiplied by the weight_scale s of the endpoints of the respective segments. If the default methods are used and the weight_scale s of all points are set to 1.0 , then this equals the sum of Euclidean distances of all segments in the path.