Up to date

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

AStar2D

继承: RefCounted < Object

A* 的一种实现,用于查找 2D 空间中连通图上两个顶点之间的最短路径。

描述

A* 算法的一种实现,用于在 2D 空间中的连通图上找到两个顶点之间的最短路径。

有关如何使用该类的更详尽的解释,请参阅 AStar3DAStar2DAStar3D 的包装器,它强制执行 2D 坐标。

方法

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, Vector2 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 ( Vector2 to_position, bool include_disabled=false ) const

Vector2

get_closest_position_in_segment ( Vector2 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 ( )

PackedVector2Array

get_point_path ( int from_id, int to_id )

Vector2

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, Vector2 position )

void

set_point_weight_scale ( int id, float weight_scale )


方法说明

float _compute_cost ( int from_id, int to_id ) virtual const

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

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


float _estimate_cost ( int from_id, int to_id ) virtual const

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

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


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

在具有给定标识符的给定位置添加一个新点。id 必须为 0 或更大,weight_scale 必须为 0.0 或更大。

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

var astar = AStar2D.new()
astar.add_point(1, Vector2(1, 0), 4) # 添加点 (1, 0)、权重为 4、ID 为 1

如果已经存在一个给定 id 的点,则它的位置和权重缩放将被更新为给定值。


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

返回两个给定点之间是否存在连接/线段。如果 bidirectionalfalse,则返回是否可以通过此段从 id 移动到 to_id


void clear ( )

清除所有点和线段。


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

在给定的点之间创建一个线段。如果 bidirectionalfalse,则只允许从 idto_id 的移动,而不允许反向移动。

var astar = AStar2D.new()
astar.add_point(1, Vector2(1, 1))
astar.add_point(2, Vector2(0, 5))
astar.connect_points(1, 2, false)

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

删除给定点之间的线段。如果 bidirectionalfalse,则仅阻止从 idto_id 的移动,并且可能会保留一个单向线段。


int get_available_point_id ( ) const

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


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

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

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


Vector2 get_closest_position_in_segment ( Vector2 to_position ) const

返回最接近 to_position 的位置,该位置位于两个连接点之间的线段内。

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)

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


PackedInt64Array get_id_path ( int from_id, int to_id )

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

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]

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


int get_point_capacity ( ) const

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


PackedInt64Array get_point_connections ( int id )

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

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]

int get_point_count ( ) const

返回点池中当前的点数。


PackedInt64Array get_point_ids ( )

返回所有点 ID 的数组。


PackedVector2Array get_point_path ( int from_id, int to_id )

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

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


Vector2 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, Vector2 position )

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


void set_point_weight_scale ( int id, float weight_scale )

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