Présentation

Lors du développement de mon jeu, je suis arrivé au point de créer les premiers PNJ. Et la question s'est posée de savoir comment faire en sorte que le PNJ contourne le mur et non «y pénètre».

En grimpant sur Internet, j'ai trouvé les algorithmes suivants:

Recherche étendue (BFS, recherche en largeur)
Algorithme de Dijkstra (Dijkstra)
Une étoile "A avec un astérisque"
Recherche par la première meilleure correspondance (Best-First Search)
IDA (A avec approfondissement itératif)
Recherche de points de saut

Et j'ai décidé d'essayer d'implémenter mon A * sur une grille 3D voxel.

Exemple de carte de mon jeu

Description de l'algorithme

Un * pas à pas examine tous les chemins menant du sommet initial au sommet final, jusqu'à ce qu'il trouve le minimum. Comme tous les algorithmes de recherche informés, il examine d'abord les itinéraires qui «semblent» menant à l'objectif. De l'algorithme gourmand, qui est également l'algorithme de recherche de la première meilleure correspondance, il se distingue par le fait que lors du choix d'un sommet, il prend en compte, entre autres, l'ensemble du chemin parcouru.

Visualisation du travail d'A * sur Wikipédia

Implémentation

Puisque l'algorithme a besoin de "nœuds" - des points pour déterminer le chemin, nous écrivons la structure de classe du nœud:

Code de nœud:

public enum EMoveAction { walk, jump, fall, swim }; public class PathPoint { //   public Vector3 point { get; set; } //    public float pathLenghtFromStart { get; set; } //     public float heuristicEstimatePathLenght { get; set; } //     public float estimateFullPathLenght { get { return this.heuristicEstimatePathLenght + this.pathLenghtFromStart; } } //   public EMoveAction moveAction = EMoveAction.walk; //      public PathPoint cameFrom; }

Constructeurs de petite classe:

  private PathPoint NewPathPoint(Vector3 point, float pathLenghtFromStart, float heuristicEstimatePathLenght, EMoveAction moveAction) { PathPoint a = new PathPoint(); a.point = point; a.pathLenghtFromStart = pathLenghtFromStart; a.heuristicEstimatePathLenght = heuristicEstimatePathLenght; a.moveAction = moveAction; return a; } private PathPoint NewPathPoint(Vector3 point, float pathLenghtFromStart, float heuristicEstimatePathLenght, EMoveAction moveAction, PathPoint ppoint) { PathPoint a = new PathPoint(); a.point = point; a.pathLenghtFromStart = pathLenghtFromStart; a.heuristicEstimatePathLenght = heuristicEstimatePathLenght; a.moveAction = moveAction; a.cameFrom = ppoint; return a; }

Ensuite, la structure des paramètres de recherche de chemin sera utile:

Code des paramètres de recherche de chemin:

  public struct SPathFinderType { //   , , ,   public bool walk, jump, fall, swim; //   ,  public int maxFallDistance, jumpHeight, jumpDistance; //   public int characterHeight; //    public static SPathFinderType normal() { SPathFinderType n = new SPathFinderType(); n.walk = true; n.jump = true; n.fall = true; n.swim = false; n.maxFallDistance = 1; n.jumpHeight = 1; n.jumpDistance = 0; n.characterHeight = 1; return n; } }

En outre, "World" est une sorte de classe de base de données pour stocker des informations sur les blocs de carte. Le vôtre peut être mis en œuvre différemment.

Le résultat de la fonction de recherche de chemin pour obtenir l'itinéraire:

  public List<PathPoint> GetPathToTarget(Vector3 beginPoint, Vector3 targetPoint, World worldData, SPathFinderType pfType) { List<PathPoint> path = new List<PathPoint>(); //     List<PathPoint> openPoints = new List<PathPoint>(); //    List<PathPoint> closedPoints = new List<PathPoint>(); //      openPoints.Add(NewPathPoint(beginPoint, 0, GameLogic.Distance(beginPoint, targetPoint), EMoveAction.walk)); //   closedPoints.Add(openPoints[0]); //       openPoints = ClosePoint(0, openPoints, closedPoints, worldData, pfType, targetPoint); // " "    bool stopFlag = true; //        float maxEstimatePath = 1500; int maxNodes = 6000; while (stopFlag) { //        int minIndex = GetMinEstimate(openPoints); if (openPoints.Count > 0) if (openPoints[minIndex].estimateFullPathLenght < maxEstimatePath) { //   closedPoints.Add(openPoints[minIndex]); //       minIndex openPoints = ClosePoint(minIndex, openPoints, closedPoints, worldData, pfType, targetPoint); } else { //      //       closedPoints.Add(openPoints[minIndex]); openPoints.RemoveAt(minIndex); } //      if (FinishFounded(closedPoints)) { Debug.Log(" !"); path = GetPathToTarget(closedPoints); stopFlag = false; //      } if (openPoints.Count <= 0) stopFlag = false; //       if ((openPoints.Count>= maxNodes) ||(closedPoints.Count>= maxNodes)) stopFlag = false; //      } Debug.Log("Nodes created "+ closedPoints.Count.ToString()); //    DrawPath(openPoints, Color.green, 6f); DrawPath(closedPoints, Color.blue, 6f); DrawPath(path, Color.red, 6f); return path; }

GetMinEstimate

  //        private int GetMinEstimate(List<PathPoint> points) { int min = 0; for (int i = 0; i < points.Count; i++) { if (points[i].estimateFullPathLenght < points[min].estimateFullPathLenght) min = i; } return min; }

Chemin de tirage

  //      public void DrawPath(List<PathPoint> points, Color c, float time) { for (int i = 0; i < points.Count; i++) { if (points[i].cameFrom != null) Debug.DrawLine(points[i].point, points[i].cameFrom.point, c, time); } }

Terminé

  //     private bool FinishFounded(List<PathPoint> points) { for (int i = 0; i < points.Count; i++) { if (points[i].heuristicEstimatePathLenght <= 0) return true; } return false; }

GetPathToTarget

  //        private List<PathPoint> GetPathToTarget(List<PathPoint> points) { List<PathPoint> path = new List<PathPoint>(); int targetIndex = 0; for (int i = 0; i < points.Count; i++) { if (points[i].heuristicEstimatePathLenght <= 0) targetIndex = i; } PathPoint ppoint = new PathPoint(); ppoint = points[targetIndex]; while (ppoint.pathLenghtFromStart > 0) { path.Add(ppoint); ppoint = ppoint.cameFrom; } path.Reverse(); return path; }

Closepoint

La fonction ClosePoint dépend uniquement de l'implémentation de la classe World, elle en ajoute tous les chemins possibles à la liste des points ouverts et supprime le point actuel de cette liste (la ferme). Je vais donner un exemple de mon «point de fermeture» dans les quatre premières directions.

Avertissement gros tas de code

  private List<PathPoint> ClosePoint(int index, List<PathPoint> openPoints, List<PathPoint> closedPoints, World worldData, SPathFinderType pfType, Vector3 targetPoint) { List<PathPoint> newOpenPoints = openPoints; PathPoint lastPoint = openPoints[index]; //     if (pfType.walk) //        if (CanStand(new Vector3(lastPoint.point.x, lastPoint.point.y, lastPoint.point.z), pfType.characterHeight, worldData)) { // --------------------------------------------------------------- //north // /|\ // | //      if (!InList(closedPoints, new Vector3(lastPoint.point.x + 1, lastPoint.point.y, lastPoint.point.z))) //     if (!InList(newOpenPoints, new Vector3(lastPoint.point.x + 1, lastPoint.point.y, lastPoint.point.z))) //     if (CanStand(new Vector3(lastPoint.point.x + 1, lastPoint.point.y, lastPoint.point.z), pfType.characterHeight, worldData)) { newOpenPoints.Add(NewPathPoint(new Vector3(lastPoint.point.x + 1, lastPoint.point.y, lastPoint.point.z) , lastPoint.pathLenghtFromStart + GetTravelCost(new Vector3(lastPoint.point.x + 1, lastPoint.point.y, lastPoint.point.z), worldData, pfType.characterHeight) , GameLogic.Distance(new Vector3(lastPoint.point.x + 1, lastPoint.point.y, lastPoint.point.z), targetPoint) , EMoveAction.walk , lastPoint)); } // south // | // \|/ //      if (!InList(closedPoints, new Vector3(lastPoint.point.x - 1, lastPoint.point.y, lastPoint.point.z))) //     if (!InList(newOpenPoints, new Vector3(lastPoint.point.x - 1, lastPoint.point.y, lastPoint.point.z))) //     if (CanStand(new Vector3(lastPoint.point.x - 1, lastPoint.point.y, lastPoint.point.z), pfType.characterHeight, worldData)) { newOpenPoints.Add(NewPathPoint(new Vector3(lastPoint.point.x - 1, lastPoint.point.y, lastPoint.point.z) , lastPoint.pathLenghtFromStart + GetTravelCost(new Vector3(lastPoint.point.x - 1, lastPoint.point.y, lastPoint.point.z), worldData, pfType.characterHeight) , GameLogic.Distance(new Vector3(lastPoint.point.x - 1, lastPoint.point.y, lastPoint.point.z), targetPoint) , EMoveAction.walk , lastPoint)); } // east // ----> // //      if (!InList(closedPoints, new Vector3(lastPoint.point.x, lastPoint.point.y, lastPoint.point.z + 1))) //     if (!InList(newOpenPoints, new Vector3(lastPoint.point.x, lastPoint.point.y, lastPoint.point.z + 1))) //     if (CanStand(new Vector3(lastPoint.point.x, lastPoint.point.y, lastPoint.point.z + 1), pfType.characterHeight, worldData)) { newOpenPoints.Add(NewPathPoint(new Vector3(lastPoint.point.x, lastPoint.point.y, lastPoint.point.z + 1) , lastPoint.pathLenghtFromStart + GetTravelCost(new Vector3(lastPoint.point.x, lastPoint.point.y, lastPoint.point.z + 1), worldData, pfType.characterHeight) , GameLogic.Distance(new Vector3(lastPoint.point.x, lastPoint.point.y, lastPoint.point.z + 1), targetPoint) , EMoveAction.walk , lastPoint)); } // west // <---- // //      if (!InList(closedPoints, new Vector3(lastPoint.point.x, lastPoint.point.y, lastPoint.point.z - 1))) //     if (!InList(newOpenPoints, new Vector3(lastPoint.point.x, lastPoint.point.y, lastPoint.point.z - 1))) //    if (CanStand(new Vector3(lastPoint.point.x, lastPoint.point.y, lastPoint.point.z - 1), pfType.characterHeight, worldData)) { newOpenPoints.Add(NewPathPoint(new Vector3(lastPoint.point.x, lastPoint.point.y, lastPoint.point.z - 1) , lastPoint.pathLenghtFromStart + GetTravelCost(new Vector3(lastPoint.point.x, lastPoint.point.y, lastPoint.point.z - 1), worldData, pfType.characterHeight) , GameLogic.Distance(new Vector3(lastPoint.point.x, lastPoint.point.y, lastPoint.point.z - 1), targetPoint) , EMoveAction.walk , lastPoint)); } } newOpenPoints.RemoveAt(index); return newOpenPoints; }

Optimisation

En divisant simplement le chemin du début au point actuel, nous réduisons le nombre de nœuds de nombreuses fois et le rendons plus gourmand.

 return this.heuristicEstimatePathLenght + this.pathLenghtFromStart /2;

Résumé

Avantages:

Recherche rapide dans les espaces ouverts.
Polyvalence des algorithmes

Inconvénients:

Il faut beaucoup de mémoire pour calculer l'itinéraire.

Le vert montre une liste ouverte de nœuds, un chemin rouge vers la cible, des nœuds fermés bleus.

Itinéraires reçus avant optimisation:

Itinéraires reçus après optimisation:

Littérature

https://tproger.ru/articles/pathfindings/
https://ru.wikipedia.org/wiki/A*

Un * algorithme de recherche de chemin dans un jeu Voxel 3d Unity