NavMesh, A* ve flow field: 200 ajanı takılmadan yürütmek

Kapı önünde biriken 200 ajan

Geçen yılın sonunda bir kuşatma sahnesi üzerinde çalışıyordum: tek bir kale kapısı ve ona doğru koşan 200 NavMeshAgent. Oyun yapay zekasında yol bulma tam olarak böyle sahnelerde çöker. Gece build'inde QA'nın açtığı kayıt hep aynı yerde donuyordu: kapının on beş metre önünde ajanların yaklaşık altmışı birbirine sürtünüp titriyor, bir kısmı geri geri gidiyordu. Kapının arkasındaki avluya ilk on saniyede yalnızca kırk kadarı girebiliyordu.

Sahnenin frame süresi ajanlar uzaktayken 11 ms idi; kapıya yaklaştıklarında 26 ms'e çıkıyordu. İlk tahminim A* aramasının patladığıydı. Profiler bunu doğrulamadı: NavMesh.CalculatePath toplamı 3,2 ms okurken NavMeshAgent'ın kendi iç güncellemesi 9,8 ms tutuyordu. Yani darboğaz aramada değil, ajanların her frame yaptığı işin içindeydi.

Aslında iki ayrı problem aynı anda görünüyor ve birbirine karışıyordu: global yolun hesaplanma maliyeti ile ajanların birbirine göre davranışı. Bu ikisini tek başlık altında toplayan her tartışma çıkmaza girer, çünkü çözümleri bambaşka yerlerde duruyor. Ayırmadan başlarsanız hangi ayarı çevirdiğinizde hangi sayının değiştiğini asla göremezsiniz. Bizde ayrım şununla başladı: profiler'da arama satırı ile ajan güncelleme satırını ayrı ayrı takip etmek.

NavMesh gerçekten nereye bakıyor?

NavMesh, sahnenizin yürünebilir yüzeyinden bake edilmiş bir üçgen ağıdır ve her kenardan ajan yarıçapı kadar içeri çekilmiştir. Yani ajanın yürüdüğü alan, gözünüzle gördüğünüz zemin değildir. Bir takılma raporunda bakılacak ilk yer Navigation penceresinde mesh'i görünür yapmak ve kapı eşiğinde gerçekte kaç santimlik şerit kaldığını ölçmektir. Voxel Size varsayılan 0,166 m iken dar köşelerde tek tek poligonların kaybolduğunu birkaç kez gördüm.

Bizde kapı açıklığı 1,6 m, Agent Radius ise 0,5 m idi. Geriye 0,6 m'lik tek bir şerit kalıyordu: bir ajan geçebiliyor, iki ajan geçemiyordu. Yarıçapı 0,35'e çekmek kolay görünen çözümdü ama tüm haritada ajanların duvarlara girmesine yol açtı; kapıyı level tarafında 2,4 m'ye açmak doğru düzeltme oldu. Ajan yarıçapı görsel bir ayar değil, tüm navigasyonun taban birimidir.

İkinci klasik tuzak hedefin mesh dışında kalmasıdır. SetDestination bu durumda false döner ve kimse dönüş değerine bakmaz; ya da yol NavMeshPathStatus.PathPartial ile gelir, ajan erişebildiği en yakın noktaya gidip orada bekler. Dışarıdan bu tam olarak "takıldı" gibi görünür. Her hedefi önce NavMesh.SamplePosition ile 2 m yarıçapta mesh'e oturtmak bu raporların çoğunu bitirdi. Aynı kontrolü spawn noktalarına da uygulayın; mesh dışında doğan bir ajan ilk frame'den itibaren kayıptır.

Merdiven, atlanan boşluk ve kapı gibi süreksizlikler için off-mesh link kullanılır. Otomatik üretilenler yerine elle yerleştirilen OffMeshLink bileşenleri çok daha öngörülebilir davranıyor. Varsayılan maliyet 1.0 iken 200 ajanın 140'ı 1,2 m'lik tek bir boşluktan atlamaya çalışıyordu; costOverride değerini 5.0 yapınca çoğu daha uzun ama açık olan yolu seçti. Link'lerin iki ucunu da mesh üzerinde tutun; bir ucu boşlukta kalan link sessizce yok sayılır.

A* maliyeti ve hiyerarşik yol bulma

A* pathfinding maliyeti taradığı düğüm sayısıyla büyür. 41.000 poligonluk bir NavMesh'te haritanın bir ucundan diğerine tek istek 0,35 ms sürüyordu. 200 ajan aynı frame'de isterse bu 70 ms eder, ama böyle bir donma görmezsiniz: Unity istekleri kuyruğa alır, yol 3-4 frame gecikmeyle gelir ve ajanlar o süre boyunca eski yönde koşmaya devam eder. Görünen semptom donma değil, geç dönüştür.

Hierarchical pathfinding bu maliyeti ikiye böler. Haritayı bölgelere ayırıp aralarındaki geçişleri portal olarak grafa yazarsınız; arama önce 30-40 düğümlük kaba graf üzerinde yapılır (0,02 ms), ardından yalnızca bir sonraki portala kadar detaylı A* çalışır. Bizde ortalama istek 0,35 ms'ten 0,06 ms'e indi ve bir ajanın tam yolu hiçbir zaman tek seferde hesaplanmadı. Kaba graf bake sırasında bir kez üretiliyor ve çalışma zamanında yalnızca dinamik bir engel portalı kapattığında güncelleniyor.

Denenip elenen alternatif paylaşılan yol önbelleğiydi. Hedefi 4 m'lik hücrelere yuvarlayıp aynı hücreye giden ajanlara tek bir yolu vermeyi denedik. Sabit hedeflerde isabet oranı %70 çıktı, ama oyuncuyu kovalarken %18'e düştü ve önbelleği geçersiz kılma mantığı kazandığından fazlasını geri aldı. Kodu sildik. Yol paylaşımı ancak hedefin onlarca frame boyunca sabit kaldığı senaryolarda geri kazanılıyor.

Kalabalık için tek bir flow field

200 ajan aynı hedefe gidiyorsa 200 ayrı arama yapmak anlamsız. Flow field yaklaşımında hedeften geriye doğru tek bir maliyet yayılımı çalıştırırsınız, sonra her hücreye en ucuz komşusunu gösteren bir yön vektörü yazarsınız. Bizde 128x128'lik bir grid ve 0,5 m hücre boyutu vardı; tam yeniden hesap 4,1 ms sürüyordu. Yayılım tüm hücreleri tek geçişte dolduruyor, yani maliyet ajan sayısından tamamen bağımsız.

Önemli olan bu 4,1 ms'in her frame değil, yalnızca hedef hücre değiştiğinde ödenmesi. Oyuncu koşarken bu saniyede üç dört kez oluyordu, yani saniyede yaklaşık 14 ms. Buna karşılık ajan başına maliyet iki bilinear örneklemeye iniyor: 0,004 ms, 200 ajan için toplam 0,8 ms. Aynı kalabalık hierarchical A* ile 12 ms tutuyordu.

Yöntemin sınırı net: her ayrı hedef ayrı bir alan demek. Üç dört hedefin ötesinde bellek ve yeniden hesap maliyeti A*'ı geçiyor. Bu yüzden hibritte kaldık; isimli NPC'ler ve patron ajanlar A* ile, kalabalık simülasyonu flow field ile yürüyor. İkisi de aynı NavMesh üçgenleri üzerinde duruyor, yalnızca yön kaynakları farklı. Ayrım kodda tek bir bool ile duruyor ve tasarımcı prefab üzerinden çevirebiliyor.

Local avoidance global yol değildir

RVO ve türevi ORCA şunu yapar: her ajan komşularının konum ve hızını okur, çarpışmaya götüren hızları yarım düzlemlerle eler, kalan kümede tercih ettiği hıza en yakın olanı seçer. Ufku bir iki saniyeliktir ve seviyenin geometrisini bilmez. Yani bu bir yön düzeltmesidir, yol bulma değil. Bir ajanı yalnızca ona bırakırsanız RVO onu hiçbir zaman hedefe götürmez.

Bu yüzden local avoidance'tan global çözüm beklemek baştan hatalıdır. U biçimli bir avlu duvarında RVO ajanı duvara yapıştırır ve karşılıklı gelen iki ajan kilitlenir. obstacleAvoidanceType değerini HighQuality yapmak bunu düzeltmez; sadece 200 ajandaki 9,8 ms'in 6,2'sini yer. Good seviyesine düşürdüğümüzde 3,9 ms'e indi ve kamera mesafesinden görülebilir bir fark olmadı.

Asıl kazanç avoidancePriority alanındaydı. Tüm ajanlar varsayılan 50 değerindeyken durum simetrik kalıyor ve kimse kimseye yol vermiyordu. Spawn anında 0-99 arasında rastgele bir öncelik dağıtınca kapı önündeki tıkanma süresi 4,2 saniyeden 1,1 saniyeye düştü. Tek satırlık bir değişiklikti.

Dinamik engeller ve path request bütçesi

Dinamik engeller için NavMeshObstacle ve carving kullanılır, ama carving her hareket için tile'ı yeniden bake eder. Sahnede 12 hareketli varil varken 5,8 ms'lik düzenli spike'lar görüyorduk. carvingMoveThreshold değerini 0,5 m'ye çekip carveOnlyStationary açtığımızda aynı sahne 0,9 ms'e indi. Sürekli hareket eden hiçbir şeyi engel yapmayın; onlar local avoidance'ın işi.

Bütçe kısmı basit: frame başına toplam tam yol isteği sayısını sabitleyin. Bizde bu sayı 12. Ajanlar 0,45 saniyelik bir aralıkla ve üzerine 0-0,15 saniyelik rastgele bir gecikmeyle istek yapıyor; bu jitter olmadan spawn dalgası hepsini aynı frame'e topluyor. Bütçe dolduğunda istek iptal edilmiyor, sıradaki frame'e kayıyor ve ajan o sırada mevcut yolunda yürümeye devam ettiği için fark edilmiyor. Bütçe sayısını hedef donanımda ölçün; konsolda 12 olan bu sayı masaüstünde rahatça 30 olabiliyor.

Bu sahnede toplam frame süresi 26 ms'ten 13,4 ms'e, yol bulmanın payı 13 ms'ten 2,1 ms'e indi; içindeki en ucuz kazanç tek satırlık öncelik değişikliğiydi. Sıralamayı şöyle kurun: önce NavMesh geometrisini gözle doğrulayın, sonra frame başına istek bütçesi koyun, sonra kalabalığı flow field'e taşıyın, local avoidance ayarlarına en son dokunun. Ters sıradan gidilirse saatler ORCA parametrelerinde kaybolur ve 0,6 metrelik kapı olduğu yerde durmaya devam eder. Ölçmediğiniz hiçbir ayarı değiştirmeyin; buradaki sayıların hepsi profiler'dan çıktı, hiçbiri tahminden gelmedi.