A * Pathfinding untuk Platformer Berbasis Grid 2D: Membuat Bot Mengikuti Jalan

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

Dalam tutorial ini, kami akan menggunakan algoritme peruntukkan platformer yang telah kami bangun untuk memberi tenaga bot yang dapat mengikuti jalur itu sendiri; cukup klik pada lokasi dan itu akan berjalan dan melompat ke sana. Ini sangat berguna untuk NPC!

Demo

Anda dapat memainkan demo Unity, atau versi WebGL (100MB +), 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.

Memperbarui Engine

Penanganan Status Bot

Bot memiliki dua definisi: yang pertama adalah tidak melakukan apa-apa, dan yang kedua adalah untuk menangani gerakan. Namun, dalam permainan Anda, Anda mungkin akan membutuhkan lebih banyak untuk mengubah perilaku bot sesuai dengan situasi.

public enum BotState
{
  None = 0,
	MoveTo,
}

Loop pembaruan bot akan melakukan hal yang berbeda tergantung pada status mana yang saat ini ditetapkan ke mCurrentBotState:

void BotUpdate()
{
    switch (mCurrentBotState)
    {
        case BotState.None:
            /* no need to do anything */
            break;
            
        case BotState.MoveTo:
            /* bot movement update logic */
            break;
    }
    
    CharacterUpdate();
}

Fungsi CharacterUpdate menangani semua input dan pembaruan fisika untuk bot.

Untuk mengubah status, kami akan menggunakan fungsi ChangeState yang hanya memberikan nilai baru ke mCurrentBotState:

1	public void ChangeState(BotState newState)
2	{
3	mCurrentBotState = newState;
4	}

Mengendalikan Bot

Kami akan mengontrol bot dengan mensimulasikan input, yang akan kami tetapkan ke array Booleans:

1	protected bool[] mInputs;

Array ini diindeks oleh KeyInput enum :

public enum KeyInput
{
    GoLeft = 0,
	GoRight,
	GoDown,
	Jump,
	Count
}

Misalnya, jika kita ingin mensimulasikan tekan tombol kiri, kita akan melakukannya seperti ini:

1	mInputs[(int)KeyInput.GoLeft] = true;

Logika karakter kemudian akan menangani input buatan ini dengan cara yang sama yang akan menangani masukan nyata.

Kita juga membutuhkan fungsi pembantu tambahan atau tabel pencarian untuk mendapatkan jumlah bingkai yang kita perlukan untuk menekan tombol lompat agar dapat melompat ke sejumlah blok yang diberikan:

int GetJumpFrameCount(int deltaY)
{
    if (deltaY <= 0)
        return 0;
    else
    {
        switch (deltaY)
        {
            case 1:
                return 1;
            case 2:
                return 2;
            case 3:
                return 5;
            case 4:
                return 8;
            case 5:
                return 14;
            case 6:
                return 21;
            default:
                return 30;
        }
    }
}

Perhatikan bahwa ini hanya akan bekerja secara konsisten jika permainan kami diperbarui dengan frekuensi tetap dan kecepatan lompatan awal karakter adalah sama. Idealnya, kami akan menghitung nilai-nilai ini secara terpisah untuk setiap karakter tergantung pada kecepatan lompatan karakter itu, tetapi hal di atas akan berfungsi dengan baik dalam kasus kami.

Mempersiapkan dan Memperoleh Jalan untuk Diikuti

Membatasi Lokasi Tujuan

Sebelum kita benar-benar menggunakan pathfinder, itu akan menjadi ide yang baik untuk memaksa tujuan tujuan berada di tanah. Ini karena pemain sangat mungkin untuk mengklik titik yang sedikit di atas tanah, dalam hal ini jalur bot akan berakhir dengan lompatan canggung ke udara. Dengan menurunkan titik akhir agar berada di permukaan tanah, kita dapat dengan mudah menghindari hal ini.

Pertama, mari kita lihat fungsi TappedOnTile. Fungsi ini dipanggil ketika pemain mengklik di mana saja dalam game; parameter mapPos adalah posisi ubin yang diklik pemain:

1	public void TappedOnTile(Vector2i mapPos)
2	{
3	}

Kita perlu menurunkan posisi ubin yang diklik hingga berada di tanah:

public void TappedOnTile(Vector2i mapPos)
{
    while (!(mMap.IsGround(mapPos.x, mapPos.y)))
        --mapPos.y;
}

Akhirnya, setelah kami tiba di ubin tanah, kami tahu di mana kami ingin memindahkan karakter ke:

public void TappedOnTile(Vector2i mapPos)
{
    while (!(mMap.IsGround(mapPos.x, mapPos.y)))
        --mapPos.y;

    MoveTo(new Vector2i(mapPos.x, mapPos.y + 1));
}

Menentukan Lokasi Awal

Sebelum kita benar-benar memanggil fungsi FindPath, kita perlu memastikan bahwa kita melewati sel awal yang benar.

Pertama, mari kita asumsikan bahwa ubin awal adalah sel kiri-bawah karakter:

1	public void MoveTo(Vector2i destination)
2	{
3	Vector2i startTile = mMap.GetMapTileAtPoint(mAABB.Center - mAABB.HalfSize + Vector2.one * Map.cTileSize * 0.5f);
4	}

Ubin ini mungkin bukan yang ingin kita berikan kepada algoritme sebagai simpul pertama, karena jika karakter kita berdiri di tepi platform, startTile dihitung dengan cara ini mungkin tidak memiliki ground, seperti dalam situasi berikut:

Dalam hal ini, kami ingin mengatur simpul awal ke ubin yang ada di sisi kiri karakter, bukan di tengahnya.

Mari kita mulai dengan membuat fungsi yang akan memberi tahu kita apakah karakter akan sesuai dengan posisi yang berbeda, dan jika itu benar, apakah itu di tanah di tempat itu:

1	bool IsOnGroundAndFitsPos(Vector2i pos)
2	{
3	}

Pertama, mari kita lihat apakah karakter sesuai dengan tempatnya. Jika tidak, kami dapat segera mengembalikan false:

bool IsOnGroundAndFitsPos(Vector2i pos)
{
    for (int y = pos.y; y < pos.y + mHeight; ++y)
    {
        for (int x = pos.x; x < pos.x + mWidth; ++x)
        {
            if (mMap.IsObstacle(x, y))
                return false;
        }
    }
}

Sekarang kita bisa melihat apakah ada ubin di bawah karakter adalah ubin tanah:

bool IsOnGroundAndFitsPos(Vector2i pos)
{
    for (int y = pos.y; y < pos.y + mHeight; ++y)
    {
        for (int x = pos.x; x < pos.x + mWidth; ++x)
        {
            if (mMap.IsObstacle(x, y))
                return false;
        }
    }

    for (int x = pos.x; x < pos.x + mWidth; ++x)
    {
        if (mMap.IsGround(x, pos.y - 1))
            return true;
    }

    return false;
}

Mari kembali ke fungsi MoveTo, dan lihat apakah kita harus mengubah ubin awal. Kita perlu melakukannya jika karakter berada di tanah tetapi ubin awal tidak:

Vector2i startTile = mMap.GetMapTileAtPoint(mAABB.Center - mAABB.HalfSize + Vector2.one * Map.cTileSize * 0.5f);
        
if (mOnGround && !IsOnGroundAndFitsPos(startTile))
{
}

Kita tahu bahwa, dalam hal ini, karakter berdiri di tepi kiri atau tepi kanan platform.

Pertama mari kita periksa tepi kanan; jika karakter cocok di sana dan ubin berada di tanah, maka kita perlu memindahkan ubin mulai satu ruang ke kanan. Jika tidak, maka kita perlu memindahkannya ke kiri.

if (mOnGround && !IsOnGroundAndFitsPos(startTile))
{
    if (IsOnGroundAndFitsPos(new Vector2i(startTile.x + 1, startTile.y)))
        startTile.x += 1;
    else
        startTile.x -= 1;
}

Sekarang kita harus memiliki semua data yang kita perlukan untuk memanggil pathfinder:

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

Argumen pertama adalah ubin awal.

Yang kedua adalah tujuan; kita bisa melewati ini apa adanya.

Argumen ketiga dan keempat adalah lebar dan tinggi yang perlu didekati oleh ukuran petak. Perhatikan bahwa di sini kita ingin menggunakan langit-langit tinggi dalam ubin —jadi, misalnya, jika tinggi sebenarnya dari karakter adalah 2,3 ubin, kami ingin algoritmanya berpikir bahwa karakternya adalah 3 ubin tinggi. (Lebih baik jika tinggi sebenarnya dari karakter sebenarnya sedikit lebih kecil dari ukurannya di ubin, untuk memungkinkan sedikit lebih banyak ruang untuk kesalahan dari jalur mengikuti AI.)

Akhirnya, argumen kelima adalah tinggi lompatan maksimum karakter.

Mencadangkan Daftar Node

Setelah menjalankan algoritma, kita harus memeriksa apakah hasilnya baik-baik saja - artinya, jika ada jalan yang ditemukan:

1	if (path != null && path.Count > 1)
2	{
3	}

Jika demikian, kita perlu menyalin node ke buffer terpisah, karena jika beberapa objek lain memanggil fungsi FindPath pathfinder sekarang, hasil lama akan ditimpa. Menyalin hasilnya ke daftar terpisah akan mencegah hal ini.

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

Seperti yang Anda lihat, kami menyalin hasilnya dalam urutan terbalik; ini karena hasilnya sendiri terbalik. Melakukan hal ini berarti simpul dalam daftar mPath akan berada di urutan pertama hingga terakhir.

Sekarang mari kita atur node tujuan saat ini. Karena simpul pertama dalam daftar adalah titik awal, kita dapat benar-benar melewatkannya dan melanjutkan dari simpul kedua dan seterusnya:

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

Setelah menetapkan node tujuan saat ini, kami mengatur status bot ke MoveTo, jadi status yang sesuai akan diaktifkan.

Mendapatkan Konteks

Sebelum kita mulai menulis aturan untuk gerakan AI, kita harus dapat menemukan situasi apa karakter tersebut pada suatu titik tertentu.

Kita perlu untuk tahu:

posisi destinasi sebelumnya, saat ini dan berikutnya
apakah tujuan saat ini ada di tanah atau di udara
apakah karakter telah mencapai tujuan saat ini pada sumbu x
apakah karakter telah mencapai tujuan saat ini pada sumbu y

Catatan: tujuan di sini belum tentu tujuan akhir; mereka adalah simpul dalam daftar dari bagian sebelumnya.

Informasi ini akan memungkinkan kita secara akurat menentukan apa yang harus dilakukan bot dalam situasi apa pun.

Mari kita mulai dengan mendeklarasikan fungsi untuk mendapatkan konteks ini:

1	public void GetContext(out Vector2 prevDest, out Vector2 currentDest, out Vector2 nextDest, out bool destOnGround, out bool reachedX, out bool reachedY)
2	{
3	}

Menghitung Posisi Dunia Node Tujuan

Hal pertama yang harus kita lakukan dalam fungsi ini adalah menghitung posisi dunia dari simpul tujuan.

Mari kita mulai dengan menghitung ini untuk tujuan sebelumnya. Operasi ini tergantung pada bagaimana dunia game Anda diatur; dalam kasus saya, koordinat peta tidak sesuai dengan koordinat dunia, jadi kami perlu menerjemahkannya.

Menerjemahkannya sangat sederhana: kita hanya perlu mengalikan posisi simpul dengan ukuran ubin, lalu mengimbangi vektor yang dihitung berdasarkan posisi peta:

1	prevDest = new Vector2(mPath[mCurrentNodeId - 1].x * Map.cTileSize + mMap.transform.position.x,
2	mPath[mCurrentNodeId - 1].y * Map.cTileSize + mMap.transform.position.y);

Perhatikan bahwa kita mulai dengan mCurrentNodeId sama dengan 1, jadi kita tidak perlu khawatir tentang tidak sengaja mencoba mengakses node dengan indeks -1.

Kami akan menghitung posisi tujuan saat ini dengan cara yang sama:

1	currentDest = new Vector2(mPath[mCurrentNodeId].x * Map.cTileSize + mMap.transform.position.x,
2	mPath[mCurrentNodeId].y * Map.cTileSize + mMap.transform.position.y);

Dan sekarang untuk posisi tujuan selanjutnya. Di sini kita perlu memeriksa apakah ada simpul yang tersisa untuk diikuti setelah kita mencapai tujuan kita saat ini, jadi pertama mari kita berasumsi bahwa tujuan berikutnya sama dengan yang sekarang:

1	nextDest = currentDest;

Sekarang, jika ada simpul yang tersisa, kami akan menghitung tujuan berikutnya dengan cara yang sama seperti yang kami lakukan sebelumnya:

if (mPath.Count > mCurrentNodeId + 1)
{
    nextDest = new Vector2(mPath[mCurrentNodeId + 1].x * Map.cTileSize + mMap.transform.position.x,
                                  mPath[mCurrentNodeId + 1].y * Map.cTileSize + mMap.transform.position.y);
}

Memeriksa apakah the Node adalah di tanah

Langkah selanjutnya adalah menentukan apakah tujuan saat ini ada di lapangan.

Ingat bahwa tidak cukup hanya memeriksa ubin tepat di bawah tujuan; kita perlu mempertimbangkan kasus-kasus di mana karakter lebih dari satu blok lebar:

Mari kita mulai dengan mengasumsikan bahwa posisi tujuan tidak ada di tanah:

1	destOnGround = false;

Sekarang kita akan melihat ubin di bawah tujuan untuk melihat apakah ada balok padat di sana. Jika ada, kita dapat mengatur destOnGround ke true:

for (int x = mPath[mCurrentNodeId].x; x < mPath[mCurrentNodeId].x + mWidth; ++x)
{
    if (mMap.IsGround(x, mPath[mCurrentNodeId].y - 1))
    {
        destOnGround = true;
        break;
    }
}

Memeriksa Apakah Node Telah Mencapai X-Axis

Sebelum kita dapat melihat apakah karakter telah mencapai tujuan, kita perlu mengetahui posisinya di jalan. Posisi ini pada dasarnya adalah pusat sel kiri bawah karakter kita. Karena karakter kita sebenarnya tidak dibangun dari sel, kita hanya akan menggunakan posisi kiri bawah kotak pembatas karakter ditambah setengah sel:

1	Vector2 pathPosition = mAABB.Center - mAABB.HalfSize + Vector2.one * Map.cTileSize * 0.5f;

Ini adalah posisi yang kita butuhkan untuk mencocokkan dengan node tujuan.

Bagaimana kita bisa menentukan apakah karakter telah mencapai tujuan pada sumbu x? Akan aman untuk mengasumsikan bahwa, jika karakter bergerak ke kanan dan memiliki posisi x lebih besar dari atau sama dengan tujuan, maka tujuan telah tercapai.

Untuk melihat apakah karakternya bergerak dengan benar, kami akan menggunakan tujuan sebelumnya, yang dalam kasus ini pasti berada di sebelah kiri yang sekarang:

1	reachedX = (prevDest.x <= currentDest.x && pathPosition.x >= currentDest.x);

Hal yang sama berlaku untuk sisi yang berlawanan; jika tujuan sebelumnya adalah di sebelah kanan saat ini dan posisi x karakter kurang dari atau sama dengan posisi tujuan, maka kita dapat yakin bahwa karakter telah mencapai tujuan pada sumbu x:

1	reachedX = (prevDest.x <= currentDest.x && pathPosition.x >= currentDest.x)
2	\|\| (prevDest.x >= currentDest.x && pathPosition.x <= currentDest.x);

Snap posisi karakter

Kadang-kadang, karena kecepatan karakter, ia melampaui tujuan, yang dapat menyebabkannya tidak mendarat di node target. Lihat contoh berikut:

Untuk memperbaikinya, kami akan menjepret posisi karakter sehingga mendarat di node tujuan.

Kondisi untuk kita untuk mengambil karakter adalah:

Tujuan tercapai pada sumbu-x.
Jarak antara posisi bot dan tujuan saat ini lebih besar dari cBotMaxPositionError.
Jarak antara posisi bot dan tujuan saat ini tidak terlalu jauh, jadi kami tidak mengambil karakter dari jauh.
Karakter tidak bergerak ke kiri atau kanan belokan terakhir, jadi kami mengambil karakter hanya jika jatuh lurus ke bawah.

if (reachedX && Mathf.Abs(pathPosition.x - currentDest.x) > Constants.cBotMaxPositionError && Mathf.Abs(pathPosition.x - currentDest.x) < Constants.cBotMaxPositionError*3.0f && !mPrevInputs[(int)KeyInput.GoRight] && !mPrevInputs[(int)KeyInput.GoLeft])
{
    pathPosition.x = currentDest.x;
    mPosition.x = pathPosition.x - Map.cTileSize * 0.5f + mAABB.HalfSizeX + mAABBOffset.x;
}

cBotMaxPositionError dalam tutorial ini sama dengan 1 piksel; ini adalah seberapa jauh kita membiarkan karakter itu dari tujuan sementara tetap membiarkannya pergi ke tujuan berikutnya.

Memeriksa Apakah Node Telah Mencapai Y-Axis

Mari kita cari tahu kapan kita dapat yakin bahwa karakter telah mencapai posisi Y targetnya. Pertama-tama, jika tujuan sebelumnya berada di bawah yang sekarang, dan karakter kita melompat ke puncak dari tujuan saat ini, maka kita dapat berasumsi bahwa tujuan telah tercapai.

1	reachedY = (prevDest.y <= currentDest.y && pathPosition.y >= currentDest.y);

Demikian pula, jika tujuan saat ini di bawah yang sebelumnya dan karakter telah mencapai y-posisi node saat ini, kita dapat mengatur reachedY menjadi true juga.

1	reachedY = (prevDest.y <= currentDest.y && pathPosition.y >= currentDest.)
2	\|\| (prevDest.y >= currentDest.y && pathPosition.y <= currentDest.y);

Terlepas dari apakah karakter perlu melompat atau jatuh untuk mencapai posisi y-tujuan node, jika itu benar-benar dekat, maka kita harus mengatur reachedY ke true juga:

reachedY = (prevDest.y <= currentDest.y && pathPosition.y >= currentDest.y)

    || (prevDest.y >= currentDest.y && pathPosition.y <= currentDest.y)

    || (Mathf.Abs(pathPosition.y - currentDest.y) <= Constants.cBotMaxPositionError);

Jika tujuan ada di tanah tetapi karakter tidak, maka kita dapat mengasumsikan bahwa posisi Y tujuan saat ini belum tercapai:

1	if (destOnGround && !mOnGround)
2	reachedY = false;

Itu saja — itulah semua data dasar yang perlu kita ketahui untuk mempertimbangkan jenis gerakan apa yang perlu dilakukan AI.

Penanganan yang Gerakan Bot

Hal pertama yang harus dilakukan dalam fungsi update kami adalah mendapatkan konteks yang baru saja kami terapkan:

1	Vector2 prevDest, currentDest, nextDest;
2	bool destOnGround, reachedY, reachedX;
3	GetContext(out prevDest, out currentDest, out nextDest, out destOnGround, out reachedX, out reachedY);

Sekarang mari kita dapatkan posisi karakter di sepanjang jalan. Kami menghitung ini dengan cara yang sama seperti yang kami lakukan dalam fungsi GetContext:

1	Vector2 pathPosition = mAABB.Center - mAABB.HalfSize + Vector2.one * Map.cTileSize * 0.5f;

Pada awal frame kita perlu mereset input palsu, dan menugaskan mereka hanya jika kondisi untuk melakukannya muncul. Kami hanya akan menggunakan empat input: dua untuk gerakan kiri dan kanan, satu untuk melompat, dan satu untuk menjatuhkan platform satu arah.

1	mInputs[(int)KeyInput.GoRight] = false;
2	mInputs[(int)KeyInput.GoLeft] = false;
3	mInputs[(int)KeyInput.Jump] = false;
4	mInputs[(int)KeyInput.GoDown] = false;

Kondisi pertama untuk gerakan adalah ini: jika tujuan saat ini lebih rendah dari posisi karakter dan karakter berdiri di platform satu arah, lalu tekan tombol ke bawah, yang akan menghasilkan karakter melompat dari platform ke bawah :

1	if (pathPosition.y - currentDest.y > Constants.cBotMaxPositionError && mOnOneWayPlatform)
2	mInputs[(int)KeyInput.GoDown] = true;

Penanganan Lompatan

Mari kita paparkan bagaimana lompatan kita seharusnya bekerja. Pertama, kami tidak ingin menekan tombol lompat jika mFramesOfJumping adalah 0.

1	if (mFramesOfJumping > 0)
2	{
3	}

Kondisi kedua yang harus diperiksa adalah karakternya tidak ada di tanah.

Dalam implementasi fisika platformer ini, karakter dibiarkan melompat jika hanya melangkah dari tepi platform dan tidak lagi di tanah. Ini adalah metode populer untuk mengurangi ilusi bahwa pemain telah menekan tombol melompat tetapi karakter tidak melompat, yang mungkin muncul karena masukan lag atau pemain menekan tombol melompat tepat setelah karakter telah pindah dari platform.

1	if (mFramesOfJumping > 0 && !mOnGround)
2	{
3	}

Kondisi ini akan berfungsi jika karakter perlu melompat dari langkan, karena bingkai lompatan akan diatur ke jumlah yang tepat, karakter secara alami akan berjalan dari langkan, dan pada titik itu juga akan memulai lompatan.

Ini tidak akan berhasil jika lompatan harus dilakukan dari tanah; untuk menangani ini kita perlu memeriksa kondisi ini:

Karakter telah mencapai node tujuan posisi x, mana itu akan mulai melompat.
Node tujuan tidak berada di tanah; Jika kita melompat, kita perlu pergi melalui simpul yang di udara pertama.

1	if (mFramesOfJumping > 0 &&
2	(!mOnGround \|\| (reachedX && !destOnGround)))
3	{
4	}

Karakter juga harus melompat jika berada di tanah dan tujuan ada di tanah juga. Ini biasanya akan terjadi jika karakter perlu melompat satu ubin ke atas dan ke samping untuk mencapai platform yang hanya satu blok lebih tinggi.

1	if (mFramesOfJumping > 0 &&
2	(!mOnGround \|\| (reachedX && !destOnGround) \|\| (mOnGround && destOnGround)))
3	{
4	}

Sekarang mari kita mengaktifkan lompatan dan pengurangan bingkai lompatan, sehingga karakter memegang lompatan untuk jumlah bingkai yang benar:

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

Perhatikan bahwa kami mengurangi mFramesOfJumping hanya jika karakter tidak ada di tanah. Ini untuk menghindari secara tidak sengaja mengurangi panjang lompatan sebelum memulai lompatan.

Melanjutkan ke Node tujuan berikutnya

Mari kita pikirkan apa yang perlu terjadi ketika kita mencapai simpul — yaitu, ketika reachedX dan reachedY bernilai true.

1	if (reachedX && reachedY)
2	{
3	}

Pertama, kami akan menaikkan ID node saat ini:

1	mCurrentNodeId++;

Sekarang kita perlu memeriksa apakah ID ini lebih besar dari jumlah node di jalur kita. Jika ya, itu berarti karakter telah mencapai tujuan:

if (mCurrentNodeId >= mPath.Count)
{
    mCurrentNodeId = -1;
    ChangeState(BotState.None);
    break;
}

Hal berikutnya yang harus kita lakukan adalah menghitung lompatan untuk simpul berikutnya. Karena kita perlu menggunakan ini di lebih dari satu tempat, mari kita buat fungsi untuk itu:

1	public int GetJumpFramesForNode(int prevNodeId)
2	{
3	}

Kami hanya ingin melompat jika node baru lebih tinggi dari yang sebelumnya dan karakter ada di tanah:

public int GetJumpFramesForNode(int prevNodeId)
{
    if (mPath[currentNodeId].y - mPath[prevNodeId].y > 0 && mOnGround)
    {
    }
}

Untuk mengetahui berapa banyak ubin yang harus kita lompati, kita akan mengulanginya melalui simpul selama lebih tinggi dan lebih tinggi. Ketika kita sampai ke node yang berada pada ketinggian lebih rendah, atau node yang memiliki tanah di bawahnya, kita dapat berhenti, karena kita tahu bahwa tidak akan ada yang lebih tinggi dari itu.

Pertama, mari kita menyatakan dan menetapkan variabel yang akan menampung nilai melompat:

public int GetJumpFramesForNode(int prevNodeId)
{
    if (mPath[currentNodeId].y - mPath[prevNodeId].y > 0 && mOnGround)
    {
        int jumpHeight = 1;
    }
}

Sekarang mari iterate melalui node, dimulai pada node saat ini:

public int GetJumpFramesForNode(int prevNodeId)
{
    if (mPath[currentNodeId].y - mPath[prevNodeId].y > 0 && mOnGround)
    {
        int jumpHeight = 1;
        
        for (int i = currentNodeId; i < mPath.Count; ++i)
        {
        }
    }
}

Jika node berikutnya lebih tinggi dari jumpHeight, dan itu tidak di tanah, maka mari kita atur ketinggian lompatan baru:

public int GetJumpFramesForNode(int prevNodeId)
{
    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 && !mMap.IsGround(mPath[i].x, mPath[i].y - 1))
                    jumpHeight = mPath[i].y - mPath[prevNodeId].y;
        }
    }
}

Jika ketinggian node baru lebih rendah dari sebelumnya, atau di tanah, maka kita mengembalikan jumlah frame lompatan yang diperlukan untuk ketinggian yang ditemukan. (Dan jika tidak perlu melompat, mari kita kembali 0.)

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

Kita perlu memanggil fungsi ini di dua tempat.

Yang pertama adalah dalam kasus di mana karakter telah mencapai simpul x dan posisi-y:

if (reachedX && reachedY)
{
    int prevNodeId = mCurrentNodeId;
    mCurrentNodeId++;

    if (mCurrentNodeId >= mPath.Count)
    {
        mCurrentNodeId = -1;
        ChangeState(BotState.None);
        break;
    }

    if (mOnGround)
        mFramesOfJumping = GetJumpFramesForNode(prevNodeId);
}

Perhatikan bahwa kita mengatur frame lompatan untuk seluruh lompatan, jadi ketika kita mencapai simpul di udara kita tidak ingin mengubah jumlah lompatan frame yang ditentukan sebelum lompatan terjadi.

Setelah kami memperbarui tujuan, kami perlu memproses semuanya lagi, sehingga bingkai pergerakan selanjutnya dihitung segera. Untuk ini, kita akan menggunakan perintah goto:

1	goto case BotState.MoveTo;

Tempat kedua yang kita perlukan untuk menghitung lompatan adalah fungsi MoveTo, karena mungkin saja simpul pertama dari lintasan adalah simpul lompatan:

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

    mCurrentNodeId = 1;

    ChangeState(BotState.MoveTo);

    mFramesOfJumping = GetJumpFramesForNode(0);
}

Penanganan Gerakan untuk Mencapai Posisi-Node

Sekarang mari kita menangani gerakan untuk kasus di mana karakter belum mencapai posisi x-node target.

Tidak ada yang rumit di sini; jika tujuannya ke kanan, kita perlu mensimulasikan penekanan tombol kanan. Jika tujuannya ke kiri, maka kita perlu mensimulasikan tombol kiri tekan. Kita hanya perlu memindahkan karakter jika perbedaan posisi lebih dari konstanta cBotMaxPositionError:

else if (!reachedX)
{
    if (currentDest.x - pathPosition.x > Constants.cBotMaxPositionError)
        mInputs[(int)KeyInput.GoRight] = true;
    else if (pathPosition.x - currentDest.x > Constants.cBotMaxPositionError)
        mInputs[(int)KeyInput.GoLeft] = true;
}

Penanganan Gerakan untuk Mencapai Posisi-Node

Jika karakter telah mencapai target x-posisi tetapi kita tetap melompat ke yang lebih tinggi, kita masih dapat memindahkan karakter ke kiri atau ke kanan tergantung di mana tujuan berikutnya adalah. Ini hanya akan berarti bahwa karakter tidak menempel begitu kaku ke jalan yang ditemukan. Berkat itu, akan jauh lebih mudah untuk mencapai tujuan berikutnya, karena alih-alih hanya menunggu untuk mencapai target y-position, karakter akan secara alami bergerak menuju posisi x node berikutnya ketika melakukan hal itu.

Kami hanya akan memindahkan karakter ke tujuan berikutnya jika ada sama sekali dan tidak ada di tanah. (Jika ada di tanah, maka kita tidak bisa melewatkannya karena ini adalah pos pemeriksaan yang penting — itu mengatur ulang kecepatan vertikal karakter dan memungkinkannya untuk menggunakan lompatan lagi.)

1	else if (!reachedY && mPath.Count > mCurrentNodeId + 1 && !destOnGround)
2	{
3
4	}

Tetapi sebelum kita benar-benar bergerak menuju tujuan berikutnya, kita perlu memeriksa bahwa kita tidak akan merusak jalur dengan melakukannya.

Menghindari Pemutusan Jatuh Prematur

Pertimbangkan skenario berikut:

Di sini, segera setelah karakter berjalan dari langkan di mana ia mulai, ia mencapai posisi x dari simpul kedua, dan jatuh untuk mencapai posisi-y. Karena simpul ketiga berada di sebelah kanan karakter, itu bergerak ke kanan — dan berakhir di terowongan di atas yang kita inginkan.

Untuk memperbaikinya, kita perlu memeriksa apakah ada rintangan antara karakter dan tujuan berikutnya; jika tidak ada, maka kita bebas untuk memindahkan karakter ke arahnya; jika ada, maka kita harus menunggu.

Pertama, mari kita lihat ubin mana yang harus kita periksa. Jika sasaran berikutnya adalah di sebelah kanan yang sekarang, maka kita harus memeriksa ubin di sebelah kanan; jika ke kiri maka kita harus memeriksa ubin ke kiri. Jika mereka berada pada posisi x yang sama, tidak ada alasan untuk melakukan gerakan pre-emptive.

int checkedX = 0;

int tileX, tileY;
mMap.GetMapTileAtPoint(pathPosition, out tileX, out tileY);

if (mPath[mCurrentNodeId + 1].x != mPath[mCurrentNodeId].x)
{
    if (mPath[mCurrentNodeId + 1].x > mPath[mCurrentNodeId].x)
        checkedX = tileX + mWidth;
    else
        checkedX = tileX - 1;
}

Seperti yang Anda lihat, koordinat-x dari node ke kanan tergantung pada lebar karakter.

Sekarang kita dapat memeriksa apakah ada ubin antara karakter dan posisi simpul berikutnya pada sumbu y:

1	if (checkedX != 0 && !mMap.AnySolidBlockInStripe(checkedX, tileY, mPath[mCurrentNodeId + 1].y))
2	{
3	}

Fungsi AnySolidBlockInStripe memeriksa apakah ada ubin padat antara dua titik yang diberikan pada peta. Titik-titik harus memiliki x-koordinat yang sama. Koordinat x yang kami periksa adalah ubin yang kami inginkan agar karakter itu dipindahkan, tetapi kami tidak yakin apakah kami bisa, seperti yang dijelaskan di atas.

Inilah implementasi dari fungsi tersebut.

public bool AnySolidBlockInStripe(int x, int y0, int y1)
{
    int startY, endY;

    if (y0 <= y1)
    {
        startY = y0;
        endY = y1;
    }
    else
    {
        startY = y1;
        endY = y0;
    }

    for (int y = startY; y <= endY; ++y)
    {
        if (GetTile(x, y) == TileType.Block)
            return true;
    }

    return false;
}

Seperti yang Anda lihat, fungsinya sangat sederhana; hanya iterates melalui ubin di kolom, mulai dari yang lebih rendah.

Sekarang kita tahu kita bisa bergerak menuju tujuan berikutnya, mari kita lakukan:

if (checkedX != 0 && !mMap.AnySolidBlockInStripe(checkedX, tileY, mPath[mCurrentNodeId + 1].y))
{
    if (nextDest.x - pathPosition.x > Constants.cBotMaxPositionError)
        mInputs[(int)KeyInput.GoRight] = true;
    else if (pathPosition.x - nextDest.x > Constants.cBotMaxPositionError)
        mInputs[(int)KeyInput.GoLeft] = true;
}

Memungkinkan Bot untuk melewati node

Itu hampir - tetapi masih ada satu kasus yang harus dipecahkan. Inilah contohnya:

Seperti yang Anda lihat, sebelum karakter mencapai posisi y simpul kedua, itu menabrak kepalanya di ubin mengambang, karena kami membuatnya bergerak menuju tujuan berikutnya ke kanan. Akibatnya, karakter berakhir tidak pernah mencapai posisi y simpul kedua; alih-alih bergerak lurus ke simpul ketiga. Karena reachedY adalah false dalam hal ini, ia tidak dapat melanjutkan dengan path.

Untuk menghindari kasus seperti itu, kami hanya akan memeriksa apakah karakter mencapai tujuan berikutnya sebelum mencapai yang saat ini.

Langkah pertama menuju ini akan memisahkan perhitungan sebelumnya dari reachedX dan reachedY menjadi fungsi mereka sendiri:

public bool ReachedNodeOnXAxis(Vector2 pathPosition, Vector2 prevDest, Vector2 currentDest)
{
    return (prevDest.x <= currentDest.x && pathPosition.x >= currentDest.x)
        || (prevDest.x >= currentDest.x && pathPosition.x <= currentDest.x)
        || Mathf.Abs(pathPosition.x - currentDest.x) <= Constants.cBotMaxPositionError;
}

public bool ReachedNodeOnYAxis(Vector2 pathPosition, Vector2 prevDest, Vector2 currentDest)
{
    return (prevDest.y <= currentDest.y && pathPosition.y >= currentDest.y)
        || (prevDest.y >= currentDest.y && pathPosition.y <= currentDest.y)
        || (Mathf.Abs(pathPosition.y - currentDest.y) <= Constants.cBotMaxPositionError);
}

Selanjutnya, ganti perhitungan dengan pemanggilan fungsi dalam fungsi GetContext:

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

Sekarang kita dapat memeriksa apakah tujuan berikutnya telah tercapai. Jika sudah, kita bisa hanya menambah mCurrentNode dan segera kembali melakukan pembaruan status. Ini akan membuat tujuan berikutnya menjadi yang sekarang, dan karena karakter sudah mencapai itu, kita akan dapat melanjutkan:

if (checkedX != 0 && !mMap.AnySolidBlockInStripe(checkedX, tileY, mPath[mCurrentNodeId + 1].y))
{
    if (nextDest.x - pathPosition.x > Constants.cBotMaxPositionError)
        mInputs[(int)KeyInput.GoRight] = true;
    else if (pathPosition.x - nextDest.x > Constants.cBotMaxPositionError)
        mInputs[(int)KeyInput.GoLeft] = true;

    if (ReachedNodeOnXAxis(pathPosition, currentDest, nextDest) && ReachedNodeOnYAxis(pathPosition, currentDest, nextDest))
    {
        mCurrentNodeId += 1;
        goto case BotState.MoveTo;
    }
}

Itu semua untuk pergerakan karakter!

Menangani Kondisi Restart

Ada baiknya untuk memiliki rencana cadangan untuk situasi di mana bot tidak bergerak melalui jalur seperti seharusnya. Ini dapat terjadi jika, misalnya, peta diubah — menambahkan penghalang ke jalur yang sudah dihitung dapat menyebabkan jalur menjadi tidak valid. Apa yang akan kita lakukan adalah me-reset path jika karakter terjebak lebih lama dari sejumlah frame tertentu.

Jadi, mari kita mendeklarasikan variabel yang akan menghitung berapa banyak frame karakter yang telah terjebak dan berapa banyak frame yang mungkin paling banyak terhenti:

1	public int mStuckFrames = 0;
2	public const int cMaxStuckFrames = 20;

Kita perlu mengatur ulang ini ketika kita memanggil fungsi MoveTo:

public void MoveTo(Vector2i destination)
{
    mStuckFrames = 0;
    /*
    ...
    */
}

Dan akhirnya, di akhir BotState.MoveTo, mari kita periksa apakah karakternya macet. Di sini, kita hanya perlu memeriksa apakah posisinya saat ini sama dengan yang lama; jika demikian, maka kita juga perlu menaikkan mStuckFrames dan memeriksa apakah karakter telah terjebak untuk lebih banyak frame daripada cMaxStuckFrames — dan jika itu memang benar, maka kita perlu memanggil fungsi MoveTo dengan simpul terakhir dari jalur saat ini sebagai parameter. Tentu saja, jika posisinya berbeda, maka kita perlu mengatur ulang mStuckFrames ke 0:

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

if (mPosition == mOldPosition)
{
    ++mStuckFrames;
    if (mStuckFrames > cMaxStuckFrames)
        MoveTo(mPath[mPath.Count - 1]);
}
else
    mStuckFrames = 0;

Sekarang karakter harus mencari jalan alternatif jika tidak bisa menyelesaikan yang awal.

Kesimpulan

Itu seluruh tutorialnya! Sudah banyak pekerjaan, tapi saya harap Anda akan menemukan metode ini berguna. Ini tidak berarti solusi sempurna untuk pathfinding platformer; pendekatan kurva lompatan untuk karakter yang perlu dibuat oleh algoritme sering cukup sulit dilakukan dan dapat menyebabkan perilaku yang salah. Algoritme ini masih bisa diperpanjang — tidak terlalu sulit untuk menambahkan langkan dan jenis lain fleksibilitas gerak yang diperluas — tetapi kami telah membahas mekanika platformer dasar. Juga dimungkinkan untuk mengoptimalkan kode untuk membuatnya lebih cepat serta menggunakan lebih sedikit memori; iterasi algoritma ini tidak sempurna sama sekali ketika menyangkut aspek-aspek tersebut. Ia juga menderita dari perkiraan kurva yang sangat buruk ketika jatuh pada kecepatan besar.

Algoritme ini dapat digunakan dalam banyak cara, terutama untuk meningkatkan musuh AI atau teman AI. Ini juga dapat digunakan sebagai skema kontrol untuk perangkat sentuh — ini akan bekerja pada dasarnya dengan cara yang sama seperti pada demo tutorial, dengan pemutar mengetuk ke mana pun mereka ingin karakter tersebut bergerak. Hal ini menghilangkan tantangan eksekusi yang digunakan oleh banyak platformer, sehingga permainan harus dirancang secara berbeda, untuk lebih memosisikan karakter Anda di tempat yang tepat daripada belajar mengontrol karakter secara akurat.

Terima kasih sudah membaca! Pastikan untuk memberikan umpan balik tentang metode ini dan beri tahu saya jika Anda sudah melakukan perbaikan!