Geekly articles weekly

A * Pfadfindungsalgorithmus in einem Voxel 3d Unity-Spiel

Einführung


Bei der Entwicklung meines Spiels habe ich die ersten NPCs erstellt. Und es stellte sich die Frage, wie man den NPC dazu bringt, um die Mauer herumzugehen und nicht "hineinzugehen".


Beim Klettern über das Internet habe ich folgende Algorithmen gefunden:


  • Breite Suche (BFS, Breitensuche)
  • Dijkstra-Algorithmus (Dijkstra)
  • Ein Stern "A mit einem Stern"
  • Suche nach der ersten besten Übereinstimmung (Best-First-Suche)
  • IDA (A mit iterativer Vertiefung)
  • Sprungpunktsuche

Und ich beschloss, mein A * in einem Voxel-3D-Raster zu implementieren.



Beispielkarte meines Spiels

Bild


Beschreibung des Algorithmus


Ein * Schritt für Schritt durchsucht alle Pfade, die vom anfänglichen zum letzten Scheitelpunkt führen, bis der minimale gefunden wird. Wie alle informierten Suchalgorithmen betrachtet er zunächst die Routen, die zum Ziel führen. Der Greedy-Algorithmus, der auch der Suchalgorithmus für die erste beste Übereinstimmung ist, unterscheidet sich dadurch, dass bei der Auswahl eines Scheitelpunkts unter anderem der gesamte Weg berücksichtigt wird, der dorthin zurückgelegt wurde.


Visualisierung der Arbeit von A * auf Wikipedia



Implementierung


Da der Algorithmus "Knoten" - Punkte zur Bestimmung des Pfades benötigt, schreiben wir die Klassenstruktur des Knotens:


Knotencode:
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; }

Konstruktoren kleiner Klassen:
  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; }

Als nächstes wird die Struktur der Pfadsucheinstellungen nützlich sein:


Code für die Einstellungen für die Pfadsuche:
  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; } }

Außerdem ist "World" eine Art Datenbankklasse zum Speichern von Informationen über Kartenblöcke. Ihre können anders implementiert werden.


Das Ergebnis der Pfadsuchfunktion zum Abrufen der Route:
  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; }

Zugweg
  //      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); } }

Fertig gegründet
  //     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; }

Nahpunkt


Die ClosePoint-Funktion hängt ausschließlich von der Implementierung der Weltklasse ab. Sie fügt der Liste der offenen Punkte alle möglichen Pfade hinzu und entfernt den aktuellen Punkt aus dieser Liste (schließt sie). Ich werde ein Beispiel für meinen "Schließpunkt" in den ersten vier Richtungen geben.


Warnung großer Codehaufen
  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; }

Optimierung


Indem wir den Pfad einfach vom Start bis zum aktuellen Punkt teilen, reduzieren wir die Anzahl der Knoten um ein Vielfaches und machen ihn gieriger.


 return this.heuristicEstimatePathLenght + this.pathLenghtFromStart /2;

Zusammenfassung


Vorteile:


  • Schnelle Suche in offenen Räumen.
  • Vielseitigkeit des Algorithmus

Nachteile:


  • Die Berechnung der Route erfordert viel Speicher.

Grün zeigt eine offene Liste von Knoten, roten Pfad zum Ziel, blau geschlossene Knoten.


Erhaltene Routen vor der Optimierung:



Erhaltene Routen nach der Optimierung:



Literatur


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

Source: https://habr.com/ru/post/de416737/

More articles:


All Articles