Attention: Here be dragons

This is the latest (unstable) version of this documentation, which may document features not available in or compatible with released stable versions of Godot.

Checking the stable version of the documentation...

AStar3D

继承： RefCounted < Object

A* 的一种实现，用于寻找 3D 空间中连接图中的两个顶点之间的最短路径。

描述

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 script that extends AStar3D and override the methods _compute_cost and _estimate_cost. Both should take two point IDs and return the distance between the corresponding points.

Example: Use Manhattan distance instead of Euclidean distance:

class_name MyAStar3D
extends AStar3D

func _compute_cost(u, v):
    var u_pos = get_point_position(u)
    var v_pos = get_point_position(v)
    return abs(u_pos.x - v_pos.x) + abs(u_pos.y - v_pos.y) + abs(u_pos.z - v_pos.z)

func _estimate_cost(u, v):
    var u_pos = get_point_position(u)
    var v_pos = get_point_position(v)
    return abs(u_pos.x - v_pos.x) + abs(u_pos.y - v_pos.y) + abs(u_pos.z - v_pos.z)

using Godot;

[GlobalClass]
public partial class MyAStar3D : AStar3D
{
    public override float _ComputeCost(long fromId, long toId)
    {
        Vector3 fromPoint = GetPointPosition(fromId);
        Vector3 toPoint = GetPointPosition(toId);

        return Mathf.Abs(fromPoint.X - toPoint.X) + Mathf.Abs(fromPoint.Y - toPoint.Y) + Mathf.Abs(fromPoint.Z - toPoint.Z);
    }

    public override float _EstimateCost(long fromId, long toId)
    {
        Vector3 fromPoint = GetPointPosition(fromId);
        Vector3 toPoint = GetPointPosition(toId);
        return Mathf.Abs(fromPoint.X - toPoint.X) + Mathf.Abs(fromPoint.Y - toPoint.Y) + Mathf.Abs(fromPoint.Z - toPoint.Z);
    }
}

_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_scales of the endpoints of the respective segments. If the default methods are used and the weight_scales of all points are set to 1.0, then this equals the sum of Euclidean distances of all segments in the path.

方法

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

方法说明

float _compute_cost(from_id: int, to_id: int) virtual const 🔗

计算两个连接点之间的成本时调用。

请注意，这个函数在默认的 AStar3D 类中是隐藏的。

float _estimate_cost(from_id: int, end_id: int) virtual const 🔗

估算某个点和路径终点之间的成本时调用。

请注意，这个函数在默认的 AStar3D 类中是隐藏的。

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

在给定的位置添加一个新的点，并使用给定的标识符。id 必须大于等于 0，weight_scale 必须大于等于 0.0。

在确定从邻点到此点的一段路程的总成本时，weight_scale 要乘以 _compute_cost 的结果。因此，在其他条件相同的情况下，算法优先选择 weight_scale 较低的点来形成路径。

var astar = AStar3D.new()
astar.add_point(1, Vector3(1, 0, 0), 4) # 添加点 (1, 0, 0)，其 weight_scale 为 4 且 id 为 1

var astar = new AStar3D();
astar.AddPoint(1, new Vector3(1, 0, 0), 4); // 添加点 (1, 0, 0)，其 weight_scale 为 4 且 id 为 1

如果对于给定的 id 已经存在一个点，它的位置和权重将被更新为给定的值。

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

返回两个给定点是否通过线段直接连接。如果 bidirectional 为 false，则返回是否可以通过该线段从 id 移动到 to_id。

void clear() 🔗

清除所有点和线段。

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

在给定的点之间创建一条线段。如果 bidirectional 为 false，则只允许从 id 到 to_id 的移动，而不允许反向移动。

var astar = AStar3D.new()
astar.add_point(1, Vector3(1, 1, 0))
astar.add_point(2, Vector3(0, 5, 0))
astar.connect_points(1, 2, false)

var astar = new AStar3D();
astar.AddPoint(1, new Vector3(1, 1, 0));
astar.AddPoint(2, new Vector3(0, 5, 0));
astar.ConnectPoints(1, 2, false);

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

删除给定点之间的线段。如果 bidirectional 为 false，则仅阻止从 id 到 to_id 的移动，并且可能会保留一个单向线段。

int get_available_point_id() const 🔗

返回下一个没有关联点的可用点 ID。

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

返回距离 to_position 最近的点的 ID，可以选择将禁用的点考虑在内。如果点池中没有点，则返回 -1。

注意：如果有多个点距离 to_position 最近，则返回 ID 最小的那个点，以保证结果的确定性。

Vector3 get_closest_position_in_segment(to_position: Vector3) const 🔗

返回位于两个连接点之间的线段中离 to_position 最近的位置。

var astar = AStar3D.new()
astar.add_point(1, Vector3(0, 0, 0))
astar.add_point(2, Vector3(0, 5, 0))
astar.connect_points(1, 2)
var res = astar.get_closest_position_in_segment(Vector3(3, 3, 0)) # 返回 (0, 3, 0)

var astar = new AStar3D();
astar.AddPoint(1, new Vector3(0, 0, 0));
astar.AddPoint(2, new Vector3(0, 5, 0));
astar.ConnectPoints(1, 2);
Vector3 res = astar.GetClosestPositionInSegment(new Vector3(3, 3, 0)); // 返回 (0, 3, 0)

结果是在从 y = 0 到 y = 5 的线段中。它是线段中距离给定点最近的位置。

PackedInt64Array get_id_path(from_id: int, to_id: int, allow_partial_path: bool = false) 🔗

Returns an array with the IDs of the points that form the path found by AStar3D between the given points. The array is ordered from the starting point to the ending point of the path.

If there is no valid path to the target, and allow_partial_path is true, returns a path to the point closest to the target that can be reached.

Note: When allow_partial_path is true and to_id is disabled the search may take an unusually long time to finish.

var astar = AStar3D.new()
astar.add_point(1, Vector3(0, 0, 0))
astar.add_point(2, Vector3(0, 1, 0), 1) # Default weight is 1
astar.add_point(3, Vector3(1, 1, 0))
astar.add_point(4, Vector3(2, 0, 0))

astar.connect_points(1, 2, false)
astar.connect_points(2, 3, false)
astar.connect_points(4, 3, false)
astar.connect_points(1, 4, false)

var res = astar.get_id_path(1, 3) # Returns [1, 2, 3]

var astar = new AStar3D();
astar.AddPoint(1, new Vector3(0, 0, 0));
astar.AddPoint(2, new Vector3(0, 1, 0), 1); // Default weight is 1
astar.AddPoint(3, new Vector3(1, 1, 0));
astar.AddPoint(4, new Vector3(2, 0, 0));
astar.ConnectPoints(1, 2, false);
astar.ConnectPoints(2, 3, false);
astar.ConnectPoints(4, 3, false);
astar.ConnectPoints(1, 4, false);
long[] res = astar.GetIdPath(1, 3); // Returns [1, 2, 3]

If you change the 2nd point's weight to 3, then the result will be [1, 4, 3] instead, because now even though the distance is longer, it's "easier" to get through point 4 than through point 2.

int get_point_capacity() const 🔗

该函数返回支持点的数据结构的容量，可以与 reserve_space 方法一起使用。

PackedInt64Array get_point_connections(id: int) 🔗

返回一个数组，其中包含与给定点形成连接的点的 ID。

var astar = AStar3D.new()
astar.add_point(1, Vector3(0, 0, 0))
astar.add_point(2, Vector3(0, 1, 0))
astar.add_point(3, Vector3(1, 1, 0))
astar.add_point(4, Vector3(2, 0, 0))

astar.connect_points(1, 2, true)
astar.connect_points(1, 3, true)

var neighbors = astar.get_point_connections(1) # 返回 [2, 3]

var astar = new AStar3D();
astar.AddPoint(1, new Vector3(0, 0, 0));
astar.AddPoint(2, new Vector3(0, 1, 0));
astar.AddPoint(3, new Vector3(1, 1, 0));
astar.AddPoint(4, new Vector3(2, 0, 0));
astar.ConnectPoints(1, 2, true);
astar.ConnectPoints(1, 3, true);

long[] neighbors = astar.GetPointConnections(1); // 返回 [2, 3]

int get_point_count() const 🔗

返回点池中当前的点数。

PackedInt64Array get_point_ids() 🔗

返回所有点 ID 的数组。

PackedVector3Array get_point_path(from_id: int, to_id: int, allow_partial_path: bool = false) 🔗

Returns an array with the points that are in the path found by AStar3D between the given points. The array is ordered from the starting point to the ending point of the path.

If there is no valid path to the target, and allow_partial_path is true, returns a path to the point closest to the target that can be reached.

Note: This method is not thread-safe. If called from a Thread, it will return an empty array and will print an error message.

Additionally, when allow_partial_path is true and to_id is disabled the search may take an unusually long time to finish.

Vector3 get_point_position(id: int) const 🔗

返回与给定 id 相关联的点的位置。

float get_point_weight_scale(id: int) const 🔗

返回与给定 id 关联的点的权重比例。

bool has_point(id: int) const 🔗

返回与给定 id 相关联的点是否存在。

bool is_point_disabled(id: int) const 🔗

返回用于寻路时点是否被禁用。默认情况下，所有点均被启用。

void remove_point(id: int) 🔗

从点池中移除与给定 id 关联的点。

void reserve_space(num_nodes: int) 🔗

该函数为 num_nodes 个点内部预留空间。如果一次添加了大量已知数量的点，例如网格上的点，则此函数很有用。新的容量必须大于或等于旧的容量。

void set_point_disabled(id: int, disabled: bool = true) 🔗

用于寻路时禁用或启用指定的点。适用于制作临时障碍物。

void set_point_position(id: int, position: Vector3) 🔗

为具有给定 id 的点设置位置 position。

void set_point_weight_scale(id: int, weight_scale: float) 🔗

为给定的 id 的点设置 weight_scale。在确定从邻接点到这个点的一段路程的总成本时，weight_scale 要乘以 _compute_cost 的结果。