Attention: Here be dragons

This is the latest (unstable) version of this documentation, which may document features not available in or compatible with released stable versions of Godot.

Checking the stable version of the documentation...

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

方法

float	_compute_cost(from_id: int, to_id: int) virtual const
float	_estimate_cost(from_id: int, end_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)

---

方法说明

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

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

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

---

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

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

请注意，这个函数在默认的 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。数组从路径的起点到终点排序。

如果没有能够到达目标的有效路径，并且 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 在给定点之间找到的路径中的点。数组从路径的起点到终点进行排序。

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

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

另外，如果 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() 的结果。