Bagaimana Mengadaptasi A * Menemukan jalan ke Platformer 2D Berbasis Jaringan: Implementasi

Sekarang kita memiliki gagasan bagus tentang bagaimana algoritma platforming A * kami akan bekerja, saatnya untuk benar-benar mengkodenya. Daripada membangunnya dari awal, kami akan mengadaptasi sistem penghubung A* yang ada untuk menambahkan kompatibilitas platfomer baru.

Implementasi yang akan kami adaptasikan dalam tutorial ini adalah sistem menemukan jalan berbasis jaringan A Gustavo Franco, yang ditulis dalam C#; jika anda tidak terbiasa dengannya, bacalah penjelasannya tentang semua bagian yang terpisah sebelum melanjutkan. Jika anda belum membaca tutorial sebelumnya dalam seri ini, yang memberikan gambaran umum tentang bagaimana adaptasi ini akan bekerja, baca yang pertama .

Catatan: kode sumber lengkap untuk tutorial ini dapat ditemukan di repo GitHub ini , di folder Implementation .

Demo

Anda dapat memainkan demo Unity , atau versi WebGL (64 MB), untuk melihat hasil akhir dalam aksi. Gunakan WASD untuk memindahkan karakter, klik kiri di suatu tempat untuk menemukan jalan yang bisa anda ikuti untuk sampai ke sana, dan klik kanan sel untuk beralih ke tanah pada titik tersebut.

Menyiapkan Proyek Permainan

Kita perlu menetapkan beberapa aturan untuk proyek permainan contoh yang digunakan dalam tutorial ini. Anda tentu saja dapat mengubah aturan-aturan ini ketika menerapkan algoritma ini dalam permainan anda sendiri!

Menyiapkan Fisika

Aturan fisika yang digunakan dalam proyek contoh sangat sederhana.

Ketika datang ke kecepatan horizontal, tidak ada momentum sama sekali. Karakter dapat mengubah arah dengan segera, dan segera bergerak ke arah itu dengan kecepatan penuh. Ini membuatnya lebih mudah bagi algoritme untuk menemukan jalur yang benar, karena kita tidak perlu peduli dengan kecepatan horisontal karakter saat ini. Ini juga mempermudah pembuatan AI yang mengikuti alur, karena kita tidak perlu membuat karakter mendapatkan momentum apa pun sebelum melakukan lompatan.

Kami menggunakan empat konstanta untuk mendefinisikan dan membatasi gerakan karakter:

• Gravitasi
• Kecepatan jatuh maksimum
• Kecepatan berjalan
• Kecepatan melompat

Berikut ini bagaimana mereka didefinisikan untuk proyek contoh ini:

1

public const float cGravity = -1030.0f;

2

public const float cMaxFallingSpeed = -900.0f;

3

public const float cWalkSpeed = 160.0f;

4

public const float cJumpSpeed = 410.0f;

Unit dasar yang digunakan dalam gim ini adalah piksel, sehingga karakternya akan bergerak 160 piksel per detik secara horizontal (saat berjalan atau melompat); saat melompat, kecepatan vertikal karakter akan ditetapkan menjadi 410 piksel per detik. Dalam proyek uji kecepatan jatuh karakter terbatas hingga 900 , jadi tidak ada kemungkinan jatuh melalui ubin. Gravitasi diatur menjadi -1030 piksel per detik² .

Tinggi lompatan karakter tidak tetap: semakin lama tombol lompat ditekan, semakin tinggi karakter akan melompat. Ini dicapai dengan mengatur kecepatan karakter menjadi tidak lebih dari 200 piksel per detik setelah tombol lompat tidak lagi ditekan:

1

if (!mInputs[(int)KeyInput.Jump] && mSpeed.y > 0.0f)

2

{

3

    mSpeed.y = Mathf.Min(mSpeed.y, 200.0f);

4

    mFramesFromJumpStart = 100;

5

}

Menyiapkan Jaringan

Jaringan adalah array sederhana dari byte yang mewakili biaya pergerakan ke sel tertentu (di mana 0 dicadangkan untuk blok yang karakter tidak dapat bergerak melalui).

Kami tidak akan membahas bobot dalam tutorial ini; kami sebenarnya hanya akan menggunakan dua nilai: 0 untuk blok padat, dan 1 untuk sel kosong.

Algoritma yang digunakan dalam tutorial ini membutuhkan lebar dan tinggi grid untuk menjadi kekuatan dua, jadi ingatlah itu.

Berikut ini contoh susunan kisi dan representasi dalam permainannya.

1

private byte[,] mGrid = {{ 0, 1, 1, 1 }

2

                         { 0, 1, 1, 1 }

3

                         { 0, 1, 0, 0 }

4

                         { 0, 0, 0, 0 }};

Catatan tentang mengatur

Biasanya kami akan mengatur proses menentukan jalan dalam utas yang terpisah, jadi tidak ada yang membeku dalam gim saat bekerja, tetapi dalam tutorial ini kami akan menggunakan versi berulir tunggal, karena keterbatasan platform WebGL yang demo ini berjalan.

Algoritme itu sendiri dapat dijalankan dalam utas yang terpisah, jadi anda seharusnya tidak memiliki masalah dengan menggabungkannya ke kode Anda dengan cara itu jika anda perlu.

Menambahkan Nilai Lompat ke Node

Ingatlah dari tinjauan teori bahwa simpul-simpul tidak hanya dibedakan oleh koordinat x dan y, tetapi juga oleh nilai lompatan. Dalam implementasi standar koordinat A *, x- dan y cukup untuk mendefinisikan sebuah simpul, jadi kita perlu memodifikasinya untuk menggunakan nilai lompatan juga.

Dari titik ini, kami akan memodifikasi file sumber PathFinderFast.cs inti dari implementasi Gustavo Franco .

Menstruktur Kembali Daftar Node

Pertama, kami akan menambahkan daftar node baru untuk setiap sel jaringan; daftar ini akan menggantikan mCalcGrid dari algoritma asli:

1

private List<PathFinderNodeFast>[] nodes;

Perhatikan bahwa PathFinderFast menggunakan array satu dimensi, daripada array 2D seperti yang kita harapkan untuk digunakan saat mewakili jaringan.

Ini bukan masalah, karena kita tahu lebar dan tinggi grid, jadi daripada mengakses data dengan indeks X dan Y, kita akan mengaksesnya dengan int tunggal yang dihitung menggunakan location = (y << gridWidthLog2) + x . (Ini adalah versi sedikit lebih cepat dari location = (y * gridWidth) + x klasiklocation = (y * gridWidth) + x )

Karena kita memerlukan jaringan yang tiga dimensi (untuk menggabungkan nilai lompatan sebagai "dimensi" ketiga), kita perlu menambahkan bilangan bulat lain, yang akan menjadi indeks node dalam daftar pada posisi X dan Y tertentu.

Perhatikan bahwa kita tidak dapat menggabungkan ketiga koordinat menjadi satu bilangan bulat, karena dimensi ketiga kisi bukan ukuran konstan. Kita bisa mempertimbangkan hanya menggunakan grid tiga dimensi, yang akan membatasi jumlah node yang mungkin pada posisi tertentu (x, y) - tetapi jika ukuran array pada "z-axis" terlalu kecil, maka algoritma dapat kembali hasil yang salah, jadi kami akan memainkannya dengan aman.

Di sini, kemudian, adalah struct yang akan kita gunakan untuk mengindeks node tertentu:

1

public struct Location

2

{

3

    public Location(int xy, int z)

4

    {

5

        this.xy = xy;

6

        this.z = z;

7

    }

8

9

    public int xy;

10

    public int z;

11

}

Hal berikutnya yang perlu kita modifikasi adalah struktur PathFinderNodeFast. Ada dua hal yang perlu kami tambahkan di sini:

• Yang pertama adalah indeks dari induk node, yang pada dasarnya adalah node sebelumnya dari mana kita tiba ke node saat ini. Kita perlu memiliki indeks itu karena kita tidak dapat mengidentifikasi orang tua hanya dengan koordinat x dan y-nya. Koordinat x dan y akan mengarahkan kita ke daftar node yang berada pada posisi tertentu, jadi kita juga perlu mengetahui indeks orang tua kita dalam daftar itu. Kami akan menamai indeks itu PZ .
• Hal lain yang perlu kita tambahkan ke struktur adalah nilai lompatan.

Berikut struktur lama:

1

internal struct PathFinderNodeFast

2

{

3

    public int     F;

4

    public int     G;

5

    public ushort  PX;      //parent x

6

    public ushort  PY;      //parent y

7

    public byte    Status;

8

}

Dan inilah yang akan kami modifikasi menjadi:

1

internal struct PathFinderNodeFast

2

{

3

    public int     F;

4

    public int     G;

5

    public ushort  PX;          //parent y

6

    public ushort  PY;          //parent x

7

    public byte    Status;

8

    public byte    PZ;          //parent z

9

    public short   JumpLength;  //jump value

10

}

Masih ada satu masalah. Ketika kami menggunakan algoritma sekali, ia akan mengisi daftar node sel. Kita perlu menghapus daftar itu setelah setiap kali pathfinder dijalankan, karena jika tidak, maka daftar tersebut akan terus bertambah setiap kali menggunakan algoritma dan penggunaan memori akan naik tak terkendali.

Masalahnya adalah, kita tidak benar-benar ingin menghapus setiap daftar setiap kali pathfinder dijalankan, karena jaringan dapat menjadi besar dan jalur kemungkinan tidak akan pernah menyentuh sebagian besar node jaringan. Ini akan menyebabkan atas yang besar, jadi lebih baik untuk hanya menghapus daftar yang dilaluinya.

Untuk itu, kami membutuhkan wadah tambahan yang akan kami gunakan untuk mengingat sel mana yang disentuh:

1

private Stack<int> touchedLocations;

Tumpukan akan berfungsi dengan baik; kita hanya perlu menghapus semua daftar yang ada di dalamnya satu per satu.

Memperbarui Antrian Prioritas

Sekarang mari kita prioritaskan antrian mOpen untuk bekerja dengan indeks baru.

Hal pertama yang perlu kita lakukan adalah mengubah deklarasi untuk menggunakan Lokasi daripada bilangan bulat — jadi, dari:

1

private PriorityQueueB<int> mOpen = null;

untuk:

1

private PriorityQueueB<Location> mOpen = null;

Selanjutnya, kita perlu mengubah pembanding antrian untuk membuatnya menggunakan struktur baru. Saat ini ia hanya menggunakan array node; kita perlu mengubahnya sehingga menggunakan array daftar node sebagai gantinya. Kita juga perlu memastikannya membandingkan simpul menggunakan Location, bukan hanya bilangan bulat.

Ini kode lama:

1

internal class ComparePFNodeMatrix : IComparer<int>

2

{

3

    PathFinderNodeFast[] mMatrix;

4

5

    public ComparePFNodeMatrix(PathFinderNodeFast[] matrix)

6

    {

7

        mMatrix = matrix;

8

    }

9

10

    public int Compare(int a, int b)

11

    {

12

        if (mMatrix[a].F > mMatrix[b].F)

13

            return 1;

14

        else if (mMatrix[a].F < mMatrix[b].F)

15

            return -1;

16

        return 0;

17

    }

18

}

Dan inilah yang baru:

1

internal class ComparePFNodeMatrix : IComparer<Location>

2

{

3

    List<PathFinderNodeFast>[] mMatrix;

4

5

    public ComparePFNodeMatrix(List<PathFinderNodeFast>[] matrix)

6

    {

7

        mMatrix = matrix;

8

    }

9

10

    public int Compare(Location a, Location b)

11

    {

12

        if (mMatrix[a.xy][a.z].F > mMatrix[b.xy][b.z].F)

13

            return 1;

14

        else if (mMatrix[a.xy][a.z].F < mMatrix[b.xy][b.z].F)

15

            return -1;

16

        return 0;

17

    }

18

}

Sekarang, mari kita inisialisasi daftar node dan tumpukan lokasi yang disentuh ketika pathfinder dibuat. Sekali lagi, inilah kode lama:

1

if (mCalcGrid == null || mCalcGrid.Length != (mGridX * mGridY))

2

{

3

    mCalcGrid = new PathFinderNodeFast[mGridX * mGridY];

4

    mClose = new List<Vector2i>(mGridX * mGridY);

5

}

Dan inilah yang baru:

1

if (others == null || others.Length != (mGridX * mGridY))

2

{

3

  nodes = new List<PathFinderNodeFast>[mGridX * mGridY];

4

    touchedLocations = new Stack<int>(mGridX * mGridY);

5

    mClose = new List<Vector2i>(mGridX * mGridY);

6

}

7

8

for (var i = 0; i < others.Length; ++i)

9

{

10

	nodes[i] = new List<PathFinderNodeFast>(1);

11

}

Akhirnya, mari kita buat antrian prioritas kita menggunakan konstruktor baru:

1

mOpen = new PriorityQueueB<Location>(new ComparePFNodeMatrix(nodes));

Inisialisasi Algoritma

Ketika kita memulai algoritma, kita ingin mengatakan seberapa besar karakter kita (dalam sel) dan juga seberapa tinggi karakter dapat melompat.

(Perhatikan bahwa, untuk tutorial ini, kita tidak akan benar-benar menggunakan characterWidth atau characterHeight; kita akan mengasumsikan bahwa ukuran karakter adalah blok 1x1.)

Ubah baris ini:

1

public List<PathFinderNode> FindPath(Point start, Point end)

Untuk ini:

1

public List<Vector2i> FindPath(Vector2i start, Vector2i end, int characterWidth, int characterHeight, short maxCharacterJumpHeight)

Hal pertama yang perlu kita lakukan adalah menghapus daftar di lokasi yang sebelumnya disentuh:

1

while (touchedLocations.Count > 0)

2

    others[touchedLocations.Pop()].Clear();

Selanjutnya, kita harus memastikan bahwa karakter bisa muat di lokasi akhir. (Jika tidak bisa, tidak ada gunanya menjalankan algoritma, karena tidak mungkin menemukan jalur yang valid.)

1

if (mGrid[end.x, end.y] == 0)

2

	return null;

Sekarang kita bisa membuat simpul awal. Daripada menetapkan nilai dalam mCalcGrid, kita perlu menambahkan node ke daftar node pada posisi tertentu.

Pertama, mari menghitung lokasi node. Tentu saja, untuk dapat melakukan ini, kita juga perlu mengubah jenis mLocation ke Location .

Ubah baris ini:

1

mLocation = (start.y << mGridXLog2) + start.x;

Untuk ini:

1

mLocation.xy = (start.y << mGridXLog2) + start.x;

2

mLocation.z = 0;

mEndLocation dapat dibiarkan apa adanya; kami akan menggunakan ini untuk memeriksa apakah kami telah mencapai tujuan kami, jadi kami hanya perlu memeriksa posisi X dan Y dalam kasus tersebut:

1

mEndLocation = (end.y << mGridXLog2) + end.x;

Untuk memulai inisialisasi simpul, kita perlu mengatur ulang PZ induk ke 0 dan menetapkan nilai lompatan yang sesuai.

Ketika titik awal berada di tanah, nilai lompatan seharusnya sama dengan 0 —tapi bagaimana jika kita mulai di udara? Solusi paling sederhana adalah mengaturnya ke nilai yang jatuh dan tidak terlalu mengkhawatirkannya;menemukan jalan ketika memulai di udara mungkin cukup merepotkan, jadi kami akan mengambil jalan keluar yang mudah.

Ini kode lama:

1

mLocation                      = (start.y << mGridXLog2) + start.x;

2

mEndLocation                   = (end.y << mGridXLog2) + end.x;

3

mCalcGrid[mLocation].G         = 0;

4

mCalcGrid[mLocation].F         = mHEstimate;

5

mCalcGrid[mLocation].PX        = (ushort) start.x;

6

mCalcGrid[mLocation].PY        = (ushort) start.y;

7

mCalcGrid[mLocation].Status    = mOpenNodeValue;

Dan yang baru:

1

mLocation.xy = (start.y << mGridXLog2) + start.x;

2

mLocation.z = 0;

3

mEndLocation = (end.y << mGridXLog2) + end.x;

4

5

PathFinderNodeFast firstNode = new PathFinderNodeFast();

6

firstNode.G = 0;

7

firstNode.F = mHEstimate;

8

firstNode.PX = (ushort)start.x;

9

firstNode.PY = (ushort)start.y;

10

firstNode.PZ = 0;

11

firstNode.Status = mOpenNodeValue;

12

13

if (mMap.IsGround(start.x, start.y - 1))

14

    firstNode.JumpLength = 0;

15

else

16

	firstNode.JumpLength = (short)(maxCharacterJumpHeight * 2);

Kita juga harus menambahkan simpul ke daftar pada posisi awal:

1

nodes[mLocation.xy].Add(firstNode);

Dan kita juga perlu mengingat bahwa daftar node awal akan dihapus pada run berikutnya:

1

touchedLocations.Push(mLocation.xy);

Akhirnya, lokasi diantrekan dan kita bisa mulai dengan algoritma inti.Singkatnya, ini adalah apa yang inisialisasi run pathfinder akan terlihat seperti:

1

while (touchedLocations.Count > 0)

2

    nodes[touchedLocations.Pop()].Clear();

3

4

if (mGrid[end.x, end.y] == 0)

5

	return null;

6

7

mFound              = false;

8

mStop               = false;

9

mStopped            = false;

10

mCloseNodeCounter   = 0;

11

mOpenNodeValue      += 2;

12

mCloseNodeValue     += 2;

13

mOpen.Clear();

14

15

mLocation.xy = (start.y << mGridXLog2) + start.x;

16

mLocation.z = 0;

17

mEndLocation                   = (end.y << mGridXLog2) + end.x;

18

19

PathFinderNodeFast firstNode = new PathFinderNodeFast();

20

firstNode.G = 0;

21

firstNode.F = mHEstimate;

22

firstNode.PX = (ushort)start.x;

23

firstNode.PY = (ushort)start.y;

24

firstNode.PZ = 0;

25

firstNode.Status = mOpenNodeValue;

26

27

if (mMap.IsGround(start.x, start.y - 1))

28

	firstNode.JumpLength = 0;

29

else

30

	firstNode.JumpLength = (short)(maxCharacterJumpHeight * 2);

31

32

nodes[mLocation.xy].Add(firstNode);

33

touchedLocations.Push(mLocation.xy);

34

35

mOpen.Push(mLocation);

Menghitung Penerus

Memeriksa Posisi

Kami tidak perlu banyak memodifikasi di bagian pemrosesan node; kita hanya perlu mengubah mLocation ke mLocation.xy sehingga mLocationX dan mLocationY dapat dihitung.

Ubah ini:

1

while(mOpen.Count > 0 && !mStop)

2

{

3

    mLocation    = mOpen.Pop();

4

5

    //Is it in closed list? means this node was already processed

6

    if (mCalcGrid[mLocation].Status == mCloseNodeValue)

7

        continue;

8

9

    mLocationX   = (ushort) (mLocation & mGridXMinus1);

10

    mLocationY   = (ushort) (mLocation >> mGridXLog2);

11

12

    if (mLocation == mEndLocation)

13

    {

14

        mCalcGrid[mLocation].Status = mCloseNodeValue;

15

        mFound = true;

16

        break;

17

    }

18

19

    if (mCloseNodeCounter > mSearchLimit)

20

    {

21

        mStopped = true;

22

        return null;

23

    }

Untuk ini

1

while(mOpen.Count > 0 && !mStop)

2

{

3

    mLocation = mOpen.Pop();

4

5

    //Is it in closed list? means this node was already processed

6

    if (nodes[mLocation.xy][mLocation.z].Status == mCloseNodeValue)

7

        continue;

8

9

    mLocationX = (ushort) (mLocation.xy & mGridXMinus1);

10

    mLocationY = (ushort) (mLocation.xy >> mGridXLog2);

11

12

    if (mLocation.xy == mEndLocation)

13

    {

14

        nodes[mLocation.xy][mLocation.z] = nodes[mLocation.xy][mLocation.z].UpdateStatus(mCloseNodeValue);

15

        mFound = true;

16

        break;

17

    }

18

19

    if (mCloseNodeCounter > mSearchLimit)

20

    {

21

        mStopped = true;

22

        return null;

23

    }

Perhatikan bahwa, ketika kita mengubah status node di dalam daftar node, kita menggunakan fungsi UpdateStatus(byte newStatus) . Kami tidak dapat benar-benar mengubah salah satu anggota struct di dalam daftar, karena daftar mengembalikan salinan dari node; kita perlu mengganti seluruh node. Fungsi hanya mengembalikan simpul yang disalin dengan Status diubah menjadi newStatus :

1

public PathFinderNodeFast UpdateStatus(byte newStatus)

2

{

3

    PathFinderNodeFast newNode = this;

4

    newNode.Status = newStatus;

5

    return newNode;

6

}

Kita juga perlu mengubah cara para penerus dihitung:

1

for (var i=0; i<(mDiagonals ? 8 : 4); i++)

2

{

3

    mNewLocationX = (ushort) (mLocationX + mDirection[i,0]);

4

    mNewLocationY = (ushort) (mLocationY + mDirection[i,1]);

5

    mNewLocation  = (mNewLocationY << mGridXLog2) + mNewLocationX;

Di sini kami hanya menghitung lokasi salah satu penerus; kita membutuhkan ini sehingga kita dapat menemukan posisi relatif dari simpul penerus.

Menentukan Jenis Posisi

Hal berikutnya yang perlu kita ketahui adalah jenis posisi apa yang diwakili oleh penerus.

Kami tertarik dengan empat varian di sini:

1. Karakter tidak sesuai dengan posisinya. Kami berasumsi bahwa posisi sel menanggapi "sel" karakter bawah kiri. Jika ini kasusnya, maka kita dapat membuang penerusnya, karena tidak ada cara untuk memindahkan karakter melaluinya.
2. Karakternya pas dalam posisi, dan ada di tanah. Ini berarti nilai lompatan penggantinya perlu diubah menjadi 0 .
3. Karakternya pas dalam posisi, dan tepat di bawah langit-langit. Ini berarti bahwa bahkan jika karakter memiliki kecepatan yang cukup untuk melompat lebih tinggi, itu tidak bisa, jadi kita perlu mengubah nilai lompatan dengan tepat.
4. Karakternya pas di tempat dan tidak di tanah maupun di langit-langit.

Pertama, mari kita asumsikan bahwa karakter tidak di tanah maupun di langit-langit:

1

var onGround = false;

2

var atCeiling = false;

Mari kita periksa apakah karakter sesuai dengan tempat baru. Jika tidak, kita dapat melewati penerus dan memeriksa yang berikutnya.

1

if (mGrid[mNewLocationX, mNewLocationY] == 0)

2

    continue;

Untuk memeriksa apakah karakter akan berada di tanah ketika berada di lokasi baru, kita hanya perlu melihat apakah ada blok yang solid di bawah penggantinya:

1

if (mGrid[mNewLocationX, mNewLocationY - 1] == 0)

2

    onGround = true;

Demikian juga, kami memeriksa apakah karakter akan berada di langit-langit:

1

if (mGrid[mNewLocationX, mNewLocationY + 1] == 0)

2

    atCeiling = true;    

Menghitung Nilai Lompatan

Hal berikutnya yang perlu kita lakukan adalah melihat apakah penerus ini valid atau tidak, dan jika kemudian menghitung JumpLength tepat untuk itu.

Pertama, mari kita dapatkan JumpLength dari node induk:

1

var jumpLength = nodes[mLocation.xy][mLocation.z].JumpLength;

Kami juga akan mengumumkan newJumpLength untuk pengganti yang saat ini diproses:

1

short newJumpLength = jumpLength;

Sekarang kita dapat menghitung newJumpLength . (Bagaimana kami melakukan ini dijelaskan pada awal ikhtisar teori .)

Jika simpul penerus ada di tanah, maka newJumpValue sama dengan 0:

1

if (onGround)

2

    newJumpLength = 0;

Tidak perlu khawatir di sini. Penting untuk memeriksa apakah karakter ada di tanah terlebih dahulu, karena jika karakternya ada di tanah dan di langit-langit maka kita ingin menetapkan nilai lompat ke 0 . 

Jika posisinya di langit-langit maka kita perlu mempertimbangkan dua kasus:

1. karakter harus turun lurus ke bawah, atau
2. karakter masih bisa memindahkan satu sel ke kedua sisi

Dalam kasus pertama, kita perlu mengatur newJumpLength menjadi minimal maxCharacterJumpHeight * 2 + 1 , karena nilai ini berarti kita jatuh dan langkah selanjutnya kita perlu dilakukan secara vertikal.

Dalam kasus kedua, nilai harus setidaknya maxCharacterJumpHeight * 2 . Karena nilainya seimbang, simpul penerus akan tetap dapat bergerak ke kiri atau ke kanan. 

1

else if (atCeiling)

2

{

3

    if (mNewLocationX != mLocationX)

4

        newJumpLength = (short)Mathf.Max(maxCharacterJumpHeight * 2 + 1, jumpLength + 1);

5

    else

6

        newJumpLength = (short)Mathf.Max(maxCharacterJumpHeight * 2, jumpLength + 2);

7

}

Kasus "di darat" dan "di langit-langit" dipecahkan; sekarang kita bisa menghitung nilai lompatan saat di udara.

Menghitung Nilai Lompatan di Mid-Air

Pertama, mari kita menangani kasus di mana simpul penerus berada di atas simpul induk.

Jika panjang lompatan genap, maka kita menaikkannya menjadi dua; jika tidak, kami menambahnya dengan satu. Ini akan menghasilkan nilai yang sama untuk newJumpLength: 

1

else if (mNewLocationY > mLocationY)

2

{

3

	if (jumpLength % 2 == 0)

4

		newJumpLength = (short)(jumpLength + 2);

5

	else

6

		newJumpLength = (short)(jumpLength + 1);

7

}

Karena, dalam lompatan rata-rata, kecepatan karakter memiliki nilai tertinggi pada awal dan akhir lompatan, kita harus mewakili fakta ini dalam algoritma.

Kami akan memperbaiki awal lompatan dengan memaksa algoritme untuk memindahkan dua sel ke atas jika kami baru saja keluar dari tanah. Ini dapat dengan mudah dicapai dengan menukar nilai lompatan 2 hingga 3 pada saat lompatan, karena pada lompatan nilai 3 , algoritme mengetahui bahwa karakter tidak dapat pergi ke samping (karena 3 adalah angka ganjil).

Kurva lompatan akan diubah menjadi berikut.

Mari kita juga mengakomodasi perubahan ini dalam kode: 

1

else if (mNewLocationY > mLocationY)

2

{

3

    if (jumpHeight < 2) //first jump is always two block up instead of one up and optionally one to either right or left

4

        newJumpHeight = 3;

5

	else if (jumpHeight % 2 == 0)

6

		newJumpHeight = (short)Mathf.Max(jumpHeight + 2, 2);

7

	else

8

		newJumpHeight = (short)Mathf.Max(jumpHeight + 1, 2);

9

}

(Kami akan memperbaiki kurva ketika kecepatan karakter terlalu tinggi untuk pergi ke samping ketika kami memvalidasi node nanti.) 

Sekarang mari kita menangani kasus di mana simpul baru di bawah yang sebelumnya.

Jika koordinat y baru lebih rendah dari yang dimiliki induk, itu artinya kita jatuh.Kami menghitung nilai lompatan dengan cara yang sama saat melompat, tetapi minimum harus disetel ke maxCharacterJumpHeight * 2 . (Itu karena karakter tidak perlu melakukan lompatan penuh untuk mulai jatuh — misalnya, ia dapat dengan mudah meninggalkan langkan.) Dalam hal ini, nilai lompatan harus diubah dari 1 hingga 6 segera (dalam kasus di mana karakter tinggi lompatan maksimum adalah 3):

1

else if (mNewLocationY < mLocationY)

2

{

3

	if (jumpLength % 2 == 0)

4

		newJumpLength = (short)Mathf.Max(maxCharacterJumpHeight * 2, jumpLength + 2);

5

	else

6

		newJumpLength = (short)Mathf.Max(maxCharacterJumpHeight * 2, jumpLength + 1);

7

}

Memvalidasi Penerus

Sekarang kami memiliki semua data yang kami butuhkan untuk memvalidasi pengganti, jadi mari kita lakukan.

Pertama, mari kita singkirkan simpul jika nilai lompatannya ganjil dan induknya adalah di sebelah kiri atau ke kanan. Itu karena jika nilai loncatan ganjil, maka itu berarti karakter pergi ke samping sekali dan sekarang perlu memindahkan satu blok ke atas atau ke bawah:

1

if (jumpLength % 2 != 0 && mLocationX != mNewLocationX)

2

    continue;

Jika karakter jatuh, dan simpul anak berada di atas orang tua, maka kita harus melewatinya. Ini adalah bagaimana kami mencegah lompatan infinitum iklan;begitu nilai lompatan menyentuh ambang kita hanya bisa turun.

1

if (jumpLength >= maxCharacterJumpHeight * 2 && mNewLocationY > mLocationY)

2

    continue;

Jika nilai lompatan node lebih besar dari (enam ditambah nilai ambang jatuh), maka kita harus berhenti membiarkan perubahan arah pada setiap bahkan lompatan nilai. Ini akan mencegah algoritma memberikan nilai yang salah ketika karakter jatuh sangat cepat, karena dalam kasus itu, alih-alih 1 blok ke samping dan 1 blok ke bawah, perlu memindahkan 1 blok ke samping dan 2 atau lebih blok ke bawah. (Saat ini, karakter dapat memindahkan 3 blok ke samping setelah mulai jatuh, dan kemudian kami mengizinkannya untuk bergerak ke samping setiap 4 blok yang dilalui secara vertikal.) 

1

if (newJumpLength >= maxCharacterJumpHeight * 2 + 6 && mNewLocationX != mLocationX && (newJumpLength - (maxCharacterJumpHeight * 2 + 6)) % 8 != 3)

2

    continue;

Jika ada kebutuhan untuk pemeriksaan lompatan yang lebih akurat, maka alih-alih mengabaikan node dengan cara yang ditunjukkan di atas, kita bisa membuat tabel pencarian dengan penentuan data di mana lompatan memanjang karakter itu akan dapat bergerak ke samping. 

Menghitung Biaya

Ketika menghitung biaya node, kita perlu memperhitungkan nilai lompatan.

Membuat Karakter Bergerak dengan Bijak

Ini bagus untuk membuat karakter menempel ke tanah sebanyak mungkin, karena itu akan membuat gerakannya kurang gelisah ketika bergerak melalui medan datar, dan juga akan mendorongnya untuk menggunakan jalur yang "lebih aman", yang tidak memerlukan jatuhnya lama.

Kita dapat dengan mudah membuat karakter melakukan ini dengan meningkatkan biaya simpul sesuai dengan nilai lompatannya. Ini kode lama:

1

mNewG = mCalcGrid[mLocation].G + mGrid[mNewLocationX, mNewLocationY];

Dan inilah yang baru:

1

mNewG = nodes[mLocation.xy][mLocation.z].G + mGrid[mNewLocationX, mNewLocationY] + newJumpLength / 4;

newJumpLength / 4 berfungsi dengan baik untuk sebagian besar kasus; kita tidak ingin karakter terlalu melekat pada tanah.

Meninjau Node Dengan Nilai Lompatan Yang Berbeda

Biasanya, ketika kami memproses node sekali, kami mengatur statusnya menjadi closed dan tidak perlu repot lagi; namun, seperti yang telah kita bahas, kita mungkin perlu mengunjungi posisi tertentu di grid lebih dari sekali.

Pertama, sebelum kita memutuskan untuk melewati node yang sedang diperiksa, kita perlu melihat apakah ada simpul pada posisi saat ini (x, y) .Jika belum ada simpul di sana, maka kita pasti tidak bisa melewatkan yang sekarang:

1

if (nodes[mNewLocation].Count > 0)

2

{

3

}

Satu-satunya kondisi yang memungkinkan kita untuk melewati node adalah ini: node tidak memungkinkan untuk pergerakan baru dibandingkan dengan node lain pada posisi yang sama 

Gerakan baru dapat terjadi jika:

• Nilai lompatan node yang diproses saat ini lebih rendah daripada node lainnya pada posisi (x, y) — dalam hal ini, node saat ini berjanji untuk membiarkan karakter melompat lebih tinggi menggunakan jalur ini daripada yang lain.
• Nilai lompatan node yang diproses saat ini bahkan, dan semua nilai lompatan node lain pada posisi tidak. Ini pada dasarnya berarti bahwa simpul khusus ini memungkinkan untuk gerakan menyamping pada posisi ini, sementara yang lain memaksa kita untuk bergerak naik atau turun.

Kasus pertama sederhana: kita ingin melihat melalui node dengan nilai loncatan yang lebih rendah karena ini memungkinkan kita melompat lebih tinggi. Kasus kedua muncul dalam situasi yang lebih aneh, seperti ini:

Di sini, kita tidak bisa bergerak ke samping ketika melompat karena kita ingin memaksa algoritma untuk naik dua kali setelah memulai lompatan.Masalahnya adalah bahwa, bahkan ketika jatuh, algoritma hanya akan mengabaikan node dengan nilai lompatan 8 , karena kita telah mengunjungi posisi itu dan node sebelumnya memiliki nilai lompatan lebih rendah dari 3 .Itulah mengapa dalam kasus ini penting untuk tidak melewatkan node dengan nilai lompatan genap (dan cukup rendah). 

Pertama, mari deklarasikan variabel-variabel kami yang akan memberi tahu kami nilai lompatan terendah pada posisi saat ini (x, y) , dan apakah ada simpul di sana yang memungkinkan gerakan menyamping:

1

int lowestJump = short.MaxValue;

2

bool couldMoveSideways = false;

Selanjutnya, kita perlu iterasi atas semua node dan mengatur variabel yang dideklarasikan ke nilai yang sesuai:

1

for (int j = 0; j < nodes[mNewLocation].Count; ++j)

2

{

3

    if (nodes[mNewLocation][j].JumpLength < lowestJump)

4

        lowestJump = nodes[mNewLocation][j].JumpLength;

5

6

    if (nodes[mNewLocation][j].JumpLength % 2 == 0 && nodes[mNewLocation][j].JumpLength < maxCharacterJumpHeight * 2 + 6)

7

        couldMoveSideways = true;

8

}

Seperti yang Anda lihat, kami tidak hanya memeriksa apakah nilai lompatan node genap, tetapi juga apakah nilai lompatan tidak terlalu tinggi untuk bergerak ke samping.

Akhirnya, mari kita ke kondisi yang akan memutuskan apakah kita dapat melewati node atau tidak:

1

if (lowestJump <= newJumpLength && (newJumpLength % 2 != 0 || newJumpLength >= maxCharacterJumpHeight * 2 + 6 || couldMoveSideways))

2

    continue;

Seperti yang anda lihat, node dilewati jika nilai lowestJump kurang atau sama dengan nilai lompatan node yang diproses dan setiap node lain dalam daftar diperbolehkan untuk gerakan menyamping. 

Kita dapat meninggalkan rumus heuristik apa adanya; kita tidak perlu mengubah apa pun di sini:

1

switch(mFormula)

2

{

3

    default:

4

    case HeuristicFormula.Manhattan:

5

        mH = mHEstimate * (Mathf.Abs(mNewLocationX - end.x) + Mathf.Abs(mNewLocationY - end.y));

6

        break;

7

    case HeuristicFormula.MaxDXDY:

8

        mH = mHEstimate * (Math.Max(Math.Abs(mNewLocationX - end.x), Math.Abs(mNewLocationY - end.y)));

9

        break;

10

    case HeuristicFormula.DiagonalShortCut:

11

        var h_diagonal  = Math.Min(Math.Abs(mNewLocationX - end.x), Math.Abs(mNewLocationY - end.y));

12

        var h_straight  = (Math.Abs(mNewLocationX - end.x) + Math.Abs(mNewLocationY - end.y));

13

        mH = (mHEstimate * 2) * h_diagonal + mHEstimate * (h_straight - 2 * h_diagonal);

14

        break;

15

    case HeuristicFormula.Euclidean:

16

        mH = (int) (mHEstimate * Math.Sqrt(Math.Pow((mNewLocationY - end.x) , 2) + Math.Pow((mNewLocationY - end.y), 2)));

17

        break;

18

    case HeuristicFormula.EuclideanNoSQR:

19

        mH = (int) (mHEstimate * (Math.Pow((mNewLocationX - end.x) , 2) + Math.Pow((mNewLocationY - end.y), 2)));

20

        break;

21

    case HeuristicFormula.Custom1:

22

        var dxy       = new Vector2i(Math.Abs(end.x - mNewLocationX), Math.Abs(end.y - mNewLocationY));

23

        var Orthogonal  = Math.Abs(dxy.x - dxy.y);

24

        var Diagonal    = Math.Abs(((dxy.x + dxy.y) - Orthogonal) / 2);

25

        mH = mHEstimate * (Diagonal + Orthogonal + dxy.x + dxy.y);

26

        break;

27

}

Merapikan

Sekarang, akhirnya, karena node telah lulus semua pemeriksaan, kita dapat membuat instance PathFinderNodeFast sesuai untuk itu.

1

PathFinderNodeFast newNode = new PathFinderNodeFast();

2

newNode.JumpLength = newJumpLength;

3

newNode.PX = mLocationX;

4

newNode.PY = mLocationY;

5

newNode.PZ = (byte)mIdentifier.y;

6

newNode.G = mNewG;

7

newNode.F = mNewG + mH;

8

newNode.Status = mOpenNodeValue;

Dan kita akhirnya bisa menambahkan node ke daftar node di mNewLocation .

Namun, sebelum kita melakukannya, mari tambahkan lokasi ke tumpukan lokasi yang disentuh jika daftar kosong. Kita akan tahu bahwa kita perlu menghapus daftar lokasi ini ketika kita menjalankan pathfinder lagi:

1

if (nodes[mNewLocation].Count == 0)

2

    touchedLocations.Push(mNewLocation);

3

4

nodes[mNewLocation].Add(newNode);

5

mOpen.Push(new Location(mNewLocation, nodes[mNewLocation].Count - 1));

Setelah semua anak diproses, kita dapat mengubah status orang tua menjadi closed dan menaikkan mCloseNodeCounter :

1

mCloseNodeCounter++;

2

nodes[mLocation.xy][mLocation.z] = nodes[mLocation.xy][mLocation.z].UpdateStatus(mCloseNodeValue);

Pada akhirnya, lingkaran anak-anak akan terlihat seperti ini.

1

//Lets calculate each successors

2

for (var i=0; i<(mDiagonals ? 8 : 4); i++)

3

{

4

    mNewLocationX = (ushort) (mLocationX + mDirection[i,0]);

5

    mNewLocationY = (ushort) (mLocationY + mDirection[i,1]);

6

    mNewLocation  = (mNewLocationY << mGridXLog2) + mNewLocationX;

7

8

	var onGround = false;

9

	var atCeiling = false;

10

11

    if (mGrid[mNewLocationX, mNewLocationY] == 0)

12

        goto CHILDREN_LOOP_END;

13

14

    if (mMap.IsGround(mNewLocationX, mNewLocationY - 1))

15

        onGround = true;

16

    else if (mGrid[mNewLocationX, mNewLocationY + characterHeight] == 0)

17

        atCeiling = true;	

18

19

	//calculate a proper jumplength value for the successor

20

21

    var jumpLength = nodes[mLocation.xy][mLocation.z].JumpLength;

22

    short newJumpLength = jumpLength;

23

24

	if (atCeiling)

25

    {

26

        if (mNewLocationX != mLocationX)

27

            newJumpLength = (short)Mathf.Max(maxCharacterJumpHeight * 2 + 1, jumpLength + 1);

28

        else

29

            newJumpLength = (short)Mathf.Max(maxCharacterJumpHeight * 2, jumpLength + 2);

30

    }

31

    else if (onGround)

32

		newJumpLength = 0;

33

	else if (mNewLocationY > mLocationY)

34

	{

35

        if (jumpLength < 2) //first jump is always two block up instead of one up and optionally one to either right or left

36

            newJumpLength = 3;

37

        else  if (jumpLength % 2 == 0)

38

            newJumpLength = (short)(jumpLength + 2);

39

        else

40

            newJumpLength = (short)(jumpLength + 1);

41

	}

42

	else if (mNewLocationY < mLocationY)

43

	{

44

		if (jumpLength % 2 == 0)

45

			newJumpLength = (short)Mathf.Max(maxCharacterJumpHeight * 2, jumpLength + 2);

46

		else

47

			newJumpLength = (short)Mathf.Max(maxCharacterJumpHeight * 2, jumpLength + 1);

48

	}

49

	else if (!onGround && mNewLocationX != mLocationX)

50

		newJumpLength = (short)(jumpLength + 1);

51

52

	if (jumpLength >= 0 && jumpLength % 2 != 0 && mLocationX != mNewLocationX)

53

		continue;

54

55

	//if we're falling and succeor's height is bigger than ours, skip that successor

56

	if (jumpLength >= maxCharacterJumpHeight * 2 && mNewLocationY > mLocationY)

57

		continue;

58

59

    if (newJumpLength >= maxCharacterJumpHeight * 2 + 6 && mNewLocationX != mLocationX && (newJumpLength - (maxCharacterJumpHeight * 2 + 6)) % 8 != 3)

60

		continue;

61

62

63

    mNewG = nodes[mLocation.xy][mLocation.z].G + mGrid[mNewLocationX, mNewLocationY] + newJumpLength / 4;

64

65

    if (nodes[mNewLocation].Count > 0)

66

    {

67

        int lowestJump = short.MaxValue;

68

        bool couldMoveSideways = false;

69

        for (int j = 0; j < nodes[mNewLocation].Count; ++j)

70

        {

71

            if (nodes[mNewLocation][j].JumpLength < lowestJump)

72

                lowestJump = nodes[mNewLocation][j].JumpLength;

73

74

            if (nodes[mNewLocation][j].JumpLength % 2 == 0 && nodes[mNewLocation][j].JumpLength < maxCharacterJumpHeight * 2 + 6)

75

                couldMoveSideways = true;

76

        }

77

78

        if (lowestJump <= newJumpLength && (newJumpLength % 2 != 0 || newJumpLength >= maxCharacterJumpHeight * 2 + 6 || couldMoveSideways))

79

            continue;

80

    }

81

82

    switch(mFormula)

83

    {

84

        default:

85

        case HeuristicFormula.Manhattan:

86

            mH = mHEstimate * (Mathf.Abs(mNewLocationX - end.x) + Mathf.Abs(mNewLocationY - end.y));

87

            break;

88

        case HeuristicFormula.MaxDXDY:

89

            mH = mHEstimate * (Math.Max(Math.Abs(mNewLocationX - end.x), Math.Abs(mNewLocationY - end.y)));

90

            break;

91

        case HeuristicFormula.DiagonalShortCut:

92

            var h_diagonal  = Math.Min(Math.Abs(mNewLocationX - end.x), Math.Abs(mNewLocationY - end.y));

93

            var h_straight  = (Math.Abs(mNewLocationX - end.x) + Math.Abs(mNewLocationY - end.y));

94

            mH = (mHEstimate * 2) * h_diagonal + mHEstimate * (h_straight - 2 * h_diagonal);

95

            break;

96

        case HeuristicFormula.Euclidean:

97

            mH = (int) (mHEstimate * Math.Sqrt(Math.Pow((mNewLocationY - end.x) , 2) + Math.Pow((mNewLocationY - end.y), 2)));

98

            break;

99

        case HeuristicFormula.EuclideanNoSQR:

100

            mH = (int) (mHEstimate * (Math.Pow((mNewLocationX - end.x) , 2) + Math.Pow((mNewLocationY - end.y), 2)));

101

            break;

102

        case HeuristicFormula.Custom1:

103

            var dxy       = new Vector2i(Math.Abs(end.x - mNewLocationX), Math.Abs(end.y - mNewLocationY));

104

            var Orthogonal  = Math.Abs(dxy.x - dxy.y);

105

            var Diagonal    = Math.Abs(((dxy.x + dxy.y) - Orthogonal) / 2);

106

            mH = mHEstimate * (Diagonal + Orthogonal + dxy.x + dxy.y);

107

            break;

108

    }

109

110

    PathFinderNodeFast newNode = new PathFinderNodeFast();

111

    newNode.JumpLength = newJumpLength;

112

    newNode.PX = mLocationX;

113

    newNode.PY = mLocationY;

114

    newNode.PZ = (byte)mLocation.z;

115

    newNode.G = mNewG;

116

    newNode.F = mNewG + mH;

117

    newNode.Status = mOpenNodeValue;

118

119

    if (nodes[mNewLocation].Count == 0)

120

        touchedLocations.Push(mNewLocation);

121

122

    nodes[mNewLocation].Add(newNode);

123

    mOpen.Push(new Location(mNewLocation, nodes[mNewLocation].Count - 1));

124

125

CHILDREN_LOOP_END:

126

	continue;

127

}

Memfilter Node

Kami tidak benar-benar membutuhkan semua node yang akan kami dapatkan dari algoritme. Memang, akan lebih mudah bagi kita untuk menulis AI yang mengikuti alur jika kita memfilter simpul ke set yang lebih kecil yang dapat kita kerjakan dengan lebih mudah.

Proses penyaringan node sebenarnya bukan bagian dari algoritma, tetapi lebih merupakan operasi untuk mempersiapkan output untuk diproses lebih lanjut. Tidak perlu dieksekusi di PathFinderFast kelas itu sendiri, tetapi itu akan menjadi tempat yang paling nyaman untuk melakukannya untuk keperluan tutorial ini.

Pemfilteran node dapat dilakukan bersamaan dengan path kode berikut; agaknya tidak mungkin kita akan memfilter simpul yang ditetapkan dengan sempurna untuk memenuhi kebutuhan kita dengan asumsi awal, jadi, sering kali, banyak penyesuaian akan diperlukan. Dalam tutorial ini kita akan melanjutkan dan mengurangi set ke bentuk akhirnya sekarang, jadi nanti kita bisa fokus pada AI tanpa harus memodifikasi kelas pathfinder lagi.

Kami ingin filter kami untuk melewati setiap node yang memenuhi salah satu persyaratan berikut:

1. Ini adalah simpul awal.
2. Ini adalah simpul akhir.
3. Ini adalah simpul lompatan.
4. Ini adalah node udara pertama dalam lompat samping (node ​​dengan nilai lompatan sama dengan 3).
5. Ini adalah simpul pendaratan (sebuah simpul yang memiliki nilai lompatan bukan nol menjadi 0).
6. Ini adalah titik tertinggi lompatan (simpul antara bergerak ke atas dan jatuh ke bawah).
7. Itu adalah simpul yang mengelilingi suatu rintangan.

Berikut ini beberapa ilustrasi yang menunjukkan simpul mana yang ingin kita pertahankan. Angka merah menunjukkan aturan mana di atas yang menyebabkan filter meninggalkan node di jalur:

Menyiapkan Nilai-Nilai

Kami memfilter node saat mereka didorong ke mClose daftar, jadi itu berarti kita akan pergi dari node akhir ke node awal.

1

if (mFound)

2

{

3

    mClose.Clear();

4

    var posX = end.x;

5

    var posY = end.y;

Sebelum memulai proses penyaringan, kami perlu menyiapkan beberapa variabel untuk melacak konteks simpul yang difilter:

1

var fPrevNodeTmp = new PathFinderNodeFast();

2

var fNodeTmp = nodes[mEndLocation][0];

3

4

var fNode = end;

5

var fPrevNode = end;

fNode dan fPrevNode sederhana Vector2, sementara fNodeTmp dan fPrevNodeTmp merupakan PathFinderNodeFast simpul. Kami membutuhkan keduanya; kita akan menggunakan Vector2 s untuk mendapatkan posisi simpul dan PathFinderNodeFast objek untuk mendapatkan lokasi induk, nilai lompatan, dan semua yang kita perlukan.

1

 var loc = (fNodeTmp.PY << mGridXLog2) + fNodeTmp.PX;

loc menunjuk ke posisi XY di grid node yang akan diproses iterasi berikutnya.

Mendefinisikan Perulangan

Sekarang kita bisa memulai putaran kita. Kami akan terus mengulang selama kami tidak sampai ke simpul awal (pada titik mana, posisi orang tua sama dengan posisi simpul):

1

while(fNode.x != fNodeTmp.PX || fNode.y != fNodeTmp.PY)

2

{

Kami akan membutuhkan akses ke node berikutnya serta yang sebelumnya, jadi mari kita dapatkan:

1

var fNextNodeTmp = nodes[loc][fNodeTmp.PZ];

Menambahkan Node Akhir

Sekarang mari kita mulai proses penyaringan. Node awal akan ditambahkan ke daftar di bagian paling akhir, setelah semua item lain telah ditangani. Karena kita pergi dari node akhir, mari pastikan untuk menyertakan yang satu di jalur akhir kita:

1

if ((mClose.Count == 0))

2

    mClose.Add(fNode);

Jika mClose kosong, itu berarti kita belum mendorong node ke dalamnya, yang berarti node yang diproses saat ini adalah node akhir, dan karena kami ingin memasukkannya ke dalam daftar akhir, kami menambahkannya mClose.

Menambahkan Node Lompatan

Untuk simpul melompat, kami ingin menggunakan dua kondisi.

Kondisi pertama adalah nilai lompatan node yang diproses saat ini 0, dan nilai lompatan node sebelumnya tidak 0:

1

if ((mClose.Count == 0)

2

    || (fNodeTmp.JumpLength == 0 && fPrevNodeTmp.JumpLength != 0))

3

    mClose.Add(fNode);

Kondisi kedua adalah nilai lompatan sama dengan 3. Ini pada dasarnya adalah lompatan awal atau titik perubahan arah udara pertama dalam lompatan tertentu:

1

if ((mClose.Count == 0)

2

    || (fNodeTmp.JumpLength == 0 && fPrevNodeTmp.JumpLength != 0)

3

    || (fNodeTmp.JumpLength == 3))

4

    mClose.Add(fNode);

Menambahkan Node Pendaratan

Sekarang untuk simpul pendaratan:

1

if ((mClose.Count == 0)

2

    || (fNodeTmp.JumpLength == 0 && fPrevNodeTmp.JumpLength != 0)

3

    || (fNodeTmp.JumpLength == 3)

4

    || (fNextNodeTmp.JumpLength != 0 && fNodeTmp.JumpLength == 0)   )

5

    mClose.Add(fNode);

Kami mendeteksi simpul pendaratan dengan melihat bahwa simpul berikutnya berada di tanah dan simpul saat ini tidak. Ingat bahwa kami memproses node dalam urutan terbalik, jadi sebenarnya pendaratan terdeteksi ketika node sebelumnya berada di tanah dan current tidak.

Menambahkan Titik Node Tertinggi

Sekarang mari tambahkan titik tinggi lompatan. Kami mendeteksi ini dengan melihat apakah node sebelumnya dan node berikutnya lebih rendah dari node saat ini:

1

if ((mClose.Count == 0)

2

    || (fNodeTmp.JumpLength == 0 && fPrevNodeTmp.JumpLength != 0)

3

    || (fNodeTmp.JumpLength == 3)

4

    || (fNextNodeTmp.JumpLength != 0 && fNodeTmp.JumpLength == 0)

5

    || (fNode.y > mClose[mClose.Count - 1].y && fNode.y > fNodeTmp.PY))

6

    mClose.Add(fNode);

Perhatikan bahwa, dalam kasus terakhir, kami tidak membandingkan koordinat y node saat ini fPrevNode.y, tetapi lebih ke yang sebelumnya didorong koordinat y node yang . Itu karena mungkin saja simpul sebelumnya berada pada ketinggian yang sama dengan yang sekarang, jika karakter dipindahkan ke samping untuk mencapainya.

Menambahkan Node yang Pergi berkeliling Hambatan

Akhirnya, mari kita urus node yang memungkinkan kita melakukan manuver di sekitar rintangan. Jika kita di samping hambatan dan simpul yang didorong sebelumnya tidak selaras dengan yang sekarang baik secara horizontal atau vertikal, maka kita asumsikan bahwa node ini akan menyelaraskan kita dengan rintangan dan membiarkan kita bergerak bersih atasnya jika perlu:

1

if ((mClose.Count == 0)

2

    || (fNextNodeTmp.JumpLength != 0 && fNodeTmp.JumpLength == 0)

3

    || (fNodeTmp.JumpLength == 3 && fPrevNodeTmp.JumpLength != 0)

4

    || (fNodeTmp.JumpLength == 0 && fPrevNodeTmp.JumpLength != 0)

5

    || (fNode.y > mClose[mClose.Count - 1].y && fNode.y > fNodeTmp.PY)

6

    || ((mMap.IsGround(fNode.x - 1, fNode.y) || mMap.IsGround(fNode.x + 1, fNode.y)) 

7

        && fNode.y != mClose[mClose.Count - 1].y && fNode.x != mClose[mClose.Count - 1].x))

8

    mClose.Add(fNode);

Mempersiapkan Perulangan Berikutnya

Setelah menambahkan node ke mClose daftar atau mengabaikannya, kita perlu menyiapkan variabel untuk iterasi berikutnya:

1

    fPrevNode = fNode;

2

    posX = fNodeTmp.PX;

3

    posY = fNodeTmp.PY;

4

    fPrevNodeTmp = fNodeTmp;

5

    fNodeTmp = fNextNodeTmp;

6

    loc = (fNodeTmp.PY << mGridXLog2) + fNodeTmp.PX;

7

    fNode = new Vector2i(posX, posY);

8

} 

Seperti yang anda lihat, kami menghitung semuanya dengan cara yang sama kami menyiapkan perulangan untuk iterasi pertama.

Menambahkan Node Mulai

Setelah semua node telah diproses (dan perulangan selesai), kita dapat menambahkan titik awal ke daftar dan menyelesaikan pekerjaan:

1

    mClose.Add(fNode);

2

3

    mStopped = true;

4

5

    return mClose;

6

}

Keseluruhan Bersama

Prosedur penyaringan seluruh jalur akan terlihat seperti ini.

1

if (mFound)

2

{

3

    mClose.Clear();

4

    var posX = end.x;

5

    var posY = end.y;

6

7

    var fPrevNodeTmp = new PathFinderNodeFast();

8

    var fNodeTmp = nodes[mEndLocation][0];

9

10

    var fNode = end;

11

    var fPrevNode = end;

12

13

    var loc = (fNodeTmp.PY << mGridXLog2) + fNodeTmp.PX;

14

15

    while (fNode.x != fNodeTmp.PX || fNode.y != fNodeTmp.PY)

16

    {

17

        var fNextNodeTmp = nodes[loc][fNodeTmp.PZ];

18

19

        if ((mClose.Count == 0)

20

    		|| (fNextNodeTmp.JumpLength != 0 && fNodeTmp.JumpLength == 0)

21

    		|| (fNodeTmp.JumpLength == 3 && fPrevNodeTmp.JumpLength != 0)

22

    		|| (fNodeTmp.JumpLength == 0 && fPrevNodeTmp.JumpLength != 0)

23

    		|| (fNode.y > mClose[mClose.Count - 1].y && fNode.y > fNodeTmp.PY)

24

    		|| ((mMap.IsGround(fNode.x - 1, fNode.y) || mMap.IsGround(fNode.x + 1, fNode.y)) 

25

    			&& fNode.y != mClose[mClose.Count - 1].y && fNode.x != mClose[mClose.Count - 1].x))

26

	    	mClose.Add(fNode);

27

28

        fPrevNode = fNode;

29

        posX = fNodeTmp.PX;

30

        posY = fNodeTmp.PY;

31

        fPrevNodeTmp = fNodeTmp;

32

        fNodeTmp = fNextNodeTmp;

33

        loc = (fNodeTmp.PY << mGridXLog2) + fNodeTmp.PX;

34

        fNode = new Vector2i(posX, posY);

35

    }

36

37

    mClose.Add(fNode);

38

39

    mStopped = true;

40

41

    return mClose;

42

}

Kesimpulan

Produk akhir dari algoritma ini adalah jalan yang ditemukan untuk karakter yang satu blok lebar dan satu blok tinggi dengan ketinggian lompatan maksimum yang ditentukan.

Kita bisa memperbaiki ini: kita bisa membiarkan ukuran karakter bervariasi, kita bisa menambahkan dukungan untuk platform satu arah, dan kita bisa mengkodekan bot AI untuk mengikuti jalannya. Kami akan membahas semua hal ini di bagian selanjutnya dari tutorial!