Unlimited WordPress themes, graphics, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Game Development
  2. Artificial Intelligence
Gamedevelopment

Mesin Finite-State: Teori dan Implementasi

by
Difficulty:IntermediateLength:LongLanguages:

Indonesian (Bahasa Indonesia) translation by Yanti Baddolo (you can also view the original English article)

Mesin finite-state adalah model yang digunakan untuk merepresentasikan dan mengendalikan aliran eksekusi. Ini sangat cocok untuk menerapkan AI (kecerdasan buatan) dalam game, menghasilkan hasil yang bagus tanpa kode yang rumit. Tutorial ini menjelaskan teori, implementasi dan penggunaan mesin finite-state secara sederhana dan berbasis stack.

Semua ikon dibuat oleh Lorc, dan tersedia di http://game-icons.net.

Catatan: Meskipun tutorial ini ditulis menggunakan AS3 dan Flash, Anda harus bisa menggunakan teknik dan konsep yang sama di hampir semua lingkungan pengembangan game.


Apa itu Mesin Finite-State?

Mesin finite-state, atau disingkat FSM, adalah model perhitungan berdasarkan mesin hipotetis yang dibuat dari satu atau lebih kedudukan. Hanya satu kedudukan yang bisa aktif pada saat bersamaan, sehingga mesin harus berpindah dari kedudukan ke kedudukan lain agar bisa melakukan tindakan yang berbeda.

FSM biasanya digunakan untuk mengatur dan merepresentasikan aliran eksekusi, yang berguna untuk menerapkan AI dalam permainan. "Otak" musuh, misalnya, dapat diimplementasikan dengan menggunakan FSM: setiap kedudukan mewakili sebuah tindakan, seperti serangan atau penghindaran:

FSM mewakili otak musuh.

FSM dapat diwakili oleh grafik, di mana simpulnya adalah suatu kedudukan dan ujungnya adalah transisi. Setiap tepi memiliki label yang menginformasikan kapan transisi harus terjadi, seperti ketika pemain berada di dekat (player is near  ) label pada gambar di atas, yang mengindikasikan bahwa mesin akan beralih dari pengembaraan (wander) menjadi menyerang (attack) jika pemainnya berada di dekatnya.


Merencanakan Kedudukan dan Transisi Mereka

Implementasi FSM dimulai dengan kedudukannya dan transisi yang akan dimilikinya. Bayangkan FSM berikut, mewakili otak seekor semut yang membawa pulang daun:

FSM mewakili otak seekor semut.

Titik awalnya adalah kedudukan mencari daun (find leaf), yang akan tetap aktif sampai semut menemukan daunnya. Bila itu terjadi, keadaan saat ini dialihkan untuk pulang ke rumah (go home), yang tetap aktif sampai semut pulang. Saat semut akhirnya tiba di rumah, keadaan aktif menjadi mencari daun lagi (find leaf), jadi semut mengulangi perjalanannya.

Jika keadaan aktif mencari daun (find leaf) dan kursor mouse mendekati semut, maka ada transisi menuju keadaan lari (run away). Sementara keadaan itu aktif, semut akan lari dari kursor mouse. Bila kursor bukan ancaman lagi, ada transisi kembali ke kedudukan mencari daun (find leaf).

Karena ada transisi yang menghubungkan mencari daun (find leaf) dan lari (run away), semut akan selalu lari dari kursor mouse saat mendekati selama semut sedang mencari daunnya. Itu tidak akan terjadi jika kedudukan aktif dalah pulang ke rumah (go home) (lihat gambar di bawah). Dalam hal ini semut akan berjalan pulang tanpa rasa takut, hanya bertransisi ke keadaan daun yang ditemukan (find leaf) saat tiba di rumah.

FSM mewakili otak seekor semut. Perhatikan terbatasnya transisi antara melarikan diri (run away) dan pulang ke rumah (go home).

Menerapkan FSM

FSM dapat diimplementasikan dan dienkapsulasi dalam satu kelas, diberi nama FSM misalnya. Idenya adalah menerapkan setiap keadaan sebagai fungsi atau metode, menggunakan properti yang disebut activeState di kelas untuk menentukan kedudukan mana yang aktif:

Karena setiap kedudukan adalah sebuah fungsi, sementara kedudkan tertentu aktif, fungsi yang mewakili kedudukan tersebut akan dimunculkan pada setiap pembaruan game. Properti ActiveState adalah petunjuk ke sebuah fungsi, jadi akan menunjuk ke fungsi state yang aktif.

Metode update() dari kelas FSM harus dimunculkan setiap frame game, sehingga bisa memanggil fungsi yang ditunjuk oleh properti ActiveState. Panggilan itu akan memperbarui tindakan kedudukan yang sedang aktif.

Metode setState() akan mentransisikan FSM ke keadaan baru dengan mengarahkan properti ActiveState ke fungsi kedudukan yang baru. Fungsi kedudkan tidak harus menjadi anggota FSM; fungsi itu bisa masuk dalam kelas lain, yang membuat kelas FSM lebih umum dan dapat digunakan kembali.


Menggunakan FSM

Menggunakan kelas FSM sudah dijelaskan, saatnya untuk menerapkan "otak" sebuah karakter. Semut yang dijelaskan sebelumnya akan digunakan dan dikendalikan oleh FSM. Berikut ini adalah representasi kedudukan dan transisi, dengan fokus pada kode:

FSM otak semut dengan fokus pada kode.

Semut diwakili oleh kelas Ant, yang memiliki properti bernama otak (brain) dan metode untuk setiap kedudukan. Properti otak (brain) adalah contoh kelas FSM:

Kelas Ant juga memiliki properti kecepatan (velocity) dan posisi (position), keduanya digunakan untuk menghitung pergerakan menggunakan integrasi Euler (Euler integration). Metode update() dimunculkan setiap frame game, jadi ini akan meng-update FSM.

Untuk menjaga hal-hal agar tetap sederhana, kode yang digunakan untuk menggerakkan semut, seperti moveBasedOnVelocity(), akan dihilangkan. Informasi lebih lanjut tentang hal itu dapat ditemukan dalam seri memahami Steering Behavior (Understanding Steering Behaviors).

Berikut ini adalah implementasi masing-masing kedudukan, dimulai dengan findLeaf(), kedudukan ini bertanggung jawab untuk membimbing semut ke posisi daun:

Kedudukan goHome(), digunakan untuk membimbing semut pulang:

akhirnya, kedudukan runAway(), digunakan agar semut menajuhi kusor mouse:

Hasilnya adalah semut yang dikendalikan oleh otak "FSM":

Semut dikontrol oleh FSM. Gerakkan kursor mouse untuk mengancam semut.

Meningkatkan Arus: FSM Berbasis Stack

Bayangkan bahwa semut juga perlu lari dari kursor mouse saat sedang pulang. FSM dapat diperbarui sebagai berikut:

Ant FSM diperbarui dengan transisi baru.

Tampaknya ini adalah sebuah modifikasi sepele, penambahan transisi baru, tapi ini menimbulkan masalah: jika keadaan saat ini adalah lari (run away) dan kursor mouse tidak dekat lagi, keadaan apa yang harus mentransisi semut: pulang ke rumah (go home) atau menemukan daun (find leaf)?

Solusi untuk masalah itu adalah FSM berbasis stack (tumpukan). Tidak seperti FSM yang ada, FSM berbasis stack menggunakan tumpukan untuk mengendalikan kedudukan. Bagian atas tumpukan berisi status aktif; transisi ditangani dengan mendorong atau memunculkan kedudukan dari tumpukan:

FSM berbasis Stack

Kedudukan aktif saat ini dapat menentukan apa yang harus dilakukan selma proses transisi:

Transisi di FSM berbasis stack: pop itself + push new; pop itself; push new.

Ini bisa muncul dari tumpukan dan mendorong kedudukan lain, yang berarti transisi penuh (seperti yang dilakukan FSM sederhana). Ini bisa muncul dari tumpukan, yang berarti keadaan saat ini komplit dan keadaan selanjutnya di dalam tumpukan harus aktif. Akhirnya, akan bisa mendorong kedudukan baru, yang berarti keadaan saat ini yang aktif akan berubah untuk sementara waktu, namun saat muncul dari tumpukan, keadaan yang sebelumnya aktif akan mengambil alih lagi.


Menerapkan FSM Berbasis Stack

FSM berbasis stack dapat diimplementasikan dengan menggunakan pendekatan yang sama seperti sebelumnya, namun kali ini menggunakan sejumlah petunjuk fungsi untuk mengendalikan tumpukan. Properti ActiveState tidak lagi dibutuhkan, karena bagian atas tumpukan sudah mengarah ke keadaan aktif saat ini:

Metode setState() diganti dengan dua metode baru: pushState() dan popState(); pushState() menambahkan kedudukan baru ke bagian atas tumpukan, sementara popState() menghapus kedudukan di bagian atas tumpukan. Kedua metode tersebut secara otomatis mentransmisikan mesin ke keadaan baru, karena keduanya mengubah bagian atas tumpukan.


Menggunakan FSM Berbasis Stack

Saat menggunakan FSM berbasis tumpukan, penting untuk dicatat bahwa setiap kedudukan bertanggung jawab untuk muncul sendiri dari tumpukan. Biasanya sebuah kedudukan menghapus dirinya dari tumpukan saat tidak lagi dibutuhkan, seperti jika attack() aktif namun targetnya telah mati.

Dengan menggunakan contoh semut, hanya sedikit perubahan yang diperlukan untuk menyesuaikan kode menggunakan FSM berbasis stack. Permasalahan tentang tidak mengetahui keadaan untuk transisi ke sekarang diselesaikan dengan mulus berkat sifat pada FSM berbasis stack:

Hasilnya adalah semut yang bisa lari dari kursor mouse, beralih kembali ke keadaan yang sebelumnya aktif sebelum ancaman:

semut dikendalikan oleh FSM berbasis stack. Gerakkan kursor mouse untuk mengancam semut.

Kesimpulan

Finite-state machine berguna untuk mengimplementasikan logika AI dalam game. Mesin ini dapat dengan mudah diwakili menggunakan grafik, yang memungkinkan pengembang melihat gambar besar, mengutak-atik dan mengoptimalkan hasil akhir.

Implementasi FSM menggunakan fungsi atau metode untuk merepresentasikan kedudukan sangatlah sederhana namun kuat.  Hasil yang lebih kompleks lagi dapat dicapai dengan menggunakan FSM berbasis tupukan, yang menjamin aliran eksekusi yang dapat dikelola dan ringkas tanpa berdampak negatif terhadap kode tersebut.  Sudah waktunya untuk membuat semua musuh game Anda lebih pintar dengan menggunakan FSM!

Advertisement
Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.