AStar2D
继承: RefCounted < Object
A* 的一种实现,用于查找 2D 空间中连通图上两个顶点之间的最短路径。
描述
A* 算法的一种实现,用于在 2D 空间中的连通图上找到两个顶点之间的最短路径。
有关如何使用该类的更详尽的解释,请参阅 AStar3D。AStar2D 是 AStar3D 的包装器,它强制执行 2D 坐标。
方法
_compute_cost(from_id: int, to_id: int) virtual const | |
_estimate_cost(from_id: int, to_id: int) virtual const | |
void | add_point(id: int, position: Vector2, weight_scale: float = 1.0) |
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) |
get_available_point_id() const | |
get_closest_point(to_position: Vector2, include_disabled: bool = false) const | |
get_closest_position_in_segment(to_position: Vector2) const | |
get_id_path(from_id: int, to_id: int, allow_partial_path: bool = false) | |
get_point_capacity() const | |
get_point_connections(id: int) | |
get_point_count() const | |
get_point_path(from_id: int, to_id: int, allow_partial_path: bool = false) | |
get_point_position(id: int) const | |
get_point_weight_scale(id: int) const | |
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: Vector2) |
void | set_point_weight_scale(id: int, weight_scale: float) |
方法说明
float _compute_cost(from_id: int, to_id: int) virtual const 🔗
计算两个连接点之间的成本时调用。
请注意,这个函数在默认的 AStar2D 类中是隐藏的。
float _estimate_cost(from_id: int, to_id: int) virtual const 🔗
估算某个点和路径终点之间的成本时调用。
请注意,这个函数在默认的 AStar2D 类中是隐藏的。
void add_point(id: int, position: Vector2, weight_scale: float = 1.0) 🔗
在具有给定标识符的给定位置添加一个新点。id
必须为 0 或更大,weight_scale
必须为 0.0 或更大。
在确定从相邻点到此点的一段路程的总成本时,weight_scale
要乘以 _compute_cost 的结果。因此,在其他条件相同的情况下,算法优先选择 weight_scale
较低的点来形成路径。
GDScriptC#
var astar = AStar2D.new()
astar.add_point(1, Vector2(1, 0), 4) # 添加点 (1, 0)、权重为 4、ID 为 1
var astar = new AStar2D();
astar.AddPoint(1, new Vector2(1, 0), 4); // 添加点 (1, 0)、权重为 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
的移动,而不允许反向移动。
GDScriptC#
var astar = AStar2D.new()
astar.add_point(1, Vector2(1, 1))
astar.add_point(2, Vector2(0, 5))
astar.connect_points(1, 2, false)
var astar = new AStar2D();
astar.AddPoint(1, new Vector2(1, 1));
astar.AddPoint(2, new Vector2(0, 5));
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: Vector2, include_disabled: bool = false) const 🔗
返回距离 to_position
最近的点的 ID,可以选择将禁用的点考虑在内。如果点池中没有点,则返回 -1
。
注意:如果有多个点距离 to_position
最近,则返回 ID 最小的那个点,以保证结果的确定性。
Vector2 get_closest_position_in_segment(to_position: Vector2) const 🔗
返回最接近 to_position
的位置,该位置位于两个连接点之间的线段内。
GDScriptC#
var astar = AStar2D.new()
astar.add_point(1, Vector2(0, 0))
astar.add_point(2, Vector2(0, 5))
astar.connect_points(1, 2)
var res = astar.get_closest_position_in_segment(Vector2(3, 3)) # 返回 (0, 3)
var astar = new AStar2D();
astar.AddPoint(1, new Vector2(0, 0));
astar.AddPoint(2, new Vector2(0, 5));
astar.ConnectPoints(1, 2);
Vector2 res = astar.GetClosestPositionInSegment(new Vector2(3, 3)); // 返回 (0, 3)
结果位于从 y = 0
到 y = 5
的线段中。它是线段中距给定点最近的位置。
PackedInt64Array get_id_path(from_id: int, to_id: int, allow_partial_path: bool = false) 🔗
返回一个数组,其中包含构成由 AStar2D 在给定点之间找到的路径的点的 ID。数组从路径的起点到终点进行排序。
如果目标没有有效路径,并且allow_partial_path
为true
,则返回到最接近可到达目标的点的路径。
GDScriptC#
var astar = AStar2D.new()
astar.add_point(1, Vector2(0, 0))
astar.add_point(2, Vector2(0, 1), 1) # 默认权重为 1
astar.add_point(3, Vector2(1, 1))
astar.add_point(4, Vector2(2, 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 AStar2D();
astar.AddPoint(1, new Vector2(0, 0));
astar.AddPoint(2, new Vector2(0, 1), 1); // 默认权重为 1
astar.AddPoint(3, new Vector2(1, 1));
astar.AddPoint(4, new Vector2(2, 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(id: int) 🔗
返回一个数组,其中包含与给定点形成连接的点的 ID。
GDScriptC#
var astar = AStar2D.new()
astar.add_point(1, Vector2(0, 0))
astar.add_point(2, Vector2(0, 1))
astar.add_point(3, Vector2(1, 1))
astar.add_point(4, Vector2(2, 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 AStar2D();
astar.AddPoint(1, new Vector2(0, 0));
astar.AddPoint(2, new Vector2(0, 1));
astar.AddPoint(3, new Vector2(1, 1));
astar.AddPoint(4, new Vector2(2, 0));
astar.ConnectPoints(1, 2, true);
astar.ConnectPoints(1, 3, true);
int[] neighbors = astar.GetPointConnections(1); // 返回 [2, 3]
返回点池中当前的点数。
PackedInt64Array get_point_ids() 🔗
返回所有点 ID 的数组。
PackedVector2Array get_point_path(from_id: int, to_id: int, allow_partial_path: bool = false) 🔗
返回一个数组,其中包含 AStar2D 在给定点之间找到的路径中的点。数组从路径的起点到终点进行排序。
如果没有通往目标的有效路径并且 allow_partial_path
为 true
,则会返回通往距离目标最近的可达点的路径。
注意:该方法不是线程安全的。如果从 Thread 调用,它将返回一个空的 PackedVector2Array 并打印一条错误消息。
Vector2 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 🔗
返回用于寻路时点是否被禁用。默认情况下,所有点均被启用。
从点池中移除与给定 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: Vector2) 🔗
为具有给定 id
的点设置位置 position
。
void set_point_weight_scale(id: int, weight_scale: float) 🔗
为给定的 id
的点设置 weight_scale
。在确定从邻接点到这个点的一段路程的总成本时,weight_scale
要乘以 _compute_cost 的结果。