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() при определении общей стоимости перемещения по сегменту от соседней точки до этой точки.