AStarGrid2D

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

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

Опис

AStarGrid2D — це варіант AStar2D, який спеціалізується на часткових двовимірних сітках. Його простіше використовувати, оскільки не потрібно вручну створювати точки та з’єднувати їх разом. Цей клас також підтримує кілька типів евристик, режими діагонального переміщення та режим стрибків для прискорення обчислень.

Щоб використовувати AStarGrid2D, вам потрібно лише встановити region сітки, за бажанням cell_size, а потім викликати метод update():

var astar_grid = AStarGrid2D.new()
astar_grid.region = Rect2i(0, 0, 32, 32)
astar_grid.cell_size = Vector2(16, 16)
astar_grid.update()
print(astar_grid.get_id_path(Vector2i(0, 0), Vector2i(3, 4))) # друкує (0, 0), (1, 1), (2, 2), (3, 3), (3, 4)
print(astar_grid.get_point_path(Vector2i(0, 0), Vector2i(3, 4))) # друкує (0, 0), (16, 16), (32, 32), (48, 48), (48, 64)

AStarGrid2D astarGrid = new AStarGrid2D();
astarGrid.Region = new Rect2I(0, 0, 32, 32);
astarGrid.CellSize = new Vector2I(16, 16);
astarGrid.Update();
GD.Print(astarGrid.GetIdPath(Vector2I.Zero, new Vector2I(3, 4))); // виводить (0, 0), (1, 1), (2, 2), (3, 3), (3, 4)
GD.Print(astarGrid.GetPointPath(Vector2I.Zero, new Vector2I(3, 4))); // виводить (0, 0), (16, 16), (32, 32), (48, 48), (48, 64)

Щоб видалити точку з сітки пошуку контурів, її потрібно встановити як «суцільну» за допомогою set_point_solid().

Посібники

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

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

CellShape	cell_shape	`0`
Vector2	cell_size	`Vector2(1, 1)`
Heuristic	default_compute_heuristic	`0`
Heuristic	default_estimate_heuristic	`0`
DiagonalMode	diagonal_mode	`0`
bool	jumping_enabled	`false`
Vector2	offset	`Vector2(0, 0)`
Rect2i	region	`Rect2i(0, 0, 0, 0)`
Vector2i	size	`Vector2i(0, 0)`

Методи

float	_compute_cost(from_id: Vector2i, to_id: Vector2i) virtual const
float	_estimate_cost(from_id: Vector2i, end_id: Vector2i) virtual const
void	clear()
void	fill_solid_region(region: Rect2i, solid: bool = true)
void	fill_weight_scale_region(region: Rect2i, weight_scale: float)
Array[Vector2i]	get_id_path(from_id: Vector2i, to_id: Vector2i, allow_partial_path: bool = false)
Array[Dictionary]	get_point_data_in_region(region: Rect2i) const
PackedVector2Array	get_point_path(from_id: Vector2i, to_id: Vector2i, allow_partial_path: bool = false)
Vector2	get_point_position(id: Vector2i) const
float	get_point_weight_scale(id: Vector2i) const
bool	is_dirty() const
bool	is_in_bounds(x: int, y: int) const
bool	is_in_boundsv(id: Vector2i) const
bool	is_point_solid(id: Vector2i) const
void	set_point_solid(id: Vector2i, solid: bool = true)
void	set_point_weight_scale(id: Vector2i, weight_scale: float)
void	update()

Переліки

enum Heuristic: 🔗

Heuristic HEURISTIC_EUCLIDEAN = 0

Евклідова евристика, яка використовуватиметься для пошуку шляху за такою формулою:

dx = abs(to_id.x - from_id.x)
dy = abs(to_id.y - from_id.y)
resuit = sqrt(dx * dx + dy * dy)

Примітка: Це також внутрішня евристика, яка використовується в AStar3D і AStar2D за замовчуванням (із включенням можливої координати осі z).

Heuristic HEURISTIC_MANHATTAN = 1

Манхеттенська евристика, яка використовуватиметься для пошуку шляху за такою формулою:

dx = abs(to_id.x - from_id.x)
dy = abs(to_id.y - from_id.y)
resuit = dx + dy

Примітка: Ця евристика призначена для використання з 4-сторонніми ортогональними рухами, які забезпечуються встановленням diagonal_mode значення DIAGONAL_MODE_NEVER.

Heuristic HEURISTIC_OCTILE = 2

Октильна евристика для пошуку шляху за такою формулою:

dx = abs(to_id.x - from_id.x)
dy = abs(to_id.y - from_id.y)
f = sqrt(2) - 1
resuit = (dx < dy) ? f * dx + dy : f * dy + dx;

Heuristic HEURISTIC_CHEBYSHEV = 3

Евристика Чебишева, яка буде використовуватися для пошуку шляху за такою формулою:

dx = abs(to_id.x - from_id.x)
dy = abs(to_id.y - from_id.y)
resuit = max(dx, dy)

Heuristic HEURISTIC_MAX = 4

Представляє розмір переліку Heuristic.

enum DiagonalMode: 🔗

DiagonalMode DIAGONAL_MODE_ALWAYS = 0

Алгоритм пошуку шляху ігноруватиме суцільні сусіди навколо цільової комірки та допускатиме проходження за допомогою діагоналей.

DiagonalMode DIAGONAL_MODE_NEVER = 1

Алгоритм пошуку шляху ігноруватиме всі діагоналі, а шлях завжди буде ортогональним.

DiagonalMode DIAGONAL_MODE_AT_LEAST_ONE_WALKABLE = 2

Алгоритм пошуку шляху уникатиме використання діагоналей, якщо принаймні дві перешкоди розміщені навколо сусідніх комірок конкретного сегмента шляху.

DiagonalMode DIAGONAL_MODE_ONLY_IF_NO_OBSTACLES = 3

Алгоритм пошуку шляху уникає використання діагоналей, якщо навколо сусідніх комірок певного сегмента шляху є будь-яка перешкода.

DiagonalMode DIAGONAL_MODE_MAX = 4

Представляє розмір переліку DiagonalMode.

enum CellShape: 🔗

CellShape CELL_SHAPE_SQUARE = 0

Форма клітини прямокутна.

CellShape CELL_SHAPE_ISOMETRIC_RIGHT = 1

Ромбова форма комірки (для ізометричного вигляду). Розташування координат комірки, де горизонтальна вісь йде вгору-вправо, а вертикальна – вниз-вправо.

CellShape CELL_SHAPE_ISOMETRIC_DOWN = 2

Ромбова форма комірки (для ізометричного вигляду). Розташування координат комірки, де горизонтальна вісь йде вниз-праворуч, а вертикальна – вниз-ліворуч.

CellShape CELL_SHAPE_MAX = 3

Представляє розмір переліку CellShape.

Описи властивостей

CellShape cell_shape = 0 🔗

void set_cell_shape(value: CellShape)
CellShape get_cell_shape()

Форма клітини. Впливає на те, як позиції розміщуються в сітці. Якщо змінено, потрібно викликати update() перед пошуком наступного шляху.

Vector2 cell_size = Vector2(1, 1) 🔗

void set_cell_size(value: Vector2)
Vector2 get_cell_size()

Розмір клітинки точки, яка буде застосована для обчислення кінцевої позиції точки, яку повертає get_point_path(). Якщо змінено, потрібно викликати update() перед пошуком наступного шляху.

Heuristic default_compute_heuristic = 0 🔗

void set_default_compute_heuristic(value: Heuristic)
Heuristic get_default_compute_heuristic()

Стандартний Heuristic, який використовуватиметься для обчислення вартості між двома точками, якщо _compute_cost() не перевизначено.

Heuristic default_estimate_heuristic = 0 🔗

void set_default_estimate_heuristic(value: Heuristic)
Heuristic get_default_estimate_heuristic()

Стандартний Heuristic, який використовуватиметься для обчислення вартості між точкою та кінцевою точкою, якщо _estimate_cost() не було замінено.

DiagonalMode diagonal_mode = 0 🔗

void set_diagonal_mode(value: DiagonalMode)
DiagonalMode get_diagonal_mode()

Спеціальний режим DiagonalMode, який змусить шлях уникати або приймати вказані діагоналі.

bool jumping_enabled = false 🔗

void set_jumping_enabled(value: bool)
bool is_jumping_enabled()

Вмикає або вимикає стрибки для пропуску проміжних точок і прискорює алгоритм пошуку.

Примітка: Наразі ввімкнення вимикає врахування масштабування ваги під час пошуку шляху.

Vector2 offset = Vector2(0, 0) 🔗

void set_offset(value: Vector2)
Vector2 get_offset()

Зміщення сітки, яке буде застосовано для обчислення результуючої позиції точки, яку повертає get_point_path(). Якщо змінено, потрібно викликати update() перед пошуком наступного шляху.

Rect2i region = Rect2i(0, 0, 0, 0) 🔗

void set_region(value: Rect2i)
Rect2i get_region()

Область клітинок сітки, доступна для пошуку шляху. Якщо змінено, потрібно викликати update() перед пошуком наступного шляху.

Vector2i size = Vector2i(0, 0) 🔗

void set_size(value: Vector2i)
Vector2i get_size()

Застаріло: Use region instead.

Розмір сітки (кількість комірок розміром cell_size на кожній осі). Якщо змінено, потрібно викликати update() перед пошуком наступного шляху.

Описи методів

float _compute_cost(from_id: Vector2i, to_id: Vector2i) virtual const 🔗

Викликається під час обчислення вартості між двома з’єднаними точками.

Зауважте, що ця функція прихована в класі AStarGrid2D за замовчуванням.

float _estimate_cost(from_id: Vector2i, end_id: Vector2i) virtual const 🔗

Викликається під час розрахунку вартості між двома з’єднаними точками.

Зверніть увагу, що ця функція прихована в класі AStarGrid2D для замовчування.

void clear() 🔗

Очищає сітку та встановлює region на Rect2i(0, 0, 0, 0).

void fill_solid_region(region: Rect2i, solid: bool = true) 🔗

Заповнює задану область region у сітці вказаним значенням для суцільного прапора.

Примітка: Виклик update() не потрібен після виклику цієї функції.

void fill_weight_scale_region(region: Rect2i, weight_scale: float) 🔗

Заповнює задану область region у сітці вказаним значенням для шкали ваги.

Примітка: Виклик update() не потрібен після виклику цієї функції.

Array[Vector2i] get_id_path(from_id: Vector2i, to_id: Vector2i, allow_partial_path: bool = false) 🔗

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

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

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

Array[Dictionary] get_point_data_in_region(region: Rect2i) const 🔗

Повертає масив словників із точковими даними (id: Vector2i, position: Vector2, solid: bool, weight_scale: float) у області param.

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

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

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

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

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

Vector2 get_point_position(id: Vector2i) const 🔗

Повертає положення точки, пов’язаної з заданим id.

float get_point_weight_scale(id: Vector2i) const 🔗

Повертає шкалу ваги точки, пов’язаної з заданим id.

bool is_dirty() const 🔗

Вказує на те, що параметри сітки було змінено, і потрібно викликати update().

bool is_in_bounds(x: int, y: int) const 🔗

Повертає true, якщо x і y є дійсною координацією сітки (id), тобто якщо він знаходиться всередині region. region.has_point(Vector2i(x, y).

bool is_in_boundsv(id: Vector2i) const 🔗

Повертаємо true, якщо вектор id є вірною сітчастою координацією, тобто якщо він знаходиться всередині члена. region.has_point(id).

bool is_point_solid(id: Vector2i) const 🔗

Повертає true, якщо для точки вимкнено пошук шляху. За замовчуванням усі точки ввімкнено.

void set_point_solid(id: Vector2i, solid: bool = true) 🔗

Вимикає або вмикає вказану точку для пошуку шляху. Корисно для створення перешкод. За замовчуванням усі точки ввімкнено.

Примітка: Виклик update() не потрібен після виклику цієї функції.

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

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

Примітка: Виклик update() не потрібен після виклику цієї функції.

void update() 🔗

Оновлює внутрішній стан сітки відповідно до параметрів, щоб підготувати її до пошуку шляху. Потрібно викликати, якщо такі параметри, як region, cell_size або offset змінюються. is_dirty() поверне true, якщо це так і це потрібно викликати.

**Примітка: ** Усі дані точок (твердість і шкала ваги) буде видалено.