AStar

继承

Reference

简要描述

A *的实现，用于在空间中的连接点之间找到最短路径。

描述

A *（星形）是一种计算机算法，广泛用于路径查找和图形遍历，即通过给定的一组边（段）绘制顶点（点）之间的短路径的过程。

您必须使用[add_point]手动添加点，并使用[connect_points]手动创建线段。

也可以使用非欧几里得距离。

class MyAStar:
    extends AStar

    func _compute_cost(u, v):
        return abs(u - v)

    func _estimate_cost(u, v):
        return min(0, abs(u - v) - 1)

_estimate_cost应该返回距离的下限，即_estimate_cost（u，v）＆lt; = _compute_cost（u，v）。 这是对算法的提示，因为自定义 _compute_cost可能需要大量计算。 如果不是这种情况，请使method_estimate_cost返回与method_compute_cost相同的值，以为算法提供最准确的信息。

方法

返回值类型	方法名称
float	_compute_cost(from_id: int, to_id: int) virtual
float	_estimate_cost(from_id: int, to_id: int) virtual
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
PoolIntArray	get_id_path(from_id: int, to_id: int)
int	get_point_capacity() const
PoolIntArray	get_point_connections(id: int)
int	get_point_count() const
PoolVector3Array	get_point_path(from_id: int, to_id: int)
Vector3	get_point_position(id: int) const
float	get_point_weight_scale(id: int) const
Array	get_points()
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)

方法说明

• _compute_cost _compute_cost(from_id: int, to_id: int) virtual

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

请注意，此函数隐藏在默认的AStar类中。

---

• _estimate_cost _estimate_cost(from_id: int, to_id: int) virtual

在估算点与路径终点之间的成本时调用。

请注意，此函数隐藏在默认的AStar类中。

---

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

在具有给定标识符的给定位置添加新点。

var astar = AStar.new()
astar.add_point(1, Vector3(1, 0, 0), 4) # Adds the point (1, 0, 0) with weight_scale 4 and id 1

如果给定的id已经存在一个点，则将其位置和权重更新为给定值。

---

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

返回两个给定点是否通过线段直接连接。

---

• clear clear()

清除所有点和线段。

---

• connect_points connect_points(id: int, to_id: int, bidirectional: bool = true)

在给定点之间创建线段。

var astar = AStar.new()
astar.add_point(1, Vector3(1, 1, 0))
astar.add_point(2, Vector3(0, 5, 0))
astar.connect_points(1, 2, false)

---

• disconnect_points disconnect_points(id: int, to_id: int, bidirectional: bool = true)

删除给定点之间的线段。

---

• get_available_point_id get_available_point_id() const

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

---

• get_closest_point get_closest_point(to_position: Vector3, include_disabled: bool = false) const

返回最接近to_position的点的ID，可以选择考虑禁用点。

---

• get_closest_position_in_segment get_closest_position_in_segment(to_position: Vector3) const

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

var astar = AStar.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)) # Returns (0, 3, 0)

结果位于从y = 0到y = 5的段中。

---

• get_id_path get_id_path(from_id: int, to_id: int)

返回一个数组，其中包含点的ID，这些点构成AStar在给定点之间找到的路径。

var astar = AStar.new()
astar.add_point(1, Vector3(0, 0, 0))
astar.add_point(2, Vector3(0, 1, 0), 1) # Default weight is 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) # Returns [2,]

如果将第二点的权重更改为3，则结果将改为[1、4、3]，因为现在即使距离更长，也比通过点4更容易

---

• get_point_capacity get_point_capacity() const

返回支持这些点的结构的容量，可与reserve_space结合使用。

---

• get_point_connections get_point_connections(id: int)

返回一个数组，该数组具有与给定点形成连接的点的ID。

var astar = AStar.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) # Returns [3]

---

• get_point_count get_point_count() const

返回数组中当前的定点数。

---

• get_point_path get_point_path(from_id: int, to_id: int)

返回一个数组，其中的点位于AStar在给定点之间找到的路径中。

---

• get_point_position get_point_position(id: int) const

返回与给定id关联的点的位置。

---

• get_point_weight_scale get_point_weight_scale(id: int) const

返回与给定id关联的点的权重。

---

• get_points get_points()

返回所有点的数组。

---

• has_point has_point(id: int) const

返回与给定id关联的点。

---

• is_point_disabled is_point_disabled(id: int) const

返回是否为寻路禁用点。

---

• remove_point remove_point(id: int)

从数组中删​​除与给定id关联的积分。

---

• reserve_space reserve_space(num_nodes: int)

在内部为num_nodes个点保留空间，如果您一次添加一个已知的大量点（例如对于网格），则很有用。

---

• set_point_disabled set_point_disabled(id: int, disabled: bool = true)

禁用或启用指定点进行寻路。

---

• set_point_position set_point_position(id: int, position: Vector3)

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

---

• set_point_weight_scale set_point_weight_scale(id: int, weight_scale: float)

为具有给定id的点设置weight_scale。

---