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...
AStar2D
繼承: RefCounted < Object
A* 的實作,可用於搜尋 2D 空間連通圖上兩頂點間的最短路徑。
說明
A* 演算法的實作,用於在 2D 空間連通圖上尋找兩頂點之間的最短路徑。
教學
屬性
|
方法
_compute_cost(from_id: int, to_id: int) virtual const |
|
_estimate_cost(from_id: int, end_id: int) virtual const |
|
_filter_neighbor(from_id: int, neighbor_id: int) virtual const |
|
void |
add_point(id: int, position: Vector2, weight_scale: float = 1.0) |
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) |
get_available_point_id() const |
|
get_closest_point(to_position: Vector2, include_disabled: bool = false) const |
|
get_closest_position_in_segment(to_position: Vector2) const |
|
get_id_path(from_id: int, to_id: int, allow_partial_path: bool = false) |
|
get_point_capacity() const |
|
get_point_connections(id: int) |
|
get_point_count() const |
|
get_point_path(from_id: int, to_id: int, allow_partial_path: bool = false) |
|
get_point_position(id: int) const |
|
get_point_weight_scale(id: int) const |
|
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: Vector2) |
void |
set_point_weight_scale(id: int, weight_scale: float) |
屬性說明
bool neighbor_filter_enabled = false 🔗
如果為 true,則啟用通過 _filter_neighbor() 過濾鄰接點。
方法說明
float _compute_cost(from_id: int, to_id: int) virtual const 🔗
在計算兩個連接點之間的代價時呼叫。
此函式在預設的 AStar2D 類別中為隱藏。
float _estimate_cost(from_id: int, end_id: int) virtual const 🔗
在估計某點到路徑終點的代價時呼叫。
此函式在預設的 AStar2D 類別中為隱藏。
bool _filter_neighbor(from_id: int, neighbor_id: int) virtual const 🔗
進入鄰接處理且 neighbor_filter_enabled 為 true 時呼叫。如果回傳 true,則不會處理對應的點。
請注意,這個函式在預設的 AStar2D 類中是隱藏的。
void add_point(id: int, position: Vector2, weight_scale: float = 1.0) 🔗
在指定位置以指定識別碼新增一個點。id 必須大於等於 0,weight_scale 必須大於等於 0.0。
在計算從相鄰點移動到此點之線段的總代價時,會把 weight_scale 乘上 _compute_cost() 的結果。因此,在其他條件相同時,演算法傾向選擇 weight_scale 較小的點來組成路徑。
var astar = AStar2D.new()
astar.add_point(1, Vector2(1, 0), 4) # 新增點 (1, 0),權重係數 4,ID 1
var astar = new AStar2D();
astar.AddPoint(1, new Vector2(1, 0), 4); // 新增點 (1, 0),權重係數 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 = AStar2D.new()
astar.add_point(1, Vector2(1, 1))
astar.add_point(2, Vector2(0, 5))
astar.connect_points(1, 2, false)
var astar = new AStar2D();
astar.AddPoint(1, new Vector2(1, 1));
astar.AddPoint(2, new Vector2(0, 5));
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: Vector2, include_disabled: bool = false) const 🔗
回傳距離 to_position 最近的點的 ID,可以選擇將停用的點考慮在內。如果點池中沒有點,則回傳 -1。
注意:如果有多個點距離 to_position 最近,則回傳 ID 最小的那個點,以保證結果的確定性。
Vector2 get_closest_position_in_segment(to_position: Vector2) const 🔗
回傳位於兩連接點線段內、最接近 to_position 的座標。
var astar = AStar2D.new()
astar.add_point(1, Vector2(0, 0))
astar.add_point(2, Vector2(0, 5))
astar.connect_points(1, 2)
var res = astar.get_closest_position_in_segment(Vector2(3, 3)) # 回傳 (0, 3)
var astar = new AStar2D();
astar.AddPoint(1, new Vector2(0, 0));
astar.AddPoint(2, new Vector2(0, 5));
astar.ConnectPoints(1, 2);
Vector2 res = astar.GetClosestPositionInSegment(new Vector2(3, 3)); // 回傳 (0, 3)
此結果位於 y = 0 到 y = 5 的線段中,並且是該線段中最靠近指定點的位置。
PackedInt64Array get_id_path(from_id: int, to_id: int, allow_partial_path: bool = false) 🔗
回傳一個陣列,其中包含構成由 AStar2D 在給定點之間找到的路徑的點的 ID。陣列從路徑的起點到終點進行排序。
如果 from_id 點被停用,則回傳一個空陣列(即使 from_id == to_id)。
如果 from_id 點未被停用,沒有能夠到達目標的有效路徑,並且 allow_partial_path 為true,則回傳能夠到達的最接近目標點的路徑。
注意:如果 allow_partial_path 為 true 並且 to_id 處於停用狀態,搜尋耗時可能異常地大。
var astar = AStar2D.new()
astar.add_point(1, Vector2(0, 0))
astar.add_point(2, Vector2(0, 1), 1) # 預設權重為 1
astar.add_point(3, Vector2(1, 1))
astar.add_point(4, Vector2(2, 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]
var astar = new AStar2D();
astar.AddPoint(1, new Vector2(0, 0));
astar.AddPoint(2, new Vector2(0, 1), 1); // 預設權重為 1
astar.AddPoint(3, new Vector2(1, 1));
astar.AddPoint(4, new Vector2(2, 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); // 回傳 [1, 2, 3]
如果將第 2 個點的權重更改為 3,則結果將改為 [1, 4, 3],因為現在即使距離更長,通過第 4 點也比通過第 2 點“更容易”。
int get_point_capacity() const 🔗
回傳儲存點資料結構的容量,可配合 reserve_space() 使用。
PackedInt64Array get_point_connections(id: int) 🔗
回傳與指定點相連之點的 ID 陣列。
var astar = AStar2D.new()
astar.add_point(1, Vector2(0, 0))
astar.add_point(2, Vector2(0, 1))
astar.add_point(3, Vector2(1, 1))
astar.add_point(4, Vector2(2, 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 AStar2D();
astar.AddPoint(1, new Vector2(0, 0));
astar.AddPoint(2, new Vector2(0, 1));
astar.AddPoint(3, new Vector2(1, 1));
astar.AddPoint(4, new Vector2(2, 0));
astar.ConnectPoints(1, 2, true);
astar.ConnectPoints(1, 3, true);
long[] neighbors = astar.GetPointConnections(1); // 回傳 [2, 3]
回傳目前點池中的點數。
PackedInt64Array get_point_ids() 🔗
回傳所有點 ID 的陣列。
PackedVector2Array get_point_path(from_id: int, to_id: int, allow_partial_path: bool = false) 🔗
回傳一個陣列,其中包含 AStar2D 在給定點之間找到的路徑中的點。陣列從路徑的起點到終點進行排序。
如果 from_id 點被停用,則回傳一個空陣列(即使 from_id == to_id)。
如果 from_id 點未被停用,沒有通往目標的有效路徑並且 allow_partial_path 為 true,則會回傳通往距離目標最近的可達點的路徑。
注意:該方法不是執行緒安全的,同一時間只能有一個 Thread 使用。請考慮使用 Mutex 來確保執行緒獨佔存取,避免競態條件。
另外,如果 allow_partial_path 為 true 並且 to_id 處於停用狀態,搜尋耗時可能異常地大。
Vector2 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 🔗
檢查指定點在尋路時是否被停用;預設所有點均啟用。
自點池中移除與指定 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: Vector2) 🔗
為具有指定 id 的點設定新位置 position。
void set_point_weight_scale(id: int, weight_scale: float) 🔗
為具有指定 id 的點設定 weight_scale。在計算從鄰近點移動至此點之線段的總代價時,會把 weight_scale 乘上 _compute_cost() 的結果。