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 星）是一种计算机算法，用于寻路和图遍历，即穿过一组给定的边（线段），在顶点（点）之间绘制短路径的过程。由于其性能和准确性，它被广泛使用。Godot 的 A* 实现默认使用 3D 空间中的点和欧几里德距离。

你需要使用 add_point 手动添加点，并使用 connect_points 手动创建线段。完成后，可以使用 are_points_connected 函数，测试两点之间是否存在路径，通过 get_id_path 获取包含索引的路径，或使用 get_point_path 获取包含实际坐标的路径。

也可以使用非欧几里德距离。为此，创建一个扩展 AStar3D 的类，并覆盖方法 _compute_cost 和 _estimate_cost。两者都接受两个索引并返回一个长度，如以下示例所示。

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 应该返回距离的下限，即 _estimate_cost(u, v) <= _compute_cost(u, v)。这可以作为算法的提示，因为自定义 _compute_cost 可能计算量很大。如果不是这种情况，请使 _estimate_cost 返回与 _compute_cost 相同的值，以便为算法提供最准确的信息。

如果使用默认的 _estimate_cost 和 _compute_cost 方法，或者如果提供的 _estimate_cost 方法返回成本的下限，则 A* 返回的路径将是成本最低的路径。这里，路径的代价等于路径中所有段的 _compute_cost 结果乘以各个段端点的权重 weight_scale 之和。如果使用默认方法，并且所有点的 weight_scale 设置为 1.0，则这等于路径中所有段的欧几里德距离之和。

方法¶

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	get_point_connections ( int id )
int	get_point_count ( ) const
PackedInt64Array	get_point_ids ( )
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 )

方法说明¶

float _compute_cost ( int from_id, int to_id ) virtual const

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

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

float _estimate_cost ( int from_id, int to_id ) virtual const

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

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

void add_point ( int id, Vector3 position, float weight_scale=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 ( int id, int to_id, bool bidirectional=true ) const

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

void clear ( )

清除所有点和线段。

void connect_points ( int id, int to_id, bool bidirectional=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 ( int id, int to_id, bool bidirectional=true )

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

int get_available_point_id ( ) const

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

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

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

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

Vector3 get_closest_position_in_segment ( Vector3 to_position ) 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 ( int from_id, int to_id )

返回一个数组，其中包含构成 AStar3D 在给定点之间找到的路径中的点的 ID。数组从路径的起点到终点排序。

var astar = AStar3D.new()
astar.add_point(1, Vector3(0, 0, 0))
astar.add_point(2, Vector3(0, 1, 0), 1) # 默认权重为 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) # 返回 [1, 2, 3]

var astar = new AStar3D();
astar.AddPoint(1, new Vector3(0, 0, 0));
astar.AddPoint(2, new Vector3(0, 1, 0), 1); // 默认权重为 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);
int[] res = astar.GetIdPath(1, 3); // 返回 [1, 2, 3]

如果将第2个点的权重更改为 3，则结果将改为 [1, 4, 3]，因为现在即使距离更长，但通过第 4 点也比通过第 2 点“更容易”。

int get_point_capacity ( ) const

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

PackedInt64Array get_point_connections ( int id )

返回一个数组，其中包含与给定点形成连接的点的 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);

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

int get_point_count ( ) const

返回点池中当前的点数。

PackedInt64Array get_point_ids ( )

返回所有点 ID 的数组。

PackedVector3Array get_point_path ( int from_id, int to_id )

返回一个数组，其中包含 AStar3D 在给定点之间找到的路径中的点。数组从路径的起点到终点进行排序。

注意：这种方法不是线程安全的。如果从 Thread 调用，它将返回一个空的 PackedVector3Array，并打印一条错误消息。

Vector3 get_point_position ( int id ) const

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

float get_point_weight_scale ( int id ) const

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

bool has_point ( int id ) const

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

bool is_point_disabled ( int id ) const

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

void remove_point ( int id )

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

void reserve_space ( int num_nodes )

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

void set_point_disabled ( int id, bool disabled=true )

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

void set_point_position ( int id, Vector3 position )

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

void set_point_weight_scale ( int id, float weight_scale )

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