A* Pathfinding untuk Platformer Berbasis Grid 2D: Ledge Grabbing

() translation by (you can also view the original English article)

Di bagian seri kami ini dengan mengadaptasi algoritma A * pathfinding ke platformers, kami akan memperkenalkan mekanik baru ke karakter: ledge grabbing. Kami juga akan membuat perubahan yang sesuai untuk algoritma pathfinding dan bot AI, sehingga mereka dapat menggunakan mobilitas yang ditingkatkan.

Demo

Anda dapat memainkan demo Unity, atau versi WebGL (16MB), untuk melihat hasil akhir dalam aksi. Gunakan WASD untuk memindahkan karakter, klik kiri di suatu tempat untuk menemukan jalan yang dapat Anda ikuti untuk sampai ke sana, klik kanan sel untuk beralih ke tanah pada titik itu, klik tengah untuk menempatkan platform satu arah, dan klik -dan-tarik slider untuk mengubah nilainya.

Ledge Grabbing Mechanics

Ikhtisar Kontrol

Pertama-tama mari kita lihat bagaimana langkan meraih mekanik bekerja di demo untuk mendapatkan beberapa wawasan tentang bagaimana kita harus mengubah algoritma pathfinding kami untuk mempertimbangkan mekanik baru ini.

Kontrol untuk langkan grabbing cukup sederhana: jika karakter tepat di samping langkan saat jatuh, dan pemain menekan tombol arah kiri atau kanan untuk memindahkannya ke langkan itu, maka ketika karakter berada pada posisi yang tepat, ia akan meraih langkan.

Setelah karakter meraih langkan, pemain memiliki dua opsi: mereka dapat melompat atau turun. Melompat bekerja seperti biasa; pemain menekan tombol lompat dan gaya lompatannya identik dengan gaya yang diterapkan saat melompat dari tanah. Menjatuhkan turun dilakukan dengan menekan tombol ke bawah (S), atau keyna arah yang menunjuk jauh dari langkan.

Menerapkan Kontrol

Mari kita lihat bagaimana kontrol ambil tepi bekerja dalam kode. Hal pertama yang harus dilakukan adalah mendeteksi apakah langkan berada di sebelah kiri atau di sebelah kanan karakter:

1	bool ledgeOnLeft = mLedgeTile.x * Map.cTileSize < mPosition.x;
2	bool ledgeOnRight = !ledgeOnLeft;

Kita dapat menggunakan informasi itu untuk menentukan apakah karakter itu seharusnya turun dari langkan. Seperti yang Anda lihat, untuk drop down, pemain harus baik:

press the down button,
tekan tombol kiri saat kita meraih langkan di kanan, atau
tekan tombol kanan ketika kita meraih langkan di sebelah kiri.

bool ledgeOnLeft = mLedgeTile.x * Map.cTileSize < mPosition.x;
bool ledgeOnRight = !ledgeOnLeft;

if (mInputs[(int)KeyInput.GoDown]
    || (mInputs[(int)KeyInput.GoLeft] && ledgeOnRight)
    || (mInputs[(int)KeyInput.GoRight] && ledgeOnLeft))
{

}

Ada peringatan kecil di sini. Pertimbangkan situasi ketika kita menahan tombol ke bawah dan tombol kanan, ketika karakter itu memegang langkan ke kanan. Ini akan menghasilkan situasi berikut:

Masalahnya di sini adalah bahwa karakter meraih langkan segera setelah ia melepaskannya.

Solusi sederhana untuk ini adalah mengunci gerakan ke arah langkan untuk beberapa frame setelah kita turun dari langkan. Itulah yang dilakukan cuplikan berikut:

bool ledgeOnLeft = mLedgeTile.x * Map.cTileSize < mPosition.x;
bool ledgeOnRight = !ledgeOnLeft;

if (mInputs[(int)KeyInput.GoDown]
    || (mInputs[(int)KeyInput.GoLeft] && ledgeOnRight)
    || (mInputs[(int)KeyInput.GoRight] && ledgeOnLeft))
{
    if (ledgeOnLeft)
        mCannotGoLeftFrames = 3;
    else
        mCannotGoRightFrames = 3;
}

Setelah ini, kita mengubah status karakter ke Jump, yang akan menangani fisika lompatan:

bool ledgeOnLeft = mLedgeTile.x * Map.cTileSize < mPosition.x;
bool ledgeOnRight = !ledgeOnLeft;

if (mInputs[(int)KeyInput.GoDown]
    || (mInputs[(int)KeyInput.GoLeft] && ledgeOnRight)
    || (mInputs[(int)KeyInput.GoRight] && ledgeOnLeft))
{
    if (ledgeOnLeft)
        mCannotGoLeftFrames = 3;
    else
        mCannotGoRightFrames = 3;

    mCurrentState = CharacterState.Jump;
}

Akhirnya, jika karakter tidak jatuh dari langkan, kami memeriksa apakah tombol lompat telah ditekan; jika demikian, kita mengatur kecepatan vertikal lompat dan mengubah negara:

bool ledgeOnLeft = mLedgeTile.x * Map.cTileSize < mPosition.x;
bool ledgeOnRight = !ledgeOnLeft;

if (mInputs[(int)KeyInput.GoDown]
    || (mInputs[(int)KeyInput.GoLeft] && ledgeOnRight)
    || (mInputs[(int)KeyInput.GoRight] && ledgeOnLeft))
{
    if (ledgeOnLeft)
        mCannotGoLeftFrames = 3;
    else
        mCannotGoRightFrames = 3;

    mCurrentState = CharacterState.Jump;
}
else if (mInputs[(int)KeyInput.Jump])
{
    mSpeed.y = mJumpSpeed;
    mCurrentState = CharacterState.Jump;
}

Mendeteksi Point Grab Ledge

Mari kita lihat bagaimana kita menentukan apakah langkan dapat diraih. Kami menggunakan beberapa hotspot di sekitar tepi karakter:

Kontur kuning mewakili batas karakter. Segmen merah mewakili sensor dinding; ini digunakan untuk menangani fisika karakter. Segmen biru mewakili di mana karakter kita bisa meraih langkan.

Untuk menentukan apakah karakter dapat mengambil langkan, kode kami terus-menerus memeriksa sisi yang sedang bergerak ke arahnya. Ini mencari genteng kosong di bagian atas segmen biru, dan kemudian ubin padat di bawahnya yang bisa diraih oleh karakter.

Catatan: ledge grabbing terkunci jika karakternya melompat ke atas. Ini dapat dengan mudah dilihat di demo dan di animasi di bagian Ikhtisar Kontrol.

Masalah utama dengan metode ini adalah bahwa jika karakter kita jatuh pada kecepatan tinggi, sangat mudah untuk melewatkan jendela di mana ia dapat meraih langkan. Kita bisa menyelesaikan ini dengan mencari semua ubin mulai dari posisi frame sebelumnya ke frame saat ini untuk mencari ubin kosong di atas yang padat. Jika salah satu ubin semacam itu ditemukan, maka itu bisa diraih.

Sekarang kami telah membersihkan bagaimana langkan meraih karya mekanik, mari kita lihat bagaimana menggabungkannya ke dalam algoritma pathfinding kami.

Perubahan Pathfinder

Jadikan Kemungkinan untuk Memutar Ledge Grabbing On dan Off

Pertama-tama, mari kita tambahkan parameter baru ke fungsi FindPath kami yang menunjukkan apakah pathfinder harus mempertimbangkan meraih tepian. Kami akan memberinya nama useLedges:

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

Deteksi Ledge Grab Nodes

Kondisi

Sekarang kita perlu memodifikasi fungsi untuk mendeteksi apakah suatu node tertentu dapat digunakan untuk merebut tepi. Kita bisa melakukan itu setelah memeriksa apakah simpul tersebut merupakan node "di darat" atau node "di langit-langit", karena dalam kedua kasus itu tidak dapat digunakan untuk meraih tepian.

if (onGround)
  newJumpLength = 0;
else if (atCeiling)
{
    if (mNewLocationX != mLocationX)
        newJumpLength = (short)Mathf.Max(maxCharacterJumpHeight * 2 + 1, jumpLength + 1);
    else
        newJumpLength = (short)Mathf.Max(maxCharacterJumpHeight * 2, jumpLength + 2);
}
else if (/*check whether there's a ledge grabbing node here */)
{
}
else if (mNewLocationY < mLocationY)
{

Baiklah: sekarang kita perlu mencari tahu kapan sebuah node harus dianggap sebagai simpul grabing. Untuk keangkuhan, berikut adalah diagram yang menunjukkan beberapa contoh posisi grabing langkan:

... dan inilah cara tampilan permainan ini:

Sprite karakter teratas direntangkan untuk menunjukkan bagaimana tampilan ini dengan karakter dari berbagai ukuran.

Sel-sel merah mewakili node yang diperiksa; bersama dengan sel hijau, mereka mewakili karakter dalam algoritma kami. Dua situasi teratas menunjukkan langkan masing-masing 2 x 2 karakter di kiri dan kanan. Dua bagian bawah menunjukkan hal yang sama, tetapi ukuran karakter di sini adalah 1x3 bukan 2x2.

Seperti yang Anda lihat, seharusnya cukup mudah untuk mendeteksi kasus-kasus ini dalam algoritma. Kondisi untuk node ambil langkan akan menjadi seperti berikut:

Ada ubin padat di sebelah ubin karakter kanan-atas / kiri-atas.
Ada ubin kosong di atas ubin padat yang ditemukan.
Tidak ada ubin padat di bawah karakter (tidak perlu meraih tepian jika di tanah).

Perhatikan bahwa kondisi ketiga sudah diurus, karena kami memeriksa nodus grabge hanya jika karakter tidak di tanah.

Pertama-tama, mari kita periksa apakah kita benar-benar ingin mendeteksi grabge grabs:

1	else if (useLedges)

Sekarang mari kita periksa apakah ada ubin di sebelah kanan node karakter kanan atas:

1	else if (useLedges
2	&& mGrid[mNewLocationX + characterWidth, mNewLocationY + characterHeight - 1] == 0)

Dan kemudian, jika di atas ubin itu ada ruang kosong:

1	else if (useLedges
2	&& mGrid[mNewLocationX + characterWidth, mNewLocationY + characterHeight - 1] == 0
3	&& mGrid[mNewLocationX + characterWidth, mNewLocationY + characterHeight] != 0)

Sekarang kita perlu melakukan hal yang sama untuk sisi kiri:

else if (useLedges

        && ((mGrid[mNewLocationX + characterWidth, mNewLocationY + characterHeight - 1] == 0 && mGrid[mNewLocationX + characterWidth, mNewLocationY + characterHeight] != 0)

            || (mGrid[mNewLocationX - 1, mNewLocationY + characterHeight - 1] == 0 && mGrid[mNewLocationX - 1, mNewLocationY + characterHeight] != 0)))

Ada satu hal lagi yang dapat kita lakukan secara opsional, yaitu menonaktifkan mencari node ambil langkan jika kecepatan jatuh terlalu tinggi, sehingga jalannya tidak mengembalikan beberapa posisi ambil langkan ekstrim yang akan sulit diikuti oleh bot:

else if (useLedges 
        && jumpLength <= maxCharacterJumpHeight * 2 + 6
        && ((mGrid[mNewLocationX + characterWidth, mNewLocationY + characterHeight - 1] == 0 && mGrid[mNewLocationX + characterWidth, mNewLocationY + characterHeight] != 0)
            || (mGrid[mNewLocationX - 1, mNewLocationY + characterHeight - 1] == 0 && mGrid[mNewLocationX - 1, mNewLocationY + characterHeight] != 0)))
{
}

Setelah semua ini, kita dapat yakin bahwa simpul yang ditemukan adalah simpul ambil langkan.

Menambahkan Node Khusus

Apa yang kita lakukan ketika kita menemukan simpul ambil langkan? Kita perlu mengatur nilai lompatannya.

Ingat, nilai lompatan adalah angka yang mewakili fase mana lompatan karakter itu, jika mencapai sel ini. Jika Anda membutuhkan rekap tentang cara kerja algoritme, lihat lagi artikel teori.

Tampaknya yang perlu kita lakukan adalah mengatur nilai lompatan dari simpul ke 0, karena dari titik raungan, karakter secara efektif dapat mengatur ulang lompatan, seolah-olah berada di tanah — tetapi ada beberapa poin untuk dipertimbangkan di sini.

Pertama, alangkah baiknya jika kita dapat mengatakan secara sekilas apakah simpul tersebut merupakan simpul ambil langkan atau tidak: ini akan sangat membantu ketika membuat perilaku bot dan juga ketika memfilter simpul.
Kedua, biasanya melompat dari tanah dapat dieksekusi dari titik mana yang akan paling cocok pada ubin tertentu, tetapi ketika melompat dari langkan, karakter terjebak ke posisi tertentu dan tidak dapat melakukan apa pun tetapi mulai jatuh atau melompat ke atas.

Mempertimbangkan peringatan tersebut, kami akan menambahkan nilai lompatan khusus untuk node ambil langkan. Tidak terlalu penting apa nilai ini, tapi itu ide yang baik untuk membuatnya negatif, karena itu akan menurunkan peluang kita salah menafsirkan node.

1	const short cLedgeGrabJumpValue = -9;

Sekarang mari kita menetapkan nilai ini ketika kita mendeteksi simpul ambil langkan:

else if (useLedges 
        && jumpLength <= maxCharacterJumpHeight * 2 + 6
        && ((mGrid[mNewLocationX + characterWidth, mNewLocationY + characterHeight - 1] == 0 && mGrid[mNewLocationX + characterWidth, mNewLocationY + characterHeight] != 0)
            || (mGrid[mNewLocationX - 1, mNewLocationY + characterHeight - 1] == 0 && mGrid[mNewLocationX - 1, mNewLocationY + characterHeight] != 0)))
{
    newJumpLength = cLedgeGrabJumpValue;
}

Membuat cLedgeGrabJumpValue negatif akan memiliki efek pada perhitungan biaya node-itu akan membuat algoritma lebih suka menggunakan langkan daripada melewatkannya. Ada dua hal yang perlu diperhatikan di sini:

Poin ambil ledge menawarkan kemungkinan gerakan yang lebih besar daripada node di udara lainnya, karena karakter dapat melompat lagi dengan menggunakan mereka; dari sudut pandang ini, itu adalah hal yang baik bahwa node ini akan lebih murah daripada yang lain.
Meraih terlalu banyak tepian sering mengarah ke gerakan yang tidak wajar, karena biasanya pemain tidak menggunakan pegangan langkan kecuali jika mereka perlu mencapai suatu tempat.

Dalam animasi di atas, Anda dapat melihat perbedaan antara naik ketika langkan lebih disukai dan ketika tidak.

Untuk saat ini kami akan meninggalkan perhitungan biaya seperti itu, tetapi cukup mudah untuk memodifikasinya, untuk membuat simpul langkan lebih mahal.

Ubah Nilai Langsung Saat Melompat atau Turun Dari Langkan

Sekarang kita perlu menyesuaikan nilai lompatan untuk node yang dimulai dari titik ambil langkan. Kita perlu melakukan ini karena melompat dari posisi ambil langkan sangat berbeda dari melompat dari tanah. Hanya ada sedikit kebebasan ketika melompat dari langkan, karena karakternya tetap pada titik tertentu.

Ketika di tanah, karakter dapat bergerak bebas ke kiri atau kanan dan melompat pada saat yang paling tepat.

Pertama, mari kita atur kasus ketika karakter turun dari langkan ambil:

else if (mNewLocationY < mLocationY)
{
    if (jumpLength == cLedgeGrabJumpValue)
        newJumpLength = (short)(maxCharacterJumpHeight * 2 + 4);
    else if (jumpLength % 2 == 0)
		newJumpLength = (short)Mathf.Max(maxCharacterJumpHeight * 2, jumpLength + 2);
	else
		newJumpLength = (short)Mathf.Max(maxCharacterJumpHeight * 2, jumpLength + 1);
}

Seperti yang Anda lihat, panjang lompatan baru sedikit lebih besar jika karakter turun dari langkan: dengan cara ini kita mengimbangi kurangnya manuver saat mengambil langkan, yang akan menghasilkan kecepatan vertikal yang lebih tinggi sebelum pemain dapat mencapai node lain. .

Selanjutnya adalah kasus di mana karakter turun ke satu sisi dari meraih langkan:

else if (!onGround && mNewLocationX != mLocationX)
{
    if (jumpLength == cLedgeGrabJumpValue)
        newJumpLength = (short)(maxCharacterJumpHeight * 2 + 3);
    else
        newJumpLength = (short)Mathf.Max(jumpLength + 1, 1);
}

Yang perlu kita lakukan adalah mengatur nilai lompatan ke nilai yang jatuh.

Abaikan Lebih Banyak Simpul

Kita perlu menambahkan beberapa kondisi tambahan ketika kita perlu mengabaikan simpul.

Pertama-tama, ketika kita melompat dari posisi ambil langkan, kita harus naik, bukan ke samping. Ini bekerja sama dengan melompat dari tanah. Kecepatan vertikal jauh lebih tinggi daripada kemungkinan kecepatan horizontal pada titik ini, dan kita perlu memodelkan fakta ini dalam algoritma:

1	if (jumpLength == cLedgeGrabJumpValue && mLocationX != mNewLocationX && newJumpLength < maxCharacterJumpHeight * 2)
2	continue;

Jika kita ingin membiarkan menjatuhkan dari langkan ke sisi yang berlawanan seperti ini:

Kemudian kita perlu mengedit kondisi yang tidak memungkinkan gerakan horizontal ketika nilai lompatan ganjil. Itu karena, saat ini, nilai ambil langkan khusus kami sama dengan -9, jadi itu hanya tepat untuk mengecualikan semua angka negatif dari kondisi ini.

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

Perbarui Filter Node

Akhirnya, mari kita lanjutkan ke pemfilteran node. Yang perlu kita lakukan di sini adalah menambahkan kondisi untuk node grabge grabge, sehingga kita tidak memfilternya. Kami hanya perlu memeriksa apakah nilai lompatan node sama dengan cLedgeGrabJumpValue:

1	\|\| (fNodeTmp.JumpLength == cLedgeGrabJumpValue)

Seluruh penyaringan terlihat seperti ini sekarang:

if ((mClose.Count == 0)
    || (mMap.IsOneWayPlatform(fNode.x, fNode.y - 1))
    || (mGrid[fNode.x, fNode.y - 1] == 0 && mMap.IsOneWayPlatform(fPrevNode.x, fPrevNode.y - 1))
    || (fNodeTmp.JumpLength == 3)
    || (fNextNodeTmp.JumpLength != 0 && fNodeTmp.JumpLength == 0)                                                                                                       //mark jumps starts
    || (fNodeTmp.JumpLength == 0 && fPrevNodeTmp.JumpLength != 0)                                                                                                       //mark landings
    || (fNode.y > mClose[mClose.Count - 1].y && fNode.y > fNodeTmp.PY)
    || (fNodeTmp.JumpLength == cLedgeGrabJumpValue)
    || (fNode.y < mClose[mClose.Count - 1].y && fNode.y < fNodeTmp.PY)
    || ((mMap.IsGround(fNode.x - 1, fNode.y) || mMap.IsGround(fNode.x + 1, fNode.y)) 
        && fNode.y != mClose[mClose.Count - 1].y && fNode.x != mClose[mClose.Count - 1].x))
    mClose.Add(fNode);

Itu saja — ini semua perubahan yang perlu kami lakukan untuk memperbarui algoritma pathfinding.

Perubahan Bot

Sekarang bahwa jalur kita menunjukkan titik-titik di mana karakter dapat mengambil langkan, mari kita memodifikasi perilaku bot sehingga memanfaatkan data ini.

Hentikan Hitung ulang reachX dan reachY

Pertama-tama, untuk membuat semuanya lebih jelas di bot, mari kita perbarui fungsi GetContext (). Masalah saat ini dengan itu adalah reachX dan nilai reachY terus dihitung ulang, yang menghilangkan beberapa informasi tentang konteksnya. Nilai-nilai ini digunakan untuk melihat apakah bot telah mencapai node target pada sumbu x dan y, masing-masing. (Jika Anda membutuhkan penyegaran tentang cara kerjanya, lihat tutorial saya tentang pengkodean bot.)

Mari kita ubah ini sehingga jika karakter mencapai simpul pada sumbu x atau y, maka nilai-nilai ini tetap benar selama kita tidak beralih ke node berikutnya.

Untuk memungkinkan hal ini, kita perlu menyatakan reachX dan reachY sebagai anggota kelas:

1	public bool mReachedNodeX;
2	public bool mReachedNodeY;

Ini berarti kita tidak perlu lagi meneruskannya ke fungsi GetContext ():

1	public void GetContext(out Vector2 prevDest, out Vector2 currentDest, out Vector2 nextDest, out bool destOnGround)

Dengan perubahan ini, kita juga perlu mengatur ulang variabel secara manual setiap kali kita mulai bergerak menuju simpul berikutnya. Kejadian pertama adalah ketika kita baru saja menemukan jalan dan akan bergerak ke arah node pertama:

if (path != null && path.Count > 1)
{
    for (var i = path.Count - 1; i >= 0; --i)
        mPath.Add(path[i]);

    mCurrentNodeId = 1;
    mReachedNodeX = false;
    mReachedNodeY = false;

Yang kedua adalah ketika kita telah mencapai target simpul saat ini dan ingin untuk bergerak ke arah berikutnya:

if (mReachedNodeX && mReachedNodeY)
{
    int prevNodeId = mCurrentNodeId;
    mCurrentNodeId++;
    mReachedNodeX = false;
    mReachedNodeY = false;

Untuk menghentikan gelondongan variabel, kita harus mengganti baris berikut:

1	reachedX = ReachedNodeOnXAxis(pathPosition, prevDest, currentDest);
2	reachedY = ReachedNodeOnYAxis(pathPosition, prevDest, currentDest);

... dengan ini, yang akan mendeteksi apakah kita telah mencapai sebuah node pada sumbu hanya jika kita belum mencapai itu:

if (!mReachedNodeX)
    mReachedNodeX = ReachedNodeOnXAxis(pathPosition, prevDest, currentDest);

if (!mReachedNodeY)
    mReachedNodeY = ReachedNodeOnYAxis(pathPosition, prevDest, currentDest);

Tentu saja, kita juga perlu untuk mengganti setiap kejadian reachedX dan reachedY dengan versi baru dinyatakan mReachedNodeX dan mReachedNodeY.

Lihat jika karakter perlu ambil birai

Mari kita menyatakan beberapa variabel yang akan kita gunakan untuk menentukan apakah bot perlu ambil birai, dan, jika demikian, yang mana:

1	public bool mGrabsLedges = false;
2	bool mMustGrabLeftLedge;
3	bool mMustGrabRightLedge;

mGrabsLedges adalah tanda bahwa kami menyampaikan pada algoritma untuk membiarkan tahu apakah itu harus menemukan jalan termasuk perampasan langkan. mMustGrabLeftLedge dan mMustGrabRightLedge akan digunakan untuk menentukan apakah node berikutnya adalah birai ambil, dan apakah bot harus ambil langkan ke kiri atau ke kanan.

Apa yang ingin kita lakukan sekarang adalah membuat fungsi yang diberikan sebuah node, akan mampu mendeteksi apakah karakter di simpul tersebut akan mampu meraih birai.

Kita akan membutuhkan dua fungsi untuk ini: satu akan memeriksa jika karakter dapat mengambil birai di sebelah kiri, dan yang lain akan memeriksa apakah karakter dapat mengambil birai di sebelah kanan. Fungsi-fungsi ini akan bekerja dengan cara yang sama sebagai kode pathfinding kita untuk mendeteksi tepian:

public bool CanGrabLedgeOnLeft(int nodeId)
{
    return (mMap.IsObstacle(mPath[nodeId].x - 1, mPath[nodeId].y + mHeight - 1)
        && !mMap.IsObstacle(mPath[nodeId].x - 1, mPath[nodeId].y + mHeight));
}

public bool CanGrabLedgeOnRight(int nodeId)
{
    return (mMap.IsObstacle(mPath[nodeId].x + mWidth, mPath[nodeId].y + mHeight - 1)
            && !mMap.IsObstacle(mPath[nodeId].x + mWidth, mPath[nodeId].y + mHeight));
}

Seperti yang Anda lihat, kami memeriksa apakah ada genteng padat di karakter kita dengan ubin kosong di atasnya.

Sekarang mari kita pergi ke fungsi GetContext(), dan menetapkan nilai-nilai yang sesuai untuk mMustGrabRightLedge dan mMustGrabLeftLedge. Kita perlu untuk mengatur mereka untuk true jika karakter seharusnya ambil tepian sama sekali (itu adalah, jika mGrabsLedges true) dan jika ada birai untuk berpegangan mmmm.

1	mMustGrabLeftLedge = mGrabsLedges && !destOnGround && CanGrabLedgeOnLeft(mCurrentNodeId);
2	mMustGrabRightLedge = mGrabsLedges && !destOnGround && CanGrabLedgeOnRight(mCurrentNodeId);

Perhatikan bahwa kita juga tidak ingin ambil tepian jika node tujuan di tanah.

Memperbarui nilai melompat

Seperti Anda mungkin memperhatikan, karakter posisi ketika meraih birai sedikit berbeda ke posisi ketika berdiri tepat di bawah ini:

Langkan meraih posisi sedikit lebih tinggi dari posisi berdiri, meskipun karakter ini menempati node yang sama. Ini berarti bahwa meraih birai akan memerlukan lompatan yang sedikit lebih tinggi daripada hanya melompat pada platform, dan kita perlu memperhitungkan ini.

Mari kita lihat fungsi yang menentukan berapa lama harus menekan tombol lompat:

public int GetJumpFramesForNode(int prevNodeId)
{
    int currentNodeId = prevNodeId + 1;

    if (mPath[currentNodeId].y - mPath[prevNodeId].y > 0 && mOnGround)
    {
        int jumpHeight = 1;
        for (int i = currentNodeId; i < mPath.Count; ++i)
        {
            if (mPath[i].y - mPath[prevNodeId].y >= jumpHeight)
                jumpHeight = mPath[i].y - mPath[prevNodeId].y;
            if (mPath[i].y - mPath[prevNodeId].y < jumpHeight || mMap.IsGround(mPath[i].x, mPath[i].y - 1))
                return GetJumpFrameCount(jumpHeight);
        }
    }

    return 0;
}

Pertama-tama, kami akan mengubah kondisi awal. Bot harus mampu melompat, bukan hanya dari tanah, tetapi juga ketika itu meraih birai:

1	if (mPath[currentNodeId].y - mPath[prevNodeId].y > 0 && (mOnGround \|\| mCurrentState == CharacterState.GrabLedge))

Sekarang kita perlu menambahkan beberapa frame lebih jika meloncat ambil birai. Pertama-tama kita perlu tahu jika itu benar-benar bisa melakukan itu, jadi mari kita membuat fungsi yang akan mengatakan apakah karakter dapat mengambil birai ke kiri atau kanan:

1	public bool CanGrabLedge(int nodeId)
2	{
3	return CanGrabLedgeOnLeft(nodeId) \|\| CanGrabLedgeOnRight(nodeId);
4	}

Sekarang mari kita menambahkan beberapa frame untuk melompat ketika bot perlu ambil birai:

if (mPath[i].y - mPath[prevNodeId].y >= jumpHeight)
    jumpHeight = mPath[i].y - mPath[prevNodeId].y;
if (mPath[i].y - mPath[prevNodeId].y < jumpHeight || mMap.IsGround(mPath[i].x, mPath[i].y - 1))
    return (GetJumpFrameCount(jumpHeight));
else if (grabLedges && CanGrabLedge(i))
    return (GetJumpFrameCount(jumpHeight) + 4);

Seperti yang Anda lihat, kita memperpanjang melompat dengan 4 frame, yang harus melakukan pekerjaan baik dalam kasus kami.

Tapi ada satu hal lagi kita perlu mengubah di sini, yang benar-benar tidak memiliki banyak hubungannya dengan meraih langkan. Ini perbaikan kasus ketika node berikutnya ketinggian yang sama sebagai satu saat ini, tapi tidak di tanah, dan node setelah itu di tinggi, berarti lompatan diperlukan:

if ((mPath[currentNodeId].y - mPath[prevNodeId].y > 0

        || (mPath[currentNodeId].y - mPath[prevNodeId].y == 0 && !mMap.IsGround(mPath[currentNodeId].x, mPath[currentNodeId].y - 1) && mPath[currentNodeId+1].y - mPath[prevNodeId].y > 0))

    && (mOnGround || mCurrentState == CharacterState.GrabLedge))

Menerapkan logika gerakan untuk meraih ke dan mengantar tepian

Kita akan ingin membagi langkan meraih logika menjadi dua fase: satu untuk Kapan bot ini masih tidak cukup langkan untuk memulai grabbing, jadi kami hanya ingin melanjutkan gerakan seperti biasa, dan satu untuk ketika anak laki-laki dapat dengan aman mulai bergerak ke arah itu untuk meraihnya.

Mari kita mulai dengan menyatakan Boolean yang akan menunjukkan apakah kami sudah pindah ke tahap kedua. Kami akan nama mCanGrabLedge:

1	public bool mGrabsLedges = false;
2	bool mMustGrabLeftLedge;
3	bool mMustGrabRightLedge;
4	bool mCanGrabLedge = false;

Sekarang kita perlu untuk menentukan kondisi yang akan membiarkan karakter yang pindah ke tahap kedua. Ini cukup sederhana:

Bot telah mencapai tujuan node pada sumbu X.
Bot perlu ambil baik langkan kiri atau kanan.
Jika bot bergerak menuju langkan, itu akan bertabrakan dinding bukannya lebih lanjut.

Baiklah, pertama dua kondisi sangat sederhana untuk memeriksa sekarang karena kita sudah melakukan semua pekerjaan yang diperlukan sudah:

1	if (!mCanGrabLedge && mReachedNodeX && (mMustGrabLeftLedge \|\| mMustGrabRightLedge))
2	{
3	}
4	else if (mReachedNodeX && mReachedNodeY)

Sekarang, ketiga kondisi kita dapat memisahkan menjadi dua bagian. Yang pertama akan mengurus situasi dimana karakter bergerak menuju langkan dari bawah, dan yang kedua dari atas. Kondisi yang kita ingin mengatur untuk kasus pertama adalah:

Posisi saat ini yang bot lebih rendah daripada posisi sasaran (itu mendekati dari bawah).
Bagian atas kotak melompat-lompat karakter lebih tinggi dari ketinggian ubin langkan.

1	(pathPosition.y < currentDest.y
2	&& (currentDest.y + Map.cTileSizemHeight) < pathPosition.y + mAABB.HalfSizeY 2)

Jika bot mendekati dari atas, kondisi adalah sebagai berikut:

Posisi saat ini yang bot lebih tinggi dibandingkan target posisi (itu mendekati dari atas).
Perbedaan antara karakter posisi dan posisi sasaran berjarak kurang dari tinggi karakter.

1	(pathPosition.y > currentDest.y
2	&& pathPosition.y - currentDest.y < mHeight * Map.cTileSize)

Sekarang mari kita menggabungkan semua ini dan mengatur bendera yang menunjukkan bahwa kita dapat dengan aman pindah ke arah birai:

 else if (!mCanGrabLedge && mReachedNodeX && (mMustGrabLeftLedge || mMustGrabRightLedge) &&
    ((pathPosition.y < currentDest.y && (currentDest.y + Map.cTileSize*mHeight) < pathPosition.y + mAABB.HalfSizeY * 2)
    || (pathPosition.y > currentDest.y && pathPosition.y - currentDest.y < mHeight * Map.cTileSize)))
{
    mCanGrabLedge = true;
}

Ada satu hal lagi yang ingin kita lakukan di sini, dan itu adalah untuk segera mulai bergerak menuju langkan:

if (!mCanGrabLedge && mReachedNodeX && (mMustGrabLeftLedge || mMustGrabRightLedge) &&
    ((pathPosition.y < currentDest.y && (currentDest.y + Map.cTileSize*mHeight) < pathPosition.y + mAABB.HalfSizeY * 2)
    || (pathPosition.y > currentDest.y && pathPosition.y - currentDest.y < mHeight * Map.cTileSize)))
{
    mCanGrabLedge = true;
    
    if (mMustGrabLeftLedge)
        mInputs[(int)KeyInput.GoLeft] = true;
    else if (mMustGrabRightLedge)
        mInputs[(int)KeyInput.GoRight] = true;
}

OK, sekarang sebelum kondisi besar ini Mari kita membuat satu lagi. Ini pada dasarnya akan versi sederhana untuk gerakan ketika bot akan ambil birai:

if (mCanGrabLedge && mCurrentState != CharacterState.GrabLedge)
{
    if (mMustGrabLeftLedge)
        mInputs[(int)KeyInput.GoLeft] = true;
    else if (mMustGrabRightLedge)
        mInputs[(int)KeyInput.GoRight] = true;
}
else if (!mCanGrabLedge && mReachedNodeX && (mMustGrabLeftLedge || mMustGrabRightLedge) &&

Itulah logika utama di balik meraih langkan, tetapi masih ada beberapa hal yang harus dilakukan.

Kita perlu mengedit kondisi di mana kami memeriksa apakah itu OK untuk pindah ke node berikutnya. Saat ini, kondisi seperti ini:

1	else if (mReachedNodeX && mReachedNodeY)

Sekarang kita perlu juga pindah ke node berikutnya jika bot siap untuk ambil langkan dan kemudian benar-benar melakukannya:

1	else if ((mReachedNodeX && mReachedNodeY) \|\| (mCanGrabLedge && mCurrentState == CharacterState.GrabLedge))

Menangani melompat dan menjatuhkan dari langkan

Setelah bot di langkan, itu harus mampu melompat normal, jadi mari kita tambahkan kondisi tambahan untuk melompat rutin:

if (mFramesOfJumping > 0 &&
    (mCurrentState == CharacterState.GrabLedge || !mOnGround || (mReachedNodeX && !destOnGround) || (mOnGround && destOnGround)))
{
    mInputs[(int)KeyInput.Jump] = true;
    if (!mOnGround)
        --mFramesOfJumping;
}

Hal berikutnya yang perlu bot dapat melakukan adalah anggun menurunkan langkan. Dengan implementasi saat ini sangat sederhana: jika kita sedang meraih birai dan kami tidak melompat, maka jelas kita perlu untuk turun dari itu!

1	if (mCurrentState == Character.CharacterState.GrabLedge && mFramesOfJumping <= 0)
2	{
3	mInputs[(int)KeyInput.GoDown] = true;
4	}

That's it! Sekarang karakter dapat sangat lancar meninggalkan langkan ambil posisi, tidak peduli apakah itu perlu melompat atau hanya drop-down.

Berhenti meraih tepian sepanjang waktu!

Saat ini, bot grabs setiap langkan dapat, terlepas dari Apakah masuk akal untuk melakukannya.

Satu solusi untuk ini adalah untuk menetapkan heuristic besar biaya untuk diperebutkan langkan, jadi algoritma prioritises melawan menggunakan mereka jika tidak harus — tapi ini akan memerlukan bot kami memiliki sedikit lebih banyak informasi tentang node. Karena semua kami melewati untuk bot adalah daftar poin, kita tidak tahu apakah algoritma berarti node tertentu menjadi langkan menyambar atau tidak; bot mengasumsikan bahwa jika birai dapat meraih, itu pasti harus!

Kita dapat menerapkan solusi cepat untuk perilaku ini: kami akan memanggil fungsi pathfinding dua kali. Pertama kali kita akan menyebutnya dengan parameter useLedges diatur ke false, dan kedua kalinya dengan itu diatur ke true.

Mari kita menetapkan jalur pertama sebagai jalan ditemukan tanpa menggunakan perampasan langkan apapun:

List<Vector2i> path1 = null;
var path = mMap.mPathFinder.FindPath(
                startTile,
                destination,
                Mathf.CeilToInt(mAABB.HalfSizeX / 8.0f),
                Mathf.CeilToInt(mAABB.HalfSizeY / 8.0f),
                (short)mMaxJumpHeight, false);

Sekarang, jika path ini tidak nol, kita perlu menyalin hasil ke daftar path1 kami, karena ketika kita memanggil pathfinder kedua kalinya, hasil di path akan mendapatkan ditimpa.

if (path != null)
{
    path1 = new List<Vector2i>();
    path1.AddRange(path);
}

Sekarang mari kita sebut pathfinder lagi, kali ini memungkinkan langkan meraih:

var path2 = mMap.mPathFinder.FindPath(
                startTile,
                destination,
                Mathf.CeilToInt(mAABB.HalfSizeX / 8.0f),
                Mathf.CeilToInt(mAABB.HalfSizeY / 8.0f),
                (short)mMaxJumpHeight, true);

Kita akan berasumsi bahwa jalan akhir kita akan menjadi jalan dengan perampasan langkan:

1	path = path2;
2	mGrabsLedges = true;

Dan tepat setelah ini, mari kita pastikan asumsi kita. Jika kami menemukan jalan tanpa langkan perampasan, dan bahwa path tidak lebih lama daripada jalan menggunakan mereka, maka kami akan membuat bot menonaktifkan perampasan langkan.

if (path1 != null && path1.Count <= path2.Count + 6)
{
    path = path1;
    mGrabsLedges = false;
}

Perhatikan bahwa kita mengukur "panjang" jalan dalam hitungan node, yang dapat menjadi cukup akurat karena node proses penyaringan. Akan lebih akurat untuk menghitung, misalnya, panjang jalan Manhattan (| x1-x 2 | + | y1 - y2 | setiap node), tapi karena seluruh metode ini adalah lebih dari sebuah hack daripada solusi nyata, itu OK untuk menggunakan tag heuristic semacam ini di sini.

Seluruh fungsi berikut seperti itu; jalan akan disalin ke buffer contoh bot dan dimulai setelah itu.

Ringkasan

Thats semua untuk tutorial! Seperti yang Anda lihat, hal ini tidak begitu sulit untuk memperluas algoritma untuk menambahkan kemungkinan gerakan tambahan, tetapi melakukan jadi pasti meningkatkan kerumitan dan menambahkan beberapa masalah yang mengganggu.

Sekali lagi, kurangnya akurasi dapat menggigit kita di sini lebih dari sekali, terutama ketika datang ke gerakan jatuh — ini adalah daerah yang perlu perbaikan yang paling, tapi saya sudah mencoba untuk membuat algoritma yang cocok fisika serta bisa dengan seperangkat nilai-nilai saat ini.

Semua dalam semua, bot dapat melintasi tingkat dengan cara yang akan saingan banyak pemain, dan saya sangat senang dengan hasil itu!