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* для пошуку найкоротшого шляху між двома вершинами на зв’язному графі в тривимірному просторі.

Опис

A* (A star) — це комп’ютерний алгоритм, який використовується для пошуку шляху та обходу графа, процесу побудови коротких шляхів між вершинами (точками), що проходять через заданий набір ребер (сегментів). Він отримав широке застосування завдяки своїй продуктивності та точності. Реалізація Godot A* за замовчуванням використовує точки в 3D просторі та евклідові відстані.

Ви повинні додати точки вручну за допомогою add_point() і створити сегменти вручну за допомогою connect_points(). Після цього ви можете перевірити, чи існує шлях між двома точками за допомогою функції are_points_connected(), отримати шлях, що містить індекси, за допомогою get_id_path() або той, що містить фактичні координати, за допомогою get_point_path().

Також можна використовувати неевклідові відстані. Для цього створіть скрипт, який розширює AStar3D і перевизначте методи _compute_cost() і _estimate_cost(). Обидва мають брати два ідентифікатори точок і повертати відстань між відповідними точками.

Приклад: Використовуйте манхеттенську відстань замість евклідової відстані:

[gdscript]
class_name MyAStar3D
extends AStar3D

func _compute_cost(u, v):
    var u_pos = get_point_position(u)
    var v_pos = get_point_position(v)
    повернути 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)
[/gdscript]
[csharp]
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);
    }
}
[/csharp] [/codeblocks]

[method _estimate_cost] має повертати нижню межу відстані, тобто [code]_estimate_cost(u, v) <= _compute_cost(u, v)[/code]. Це слугує підказкою для алгоритму, оскільки спеціальний [method _compute_cost] може бути важким для обчислення. Якщо це не так, змусьте [method _estimate_cost] повертати те саме значення, що й [method _compute_cost], щоб надати алгоритму найточнішу інформацію.

Якщо використовуються методи за замовчуванням [method _estimate_cost] і [method _compute_cost] або якщо наданий метод [method _estimate_cost] повертає нижню межу вартості, тоді шляхи, які повертає A*, будуть шляхами з найнижчою вартістю. Тут вартість шляху дорівнює сумі результатів [method _compute_cost] усіх сегментів у шляху, помноженій на [code]weight_scale[/code] кінцевих точок відповідних сегментів. Якщо використовуються методи за замовчуванням і [code]weight_scale[/code]s усіх точок встановлено на [code]1.0[/code], тоді це дорівнює сумі евклідових відстаней усіх сегментів шляху.

Властивості

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

Якщо true, увімкнено фільтрацію сусідів за допомогою _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 🔗

Викликається, коли сусідня точка входить в обробку, і якщо neighbor_filter_enabled має значення true. Якщо повертається значення true, точка не буде оброблена.

Зверніть увагу, що ця функція прихована в класі 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 для формування шляху.

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 🔗

Повертає ідентифікатор наступної доступної точки без пов’язаної з нею точки.

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

Повертає ідентифікатор найближчої точки до to_position, необов’язково враховуючи вимкнені точки. Повертає -1, якщо в пулі балів немає балів.

Примітка: якщо кілька точок є найближчими до to_position, буде повернено ту з найменшим ідентифікатором, що гарантує детермінований результат.

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(новий 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) 🔗

Повертає масив з ідентифікаторами точок, які утворюють шлях, знайдений AStar3D між заданими точками. Масив упорядковується від початкової до кінцевої точки шляху.

Якщо точка from_id вимкнена, повертає порожній масив (навіть якщо from_id == to_id).

Якщо точка from_id не вимкнена, то немає дійсного шляху до цілі, а parum allow_partial_path є true, повертає шлях до точки, найближчої до цільового значення, яку можна досягти.

Примітка. Якщо allow_partial_path має значення true і to_id вимкнено, пошук може тривати надзвичайно довго.

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]

var astar = new AStar3D();
astar.AddPoint(1, new Vector3(0, 0, 0));
astar.AddPoint(2, new Vector3(0, 1, 0), 1); // Вага за замовчуванням — 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); // Повертає [1, 2, 3]

Якщо ви зміните вагу другої точки на 3, тоді результатом буде [1, 4, 3], тому що тепер, навіть якщо відстань більша, «легше» пройти через точку 4, ніж через точку 2.

int get_point_capacity() const 🔗

Повертає ємність структури, що підтримує точки, корисно в поєднанні з reserve_space().

PackedInt64Array get_point_connections(id: int) 🔗

Повертає масив з ідентифікаторами точок, які утворюють з’єднання з даною точкою.

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, істина)
astar.connect_points(1, 3, істина)

var neighbours = 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() 🔗

Повертає масив усіх ідентифікаторів точок.

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

Повертає масив із точками, які знаходяться на шляху, знайденому AStar3D між заданими точками. Масив упорядковується від початкової до кінцевої точки шляху.

Якщо точка from_id вимкнена, повертає порожній масив (навіть якщо from_id == to_id).

Якщо точка from_id не вимкнена, то немає дійсного шляху до цілі, а parum allow_partial_path є true, повертає шлях до точки, найближчої до цільового значення, яку можна досягти.

Примітка: Цей метод не є безпечним для потоків; його можна використовувати лише з одного Thread за певний час. Розгляньте можливість використання Mutex, щоб забезпечити ексклюзивний доступ до однієї теми та уникнути перегонів.

Крім того, коли 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) 🔗

Встановлює position для точки з указаним id.

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

Встановлює weight_scale для точки з указаним id. weight_scale множиться на результат _compute_cost() під час визначення загальної вартості подорожі по сегменту від сусідньої точки до цієї точки.