AStar3D

Una implementación de A* para encontrar el camino más corto entre dos vértices en un grafo conectado en un espacio 3D.

Descripción

A* (A Star) es un algoritmo informático utilizado en la búsqueda de rutas y el recorrido de grafos, el proceso de trazar rutas cortas entre vértices (puntos), pasando por un conjunto dado de aristas (segmentos). Goza de un uso generalizado debido a su rendimiento y precisión. La implementación de A* de Godot utiliza puntos en el espacio 3D y distancias euclidianas por defecto.

Debes añadir puntos manualmente con add_point() y crear segmentos manualmente con connect_points(). Una vez hecho, puedes comprobar si hay una ruta entre dos puntos con la función are_points_connected(), obtener una ruta que contenga índices con get_id_path(), o una que contenga coordenadas reales con get_point_path().

También es posible utilizar distancias no euclidianas. Para ello, crea un script que extienda AStar3D y sobrescribe los métodos _compute_cost() y _estimate_cost(). Ambos deben tomar dos ID de puntos y devolver la distancia entre los puntos correspondientes.

Ejemplo: Usa la distancia Manhattan en lugar de la distancia euclidiana:

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() debería devolver un límite inferior de la distancia, es decir, _estimate_cost(u, v) <= _compute_cost(u, v). Esto sirve como una pista para el algoritmo porque el _compute_cost() personalizado podría ser computacionalmente pesado. Si este no es el caso, haz que _estimate_cost() devuelva el mismo valor que _compute_cost() para proporcionar al algoritmo la información más precisa.

Si se utilizan los métodos predeterminados _estimate_cost() y _compute_cost(), o si el método _estimate_cost() proporcionado devuelve un límite inferior del costo, entonces las rutas devueltas por A* serán las rutas de menor costo. Aquí, el costo de una ruta es igual a la suma de los resultados de _compute_cost() de todos los segmentos en la ruta multiplicada por las weight_scales de los puntos finales de los segmentos respectivos. Si se utilizan los métodos predeterminados y las weight_scales de todos los puntos se establecen en 1.0, entonces esto es igual a la suma de las distancias euclidianas de todos los segmentos en la ruta.

Propiedades

bool

neighbor_filter_enabled

false

Métodos

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)

Descripciones de Propiedades

bool neighbor_filter_enabled = false 🔗

void set_neighbor_filter_enabled(value: bool)
bool is_neighbor_filter_enabled()

Si es true, habilita el filtrado de vecinos a través de _filter_neighbor().

Descripciones de Métodos

float _compute_cost(from_id: int, to_id: int) virtual const 🔗

Se llama al calcular el coste entre dos puntos conectados.

Ten en cuenta que esta función está oculta en la clase AStar3D predeterminada.

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

Se llama al estimar el coste entre un punto y el punto final del camino.

Ten en cuenta que esta función está oculta en la clase AStar3D predeterminada.

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

Se llama cuando un punto vecino entra en el procesamiento y si neighbor_filter_enabled es true. Si se devuelve true, el punto no se procesará.

Ten en cuenta que esta función está oculta en la clase AStar3D predeterminada.

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

Añade un nuevo punto en la posición dada con el identificador dado. El id debe ser 0 o mayor, y el weight_scale debe ser 0.0 o mayor.

El weight_scale se multiplica por el resultado de _compute_cost() al determinar el coste total de viajar a través de un segmento desde un punto vecino a este punto. Por lo tanto, en igualdad de condiciones, el algoritmo prefiere los puntos con weight_scales más bajos para formar un camino.

var astar = AStar3D.new()
astar.add_point(1, Vector3(1, 0, 0), 4) # Añade el punto (1, 0, 0) con weight_scale 4 e id 1

var astar = new AStar3D();
astar.AddPoint(1, new Vector3(1, 0, 0), 4); // Añade el punto (1, 0, 0) con weight_scale 4 e id 1

Si ya existe un punto para el id dado, su posición y escala de peso se actualizan a los valores dados.

bool are_points_connected(id: int, to_id: int, bidirectional: bool = true) const 🔗

Devuelve si los dos puntos dados están directamente conectados por un segmento. Si bidirectional es false, devuelve si el movimiento desde id a to_id es posible a través de este segmento.

void clear() 🔗

Limpia todos los puntos y segmentos.

void connect_points(id: int, to_id: int, bidirectional: bool = true) 🔗

Crea un segmento entre los puntos dados. Si bidirectional es false, solo el movimiento desde id hasta to_id está permitido, no en la dirección inversa.

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

Elimina el segmento entre los puntos dados. Si bidirectional es false, solo el movimiento desde id a to_id se impide, y un segmento unidireccional posiblemente permanece.

int get_available_point_id() const 🔗

Devuelve el punto de Ide proximo disponible con ningun punto asociado a el.

int get_closest_point(to_position: Vector3, include_disabled: bool = false) const 🔗

Devuelve el ID del punto más cercano a to_position, opcionalmente teniendo en cuenta los puntos desactivados. Devuelve -1 si no hay puntos en el grupo de puntos.

Nota: Si varios puntos son los más cercanos a to_position, se devolverá el que tenga el ID más pequeño, lo que garantiza un resultado determinista.

Vector3 get_closest_position_in_segment(to_position: Vector3) const 🔗

Devuelve la posición más cercana a to_position que reside dentro de un segmento entre dos puntos conectados.

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)) # Devuelve (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)); // Devuelve (0, 3, 0)

El resultado está en el segmento que va desde y = 0 hasta y = 5. Es la posición más cercana en el segmento al punto dado.

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

Devuelve un array con los ID de los puntos que forman el camino encontrado por AStar3D entre los puntos dados. El array está ordenado desde el punto de inicio hasta el punto final del camino.

Si no hay un camino válido hacia el objetivo, y allow_partial_path es true, devuelve un camino al punto más cercano al objetivo que se pueda alcanzar.

Nota: Cuando allow_partial_path es true y to_id está deshabilitado, la búsqueda puede tardar mucho tiempo en terminar.

var astar = AStar3D.new()
astar.add_point(1, Vector3(0, 0, 0))
astar.add_point(2, Vector3(0, 1, 0), 1) # El peso por defecto es 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) # Returns [1, 2, 3]

var astar = new AStar3D();
astar.AddPoint(1, new Vector3(0, 0, 0));
astar.AddPoint(2, new Vector3(0, 1, 0), 1); // Default weight is 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); // Returns [1, 2, 3]

Si tu cambias el peso del segundo punto a 3, entonces el resultado será [1, 4, 3] en su lugar, porque ahora, aunque la distancia sea mayor, es "más fácil" pasar por el punto 4 que por el punto 2.

int get_point_capacity() const 🔗

Devuelve la capacidad de la estructura que respalda los puntos, útil en conjunto con reserve_space().

PackedInt64Array get_point_connections(id: int) 🔗

Devuelve un array con los ID de los puntos que forman la conneccion con el punto dado.

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 vecinos = astar.get_point_connections(1) # Devuelve [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[] vecinos = astar.GetPointConnections(1); // Devuelve [2, 3]

int get_point_count() const 🔗

Devuelve el numero de puntos actualmente en el grupo(pool) de puntos.

PackedInt64Array get_point_ids() 🔗

Devuelve un array de todos los ID de los puntos.

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

Devuelve un array con los puntos que están en la ruta encontrada por AStar3D entre los puntos dados. El array se ordena desde el punto de inicio hasta el punto final de la ruta.

Si no hay una ruta válida al destino, y allow_partial_path es true, devuelve una ruta al punto más cercano al destino que se puede alcanzar.

Nota: Este método no es seguro para hilos; solo se puede usar desde un único Thread a la vez. Considera usar Mutex para asegurar el acceso exclusivo a un hilo para evitar condiciones de carrera.

Adicionalmente, cuando allow_partial_path es true y to_id está deshabilitado, la búsqueda puede tardar un tiempo inusualmente largo en finalizar.

Vector3 get_point_position(id: int) const 🔗

Devuelve la posición del punto asociado con el id dado.

float get_point_weight_scale(id: int) const 🔗

Devuelve la escala de peso del punto asociado con el id dado.

bool has_point(id: int) const 🔗

Devuelve si existe un punto asociado con el id dado.

bool is_point_disabled(id: int) const 🔗

Devuelve si un punto esta deshabilitado or no para el buscador de rutas. Por defecto, todos los puntos estan habilitados.

void remove_point(id: int) 🔗

Elimina el punto asociado con el id dado del grupo de puntos.

void reserve_space(num_nodes: int) 🔗

Reserva espacio internamente para num_nodes puntos. Útil si vas a añadir un número grande conocido de puntos a la vez, como puntos en una cuadrícula.

void set_point_disabled(id: int, disabled: bool = true) 🔗

Deshabilita o habilita el punto especificado para el buscador de rutas. Util para crear obstaculos temporales.

void set_point_position(id: int, position: Vector3) 🔗

Establece la position para el punto con el id dado.

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

Establece el weight_scale para el punto con el id dado. El weight_scale se multiplica por el resultado de _compute_cost() al determinar el coste total de viajar a través de un segmento desde un punto vecino a este punto.