Struct AStar

A* (A star) is a computer algorithm that is widely 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 three-dimensional space and Euclidean distances by default. You must add points manually with addPoint and create segments manually with connectPoints. Then you can test if there is a path between two points with the arePointsConnected function, get a path containing indices by getIdPath, or one containing actual coordinates with getPointPath. It is also possible to use non-Euclidean distances. To do so, create a class that extends AStar and override methods computeCost and estimateCost. Both take two indices and return a length, as is shown in the following example.

class MyAStar: extends AStar

func compute_cost(u, v): return abs(u - v)

func estimate_cost(u, v): return min(0, abs(u - v) - 1)

estimateCost 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 estimateCost return the same value as computeCost to provide the algorithm with the most accurate information.

Methods