Doğrusal yol bulma
- Canavar ile oyuncu arasına düz bir rota çizip canavarın o yönde hareket etmesini sağlayan en temel yol bulma yöntemi.
- Canavar duvara çarptığında durur, ancak bu sorun duvar boyunca hareket etmeyi sağlayan wall sliding tekniğiyle çözülebilir.
- Wall sliding yalnızca yol bulmada değil, oyuncu hareketinde de etkilidir ve birçok oyun bu tekniği kullanır.
Dijkstra algoritması
- Okulda öğretilen algoritmalardan biridir ve başlangıç düğümünden diğer tüm düğümlere olan en kısa yolları bulur.
- Hedef düğüm bulunduğunda durdurulabilir, ancak algoritmayı belirli bir yöne yönlendirecek bir yöntem yoktur.
- Oyunlarda canavarın hedefi oyuncunun hareketine göre sürekli değiştiği için Dijkstra algoritması verimsizdir.
A* arama algoritması
- Başlangıç düğümünden hedefe olan mesafeyi ağırlık olarak kullanır ve önce düz rotayı denemeye çalışır.
- Duvarla karşılaşırsa çevredeki düğümleri inceleyerek duvarın etrafından dolaşmayı dener; daha önce ziyaret edilen düğümleri yeniden ziyaret etmediği için sonunda duvarı aşan bir rota bulur.
A* algoritması hileleri
- Örtük grafik veri yapısı: Düğümler ile komşuluk matrisi ya da komşuluk listesi kullanmak yerine, piksel koordinatlarını düğüm olarak kullanıp komşu düğümleri dinamik olarak oluşturarak bellek kullanımını azaltır.
- Geometrik sezgisel: Karoları düğüm olarak kullanarak arama hızını artırır ve sabit bir yineleme derinliği belirleyerek algoritmayı tamamen çalıştırmadan da makul bir ilerleme sağlayabilir.
GN⁺ görüşü:
- Bu yazıdaki en önemli nokta, A* algoritmasını verimli uygulamak için çeşitli hileleri tanıtması.
- A* algoritması, oyun geliştirmede, özellikle kaynakları sınırlı platformlarda yol bulma problemlerini çözmek için çok kullanışlıdır.
- Algoritmanın karmaşıklığını azaltma ve bellek kullanımını optimize etme yöntemleri sunarak, başlangıç seviyesindeki yazılım mühendislerinin yol bulma algoritmalarını daha iyi anlamasına ve uygulamasına yardımcı olur.
Henüz yorum yok.