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

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