AStar2D

Успадковує: RefCounted < Object

Реалізація A* для пошуку найкоротшого шляху між двома вершинами на зв’язному графі в 2D-просторі.

Опис

Реалізація алгоритму A*, який використовується для пошуку найкоротшого шляху між двома вершинами на зв’язному графі у 2D-просторі.

Дивіться AStar3D для детальнішого пояснення використання цього класу. AStar2D — це оболонка для AStar3D, яка забезпечує 2D-координати.

Посібники

Навігація на основі сітки з AStarGrid2D Демонстрація

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

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 🔗

Викликається, коли neighborhood входить в обробку, і якщо 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 для формування шляху.

   [gdscript]
   var astar = AStar2D.new()
   astar.add_point(1, Vector2(1, 0), 4) # Додає точку (1, 0) з weight_scale 4 та id 1
   [/gdscript]
   [csharp]
   var astar = new AStar2D();
   astar.AddPoint(1, new Vector2(1, 0), 4); // Додає точку (1, 0) з weight_scale 4 та id 1
   [/csharp][/codeblocks]

Якщо для заданого [param 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, а не у зворотному напрямку.

[gdscript]
var astar = AStar2D.new()
astar.add_point(1, Vector2(1, 1))
astar.add_point(2, Vector2(0, 5))
astar.connect_points(1, 2, false)
[/gdscript]
[csharp]
var astar = new AStar2D();
astar.AddPoint(1, new Vector2(1, 1));
astar.AddPoint(2, new Vector2(0, 5));
astar.ConnectPoints(1, 2, false);
[/csharp][/codeblocks]

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

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

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

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 між заданими точками. Масив упорядковується від початкової до кінцевої точки шляху.

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

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

var liner = 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]

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

int get_point_capacity() const 🔗

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

PackedInt64Array get_point_connections(id: int) 🔗

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

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

var neighbours = 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]

int get_point_count() const 🔗

Повертає поточну кількість балів у пулі балів.

PackedInt64Array get_point_ids() 🔗

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

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

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

Якщо немає дійсного шляху до цілі, і 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) 🔗

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

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

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