AStar3D

继承： RefCounted < Object

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

描述

A*（A 星）是一种用于寻路和图遍历的计算机算法，会根据一组给定的边（线段）测定顶点（点）之间的短路径。由于高性能和高准确度，A* 算法被广泛使用。Godot 的 A* 实现默认使用 3D 空间中的点和欧几里德距离。

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

也可以使用非欧几里德距离。做法是创建一个扩展自 AStar3D 的类，然后覆盖 _compute_cost() 和 _estimate_cost() 方法。两者都接受两个点 ID 并返回对应点之间的距离。

示例：用曼哈顿距离代替欧几里德距离：

GDScriptC#

class_name MyAStar3D
extends AStar3D

func _compute_cost(u, v):
    var u_pos = get_point_position(u)
    var v_pos = get_point_position(v)
    return abs(u_pos.x - v_pos.x) + abs(u_pos.y - v_pos.y) + abs(u_pos.z - v_pos.z)

func _estimate_cost(u, v):
    var u_pos = get_point_position(u)
    var v_pos = get_point_position(v)
    return abs(u_pos.x - v_pos.x) + abs(u_pos.y - v_pos.y) + abs(u_pos.z - v_pos.z)

_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，则成本等于路径中所有线段的欧几里德距离之和。

属性

bool

neighbor_filter_enabled

false

方法

float	_compute_cost(from_id: int, to_id: int) virtual const
float	_estimate_cost(from_id: int, end_id: int) virtual const
bool	_filter_neighbor(from_id: int, neighbor_id: int) virtual const
void	add_point(id: int, position: Vector3, weight_scale: float = 1.0)
bool	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)
int	get_available_point_id() const
int	get_closest_point(to_position: Vector3, include_disabled: bool = false) const
Vector3	get_closest_position_in_segment(to_position: Vector3) const
PackedInt64Array	get_id_path(from_id: int, to_id: int, allow_partial_path: bool = false)
int	get_point_capacity() const
PackedInt64Array	get_point_connections(id: int)
int	get_point_count() const
PackedInt64Array	get_point_ids()
PackedVector3Array	get_point_path(from_id: int, to_id: int, allow_partial_path: bool = false)
Vector3	get_point_position(id: int) const
float	get_point_weight_scale(id: int) const
bool	has_point(id: int) const
bool	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: Vector3)
void	set_point_weight_scale(id: int, weight_scale: float)

---

属性说明

bool neighbor_filter_enabled = false 🔗

• void set_neighbor_filter_enabled(value: bool)

• bool is_neighbor_filter_enabled()

如果为 true，则启用通过 _filter_neighbor() 过滤邻接点。

---

方法说明

float _compute_cost(from_id: int, to_id: int) virtual const 🔗

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

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

---

float _estimate_cost(from_id: int, end_id: int) virtual const 🔗

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

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

---

bool _filter_neighbor(from_id: int, neighbor_id: int) virtual const 🔗

进入邻接处理且 neighbor_filter_enabled 为 true 时调用。如果返回 true，则不会处理对应的点。

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

---

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

在给定的位置添加一个新的点，并使用给定的标识符。id 必须大于等于 0，weight_scale 必须大于等于 0.0。

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

GDScriptC#

var astar = AStar3D.new()
astar.add_point(1, Vector3(1, 0, 0), 4) # 添加点 (1, 0, 0)，其 weight_scale 为 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 = AStar3D.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(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: Vector3, include_disabled: bool = false) const 🔗

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

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

---

Vector3 get_closest_position_in_segment(to_position: Vector3) const 🔗

返回位于两个连接点之间的线段中离 to_position 最近的位置。

GDScriptC#

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)

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

---

PackedInt64Array get_id_path(from_id: int, to_id: int, allow_partial_path: bool = false) 🔗

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

如果 from_id 点被禁用，则返回一个空数组（即使 from_id == to_id）。

如果 from_id 点未被禁用，没有能够到达目标的有效路径，并且 allow_partial_path 为true，则返回能够到达的最接近目标点的路径。

注意：如果 allow_partial_path 为 true 并且 to_id 处于禁用状态，搜索耗时可能异常地大。

GDScriptC#

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]

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

---

int get_point_capacity() const 🔗

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

---

PackedInt64Array get_point_connections(id: int) 🔗

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

GDScriptC#

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]

---

int get_point_count() const 🔗

返回点池中当前的点数。

---

PackedInt64Array get_point_ids() 🔗

返回所有点 ID 的数组。

---

PackedVector3Array get_point_path(from_id: int, to_id: int, allow_partial_path: bool = false) 🔗

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

如果 from_id 点被禁用，则返回一个空数组（即使 from_id == to_id）。

如果 from_id 点未被禁用，没有通往目标的有效路径并且 allow_partial_path 为 true，则会返回通往距离目标最近的可达点的路径。

注意：该方法不是线程安全的，同一时间只能有一个 Thread 使用。请考虑使用 Mutex 来确保线程独占访问，避免竞态条件。

另外，如果 allow_partial_path 为 true 并且 to_id 处于禁用状态，搜索耗时可能异常地大。

---

Vector3 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 🔗

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

---

void remove_point(id: int) 🔗

从点池中移除与给定 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: Vector3) 🔗

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

---

void set_point_weight_scale(id: int, weight_scale: float) 🔗

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