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

AStar2D

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

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

Описание

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

Более подробное объяснение использования этого класса см. в AStar3D. AStar2D — это оболочка для AStar3D, которая обеспечивает двумерные координаты.

Обучающие материалы

Демонстрация 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 🔗

Вызывается, когда соседний элемент начинает обработку, и если 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 для формирования пути.

var astar = AStar2D.new()
astar.add_point(1, Vector2(1, 0), 4) # Adds the point (1, 0) with weight_scale 4 and id 1

var astar = new AStar2D();
astar.AddPoint(1, new Vector2(1, 0), 4); // Adds the point (1, 0) with weight_scale 4 and 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 = AStar2D.new()
astar.add_point(1, Vector2(1, 1))
astar.add_point(2, Vector2(0, 5))
astar.connect_points(1, 2, false)

var astar = new AStar2D();
astar.AddPoint(1, new Vector2(1, 1));
astar.AddPoint(2, new Vector2(0, 5));
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: 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)) # Returns (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)); // Returns (0, 3)

Результат находится в сегменте, который идет от y = 0 до y = 5. Это ближайшая позиция в сегменте к заданной точке.

PackedInt64Array get_id_path(from_id: int, to_id: int, 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 отключен, поиск может занять необычно много времени.

var astar = 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, true)
astar.connect_points(1, 3, true)

var neighbors = astar.get_point_connections(1) # Returns [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); // Returns [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 между заданными точками. Массив упорядочен от начальной точки до конечной точки пути.

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

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

Примечание: Этот метод не является потокобезопасным; его можно использовать только из одного потока одновременно. Рекомендуется использовать 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() при определении общей стоимости перемещения по сегменту от соседней точки до этой точки.