AStar

Inherits: Reference < Object

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

描述

A*（A 星）是一种计算机算法，广泛用于寻路和图遍历，是通过一组给定的边（线段），在顶点（点）之间绘制短路径的过程。A* 因其性能和准确性而被广泛使用。Godot 的 A* 实现默认使用三维空间中的点和欧式距离。

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

也可以使用非欧式距离。为此，创建一个扩展 AStar 的类并重写方法 _compute_cost 和 _estimate_cost。这两个方法都接受两个索引并返回一个长度，如以下示例所示：

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)

_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

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

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

• float _estimate_cost ( int from_id, int to_id ) virtual

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

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

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

在给定的位置添加一个新的点，并使用给定的标识符。id必须是0或者更大，weight_scale必须是1或者更大。

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

var astar = AStar.new()
astar.add_point(1, Vector3(1, 0, 0), 4) # Adds the point (1, 0, 0) with weight_scale 4 and 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 )

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

var astar = AStar.new()
astar.add_point(1, Vector3(1, 1, 0))
astar.add_point(2, Vector3(0, 5, 0))
astar.connect_points(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 = AStar.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)

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

• PoolIntArray get_id_path ( int from_id, int to_id )

返回一个数组，该数组中包含了 AStar 在给定点之间找到的路径的点的 ID。数组从路径的起始点到结束点排序。

var astar = AStar.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]

如果你把第 2 点的权重改为 3，那么结果就会变成 [1, 4, 3]，因为现在虽然距离长了，但通过第 4 点比通过第 2 点 “容易”。

• int get_point_capacity ( ) const

返回支持点的结构的容量，与 reserve_space 配合使用。

• PoolIntArray get_point_connections ( int id )

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

var astar = AStar.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]

• int get_point_count ( ) const

返回当前积分池中的积分数量。

• PoolVector3Array get_point_path ( int from_id, int to_id )

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

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

• Vector3 get_point_position ( int id ) const

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

• float get_point_weight_scale ( int id ) const

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

• Array get_points ( )

返回所有点的数组。

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