AStar3D

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

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

Описание

A* (звезда) — это компьютерный алгоритм, используемый в поиске пути и обходе графа, процессе построения коротких путей между вершинами (точками), проходящих через заданный набор ребер (сегментов). Он широко используется благодаря своей производительности и точности. Реализация Godot's A* по умолчанию использует точки в трехмерном пространстве и евклидовы расстояния.

Вы должны вручную добавлять точки с помощью add_point() и вручную создавать сегменты с помощью connect_points(). После этого вы можете проверить, есть ли путь между двумя точками, с помощью функции are_points_connected(), получить путь, содержащий индексы, с помощью get_id_path() или путь, содержащий фактические координаты, с помощью get_point_path().

Также возможно использовать неевклидовы расстояния. Для этого создайте скрипт, который расширяет AStar3D и переопределяет методы _compute_cost() и _estimate_cost(). Оба должны принимать два идентификатора точек и возвращать расстояние между соответствующими точками.

Пример: Используйте Манхэттенское (Manhattan) расстояние вместо евклидова расстояния:

class_name MyAStar3D
extends AStar3D

func _compute_cost(u, v):
    var u_pos = get_point_position(u)
    var v_pos = get_point_position(v)
    return abs(u_pos.x - v_pos.x) + abs(u_pos.y - v_pos.y) + abs(u_pos.z - v_pos.z)

func _estimate_cost(u, v):
    var u_pos = get_point_position(u)
    var v_pos = get_point_position(v)
    return abs(u_pos.x - v_pos.x) + abs(u_pos.y - v_pos.y) + abs(u_pos.z - v_pos.z)

using Godot;

[GlobalClass]
public partial class MyAStar3D : AStar3D
{
    public override float _ComputeCost(long fromId, long toId)
    {
        Vector3 fromPoint = GetPointPosition(fromId);
        Vector3 toPoint = GetPointPosition(toId);

        return Mathf.Abs(fromPoint.X - toPoint.X) + Mathf.Abs(fromPoint.Y - toPoint.Y) + Mathf.Abs(fromPoint.Z - toPoint.Z);
    }

    public override float _EstimateCost(long fromId, long toId)
    {
        Vector3 fromPoint = GetPointPosition(fromId);
        Vector3 toPoint = GetPointPosition(toId);
        return Mathf.Abs(fromPoint.X - toPoint.X) + Mathf.Abs(fromPoint.Y - toPoint.Y) + Mathf.Abs(fromPoint.Z - toPoint.Z);
    }
}

_estimate_cost() должен возвращать нижнюю границу расстояния, т. е. _estimate_cost(u, v) <= _compute_cost(u, v). Это служит подсказкой для алгоритма, поскольку пользовательский _compute_cost() может быть вычислительно интенсивным. Если это не так, заставьте _estimate_cost() возвращать то же значение, что и _compute_cost(), чтобы предоставить алгоритму наиболее точную информацию.

Если используются методы по умолчанию _estimate_cost() и _compute_cost() или если предоставленный метод _estimate_cost() возвращает нижнюю границу стоимости, то пути, возвращаемые A*, будут путями с наименьшей стоимостью. Здесь стоимость пути равна сумме результатов _compute_cost() всех сегментов в пути, умноженных на weight_scales конечных точек соответствующих сегментов. Если используются методы по умолчанию и weight_scales всех точек установлены на 1.0, то это равно сумме евклидовых расстояний всех сегментов в пути.

Свойства

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: Vector3, 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: Vector3, include_disabled: bool = false) const
Vector3	get_closest_position_in_segment(to_position: Vector3) 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()
PackedVector3Array	get_point_path(from_id: int, to_id: int, allow_partial_path: bool = false)
Vector3	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: Vector3)
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 🔗

Вызывается при вычислении стоимости между двумя соединенными точками.

Обратите внимание, что эта функция скрыта в классе по умолчанию AStar3D.

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

Вызывается при оценке стоимости между точкой и конечной точкой пути.

Обратите внимание, что эта функция скрыта в классе по умолчанию AStar3D.

bool _filter_neighbor(from_id: int, neighbor_id: int) virtual const 🔗

Вызывается, когда соседняя точка входит в обработку и если neighbor_filter_enabled имеет значение true. Если возвращается значение true, точка не будет обработана.

Обратите внимание, что эта функция скрыта в классе AStar3D по умолчанию.

void add_point(id: int, position: Vector3, weight_scale: float = 1.0) 🔗

Добавляет новую точку в указанной позиции с указанным идентификатором. id должен быть 0 или больше, а weight_scale должен быть 0.0 или больше.

weight_scale умножается на результат _compute_cost() при определении общей стоимости перемещения по сегменту от соседней точки до этой точки. Таким образом, при прочих равных условиях алгоритм предпочитает точки с меньшими weight_scale для формирования пути.

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

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

var astar = new AStar3D();
astar.AddPoint(1, new Vector3(1, 1, 0));
astar.AddPoint(2, new Vector3(0, 5, 0));
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: Vector3, include_disabled: bool = false) const 🔗

Возвращает идентификатор ближайшей точки к to_position, при необходимости принимая во внимание отключенные точки. Возвращает -1, если в пуле точек нет точек.

Примечание: Если несколько точек являются ближайшими к to_position, будет возвращена точка с наименьшим идентификатором, что гарантирует детерминированный результат.

Vector3 get_closest_position_in_segment(to_position: Vector3) const 🔗

Возвращает ближайшую позицию к to_position, которая находится внутри сегмента между двумя соединенными точками.

var astar = AStar3D.new()
astar.add_point(1, Vector3(0, 0, 0))
astar.add_point(2, Vector3(0, 5, 0))
astar.connect_points(1, 2)
var res = astar.get_closest_position_in_segment(Vector3(3, 3, 0)) # Returns (0, 3, 0)

var astar = new AStar3D();
astar.AddPoint(1, new Vector3(0, 0, 0));
astar.AddPoint(2, new Vector3(0, 5, 0));
astar.ConnectPoints(1, 2);
Vector3 res = astar.GetClosestPositionInSegment(new Vector3(3, 3, 0)); // Returns (0, 3, 0)

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

PackedInt64Array get_id_path(from_id: int, to_id: int, allow_partial_path: bool = false) 🔗

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

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

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

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

var astar = AStar3D.new()
astar.add_point(1, Vector3(0, 0, 0))
astar.add_point(2, Vector3(0, 1, 0), 1) # Вес по умолчанию равен 1.
astar.add_point(3, Vector3(1, 1, 0))
astar.add_point(4, Vector3(2, 0, 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 AStar3D();
astar.AddPoint(1, new Vector3(0, 0, 0));
astar.AddPoint(2, new Vector3(0, 1, 0), 1); // Вес по умолчанию равен 1.
astar.AddPoint(3, new Vector3(1, 1, 0));
astar.AddPoint(4, new Vector3(2, 0, 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 = AStar3D.new()
astar.add_point(1, Vector3(0, 0, 0))
astar.add_point(2, Vector3(0, 1, 0))
astar.add_point(3, Vector3(1, 1, 0))
astar.add_point(4, Vector3(2, 0, 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 AStar3D();
astar.AddPoint(1, new Vector3(0, 0, 0));
astar.AddPoint(2, new Vector3(0, 1, 0));
astar.AddPoint(3, new Vector3(1, 1, 0));
astar.AddPoint(4, new Vector3(2, 0, 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() 🔗

Возвращает массив всех идентификаторов точек.

PackedVector3Array get_point_path(from_id: int, to_id: int, allow_partial_path: bool = false) 🔗

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

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

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

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

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

Vector3 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: Vector3) 🔗

Устанавливает position для точки с указанным id.

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

Устанавливает weight_scale для точки с заданным id. weight_scale умножается на результат _compute_cost() при определении общей стоимости перемещения по сегменту от соседней точки до этой точки.