AStarGrid2D

Наследует: RefCounted < Object

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

Описание

AStarGrid2D — это вариант AStar2D, который специализирован для частичных 2D-сеток. Он проще в использовании, поскольку не требует ручного создания точек и их соединения. Этот класс также поддерживает несколько типов эвристик, режимы для диагонального перемещения и режим прыжка для ускорения вычислений.

Чтобы использовать 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))) # Prints [(0, 0), (1, 1), (2, 2), (3, 3), (3, 4)]
print(astar_grid.get_point_path(Vector2i(0, 0), Vector2i(3, 4))) # Prints [(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))); // Prints [(0, 0), (1, 1), (2, 2), (3, 3), (3, 4)]
GD.Print(astarGrid.GetPointPath(Vector2I.Zero, new Vector2I(3, 4))); // Prints [(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

Евклидова эвристика (Euclidean heuristic), используемая для поиска пути, по следующей формуле:

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

Примечание: Это также внутренняя эвристика, используемая в AStar3D и AStar2D по умолчанию (с включением возможной координаты оси z).

Heuristic HEURISTIC_MANHATTAN = 1

Manhattan heuristic для использования при поиске пути с использованием следующей формулы:

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

Примечание: Эта эвристика предназначена для использования с 4-сторонними ортогональными движениями, обеспечиваемыми установкой dialog_mode на DIAGONAL_MODE_NEVER.

Heuristic HEURISTIC_OCTILE = 2

Эвристика Octile, используемая для поиска пути, использует следующую формулу:

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

Heuristic HEURISTIC_CHEBYSHEV = 3

Chebyshev heuristic для использования при поиске пути с использованием следующей формулы:

dx = abs(to_id.x - from_id.x)
dy = abs(to_id.y - from_id.y)
result = 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 между заданными точками. Массив упорядочен от начальной точки до конечной точки пути.

Если параметр from_id point отключен, возвращает пустой массив (даже если from_id == to_id).

Если параметр from_id point не отключен, то нет допустимого пути к цели, и allow_partial_path имеет значение true, возвращает путь к ближайшей к цели точке, до которой можно добраться.

Примечание: Когда allow_partial_path имеет значение true и to_id имеет значение solid, поиск может занять необычно много времени.

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

Возвращает массив словарей с данными точек (id: Vector2i, position: Vector2, solid: bool, weight_scale: float) в области .

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

Возвращает массив точек, находящихся на пути, найденном с помощью AStarGrid2D между заданными точками. Массив упорядочен от начальной точки до конечной точки пути.

Если from_id point отключено, возвращает пустой массив (даже если from_id == to_id).

Если from_id point не отключено, то нет допустимого пути к цели, и allow_partial_path равно true, возвращает путь к точке, ближайшей к цели, до которой можно добраться.

Примечание: Этот метод не является потокобезопасным; его можно использовать только из одного потока одновременно. Рекомендуется использовать Mutex для обеспечения эксклюзивного доступа к одному потоку во избежание состояний гонки.

Кроме того, когда allow_partial_path равно true и to_id равно solid, поиск может занять необычно много времени.

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. Эквивалентно 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, если это так и это необходимо вызвать.

Примечание: Все данные точек (твердость и шкала веса) будут очищены.