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 Star）是一種用於路徑尋找（pathfinding）與圖遍歷（graph traversal）的電腦演算法，可在頂點（點）之間，沿著一組指定邊（線段）規劃最短路徑。因其效能與準確度而被廣泛使用。Godot 的 A* 實作預設在 3D 空間中使用點並以歐氏距離計算。

你必須先使用 add_point() 手動加入點，再用 connect_points() 手動建立線段。完成後，可透過 are_points_connected() 檢查兩點之間是否存在路徑，利用 get_id_path() 取得由索引組成的路徑，或使用 get_point_path() 取得包含實際座標的路徑。

亦可改用非歐氏距離。若要這麼做，請撰寫一個繼承自 AStar3D 的腳本，並覆寫 _compute_cost() 與 _estimate_cost() 兩個方法。這兩個方法皆應接收兩個點的 ID，並回傳這兩點之間的距離。

範例： 使用曼哈頓距離取代歐氏距離：

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)

using Godot;

[GlobalClass]
public partial class MyAStar3D : AStar3D
{
    public override float _ComputeCost(long fromId, long toId)
    {
        Vector3 fromPoint = GetPointPosition(fromId);
        Vector3 toPoint = GetPointPosition(toId);
        return Mathf.Abs(fromPoint.X - toPoint.X) + Mathf.Abs(fromPoint.Y - toPoint.Y) + Mathf.Abs(fromPoint.Z - toPoint.Z);
    }

    public override float _EstimateCost(long fromId, long toId)
    {
        Vector3 fromPoint = GetPointPosition(fromId);
        Vector3 toPoint = GetPointPosition(toId);
        return Mathf.Abs(fromPoint.X - toPoint.X) + Mathf.Abs(fromPoint.Y - toPoint.Y) + Mathf.Abs(fromPoint.Z - toPoint.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()

If true enables the filtering of neighbors via _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 🔗

Called when neighboring point enters processing and if neighbor_filter_enabled is true. If true is returned the point will not be processed.

Note that this function is hidden in the default AStar3D class.

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

在給定的位置新增一個點並指定其識別碼。 id 必須大於等於 0，weight_scale 必須大於等於 0.0。

在計算從鄰近點移動至此點的段落總成本時，會將 _compute_cost() 的結果乘以 weight_scale。因此在其他條件相同時，演算法傾向選擇擁有較低 weight_scale 的點來組成路徑。

var astar = AStar3D.new()
astar.add_point(1, Vector3(1, 0, 0), 4) # 新增點 (1, 0, 0)，weight_scale 為 4，id 為 1

var astar = new AStar3D();
astar.AddPoint(1, new 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，反向則不允許。

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)

var astar = new AStar3D();
astar.AddPoint(1, new Vector3(1, 1, 0));
astar.AddPoint(2, new Vector3(0, 5, 0));
astar.ConnectPoints(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。

注意： 若有多個點同樣最接近，將回傳最小 ID 的點，以確保結果一致。

Vector3 get_closest_position_in_segment(to_position: Vector3) const 🔗

返回位於兩個連接點之間線段中、最靠近 to_position 的位置。

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)

var astar = new AStar3D();
astar.AddPoint(1, new Vector3(0, 0, 0));
astar.AddPoint(2, new Vector3(0, 5, 0));
astar.ConnectPoints(1, 2);
Vector3 res = astar.GetClosestPositionInSegment(new 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) 🔗

Returns an array with the IDs of the points that form the path found by AStar3D between the given points. The array is ordered from the starting point to the ending point of the path.

If from_id point is disabled, returns an empty array (even if from_id == to_id).

If from_id point is not disabled, there is no valid path to the target, and allow_partial_path is true, returns a path to the point closest to the target that can be reached.

Note: When allow_partial_path is true and to_id is disabled the search may take an unusually long time to finish.

var astar = AStar3D.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 [1, 2, 3]

var astar = new AStar3D();
astar.AddPoint(1, new Vector3(0, 0, 0));
astar.AddPoint(2, new Vector3(0, 1, 0), 1); // Default weight is 1
astar.AddPoint(3, new Vector3(1, 1, 0));
astar.AddPoint(4, new Vector3(2, 0, 0));
astar.ConnectPoints(1, 2, false);
astar.ConnectPoints(2, 3, false);
astar.ConnectPoints(4, 3, false);
astar.ConnectPoints(1, 4, false);
long[] res = astar.GetIdPath(1, 3); // Returns [1, 2, 3]

If you change the 2nd point's weight to 3, then the result will be [1, 4, 3] instead, because now even though the distance is longer, it's "easier" to get through point 4 than through point 2.

int get_point_capacity() const 🔗

回傳儲存點資料結構的容量，可配合 reserve_space() 使用。

PackedInt64Array get_point_connections(id: int) 🔗

返回一個陣列，包含與指定點直接相連之點的 ID。

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]

var astar = new AStar3D();
astar.AddPoint(1, new Vector3(0, 0, 0));
astar.AddPoint(2, new Vector3(0, 1, 0));
astar.AddPoint(3, new Vector3(1, 1, 0));
astar.AddPoint(4, new Vector3(2, 0, 0));
astar.ConnectPoints(1, 2, true);
astar.ConnectPoints(1, 3, true);

long[] neighbors = astar.GetPointConnections(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) 🔗

Returns an array with the points that are in the path found by AStar3D between the given points. The array is ordered from the starting point to the ending point of the path.

If from_id point is disabled, returns an empty array (even if from_id == to_id).

If from_id point is not disabled, there is no valid path to the target, and allow_partial_path is true, returns a path to the point closest to the target that can be reached.

Note: This method is not thread-safe; it can only be used from a single Thread at a given time. Consider using Mutex to ensure exclusive access to one thread to avoid race conditions.

Additionally, when allow_partial_path is true and to_id is disabled the search may take an unusually long time to finish.

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() 的結果。