Up to date

This page is up to date for Godot `4.2`. If you still find outdated information, please open an issue.

# AStar3D¶

Inherits: RefCounted < Object

An implementation of A* for finding the shortest path between two vertices on a connected graph in 3D space.

## 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)
```

_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.

## Methods¶

 float _compute_cost ( int from_id, int to_id ) virtual const float _estimate_cost ( int from_id, int to_id ) virtual const void add_point ( int id, Vector3 position, float weight_scale=1.0 ) bool are_points_connected ( int id, int to_id, bool bidirectional=true ) const void clear ( ) void connect_points ( int id, int to_id, bool bidirectional=true ) void disconnect_points ( int id, int to_id, bool bidirectional=true ) int get_available_point_id ( ) const int get_closest_point ( Vector3 to_position, bool include_disabled=false ) const Vector3 get_closest_position_in_segment ( Vector3 to_position ) const PackedInt64Array get_id_path ( int from_id, int to_id ) int get_point_capacity ( ) const PackedInt64Array int get_point_count ( ) const PackedInt64Array PackedVector3Array get_point_path ( int from_id, int to_id ) Vector3 get_point_position ( int id ) const float get_point_weight_scale ( int id ) const bool has_point ( int id ) const bool is_point_disabled ( int id ) const void remove_point ( int id ) void reserve_space ( int num_nodes ) void set_point_disabled ( int id, bool disabled=true ) void set_point_position ( int id, Vector3 position ) void set_point_weight_scale ( int id, float weight_scale )

## Method Descriptions¶

float _compute_cost ( int from_id, int to_id ) virtual const

Called when computing the cost between two connected points.

Note that this function is hidden in the default AStar3D class.

float _estimate_cost ( int from_id, int to_id ) virtual const

Called when estimating the cost between a point and the path's ending point.

Note that this function is hidden in the default AStar3D class.

void add_point ( int id, Vector3 position, float weight_scale=1.0 )

Adds a new point at the given position with the given identifier. The `id` must be 0 or larger, and the `weight_scale` must be 0.0 or greater.

The `weight_scale` is multiplied by the result of _compute_cost when determining the overall cost of traveling across a segment from a neighboring point to this point. Thus, all else being equal, the algorithm prefers points with lower `weight_scale`s to form a path.

```var astar = AStar3D.new()
astar.add_point(1, Vector3(1, 0, 0), 4) # Adds the point (1, 0, 0) with weight_scale 4 and id 1
```

If there already exists a point for the given `id`, its position and weight scale are updated to the given values.

bool are_points_connected ( int id, int to_id, bool bidirectional=true ) const

Returns whether the two given points are directly connected by a segment. If `bidirectional` is `false`, returns whether movement from `id` to `to_id` is possible through this segment.

void clear ( )

Clears all the points and segments.

void connect_points ( int id, int to_id, bool bidirectional=true )

Creates a segment between the given points. If `bidirectional` is `false`, only movement from `id` to `to_id` is allowed, not the reverse direction.

```var astar = AStar3D.new()
astar.connect_points(1, 2, false)
```

void disconnect_points ( int id, int to_id, bool bidirectional=true )

Deletes the segment between the given points. If `bidirectional` is `false`, only movement from `id` to `to_id` is prevented, and a unidirectional segment possibly remains.

int get_available_point_id ( ) const

Returns the next available point ID with no point associated to it.

int get_closest_point ( Vector3 to_position, bool include_disabled=false ) const

Returns the ID of the closest point to `to_position`, optionally taking disabled points into account. Returns `-1` if there are no points in the points pool.

Note: If several points are the closest to `to_position`, the one with the smallest ID will be returned, ensuring a deterministic result.

Vector3 get_closest_position_in_segment ( Vector3 to_position ) const

Returns the closest position to `to_position` that resides inside a segment between two connected points.

```var astar = AStar3D.new()