AStar2D

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

Descrizione

Un'implementazione dell'algoritmo A*, usato per trovare il percorso più breve tra due vertici su un grafico collegato nello spazio 2D.

Vedi AStar3D per una spiegazione più approfondita su come utilizzare questa classe. AStar2D è un wrapper per AStar3D che impone coordinate in 2D.

Tutorial

Demo di navigazione basata su griglia con AStarGrid2D

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: Vector2, 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: Vector2, include_disabled: bool = false) const
Vector2	get_closest_position_in_segment(to_position: Vector2) 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()
PackedVector2Array	get_point_path(from_id: int, to_id: int, allow_partial_path: bool = false)
Vector2	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: Vector2)
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 AStar2D.

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

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

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

Aggiunge un nuovo punto nella posizione specificata con l'identificatore specificato. id deve essere 0 o maggiore e la sua scala di peso (weight_scale) deve essere 0,0 o maggiore.

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 tutto il resto, l'algoritmo preferisce i punti con weight_scale minori per formare un percorso.

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

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

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

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

Restituisce se c'è un collegamento/segmento tra i punti specificati. Se bidirectional è false, restituisce se è possibile il movimento da id a to_id 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 = AStar2D.new()
astar.add_point(1, Vector2(1, 1))
astar.add_point(2, Vector2(0, 5))
astar.connect_points(1, 2, false)

var astar = new AStar2D();
astar.AddPoint(1, new Vector2(1, 1));
astar.AddPoint(2, new Vector2(0, 5));
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: Vector2, 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.

Vector2 get_closest_position_in_segment(to_position: Vector2) const 🔗

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

var astar = AStar2D.new()
astar.add_point(1, Vector2(0, 0))
astar.add_point(2, Vector2(0, 5))
astar.connect_points(1, 2)
var res = astar.get_closest_position_in_segment(Vector2(3, 3)) # Restituisce (0, 3)

var astar = new AStar2D();
astar.AddPoint(1, new Vector2(0, 0));
astar.AddPoint(2, new Vector2(0, 5));
astar.ConnectPoints(1, 2);
Vector2 res = astar.GetClosestPositionInSegment(new Vector2(3, 3)); // Restituisce (0, 3)

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

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 AStar2D 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 = AStar2D.new()
astar.add_point(1, Vector2(0, 0))
astar.add_point(2, Vector2(0, 1), 1) # Il peso predefinito è 1
astar.add_point(3, Vector2(1, 1))
astar.add_point(4, Vector2(2, 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 AStar2D();
astar.AddPoint(1, new Vector2(0, 0));
astar.AddPoint(2, new Vector2(0, 1), 1); // Il peso predefinito è 1
astar.AddPoint(3, new Vector2(1, 1));
astar.AddPoint(4, new Vector2(2, 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 il collegamento con il punto indicato.

var astar = AStar2D.new()
astar.add_point(1, Vector2(0, 0))
astar.add_point(2, Vector2(0, 1))
astar.add_point(3, Vector2(1, 1))
astar.add_point(4, Vector2(2, 0))

astar.connect_points(1, 2, true)
astar.connect_points(1, 3, true)

var neighbors = astar.get_point_connections(1) # Restituisce [2, 3]

var astar = new AStar2D();
astar.AddPoint(1, new Vector2(0, 0));
astar.AddPoint(2, new Vector2(0, 1));
astar.AddPoint(3, new Vector2(1, 1));
astar.AddPoint(4, new Vector2(2, 0));

astar.ConnectPoints(1, 2, true);
astar.ConnectPoints(1, 3, true);

long[] neighbors = astar.GetPointConnections(1); // Restituisce [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.

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

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

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.