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

Hérite de : RefCounted < Object

Une implémentation de A* pour trouver le chemin le plus court entre deux sommets d'une graphe connecté de l'espace 3D.

Description

A* (A star) est un algorithme informatique qui est largement utilisé dans le cheminement et la traversée de graphe, le processus de traçage des chemins courts parmi les sommets (points) passant par un ensemble donné d’arêtes (segments). Il est souvent utilisé en raison de sa performance et de sa précision. L'implémentation dans Godot de A* utilise par défaut des points dans un espace tridimensionnel et des distances euclidiennes.

Vous devez ajouter des points manuellement avec add_point() et créer des segments manuellement avec connect_points(). Ensuite, vous pouvez tester s'il y a un chemin entre deux points avec la fonction are_points_connected(), obtenir un chemin contenant des indices par get_id_path(), ou un contenant des coordonnées réelles avec get_point_path().

Il est également possible d'utiliser des distances non euclidiennes. Pour ce faire, créez une classe qui hérite de AStar3D et surchargez les méthodes _compute_cost() et _estimate_cost(). Les deux doivent prendre deux identifiants de points et renvoyer la longueur entre les points correspondants.

Exemple : Utiliser la distance de Manhattan au lieu de la distance euclidienne.

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() doit renvoyer une borne inférieure de la distance, c.a.d. _estimate_cost(u, v) <= _compute_cost(u, v). Cela sert d'indice pour l'algorithme car la méthode _compute_cost() personnalisée peut être longue à calculer. Si ce n'est pas le cas, utilisez _estimate_cost() pour renvoyer la même valeur que _compute_cost() pour fournir à l'algorithme les informations les plus précises.

Si les méthodes par défaut _estimate_cost() et _compute_cost() sont utilisées, ou si la méthode _estimate_cost() fournie renvoie une borne inférieure du coût du chemin, les chemins renvoyés par A* seront les chemins les moins coûteux. Ici, le coût d'un chemin correspond à la somme des résultats de _compute_cost() de tous les segments dans le chemin multiplié par le weight_scale des points finaux des segments respectifs. Si les méthodes par défaut sont utilisées et que le weight_scale de tous les points vaut 1.0, cela correspond à la somme des distances euclidiennes de tous les segments du chemin.

Propriétés

bool

neighbor_filter_enabled

false

Méthodes

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)

Descriptions des propriétés

bool neighbor_filter_enabled = false 🔗

void set_neighbor_filter_enabled(value: bool)
bool is_neighbor_filter_enabled()

Si true, active le filtrage des voisins via _filter_neighbor().

Descriptions des méthodes

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

Appelée lors du calcul du coût entre deux points connectés.

À noter que cette fonction est cachée dans la classe AStar3D par défaut.

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

Appelée lors du calcul du coût entre un point et le dernier point du chemin.

À noter que cette fonction est cachée dans la classe AStar3D par défaut.

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

Appelée lorsque le point voisin commence à être traité et si neighbor_filter_enabled vaut true. Si true est renvoyé, le point ne sera pas traité.

Notez que cette fonction est cachée dans la classe AStar3D par défaut.

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

Ajoute un nouveau point à la position donnée avec l'identifiant donné. L'identifiant id doit être de 0 ou plus, et le facteur de poids weight_scale doit être de 0,0 ou plus.

Le facteur de poids weight_scale est multiplié par le résultat de _compute_cost() pour déterminer le coût global de voyage à travers un segment d'un point voisin à ce point. Ainsi, tous les autres étant égaux, l'algorithme préfère les points avec des facteurs weight_scale inférieurs pour former un chemin.

var astar = AStar3D.new()
astar.add_point(1, Vector3(1, 0, 0), 4) # Ajoute le point (1,0,0) avec weight_scale 4 et id 1

var astar = new AStar3D();
astar.AddPoint(1, nouveau Vector3(1, 0, 0), 4); // Ajoute le point (1,0,0) avec weight_scale 4 et id 1

S'il existe déjà un point pour l'id donné, sa position et son facteur de poids sont mises à jour aux valeurs données.

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

Renvoie si les deux points donnés sont directement reliés par un segment. Si bidirectional vaut false, renvoie si le déplacement du point id au point to_id est possible à travers ce segment.

void clear() 🔗

Retire tous les points et segments.

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

Crée un segment entre les points donnés. Si bidirectional vaut false, seul le mouvement du point id au point to_id sera autorisé, et non le sens inverse.

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

Supprime le segment entre les points donnés. Si bidirectional vaut false, seul le mouvement de l'identifiant id vers l'autre identifiant to_id est empêché, et un segment unidirectionnel peut rester.

int get_available_point_id() const 🔗

Renvoie l'identifiant du point disponible suivant avec aucun point lui étant associé.

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

Renvoie l'identifiant du point le plus proche de to_position, en prenant en compte les points désactivés en option. Renvoie -1 s'il n'y a pas de points dans l'ensemble de points.

Note : Si plusieurs points sont proches de to_position, celui avec le plus petit identifiant sera renvoyé, permettant d'obtenir un résultat déterministe.

Vector3 get_closest_position_in_segment(to_position: Vector3) const 🔗

Renvoie la position la plus proche de to_position qui est à l'intérieur du segment entre deux points connectés.

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)

Le résultat est dans le segment qui va de y = 0 à y = 5. C'est la position la plus proche dans le segment du point donné.

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

Renvoie un tableau avec les identifiants des points qui forment le chemin trouvé par AStar entre les points donnés. Le tableau est dans l'ordre du point de départ de celui de l'arrivée.

Si from_id point est désactivé, retourne un tableau vide (même si from_id == to_id).

Si from_id point n'est pas désactivé, qu'il n'y a pas de chemin valide vers la cible, et allow_partial_path vauest true, renvoitourne un chemin vers le point le plus proche de la cible qui peut être atteinte.

Note : Lorsque allow_partial_path vaut true et to_id est désactivé, la recherche peut prendre un temps inhabituel à se terminer.

var astar = AStar.new()
astar.add_point(1, Vector3(0, 0, 0))
astar.add_point(2, Vector3(0, 1, 0), 1) # Le poids par défaut est 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) # Renvoie [1, 2, 3]

var astar = new AStar3D();
astar.AddPoint(1, new Vector3(0, 0, 0));
astar.AddPoint(2, new Vector3(0, 1, 0), 1); // Le poids par défaut est 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); // Renvoie [1, 2, 3]

Si vous changez le poids du deuxième point à 3, alors le résultat sera [1, 4, 3] à la place, parce que même si la distance est plus grande, c'est plus "facile" d'aller en passant par le point 4 que le point 2.

int get_point_capacity() const 🔗

Renvoie la capacité de la structure qui garde les points en cache, utile avec reserve_space().

PackedInt64Array get_point_connections(id: int) 🔗

Renvoie un tableau avec les identifiants des points qui forment une connexion avec le point donné.

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

int get_point_count() const 🔗

Renvoie le nombre de points actuellement dans le pool de points.

PackedInt64Array get_point_ids() 🔗

Renvoie un tableau de tous les identifiants des points.

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

Renvoie un tableau avec les points qui sont dans le chemin trouvé par AStar3D entre les points donnés. Le tableau est trié du point de départ au point final du chemin.

Si from_id point est désactivé, retourne un tableau vide (même si from_id == to_id).

Si from_id point n'est pas désactivé, qu''il n'y a pas de chemin valide vers la cible, et allow_partial_path vaut true, renvoie un chemin vers le point le plus proche de la cible qui peut être atteinte.

Note : Cette méthode n'est pas thread-safe, elle ne peut être appelée que depuis un seul Thread à un instant donné. Envisagez d'utiliser des Mutex pour vous assurer de l'accès exclusif à un thread pour éviter des accès concurrents.

De plus, lorsque allow_partial_path vaut true et to_id est désactivé, la recherche peut prendre un temps inhabituellement long pour se terminer.

Vector3 get_point_position(id: int) const 🔗

Renvoie la position du point associé à l'identifiant id donné.

float get_point_weight_scale(id: int) const 🔗

Renvoie le facteur de poids du point associé à l'identifiant id donné.

bool has_point(id: int) const 🔗

Renvoie si un point associé à l'identifiant id donné existe.

bool is_point_disabled(id: int) const 🔗

Renvoie si un point est désactivé ou non pour le calcul du chemin. Par défaut, tous les points sont activés.

void remove_point(id: int) 🔗

Retire le point associé à l'id donné du pool des points.

void reserve_space(num_nodes: int) 🔗

Réserve l'espace interne pour num_nodes points. Utile si vous voulez ajouter un grand nombre de points à la fois, pour une grille par exemple.

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

Désactive ou active le point spécifié pour le pathfinding. Utile pour faire des obstacles temporaires.

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

Définit la position du point avec l'identifiant id donné.

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

Définit le facteur de poids weight_scale pour le point avec l'identifiant id donné. Le facteur de poids weight_scale est multiplié par le résultat de _compute_cost() pour déterminer le coût global de voyage le long d'un segment d'un point voisin à ce point.