Up to date

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

AStar3D¶

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 的结果。