AStar3D

Un'implementazione di A* per trovare il percorso più breve tra due vertici su un grafico collegato nello spazio 3D.

Descrizione

A* (A star) è un algoritmo informatico utilizzato per le ricerche di percorsi e l'attraversamento di grafi, ovvero il processo di tracciare brevi percorsi tra vertici (punti) che passano per un determinato insieme di spigoli (segmenti). È ampiamente utilizzato grazie alle sue prestazioni e alla sua precisione. L'implementazione di A* di Godot utilizza punti nello spazio 3D e distanze euclidee per impostazione predefinita.

È necessario aggiungere manualmente i punti con add_point() e creare manualmente i segmenti con connect_points(). Una volta fatto, è possibile verificare se esiste un percorso tra due punti con la funzione are_points_connected(), ottenere un percorso contenente indici con get_id_path() o uno contenente coordinate effettive con get_point_path().

È anche possibile utilizzare distanze non euclidee. Per farlo, è necessario creare uno script che estenda AStar3D e sovrascriva i metodi _compute_cost() e _estimate_cost(). Entrambi dovrebbero accettare due ID punto e restituire la distanza tra i punti corrispondenti.

Esempio: Usa la distanza di Manhattan invece della distanza euclidea:

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() dovrebbe restituire un limite inferiore della distanza, ovvero _estimate_cost(u, v) <= _compute_cost(u, v). Questo serve come suggerimento per l'algoritmo, poiché il metodo personalizzato _compute_cost() potrebbe richiedere un'elaborazione complessa. In caso contrario, assicurarsi che _estimate_cost() restituisca lo stesso valore di _compute_cost() per fornire all'algoritmo le informazioni più accurate.

Se sono utilizzati i metodi predefiniti _estimate_cost() e _compute_cost(), o se il metodo _estimate_cost() fornito restituisce un limite inferiore del costo, i percorsi restituiti da A* saranno quelli con il costo più basso. In questo caso, il costo di un percorso è uguale alla somma dei risultati di _compute_cost() di tutti i segmenti del percorso, moltiplicati per i valori di weight_scale dei punti finali dei rispettivi segmenti. Se sono utilizzati i metodi predefiniti, e i valori di weight_scale di tutti i punti sono impostati su 1.0, questo è uguale alla somma delle distanze euclidee di tutti i segmenti del percorso.

Proprietà

bool

neighbor_filter_enabled

false

Metodi

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)

Descrizioni delle proprietà

bool neighbor_filter_enabled = false 🔗

void set_neighbor_filter_enabled(value: bool)
bool is_neighbor_filter_enabled()

Se true abilita il filtraggio dei vicini tramite _filter_neighbor().

Descrizioni dei metodi

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

Chiamato quando si calcola il costo tra due punti collegati.

Si noti che questa funzione è nascosta nella classe predefinita AStar3D.

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

Chiamato quando si stima il costo tra un punto e il punto finale del percorso.

Si noti che questa funzione è nascosta nella classe predefinita AStar3D.

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

Chiamato quando il punto adiacente entra in elaborazione e se neighbor_filter_enabled è true. Se viene restituito true, il punto non sarà elaborato.

Si noti che questa funzione è nascosta nella classe predefinita AStar3D.

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

Aggiunge un nuovo punto nella posizione specificata con l'identificatore specificato. id deve essere uguale o superiore a 0 e weight_scale deve essere uguale o superiore a 0,0.

weight_scale viene moltiplicato per il risultato di _compute_cost() quando si determina il costo complessivo del viaggio attraverso un segmento da un punto vicino a questo punto. Pertanto, a parità di condizioni, l'algoritmo preferisce i punti con weight_scale più bassi per formare un percorso.

var astar = AStar3D.new()
astar.add_point(1, Vector3(1, 0, 0), 4) # Aggiunge il punto (1, 0, 0) con weight_scale 4 e id 1

var astar = new AStar3D();
astar.AddPoint(1, nuovo Vector3(1, 0, 0), 4); // Aggiunge il punto (1, 0, 0) con weight_scale 4 e id 1

Se esiste già un punto per l'id specificato, la sua posizione e la sua scala di peso vengono aggiornate ai valori specificati.

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

Restituisce se i due punti indicati sono collegati direttamente da un segmento. Se bidirectional è false, restituisce se il movimento da id a to_id è possibile attraverso questo segmento.

void clear() 🔗

Cancella tutti i punti e i segmenti.

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

Crea un segmento tra i punti specificati. Se bidirectional è false, è consentito solo il movimento da id a to_id, non la direzione opposta.

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 il segmento tra i punti indicati. Se bidirectional è false, solo il movimento da id a to_id è impedito, e un segmento unidirezionale può rimanere.

int get_available_point_id() const 🔗

Restituisce il prossimo disponibile ID di punto senza alcun punto ad esso associato.

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

Restituisce l'ID del punto più vicino a to_position, facoltativamente prendendo in considerazione i punti disabilitati. Restituisce -1 se non ci sono punti nella pool dei punti.

Nota: Se diversi punti sono i più vicini a to_position, quello con l'ID più piccolo sarà restituito, garantendo un risultato deterministico.

Vector3 get_closest_position_in_segment(to_position: Vector3) const 🔗

Restituisce la posizione più vicina a to_position che si trova all'interno di un segmento tra due punti collegati.

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)

Il risultato è nel segmento che va da y = 0 a y = 5. È la posizione più vicina nel segmento al punto specificato.

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

Restituisce un array con gli ID dei punti che formano il percorso trovato da AStar3D tra i punti indicati. L'array è ordinato dal punto iniziale al punto finale del percorso.

Se non c'è un percorso valido per la destinazione, e allow_partial_path è true, restituisce un percorso al punto più vicino alla destinazione che può essere raggiunto.

Nota: quando allow_partial_path è true e to_id è disabilitato, la ricerca potrebbe richiedere un tempo insolitamente lungo per essere completata.

var astar = AStar3D.new()
astar.add_point(1, Vector3(0, 0, 0))
astar.add_point(2, Vector3(0, 1, 0), 1) # Il peso predefinito è 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) # Restituisce [1, 2, 3]

var astar = new AStar3D();
astar.AddPoint(1, new Vector3(0, 0, 0));
astar.AddPoint(2, new Vector3(0, 1, 0), 1); // Il peso predefinito è 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); // Restituisce [1, 2, 3]

Se si cambia il peso a 3 per il punto 2, allora il risultato sarà [1, 4, 3] invece, poiché adesso anche se la distanza è più lunga, è "più facile" arrivare attraverso il punto 4 che attraverso il punto 2.

int get_point_capacity() const 🔗

Restituisce la capacità della struttura che sostiene i punti, utile in combinazione con reserve_space().

PackedInt64Array get_point_connections(id: int) 🔗

Restituisce un array con gli ID dei punti che formano la connessione con il punto indicato.

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 🔗

Restituisce il numero di punti attualmente nell'insieme dei punti.

PackedInt64Array get_point_ids() 🔗

Restituisce un array di tutti gli ID dei punti.

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

Restituisce un array con i punti che sono presenti nel percorso trovato da AStar3D tra i punti indicati. L'array è ordinato dal punto iniziale al punto finale del percorso.

Se non c'è un percorso valido per la destinazione, e allow_partial_path è true, restituisce un percorso al punto più vicino alla destinazione che può essere raggiunto.

Nota: Questo metodo non è thread-safe; si può usare solo da un singolo Thread alla volta. Si consiglia di utilizzare Mutex per garantire l'accesso esclusivo a un thread ed evitare accessi concorrenti.

Inoltre, quando allow_partial_path è true e to_id è disabilitato, la ricerca potrebbe richiedere un tempo insolitamente lungo per essere completata.

Vector3 get_point_position(id: int) const 🔗

Restituisce la posizione del punto associato all'id fornito.

float get_point_weight_scale(id: int) const 🔗

Restituisce la scala di peso del punto associato all'id fornito.

bool has_point(id: int) const 🔗

Restituisce se esiste un punto associato all'id fornito.

bool is_point_disabled(id: int) const 🔗

Restituisce se un punto è disabilitato o no per il rilevamento del percorso. Per impostazione predefinita, tutti i punti sono abilitati.

void remove_point(id: int) 🔗

Rimuove il punto associato all'id fornito dall'insieme di punti.

void reserve_space(num_nodes: int) 🔗

Riserva internamente lo spazio per il numero di punti num_nodes, utile se si sta aggiungendo un gran numero di punti conosciuti alla volta, come punti su una griglia.

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

Disabilita o abilita il punto specificato per il rilevamento del percorso. Utile per creare un ostacolo temporaneo.

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

Imposta la posizione position per il punto con l'id fornito.

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

Imposta la scala del peso (weight_scale) per il punto con l'id fornito. weight_scale è moltiplicato per il risultato di _compute_cost() quando si determina il costo complessivo di viaggiare attraverso un segmento da un punto vicino a questo punto.