AStar3D

继承： RefCounted < Object

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

描述

A*（A-star）是一种用于寻路和图形遍历的计算机算法，用于在顶点（点）之间绘制短路径，穿过给定的边（段）集合。由于其性能和准确性，该算法被广泛使用。i3D的A*实现默认使用3D空间中的点和欧几里得距离。

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

也可以使用非欧几里德距离。为此，请创建一个扩展AStar3D并覆盖方法_compute_cost()和_estimate_cost()的脚本。两者都应该采用两个点ID并返回相应点之间的距离。

示例：使用曼哈顿距离而不是欧几里德距离：

S3ScriptC#

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较低的点来形成路径。

S3ScriptC#

var astar = AStar3D.new()
astar.add_point(1, Vector3(1, 0, 0), 4)

如果给定的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 的移动，而不允许反向移动。

S3ScriptC#

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 的位置。

S3ScriptC#

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

返回一个数组，其中包含3D A-star算法在给定点之间找到的路径的点的ID。该数组按照从起点到终点的顺序排列。

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

注意：当allow_partial_path为true且to_id被禁用时，搜索可能需要异常长的时间才能完成。

S3ScriptC#

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]

如果将第二个点的权重改为3，则结果将变为[1, 4, 3]，因为现在虽然距离更长，但穿过第四个点比穿过第二个点更“容易”。

---

int get_point_capacity() const 🔗

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

---

PackedInt64Array get_point_connections(id: int) 🔗

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

S3ScriptC#

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调用，它将返回一个空数组并打印错误消息。

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