- 8-bit, yukarıdan görünümlü Zelda tarzı bir oyunda canavar takibini uygulamak için basit düz çizgi hareketi yeterli olmadığından, Dijkstra ve A* karşılaştırılarak oyunlara yönelik yol bulmada dengeler aranıyor
- Düz çizgi hareketi duvara takılınca durur; ancak wall-sliding eklendiğinde duvar boyunca hareket edebilir, bu da kontrol hissini iyileştirir ve canavarları araziye hapsetmeye dayalı stratejik öğeler yaratabilir
- Dijkstra algoritması en kısa yolu garanti eder, ancak başlangıç düğümünün çevresini geniş biçimde taradığı için hedefin her karede değiştiği oyunlarda gereken sonraki yönden daha fazla hesaplama yapar
- A*, arama önceliğini hedefe olan mesafeye göre belirleyerek önce hedef yönünü inceler; bir duvarla karşılaşınca çevredeki düğümleri araştırır ve daha önce gördüğü düğümleri tekrar ziyaret etmediği için dolambaçlı bir yol bulabilir
- Oyun haritalarında hız ve uygulama zorluğu; komşuluk listelerini önceden oluşturmayan örtük grafikler, karo bazlı arama ve yineleme derinliği sınırı gibi geometri tabanlı sezgisellerle ayarlanabilir
Oyun bağlamı ve temel gereksinim
- PPU466 tabanlı, 8-bit, yukarıdan görünümlü Zelda tarzı bir oyunda canavarların oyuncuyu takip etmesi gerekiyordu
- PPU466, PICO-8 gibi fantazi konsollara benzer şekilde 8-bit grafikler, karo başına 4 renk, sabit arka plan ve az sayıda sprite kısıtına sahip
- Amaç, canavarların oyuncuyu izlemesi; ancak basitçe duvara takılıp durmamaları veya istenmeyen biçimde sıkışıp kalmamalarıydı
Düz çizgi hareketi ve wall-sliding
- En basit yöntem, canavar ile oyuncu arasına düz bir çizgi çizip o yönde hareket etmektir
- Yalnızca bu yöntem kullanılırsa canavar duvara değdiği anda durur
- wall-sliding uygulanırsa duvara çarptığında durmak yerine duvar boyunca hareket eder
- Oyuncu hareketinde, duvar ve köşelere yakın kontrolleri daha tepkisel hâle getiren bir tekniktir ve neredeyse tüm oyunlarda kullanılır
- Pac-Man’den beri kullanılmaktadır; Pac-Man Championship Edition DX+ ise oyuncu wall-slide yaptığında kıvılcım efekti ekler
- Düz çizgi hareketine wall-sliding eklendiğinde canavarları belirli bir araziye hapsetmek mümkün olur
- Bazı oyunlar bunu stratejik bir öğe olarak kullanır; Runescape’teki safespotting buna örnektir
- Bu oyunda istenen davranış bu olmadığı için gerçek yol bulma algoritmaları incelenmiştir
Dijkstra algoritmasının sınırları
- Dijkstra algoritmasının uygulanması sezgiseldir ve en kısa yolu garanti eder
- Sorun, gerekenden çok daha fazla iş yapmasıdır
- Başlangıç düğümünden grafikteki diğer tüm düğümlere en kısa yolu bulur
- Hedef düğüm bulunduğunda durmak mümkün olsa da aramayı belirli bir hedef yönüne yönlendirmenin bir yolu yoktur
- Video oyunlarında oyuncu sürekli hareket ettiğinden canavarın hedefi her karede değişir
- Canavarın ihtiyacı olan şey, tüm rotadan çok o anda hangi yöne hareket edeceğidir
- Haritadaki tüm pikseller veya karolar için en kısa yollar önceden hesaplanabilir, ancak bu çok bellek kullanır
- Eski platformlarda veya kaynakları kısıtlı platformlarda Dijkstra uygun değildir
A*’ın oyun yol bulmasına uygun olma nedeni
- A* Arama Algoritması, başlangıç düğümünden hedefe olan mesafe bilgisini kullanarak arama önceliğini belirler
- İlk adımda, hedefe düz çizgiyle gitmeye yönelik yönü önce denemeye çalışır
- Dijkstra’dan farklı olarak gerekmedikçe zıt yönü aramaya çok zaman harcamaz
- Bir duvar yolu kapatırsa, duvarın etrafından dolaşmak için çevredeki düğümleri inceler
- Dijkstra gibi daha önce görülen düğümleri tekrar ziyaret etmediği için, çok geri dönüş gerekse bile sonunda bir dolambaç yolu bulabilir
- Örnekte A* kullanan canavar duvarın arkasında sıkışıp kalmaz
Örtük grafik veri yapısı
- Ders kitabı tarzı grafikler düğüm listesi ve komşuluk matrisi veya komşuluk listesiyle temsil edilir; ancak oyunlarda komşu düğümler daha esnek oluşturulabilir
- Örneğin 256×240 piksellik bir ekranda her piksel koordinatı bir düğüm olarak görülebilir
- Komşu pikseller; yukarı, aşağı, sol, sağ ve dört çapraz yön dâhil olmak üzere 8 yönlüdür
- Yukarı-aşağı/sol-sağ hareket ağırlığı 1, çapraz hareket ağırlığı √2, yani yaklaşık 1,4’tür
- Dev bir komşuluk listesini önceden oluşturmak yerine, yalnızca gerçekten ziyaret edilecek düğümler için anında üretilebilir
- Duvar üzerinde bulunan veya başka bir sprite tarafından işgal edilen pikseller geçerli canavar konumları olmadığından, komşuluk listesinden dinamik olarak çıkarılır
- Bu yöntemle harita düzenleyicide komşu olamayacak düğümleri elle dışlamaya gerek kalmaz
Harita geometrisini yansıtan sezgiseller
- A*’ın bazı öğeleri haritanın geometrik yapısına göre doğrudan ayarlanabilir
-
Adım boyutu
- Pikseli düğüm olarak kullanmak yerine, 2D karo tabanlı oyunlarda karolar düğüm olarak kullanılabilir
- Karo bazlı arama, oyuncuya giden yolu bulmak için gereken yineleme sayısını büyük ölçüde azaltarak aramayı hızlandırır
- Bu durumda rota, kare kare kesin bir hareket listesinden çok canavarın gitmesi gereken yönler dizisine benzer
- Canavar genellikle kare başına 1 karo hızla hareket etmediğinden, karo tabanlı bir rota için bile gerçekten gereken bilgi oyuncuya ulaşmayı sağlayan yöndür
- Piksel tabanlı rotalar da aynı niteliğe sahiptir; canavar kare başına 1 piksel veya tam sayı piksel birimleriyle hareket etmeyebilir
-
Yineleme derinliği
- A*’ta bir düğüm öncelik kuyruğundan çıktığında, o düğüm o ana kadar görülen en iyi yolun son adımıdır
- Algoritma sabit bir yineleme sayısında durdurulursa hedefe giden en kısa yol için o ana kadarki en iyi tahmini yol elde edilebilir
- Algoritmayı sonuna kadar çalıştırmadan da makul bir ilerleme yönü elde edilebilir
- Maksimum yineleme derinliği, seviyenin geometrik yapısına göre ayarlanmalıdır
- Derinlik çok küçükse canavar hâlâ duvarın arkasında sıkışıp kalabilir
- Örnekte, sabit 30 karo derinliğinde oyuncu konumuna bağlı olarak canavar sıkışıp ilerleyemiyor
- A* her karede yeniden hesaplandığı için döngü oluşabilir
- Duvara ulaşılan ilk karede aşağı gitmesi gerektiğini hesaplar
- Bir sonraki karede yukarı gitmesi gerektiğini hesaplar
- Bu tekrar nedeniyle canavar bir döngüye sıkışır
- Oyuncu canavarın arama menziline girerse doğru rota bulunabilir
- Sabit
1derinliğinde bu olgu daha uç biçimde görülür; canavar, oyuncuyla arasındaki Öklid mesafesinin en kısa olduğu piksele sürekli geri döner
Ön hesaplama için bir denge noktası
- Daha incelikli hâle getirmek için, haritanın herhangi bir konumundan A*’ın rota bulmak için ihtiyaç duyduğu maksimum derinlik önceden hesaplanabilir
- Dijkstra tarzı tüm rotaları önceden hesaplamadan farklı olarak saklanması gereken şey yalnızca bu tek maksimum değerdir
- Bu maksimum derinlik verildiğinde A*, gerçek zamanlı olarak geçerli bir rota bulabilir
1 yorum
Hacker News yorumları
Prodüksiyon MMO'da A* için kullandığım püf noktaları: 1) şehir düzeyi, bina içindeki odalar arası ve oda içi gibi hiyerarşik grafikler kurarsanız, bir şehrin herhangi bir binasındaki herhangi bir odadaki bir noktadan başka bir noktaya milisaniyenin bir kesrinde yol bulunabilir
2) mevcut A* aramasının meta verisini grafik düğümünün kendisinde tutarsanız ayrı bir ilişkisel dizi tutmanız gerekmez
3) çıkan rotayı olduğu gibi takip etmek yerine, mümkün olduğunda bir sonraki yol düğümüne doğru köşeyi kesmeye çalışan yönlendirme davranışına girdi olarak kullanmak daha iyidir. Başka bir karaktere giden bir rotaysa, hedef karakterin “ekmek kırıntıları” bırakmasını sağlayıp, yeni konum rotanın son düğümünden düz bir çizgide gidilemeyecek durumdaysa bunu rotaya ekleyin
2b) Bunu 16 bitlik bir bitmask içine sıkıştırıyorum. 8 adet 2 bitlik parça, yani 8 yön, ve bunu hash tabloda saklıyorum
2c) Her bit parçasının dört durumu var: FULL_BLOCK(duvar), HARD_BLOCK(karonun hiçbir yönden geçilememesine yol açan büyük nesne), SOFT_BLOCK(tek bir köşeden geçişi engelleyen küçük nesne), NO_BLOCK(boş karo ya da çok küçük nesne bulunan karo)
Böylece bina içindeki birim yol ararken her karo için engel kontrolü yapmak gerekmiyor. Nesne devasa değilse ve dönüş yönüne göre giriş ve çıkış köşelerini kapatmıyorsa, nesneli karodan da geçilebilir. Son olarak, oyuncu kapı yerleşimini unuttuğunda simülasyonun bozulmaması için ajanların duvarlardan da geçebilmesine izin veriyorum
https://store.steampowered.com/app/2287430/Metropolis_1998/
Karakter bu tür bir “balon” içindeyken dünyayla çarpışma kontrollerini tamamen atlayabilirsiniz
Üniversitedeyken RTS'de A*'ın neden bu kadar zor olduğunu anlamıyordum, ama birimlerin birbirinin içinden geçmemesi için hareket eden her şeyin diğer tüm birimlerden sürekli kaçınarak yeniden yol bulması gerektiği açıklamasını görünce Command & Conquer'a yeniden saygı duydum
Çok güçlü bir gerekçe yoksa ben şahsen kaçınırdım
Scala ile yazılmış bir Quoridor AI'ını hızlandırmak için hızlı yol bulma üzerine epey düşündüm; öğrendiğim püf noktaları şunlar
MPAA(çoklu yol uyarlamalı A*), engellerin eklendiği durumlarda aynı bölgeyi tekrar tekrar aramak gerektiğinde işe yarar. Önceki arama sonuçlarını yeniden kullanarak yol bulmayı hızlandırabilirsiniz
JPS(jump point search), dikkate alınacak “düğüm” sayısını ciddi biçimde azaltabildiği için teoride çekici, ama jump point bulma ek yükü çok arttığından pratikte hız kazancı sağlamadı. MPAA ve JPS fikirlerini birleştirmenin bir yolu olabilir, fakat algoritmalarla yaratıcı biçimde oynadığınızda küçük kavramsal ayrıntılar yüzünden kolayca tökezleyebilirsiniz. Örneğin
>=gerekirken>kullanmak, bazı durumlarda gerçekten en kısa yolu garanti edemeyebilirAçık düğümleri saklarken düzgün bir heap yerine, azami öncelik değeri nispeten küçük bir tamsayıysa bucket priority queue da düşünülebilir. İç diziyi önceliğe göre indekslediği için ekleme ve çıkarma oldukça hızlı olur
Quoridor 9x9'luk bir ızgarada oynanır; oyuncunun hedefe ne kadar yakın olduğunu ve hedefe ulaşılıp ulaşılamayacağını değerlendirmek için tekrarlanan yol bulma şarttır. Belirli bir konumdaki olası hamleleri değerlendirmek için, tüm hamlelerin hedefe ulaşmayı imkânsız kılıp kılmadığını kontrol etmek gerekir. Birkaç ay içinde yayımlamayı planlıyorum ve en az 3 karar verme “motoru” içerecek: mtdf(minimax türevi), MCTS(bazı püf noktaları eklenmiş paralel sürüm), catboost ile karıştırılmış hibrit
Bunun güzel yanı, sıradan kuş uçuşu mesafe yerine bunu sezgisel fonksiyon için bir lookup tablosu olarak kullanabilmeniz. Örneğin her turun başında, yerleştirilmiş duvarları yansıtacak şekilde Floyd-Warshall algoritmasıyla bu tabloyu başlatabilirsiniz. Benzer bir problemde bu teknikle A*'ı oldukça ciddi hızlandırmıştım ve çok basitti. Yalnız bu, MPAA veya JPS olmadan saf A* idi
Yıllar önce PathFinding.js'in JPS uygulamasına, jump node bulmak için yapılan özyinelemeli aramayı görselleştiren bir özellik eklemiştim. Çevrimiçi demo burada: https://qiao.github.io/PathFinding.js/visual/
Düşman sayısı ikiden fazlaysa, oyuncu perspektifinden bir kez Dijkstra çalıştırıp her canavarın oyuncuya giden en iyi yolu oradan sorgulamasını sağlamak daha avantajlı olabilir
Canavar sayısı değiştiğinde hesaplama maliyeti daha öngörülebilir olur
Son animasyondaki derinliğin fazla sığ olması sorunu ilginç bir davranış gibi görünüyor. Canavar, sanki “hangi tarafa gideceğini görmek için bekliyormuş” gibi görünüyor
Bir tarafa gidiyormuş gibi yapıp sonra yön değiştirerek onu kandırmak mümkün olmaz mı? Neyse ki insanlar bu tür şeylere epey hoşgörülü; görünüşe göre her şeyi sanki zekiymiş gibi modelliyoruz
Temelde düşmanın yolu her frame'de değil, kısa bir gecikmeden sonra güncellemesini sağlamak yeterli. Böylece “atalet” nedeniyle mevcut rotayı izler ve oyuncu onu kandırabilir
Oyun bağlamında A*'ın ilginç bir kullanımında, 2000'lerin başındaki bir oyun için bilgisayar rakibi yapmak zorunda olan bir programcı vardı
Oyundaki AI'ın sahip olduğu seçenekleri soyutlayıp, o graf üzerinde en kısa mesafeyi A* ile bulmasını sağlamış. Bunu dünya üzerinde yol bulma gibi geleneksel kullanım için değil, bilgisayarın yapabileceği seçimlerin temsili üzerinde arama yapıp en kısa yolun mümkün olan en iyi stratejiyi temsil etmesi için kullanmış olması hoşuma gitmişti
0 - https://www.gamedeveloper.com/design/building-the-ai-of-f-e-...
1 - https://web.archive.org/web/20230804100329/https://alumni.me...
Ek kaynaklar da var (benim değil): https://github.com/agoose77/goap-resources
İnsanlar, kendilerinin ve diğer insanların rota planlama, risk/ödül değerlendirmesi ve 6 ay sonraki bir etkinliği planlama gibi tamamen farklı faaliyetlerde bile benzer düşünce kalıpları ve benzer derinlikte düşünme kullandığını varsayıyor gibi görünüyor. Çeşitli “arama uzayları” ortak bir algoritmaya uygun graflar olarak kodlanabilirse, oynanış sırasında oyuncunun akış halinde olduğu anda AI'ın düşünceli, hatta neredeyse kişilik sahibi gibi görünmesi makul hale geliyor
Üniversitede A* öğrenirken, aynı zamanda ortak bir Minecraft sunucusunda o tuhaf problemle karşılaşmıştım
Sunucu çok kötü tekliyordu; iz sürünce zombilerin, büyük bir çitle tamamen kapatılmış bir köye girmeye çalışırken yol bulma döngüsüne saplandığını gördük. Bu da o zamanki uygulamanın saf olduğunu ve asla vazgeçmediğini gösteriyordu
Bunun nasıl düzeltileceğine dair epey ayrıntılı bir hata raporu olduğunu hatırlıyorum
Özellikle birden fazla hayvanın hep birlikte geçilemeyen bir girişten geçmeye çalışması fps üzerinde çok fark edilir bir etki yaratabiliyordu. Tabii bunu, kapalı bir kapıdan geçmekte aşırı ısrarcı kedi davranışı olarak düşünürseniz inanılmaz gerçekçi de denebilir. Kapıyı açar açmaz kedinin anında fikrini değiştirip geçmeye ilgisini kaybetmesi daha da gerçekçi olurdu gerçi!
Bilinmeyen arazide A* kullanan çok ajanlı sistemler üzerine şu makale ilginizi çekebilir: https://www.researchgate.net/publication/333917261_Implement...
Bu yazıda ve HN başlığında güzel ipuçları var. Henüz A*'ı çok kullanmam gerekmedi ama iyi bir Haskell kütüphanesi olduğunu biliyorum: https://hackage.haskell.org/package/astar-monad-0.3.0.0#read...