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...

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

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