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

Eredita: RefCounted < Object

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 il punto from_id è disabilitato, restituisce un array vuoto (anche se from_id == to_id).

Se il punto from_id non è disabilitato, non esiste un percorso valido verso la destinazione e allow_partial_path è true, restituisce un percorso verso il 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 il punto from_id è disabilitato, restituisce un array vuoto (anche se from_id == to_id).

Se il punto from_id non è disabilitato, non esiste un percorso valido verso la destinazione e allow_partial_path è true, restituisce un percorso verso il 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.