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.

AStar2D

繼承: RefCounted < Object

A* 的實作,可用於搜尋 2D 空間連通圖上兩頂點間的最短路徑。

說明

A* 演算法的實作,用於在 2D 空間連通圖上尋找兩頂點之間的最短路徑。

更完整的用法請參考 AStar3D。 AStar2D 為 AStar3D 的封裝,專門處理 2D 座標。

教學

屬性

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: Vector2, 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: Vector2, include_disabled: bool = false) const

Vector2

get_closest_position_in_segment(to_position: Vector2) 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()

PackedVector2Array

get_point_path(from_id: int, to_id: int, allow_partial_path: bool = false)

Vector2

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: Vector2)

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

如果為 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

若指定 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)

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)

此結果位於 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]

如果將第 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]

int get_point_count() const 🔗

回傳目前點池中的點數。


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 🔗

檢查指定點在尋路時是否被停用;預設所有點均啟用。


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

為具有指定 id 的點設定新位置 position。


void set_point_weight_scale(id: int, weight_scale: float) 🔗

為具有指定 id 的點設定 weight_scale。在計算從鄰近點移動至此點之線段的總代價時,會把 weight_scale 乘上 _compute_cost() 的結果。