Başkent Üniversitesi'nde Oyunlar için Yapay Zeka Eğitimi

IEEE Başkent Üniversitesi Öğrenci Kolu'nun Computer Society Komitesi ve Yapay Zeka Çalışma Grubu bizi Yapay Zeka Eğitim Serisi'ne davet etti. Yaklaşık doksan dakika süren eğitimde kurucumuz bilgisayar mühendisi Can Karabulut, oyunlarda kullanılan yapay zeka algoritmalarını anlattı. Bilgisayar mühendisimiz Batuhan Tatlısert de oyun kodlamaya giriş yaptı. Etkinliğe 70'ten fazla öğrenci katıldı ve öğrendiklerimizi birlikte bir oyun kodlayarak uyguladık.

Aşağıda o gün anlattıklarımızı, on yılı aşkın yazılım sektörü tecrübemizden örneklerle paylaşıyoruz. Oyun yapay zekasına yeni başlayan herkes için iyi bir başlangıç noktası olmasını umuyoruz.

Sonlu durum makineleri

Devriye gezen, oyuncuyu görünce peşine düşen ve canı bitince yere yığılan bir düşman aslında durumlar arasında geçiş yapıyor. Sonlu durum makinesi (Finite State Machine, FSM), bir karakterin, düşmanın ya da menünün bu durumlar arasında nasıl geçiş yaptığını tanımlayan bir modeldir. Her durum bir davranışı temsil eder. Geçişler ise bir durumdan diğerine hangi şartlarda geçileceğini belirler. Bu şart bir tetikleyici olay, dolan bir süre ya da oyuncunun bastığı bir tuş olabilir.

FSM oyun geliştiriciye üç konuda yardımcı olur. Karmaşık davranışlar net durumlar üzerinden yönetildiği için kod düzenli kalır. Yeni bir davranış eklemek ya da var olanı değiştirmek kolaylaşır. Her durumun hangi geçişle değişeceği belli olduğu için hata ayıklamak da kolaylaşır.

Unity'de kurmanın üç yolu

En hızlı başlangıç, durumları bir enum ile tanımlamak ve bir C# betiğinin update metodunda yönetmektir.

public enum EnemyState
{
    Idle,
    Patrol,
    Chase,
    Attack,
    Dead
}

Daha esnek ve yeniden kullanılabilir bir yapı için her durumu ayrı bir sınıf olarak yazabilirsiniz (State Pattern). Her durum sınıfının EnterState, UpdateState ve ExitState metotları olur. Karakter ya da yapay zeka sınıfı yalnızca o anki durumu çalıştırır.

Unity'nin Animator penceresi (Mecanim) de bir FSM'dir. Her animasyon klibi bir durumdur ve aralarındaki geçişler bool, trigger, float ve int parametreleriyle kurulur. Örneğin karakterin hızı sıfırdan büyük olunca koşma animasyonuna geçilir. Animator animasyonları yönetmek için çok iyidir. Yapay zeka gibi oyun mantığını ise C# ile yazılmış bir FSM'de tutmak genellikle daha temiz bir yoldur.

Örnek bir Boss karakteri

Beş durumu olan güçlü bir Boss karakteri düşünelim. Oyuncu yaklaşana kadar bekler (Idle). Sonra ilk saldırı kalıplarına başlar (PhaseOne). Canı yarının altına inince yeni saldırılara ve zemindeki tuzaklara geçer (PhaseTwo). Belirli bir saldırı aldığında kısa bir süre öfkelenip daha hızlı saldırır, süre bitince ikinci aşamaya döner (Rage). Canı sıfırlanınca ölüm animasyonu oynar (Dead). FSM sayesinde her aşamanın saldırı ve hareket mantığı birbirinden ayrı kalır ve bakımı kolaylaşır.

Yol bulma algoritmaları

Bir düşmanın oyuncuya giden yolu bulması bir graf problemidir. Haritadaki noktalar düğüm, aralarındaki yollar kenardır. Eğitimde beş yaklaşımı karşılaştırdık.

BFS (genişlik öncelikli arama)

BFS bir grafı katman katman gezer. Önce başlangıç düğümünün komşularını, sonra onların komşularını ziyaret eder ve bunu bütün düğümler bitene kadar sürdürür. Bunu yaparken bir kuyruk kullanır. Bütün kenarların ağırlığı eşitse en kısa yolu bulur ve belirli bir uzaklıktaki düğümleri kolayca çıkarır. Derin ve çok dallı graflarda bellek kullanımı yükselebilir. Kenar ağırlıkları farklıysa gerçek en kısa yolu bulamaz.

DFS (derinlik öncelikli arama)

DFS bir dalın sonuna kadar iner, sonra geri dönüp ziyaret etmediği dallara geçer. Bir yığın ya da özyineleme ile yazılır. En kısa yolu bulmayı garanti etmez.

Dijkstra algoritması

Dijkstra, kenarları pozitif ağırlıklı graflarda en kısa yolu bulur. Başlangıç düğümünden diğer düğümlere olan en kısa uzaklıkları öncelikli bir kuyruk (priority queue) ile hesaplar. BFS'nin aksine ağırlıklar farklı olduğunda da doğru çalışır. Pozitif bir ağırlık, o kenardan geçmenin bir maliyeti ya da uzaklığı olduğu anlamına gelir. Negatif ağırlıklarda doğru sonuç vermez ve arama büyüdükçe kuyruk işlemleri daha çok zaman alır.

A* algoritması

A* da en kısa yolu arar ama bir sezgi (heuristic) kullanarak aramayı hızlandırır. Her düğüm için f(n) = g(n) + h(n) hesaplanır. Burada g(n) başlangıçtan o düğüme kadar olan gerçek maliyet, h(n) ise o düğümden hedefe kalan tahmini maliyettir. Izgara haritalarda h(n) için çoğu zaman yatay ve dikey farkların toplamı olan Manhattan uzaklığı kullanılır. Düz çizgi (Öklid) uzaklığı da işe yarar. İyi bir sezgi gereksiz dallanmayı azaltır, bu yüzden A* çoğu durumda Dijkstra'dan daha hızlı sonuç verir.

Greedy (açgözlü) yaklaşım

Greedy yaklaşımı her adımda o an en iyi görünen seçimi yapar. Uygulaması basittir ve hızlı hesaplanır. Huffman kodlaması, Prim ve Kruskal algoritmaları gibi bazı problemlerde en iyi çözüme ulaşır. Yine de her zaman en iyi sonucu garanti etmez, çünkü adım adım yapılan en iyi yerel seçimler bütün problemi en iyi şekilde çözmeyebilir.

Karşılaştırma

Algoritma	En kısa yol	Ağırlık desteği	Sezgi	Zaman karmaşıklığı
BFS	Yalnızca eşit kenar ağırlığında	Yok	Yok	O(V + E)
DFS	Hayır	Yok	Yok	O(V + E)
Dijkstra	Evet	Pozitif	Yok	O((V + E) log V)
A*	Evet	Pozitif	Var	O((V + E) log V), iyi bir sezgiyle pratikte daha hızlı
Greedy	Probleme göre	Değişir	Yok	Değişir

Burada V düğüm sayısını, E kenar sayısını gösterir.

Birlikte oyun kodladık

Teoriden sonra sıra uygulamaya geldi. Batuhan'ın oyun kodlamaya giriş bölümü ve yukarıdaki algoritmalar, öğrencilerle birlikte yazdığımız oyunda bir araya geldi. Eğitimden kısa anları aşağıdaki videolarda izleyebilirsiniz.

Teşekkürler

Bizi ağırlayan IEEE Başkent Üniversitesi Öğrenci Kolu'na, Computer Society Komitesi'ne ve Yapay Zeka Çalışma Grubu'na, etkinliğe katılan bütün öğrencilere çok teşekkür ederiz. Oyun yapay zekasıyla ilgili bir sorunuz olursa bize her zaman yazabilirsiniz.