Geekly articles weekly

A * Path Finding Algorithm dalam Voxel 3d Unity Game

Pendahuluan


Ketika mengembangkan game saya, saya sampai pada titik untuk menciptakan NPC pertama. Dan muncul pertanyaan tentang bagaimana membuat NPC berputar-putar dan tidak "masuk ke dalamnya."


Mendaki melalui Internet, saya menemukan algoritma berikut:


  • Pencarian Luas (BFS, Pencarian Luas Pertama)
  • Algoritma Dijkstra (Dijkstra)
  • A Star "A with a asterisk"
  • Cari berdasarkan kecocokan terbaik pertama (Pencarian Terlebih Dahulu)
  • IDA (A dengan pendalaman berulang)
  • Pencarian titik lompat

Dan saya memutuskan untuk mencoba menerapkan A * saya pada kotak 3D voxel.



Contoh peta permainan saya

gambar


Deskripsi algoritma


A * langkah demi langkah melihat melalui semua jalur yang mengarah dari titik awal ke yang terakhir, sampai menemukan yang minimum. Seperti semua algoritma pencarian yang diinformasikan, ia pertama-tama melihat rute-rute yang “tampaknya” mengarah ke tujuan. Dari algoritma serakah, yang juga merupakan algoritma pencarian untuk kecocokan terbaik pertama, dibedakan oleh fakta bahwa ketika memilih sebuah vertex, ia memperhitungkan, antara lain, seluruh jalur yang dilaluinya.


Visualisasi karya A * di Wikipedia



Implementasi


Karena algoritme memerlukan "simpul" - titik untuk menentukan jalur, kami menulis struktur kelas simpul:


Kode Node:
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; }

Konstruktor kelas kecil:
  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; }

Selanjutnya, struktur pengaturan pencarian jalur akan berguna:


Kode pengaturan pencarian jalur:
  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; } }

Lebih jauh, "Dunia" adalah semacam kelas basis data untuk menyimpan informasi tentang blok peta. Milik Anda dapat diimplementasikan secara berbeda.


Hasil dari fungsi pencarian jalur untuk mendapatkan rute:
  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; }

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

Selesai ditemukan
  //     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


Fungsi ClosePoint semata-mata tergantung pada implementasi kelas Dunia, itu menambahkan semua jalur yang mungkin ke daftar titik terbuka dari itu dan menghilangkan titik saat ini dari daftar ini (menutupnya). Saya akan memberikan contoh "titik penutup" saya di empat arah pertama.


Peringatan tumpukan kode
  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; }

Optimasi


Dengan hanya membagi jalur dari awal ke titik saat ini, kami mengurangi jumlah node berkali-kali dan membuatnya lebih serakah.


 return this.heuristicEstimatePathLenght + this.pathLenghtFromStart /2;

Ringkasan


Pro:


  • Pencarian cepat di ruang terbuka.
  • Fleksibilitas algoritma

Cons:


  • Membutuhkan banyak memori untuk menghitung rute.

Hijau menunjukkan daftar node terbuka, jalur merah ke target, node tertutup biru.


Rute yang diterima sebelum pengoptimalan:



Menerima rute setelah optimisasi:



Sastra


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

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

More articles:


All Articles