T: tema · Z: kodu büyüt · S: konuşmacı notları · F: tam ekran · Esc: genel bakış · ⌂ ders haritası
OYUNLARDA YAPAY ZEKÂ · HAFTA 8
A* ile Yol Bulma
Izgaralar, sezgiler, oyun hileleri — oyun yapay zekâsının en çok kullanılan algoritması
PRESS ▶ TO START

Bu derste oyunun haritası 🗺️

  1. Yol bulma problemi — ızgara, yol noktası grafı, navmesh
  2. BFS’ten A*’a — dört algoritma aynı haritada yarışıyor
  3. Sezgiler — Manhattan, octile, Öklid; ağırlıklı A*
  4. Kod — 30 satırlık A* + üç laboratuvar
  5. Oyunlarda — StarCraft’ın yol bulma hilesi, yol yumuşatma, sık hatalar
  6. Hızlandırma — hiyerarşi (Dragon Age, Factorio), JPS, akış alanı
  7. Kütüphaneler — A* Pathfinding Project, Godot AStarGrid2D, PathFinding.js, NetworkX
🎮 Bu dersin sonunda…

…bir oyun haritasını grafa çevirebilecek, A*’ı yazıp ızgarada çalıştırabilecek, doğru sezgiyi seçebilecek, bulunan yolu yumuşatıp steering ile izletebilecek ve büyük haritalarda yol bulmayı hızlandırmanın yollarını tanıyacaksınız.

🤔 ISINMA: 50 ASKER SEÇİP HARİTANIN ÖBÜR UCUNA TIKLADINIZ

Ne bekliyorsunuz? Ne olursa oyunu “bozuk” bulursunuz?

  • Duvara toslayan, gölün etrafında dönüp duran, köprüde birbirine sıkışan birimler… Oyuncuların en çabuk fark ettiği yapay zekâ hatası yol bulma hatasıdır.
  • Patrick Wyatt (StarCraft): “Yol bulma, çoğu oyuncunun düzgün çalışmadığı ana kadar fark etmediği bir şeydir; sonra o küçük sorun çileden çıkaran bir dünyanın sonuna dönüşür.”
  • İyi haber: algoritma 1968’den beri belli (A*). Kötü haber: oyunda iyi çalıştırmak bir mühendislik sanatı.

🎯 Bu konu için bilmeniz gerekenler

Yeşil = gerekli · kesikli = faydalı ama şart değil. Tıklayınca ilgili sunuma gider.

En Kısa Yollar (Dijkstra)Y0 · Hazırlık (vektör, mesafe)
Öncelik Kuyrukları (yığın)Yönsüz Graflar (BFS)Union-Find (erişilebilirlik)Y7 · Steering (yolu izlemek)
Neden?A*, Dijkstra’ya tek bir fikir ekler: “hedefe ne kadar kaldığını tahmin et.” Dijkstra’yı En Kısa Yollar sunumundan hatırlıyorsanız bu sunum çok kolay gelecek; hatırlamıyorsanız Level 1 baştan anlatıyor.
🧰 Kodlamadan korkuyorsanızUnity’de NavMesh (Y9) ve A* Pathfinding Project, Godot’da AStarGrid2D, Unreal’da NavMesh hazır A* içerir: kod yazmadan yol bulabilirsiniz. Ama “neden takıldı?”, “neden yavaş?” sorularının cevabı bu sunumda.

Mini sözlük

pathfindingyol bulmaBaşlangıçtan hedefe engellere çarpmadan giden (en ucuz) yolu bulmak
node · edge · costdüğüm · kenar · maliyetGidilebilir yer · iki yer arası geçiş · geçişin “pahası” (mesafe, arazi)
g · h · f—g: başlangıçtan buraya gerçek maliyet · h: buradan hedefe tahmin · f = g + h
heuristic · admissiblesezgi · kabul edilebilirKalan maliyet tahmini · tahminin asla fazla olmaması (en kısa yolu garanti eder)
open / closed listaçık / kapalı listeKeşfedilmiş ama işlenmemiş düğümler · işi bitmiş düğümler
Manhattan · octile · Euclidean—4 yönlü · 8 yönlü · her açıda mesafe tahminleri
path smoothing / string pullingyol yumuşatma / ip germeIzgara yolunun gereksiz köşelerini kaldırmak
hierarchical pathfindinghiyerarşik yol bulmaÖnce kaba haritada (odalar), sonra ayrıntıda arama
JPS · flow fieldsıçrama noktası araması · akış alanıIzgarada simetrik yolları atlayan hızlı A* · binlerce birim için yön haritası
LEVEL 0
Yol bulma problemi
dünyayı grafa çevirmek
  • yol bulma problemi
  • BFS’ten A*’a
  • sezgiler
  • kod ve laboratuvarlar
  • oyunlarda tuzaklar ve hileler
  • hızlandırma
  • kütüphaneler ve entegrasyon

Dünya → graf: üç yaygın gösterim

Izgara (grid)25 düğümHarita karelere bölünür; her kare bir düğüm, komşu kareler kenar. 4 yön ya da 8 yön. Basit, düzenlenmesi kolay, arazi maliyeti eklemek kolay. Strateji, kule savunma, roguelike, 2B oyunlar.

Bedeli: çok düğüm, “basamaklı” yollar.

Yol noktası grafı (waypoints)3 düğümTasarımcı haritaya noktalar koyar ve aralarını bağlar. Az düğüm, hızlı arama. 2000’lerin nişancı oyunlarında yaygındı.

Bedeli: elle bakım; noktaların dışındaki alanı “bilmez”.

Gezinti ağı (navmesh)2 çokgenYürünebilir zemin dışbükey çokgenlere bölünür; her çokgen bir düğüm. Bugün 3B oyunların standardı (Unity, Unreal, Godot). Y9’un konusu.

Bedeli: üretmesi karmaşık (motorlar yapar).

A* üçünde de aynı çalışır: sadece “komşular kim, geçiş maliyeti ne?” sorusunun cevabı değişir. Bu sunumda ızgara kullanıyoruz çünkü görmesi en kolayı.

Hikâye: A*’ın doğumu (1968)

  • Y5’ten hatırlayın: Stanford Research Institute’teki robot Shakey, bir odadan diğerine nasıl gideceğini bulmak zorundaydı.
  • Nils Nilsson önce “A1” adlı bir algoritma, Bertram Raphael onu iyileştiren “A2”yi önerdi. Peter Hart, belirli koşullarda en iyi sonucu garanti eden bir sürüm olduğunu kanıtladı ve isim “A*” (“A yıldız”: en iyisi) oldu.
  • 1968’de Hart, Nilsson ve Raphael yayımladı. 55 yıl sonra hâlâ oyunlarda “yol bulma algoritması” denince ilk akla gelen.
💡 Fikir tek cümleDijkstra her yöne eşit yayılır, çünkü hedefin nerede olduğunu umursamaz. A* ise her adımda “bu yoldan hedefe toplam ne kadar sürer?” diye tahmin eder ve en umut vadeden yolu önce dener. Tahmin asla abartılı değilse, bulunan yol yine en kısadır.
LEVEL 1
BFS’ten A*’a
dört algoritma, bir harita
  • yol bulma problemi
  • BFS’ten A*’a
  • sezgiler
  • kod ve laboratuvarlar
  • oyunlarda tuzaklar ve hileler
  • hızlandırma
  • kütüphaneler ve entegrasyon

Önce sezgi: navigasyon gibi düşünün 🧭

Yola çıktınız ve bir kavşaktasınız. Hangi yöne sapacağınıza karar verirken iki şeye bakarsınız:

  • g = buraya kadar kaç kilometre yaptım? (kesin bildiğim)
  • h = buradan hedefe kuş uçuşu kaç kilometre kaldı? (tahmin; yolu, köprüyü, trafiği bilmez)
  • f = g + h = bu kavşaktan geçersem yolculuğun toplamı en az ne kadar olur?

A* her adımda, bildiği bütün kavşaklar içinden f’si en küçük olanı seçip oradan devam eder. Hepsi bu.

Üç sürücü
  • BFS / Dijkstra: yalnızca g’ye bakar. Hedefin nerede olduğunu umursamadan her yöne eşit yayılır: doğru ama yavaş.
  • Açgözlü: yalnızca h’ye bakar. Hep hedefe doğru koşar; çıkmaza girer, dolambaçlı yol bulur.
  • A*: ikisinin toplamına bakar. Hedefe doğru çekilir ama yaptığı yolu da unutmaz.
Sonraki slaytAynı fikri 7 × 5’lik bir ızgarada, her karenin g, h ve f sayılarını göre göre elle izleyeceğiz.

Elle A*: her karede g, h ve f

Dört kardeş: hangisini önce genişletiyoruz?

algoritmaönceliken kısa yolu garanti eder mi?hız
BFSönce keşfedilen (kuyruk)Sadece bütün adımlar eşit maliyetliyseyavaş: her yöne dalga
Dijkstraen küçük gEvet (negatif maliyet yoksa)yavaş: her yöne, maliyete göre
Greedy best-firsten küçük hHayır: “hedefe en yakın görünen” yolu seçerçok hızlı ama aptal olabilir
A*en küçük f = g + hEvet (h kabul edilebilirse)hızlı ve doğru

Dördü de aynı kod: bir öncelik kuyruğu, komşulara bak, daha iyi yol bulursan güncelle. Sadece kuyruğun “sıralama ölçütü” değişir.

⚙️ İki uçh = 0 → A* = Dijkstra (güvenli, yavaş). g’yi yok say → A* = Greedy (hızlı, riskli). A* ikisinin tam ortası.

Yarış: aynı harita, dört algoritma 🏁

  1. U şeklindeki engel: Greedy önce düz hedefe koşuyor, U’nun içine giriyor, sonra çıkış arıyor. Bulduğu yolun maliyeti diğerlerinden yüksek mi?
  2. BFS ve Dijkstra neredeyse bütün haritayı renklendiriyor (genişletilen düğüm sayısına bakın). A* hedefe doğru “uzanıyor”.
  3. U’nun ağzını bir duvarla kapatın: Greedy artık daha iyi mi, daha kötü mü?
  4. B’yi U’nun içine taşıyın. Hangi algoritma en az düğümle buluyor?
  5. Renkler: mavi → kırmızı, başlangıçtan uzaklık (g). Sarı = açık liste (keşfedilmiş, sırada bekliyor).
  • Dört küçük harita aynı haritadır; her birinde başka bir algoritma çalışıyor: BFS, Dijkstra, Greedy best-first ve A*.
  • B başlangıç, H hedef, koyu kareler duvar. Renkli kareler, algoritmanın o ana kadar baktığı (genişlettiği) kareler; kalın çizgi bulunan yol.
  • Her haritanın altında: kaç kareye bakıldığı ve bulunan yolun maliyeti. Az kare = hızlı; düşük maliyet = kısa yol.
  • ⏮ Geri ▶ Oynat İleri ⏭: aramayı baştan, adım adım ya da sona kadar oynatır. Hız kaydırıcısı saniyede kaç karenin açılacağı.
  • Herhangi bir haritada fareyle duvar çizin ya da B/H’yi sürükleyin: dördü yeni haritada yeniden yarışır.

Dördü de aynı döngüyü çalıştırır; tek fark bir sonraki kareyi neye göre seçtikleri:

  1. Başlangıcı “bakılacaklar” listesine koy.
  2. Listeden bir kare seç (aşağıya bakın) ve onu “bakıldı” diye işaretle.
  3. Seçilen kare hedefse dur: geldiğin kareleri geriye izleyerek yolu çıkar.
  4. Değilse komşularını listeye ekle (daha kısa bir yoldan geldiysen eski kaydı güncelle) ve 2. adıma dön.
  • BFS: listeye en önce gireni seçer (kuyruk). Adım maliyetini bilmez; her yöne eşit yayılır.
  • Dijkstra: başlangıçtan uzaklığı (g) en küçük olanı seçer. Bataklık gibi pahalı kareleri hesaba katar; yine her yöne yayılır.
  • Greedy: hedefe kuş uçuşu uzaklığı (h) en küçük olanı seçer. Hedefe koşar ama yol uzun ya da dolambaçlı olabilir.
  • A*: f = g + h en küçük olanı seçer. Hem hedefe yönelir hem en kısa yolu garanti eder (h hedefe olan gerçek uzaklığı aşmadıkça).
🔎 DEMODA DENEYİN
  1. U şeklindeki engel: Greedy önce düz hedefe koşuyor, U’nun içine giriyor, sonra çıkış arıyor. Bulduğu yolun maliyeti diğerlerinden yüksek mi?
  2. BFS ve Dijkstra neredeyse bütün haritayı renklendiriyor (genişletilen düğüm sayısına bakın). A* hedefe doğru “uzanıyor”.
  3. U’nun ağzını bir duvarla kapatın: Greedy artık daha iyi mi, daha kötü mü?
  4. B’yi U’nun içine taşıyın. Hangi algoritma en az düğümle buluyor?
  5. Renkler: mavi → kırmızı, başlangıçtan uzaklık (g). Sarı = açık liste (keşfedilmiş, sırada bekliyor).

🎬 Ara: A*, çizimlerle

A* Pathfinding (E01: algorithm explanation)
Sebastian Lague · 11 dk 38 sn · YouTube’da aç

Elle yaptığımız g, h, f hesabının ızgara üzerinde kare kare, çok temiz çizimlerle anlatımı. Açık ve kapalı listeler, komşu maliyetleri (10 ve 14) ve yolun geriye izlenmesi.

🤔 İzlerkenVideoda çapraz adımın maliyeti neden 14, düz adımınki 10? Bir karenin g değeri ne zaman güncelleniyor? Açık listeden alınan kare neden her zaman f’si en küçük olan?

🔗 Başka gözle: etkileşimli anlatımlar ve yazılar

Aynı konuyu başka bir anlatımla, kendi elinizle oynayarak görmek çok işe yarar. Kartlar yeni sekmede açılır; çoğu İngilizce ama görsel ve etkileşimli.

🔴 Introduction to the A* Algorithm
Red Blob Games (Amit Patel)
BFS, Dijkstra ve A*’ı aynı harita üzerinde, sürüklenebilir duvarlarla anlatan klasik etkileşimli yazı. Bu dersin yol bulma bölümünün en iyi tamamlayıcısı.
🔴 Grids and Graphs
Red Blob Games (Amit Patel)
Izgaranın bir graf olduğunu ve komşuların nasıl bulunduğunu çizimlerle anlatır.
🔴 Flow Field Pathfinding (kule savunması)
Red Blob Games (Amit Patel)
Tek bir BFS ile bütün düşmanlara yol bulmak: haritaya tıklayıp hedefi değiştirin, oklar anında güncellenir.
🔗 PathFinding.js
Xueqiao Xu
A*, Dijkstra, BFS ve Jump Point Search’ü aynı ızgarada yarıştırın; duvarları fareyle çizin.
Quiz 1 · algoritmalar
A*’da h değerini her yerde 0 alırsanız hangi algoritmayı elde edersiniz?
f = g + 0 = g: öncelik sadece başlangıçtan uzaklık olur, bu da tam olarak Dijkstra’dır. Doğrudur ama hedefe yönelmez, gereksiz çok düğüm açar. BFS ise maliyetleri hiç dikkate almaz (bataklık haritasında farkı görün).
LEVEL 2
Sezgiler
iyi bir tahmin, yarı yarıya iş
  • yol bulma problemi
  • BFS’ten A*’a
  • sezgiler
  • kod ve laboratuvarlar
  • oyunlarda tuzaklar ve hileler
  • hızlandırma
  • kütüphaneler ve entegrasyon

Sezgi (h) nedir, hangisi seçilmeli?

h, bir kareden hedefe “daha ne kadar yol kaldı?” sorusuna verilen tahmindir; A* bunu yolu henüz bilmeden, her kare için hesaplar. Tahminin iyisi, gerçek kalan yola eşit olanıdır. Gerçekten az tahmin etmek güvenlidir ama A* gereğinden çok kareye bakar; fazla tahmin etmek A*’ı hızlandırır ama bulduğu yol en kısa olmayabilir.

SHS’den H’ye: 4 sütun sağa, 2 satır yukarı

yeşil: 8 yönde gerçek en kısa yol = 2 çapraz + 2 düz = 2·1,41 + 2 = 4,83
turuncu: yalnızca 4 yönde gerçek en kısa yol = 4 + 2 = 6
mor: kuş uçuşu = √(4² + 2²) = 4,47

sezgiformülbu örnekte h8 yönlü ızgarada
(gerçek 4,83)		4 yönlü ızgarada
(gerçek 6)
Manhattandx + dy6fazla ✗
yol yanlış olabilir		tam ✓
Octilemax + 0,41·min4,83tam ✓az
doğru, biraz yavaş
Chebyshevmax(dx, dy)4az
(çapraz da 1 sayılıyorsa tam)		az
Öklid√(dx² + dy²)4,47azaz
doğru ama en yavaşı
KuralHiçbir zaman gerçeği aşmayan bir sezgiye kabul edilebilir (admissible) denir; A* onunla en kısa yolu garanti eder. En iyisi, hareket kurallarınızın gerçek mesafesidir: 4 yönde Manhattan, 8 yönde octile, serbest harekette (navmesh) Öklid. Amit Patel’in A* yazısındaki etkileşimli örnekte sezgiyi değiştirip farkı görebilirsiniz.

Ağırlıklı A*: biraz hata, çok hız

  • f = g + w · h, w > 1. Arama hedefe daha aç gözlü koşar: çok daha az düğüm.
  • Bedeli: yol en kısa olmayabilir; ama en fazla w katı uzun olur (w = 1,5 ise en kötü %50 uzun).
  • Oyunlarda sık kullanılır: oyuncu %5 uzun bir yolu fark etmez, 5 kat yavaş yol bulmayı fark eder (takılan kare hızı).
Eşitlik bozma hilesiAçık arazide çok sayıda eşit uzunlukta yol vardır ve A* hepsini açar. h’yi çok küçük bir oranla büyütmek (ör. × 1,001) eşitlikleri hedefe yakın olan lehine bozar; yol aynı kalır, arama küçülür.
🧪 Deney: aynı harita, dört wBHwaçılanyol1431561,519360 (+%7)218070 (+%25)511674 (+%32)yeşil: w = 1 (en kısa)kırmızı: w = 5gölge: açılan düğümler
Arazi maliyetiBataklık 5, yol 1, orman 2… A* maliyeti zaten hesaba katar: hızlı ama dolambaçlı yolu seçer. Tasarım için güçlü bir araç: “düşmanlar köprüyü tercih etsin” → köprü ucuz. Taktik maliyetler (tehlikeli bölge pahalı) Y12’de.

Canlı: A* laboratuvarı 🧭

  1. Çizim: ızgaraya tıklayıp sürükleyin (duvar). Fırçayı “bataklık” yapın. B ve H’yi sürükleyin: arama anında yenilenir.
  2. “Bataklık” hazır haritası: BFS bataklıktan geçiyor (maliyeti bilmiyor), A* üstteki dar yoldan dolaşıyor. Yol maliyetlerini karşılaştırın.
  3. Sezgiyi “sıfır” yapın: A* = Dijkstra. Genişletilen düğüm sayısı kaç kat arttı?
  4. Ağırlık w = 3: düğüm sayısı düşüyor; yol maliyeti değişti mi? “Labirent”te dene: ağırlık orada işe yarıyor mu?
  5. 8 yön açıkken sezgiyi “Manhattan” yapın: yol maliyeti octile ile aynı mı? (Abartılı sezgi.)
  6. “g değerleri”ni açıp adım adım oynatın: her karede başlangıçtan gerçek uzaklık yazıyor.
  7. 🔗 Bu konunun en iyi etkileşimli anlatımı: Red Blob Games — Introduction to A* (sayfadaki her şekil oynanabilir). Onlarca algoritmayı yan yana denemek için: PathFinding.js görselleştirici.
  • Fırça menüsü: 🧱 duvar çizer, 🟩 bataklık çizer (geçmek 5 kat pahalı), 🧽 siler. Haritaya tıklayıp sürükleyin.
  • B ve H’yi sürükleyerek başlangıcı ve hedefi taşıyın.
  • Sezgi menüsü: h’nin nasıl hesaplanacağı (Manhattan, octile, Öklid, 0 = Dijkstra).
  • A* ağırlığı w: f = g + w·h. w = 1 klasik A*; w büyüdükçe daha az kareye bakar ama yol biraz uzayabilir.
  • Çapraz kutusu: 8 yönlü hareket. g değerleri kutusu: her kareye başlangıçtan uzaklığı yazar.
  • ▶ Aramayı oynat: aramayı adım adım canlandırır; alttaki sayaçlar bakılan kare sayısı ve yol maliyeti.
  1. Açık listeye başlangıcı koy: g = 0, f = h.
  2. Açık listeden f’si en küçük kareyi çıkar (renkli kareler bunlar).
  3. Hedefse bitti; ebeveyn oklarını geriye izle.
  4. Değilse her komşu için yeni g = g(şimdiki) + adım maliyeti (düz 1, çapraz 1,41, bataklık ×5). Komşu ilk kez görülüyorsa ya da bu g daha küçükse: g’yi yaz, ebeveynini şimdiki kare yap, f = g + w·h ile açık listeye koy.
  5. 2. adıma dön. Açık liste boşalırsa hedefe yol yok.

Elle izlemesi için iki slayt önceki “Elle A*” demosuna bakın.

🔎 DEMODA DENEYİN
  1. Çizim: ızgaraya tıklayıp sürükleyin (duvar). Fırçayı “bataklık” yapın. B ve H’yi sürükleyin: arama anında yenilenir.
  2. “Bataklık” hazır haritası: BFS bataklıktan geçiyor (maliyeti bilmiyor), A* üstteki dar yoldan dolaşıyor. Yol maliyetlerini karşılaştırın.
  3. Sezgiyi “sıfır” yapın: A* = Dijkstra. Genişletilen düğüm sayısı kaç kat arttı?
  4. Ağırlık w = 3: düğüm sayısı düşüyor; yol maliyeti değişti mi? “Labirent”te dene: ağırlık orada işe yarıyor mu?
  5. 8 yön açıkken sezgiyi “Manhattan” yapın: yol maliyeti octile ile aynı mı? (Abartılı sezgi.)
  6. “g değerleri”ni açıp adım adım oynatın: her karede başlangıçtan gerçek uzaklık yazıyor.
  7. 🔗 Bu konunun en iyi etkileşimli anlatımı: Red Blob Games — Introduction to A* (sayfadaki her şekil oynanabilir). Onlarca algoritmayı yan yana denemek için: PathFinding.js görselleştirici.
Quiz 2 · sezgiler
8 yönlü (çapraz maliyeti √2) bir ızgarada hedef 3 sağda ve 4 yukarıda. Octile sezgisi kaç verir?
Octile: max(3, 4) + (√2 − 1)·min(3, 4) = 4 + 0,414·3 ≈ 5,24. Gerçekte 3 çapraz (3√2 ≈ 4,24) + 1 düz = 5,24 adımlık maliyet. Manhattan 7 der (abartılı), Öklid 5 der (iyimser), Chebyshev 4 der (çapraz = 1 varsayımı).
LEVEL 3
Kod ve laboratuvarlar
30 satırlık A*
  • yol bulma problemi
  • BFS’ten A*’a
  • sezgiler
  • kod ve laboratuvarlar
  • oyunlarda tuzaklar ve hileler
  • hızlandırma
  • kütüphaneler ve entegrasyon

🎒 Ön bilgi: A*’ın üç veri yapısı

Öncelik kuyruğu (açık liste)“f’si en küçük düğümü ver.” Python heapq, C# PriorityQueue (.NET 6+; Unity’de yoksa kendi yığınınız), JS’de kendi yığınınız. Öncelik Kuyrukları sunumundaki ikili yığın.
g tablosu“Bu düğüme şimdiye kadar bulduğum en ucuz maliyet.” Sözlük ya da dizi. Daha ucuz yol bulursan güncelle ve kuyruğa yeniden koy.
came_from (ebeveyn) tablosu“Bu düğüme hangi düğümden geldim?” Hedefe ulaşınca geriye doğru izleyip yolu çıkarırsın. En Kısa Yollar sunumundaki edgeTo.

“Kuyrukta aynı düğüm iki kez olabilir mi?” Evet: basit uygulamalarda düğümü güncellemek yerine yeniden eklenir; çıkarken “zaten kapalıysa atla” denir (tembel silme). Kod bunu yapıyor.

A* (ızgara, 8 yön) (1/2)

A* (ızgara, 8 yön) (2/2)

🎒 Kod sözlüğü

heapq.heappush / heappopyığınEn küçük öncelikli elemanı O(log n)’de verir
yieldüreteçFonksiyon bir liste döndürmek yerine elemanları tek tek “verir”; for döngüsüyle kullanılır
g.get(k, math.inf) · TryGetValuegüvenli okumaHiç görülmemiş düğüm için “sonsuz” varsay
path[::-1]ters çevirmeHedeften başlangıca toplanan yolu başlangıçtan hedefe çevirir
Vector2Int · DictionaryUnity tam sayılı vektör · sözlükIzgara koordinatı ve anahtar → değer tablosu
grid[ny]?.[nx]isteğe bağlı zincirlemeSatır yoksa hata vermeden undefined
a ?? bboşsa varsayılana undefined/null ise b

📦 Tam kod: p5.js’te A*

A*’ın tamamı bu döngüdür. Üç tablo: open (sırada bekleyenler), g (buraya en ucuz maliyet), cameFrom (buraya nereden geldim). heuristic’i 0 yaparsanız Dijkstra olur.

🎮 Çalıştırın, kopyalayın, bozun

▶ Eksiksiz örneği aç — yaklaşık 110 satır: fareyle duvar çizin, sarı ajan farenin olduğu kareye yol bulup yürüsün. Açık mavi kareler A*’ın baktığı yerler.

Deneyin:

  • H tuşu: sezgiyi kapatın (Dijkstra). “Bakılan kare” kaç katına çıktı?
  • D tuşu: çapraz hareketi kapatın; yol nasıl değişti?
  • Ajanı duvarlarla tamamen kapatın: “yol: YOK” ve bütün alan mavi — en pahalı arama.
  • Kodda sezgiyi 3 ile çarpın: daha az kare, ama yol hâlâ en kısa mı?

🌱 Isınma kodu: Manhattan mesafesi

Adını Manhattan’ın ızgara biçimli sokaklarından alır: çapraz gidemezsiniz, yatay + dikey blok sayarsınız. A*’ın 4 yönlü ızgaralardaki sezgisi (h) tam olarak budur. İpucu: Math.abs.

🌱 Isınma kodu: yolu geriye doğru çıkar

A* hedefe ulaşınca elinde bir yol değil, “her kareye nereden geldim” tablosu olur. Yol, hedeften geriye doğru ekmek kırıntılarını izleyerek çıkarılır ve sonra ters çevrilir (path.reverse()).

🧪 Canlı laboratuvar: octile sezgisi

Manhattan’ı octile ile değiştirin: max + (√2 − 1)·min. Sağda üç harita sırayla aranıyor; sizin sezginizle A*’ın genişlettiği düğüm sayısını ve yolun en kısa olup olmadığını izleyin. Sonra deney: 3 * octile yapın; düğüm azalır ama yol hâlâ en kısa mı?

🐍 Laboratuvar: arazili ızgarada yol maliyeti

Dikkat: kuyruğa g + h koyuyorsunuz ama çekince g’ye ihtiyacınız var; best[(x, y)]’den okuyun. Testlerde bataklıkta dolaşmanın daha ucuz olduğu, yolun olmadığı ve başlangıç = hedef olan ızgaralar var.

🐍 Laboratuvar: üç sezgi

Hepsi aynı (dx, dy) için. Sonucu inceleyin: hangisi her zaman en büyük, hangisi en küçük? Bu sıralama, hangisinin hangi ızgarada “abartılı” olduğunu söyler.
LEVEL 4
Oyunlarda tuzaklar ve hileler
StarCraft’tan DigiPen’e
  • yol bulma problemi
  • BFS’ten A*’a
  • sezgiler
  • kod ve laboratuvarlar
  • oyunlarda tuzaklar ve hileler
  • hızlandırma
  • kütüphaneler ve entegrasyon

Derin hikâye: StarCraft’ın yol bulma hilesi (1998) ⛏️

Patrick Wyatt’ın (Blizzard) 2013 blog yazısından:

  • StarCraft’ın çıkışı yaklaşırken yol bulmada o kadar çok uç durum vardı ki oyun “çıkarılamaz” hâldeydi: birimler savaş alanında takılıyor, ileri geri kıpırdayıp duruyordu.
  • En büyük sorun işçilerdi (SCV, drone, probe). Oyuncular kazancı artırmak için bir maden yatağına olabildiğince çok işçi koyar; işçiler maden ile üs arasında gidip gelirken karşı yönden gelenlerle çarpışır. Yeterince kalabalıkta bazıları kilitlenir; oyuncu savaşla uğraşırken üssündeki ekonomi durur.
  • Wyatt’ın itirafı: yol bulma kodunu uzun uzun inceledikten sonra “sorunu düzeltecek kadar akıllı olmadığını” anladı ve bir hile yaptı: maden taşıyan ya da madene giden işçiler, aynı işi yapan diğer işçilerle çarpışmayı yok sayar.
  • Sonuç: “trafik sıkışıklığı” tamamen kayboldu. Bugün bile bir grup çalışan işçiyi seçip “dur” derseniz, hemen dağılıp boş kareler aradıklarını görürsünüz.
🐘 DragoonDiğer sorunlar ya etrafından dolaşıldı ya da görmezden gelindi. Wyatt’a göre Protoss Dragoon, en büyük kara birimi olduğu için sık sık yol bulamadı ve kötü bir üne kavuştu. (Büyük birimler için “boşluk” (clearance) farklı hesaplanmalı: dar geçitler onlara kapalı.)
💡 Ders“Doğru” çözüm her zaman gerekli değil; oyuncunun gördüğü sonuç önemli. Wyatt: “Çalışıyor; bu en iyi hile türü.”

Izgara yolu çirkindir: yumuşatma

Kırmızı: A*’ın ızgara yolu (45° basamaklı). Mor: “ip germe” (string pulling): görüş hattı olan en uzak noktaya düz git. Sarı ajan yolu steering ile izler (Y7). Renkli kareler A*’ın baktığı yerler: mavi = başlangıca yakın, yeşil = uzak; açık sarı = sırada bekleyen; beyaz = hiç bakılmadı.

Sık düşülen tuzaklar

1) Ulaşılamayan hedefHedef bir adanın üstündeyse A* bütün haritayı tarar ve “yol yok” der: oyunun en pahalı araması. Çare: haritayı önceden “bağlantılı bölgelere” ayırın (Union-Find sunumu!) ve aynı bölgede değillerse hiç arama yapmayın.
2) Herkes aynı karede50 birim tek bir noktaya gider ve orada üst üste biner. Çare: hedef etrafında formasyon/dağıtma, birimler arası kaçınma (Y7: RVO).
3) Hareketli engellerYol bulunduktan sonra kapı kapanır. Çare: yolu izlerken önü kontrol et, gerekirse yeniden ara (Y5’teki yeniden planlama).
4) Hepsi aynı karede aramaYüz birim aynı karede yol isterse kare hızı düşer. Çare: istekleri kuyruğa al, karelere yay (zaman dilimleme); aynı hedefe gidenler için akış alanı.
5) Birim boyuBüyük birimler için dar koridorlar kapalı olmalı (Dragoon!). Çare: her hücre için “buradan geçebilecek en büyük birim” (clearance) haritası ya da boya göre ayrı navmesh.
6) Her kare aramaKovalayan düşman her karede yeniden yol bulursa işlemci yanar. Çare: hedef bir eşikten fazla kımıldadıysa yeniden ara; arada steering ile hedefe yaklaş.

Hikâye: DigiPen’in A* yarışması — 100 kat fark 🏎️

Steve Rabin ve Nathan Sturtevant (Game AI Pro, 17. bölüm): DigiPen Teknoloji Enstitüsü’nde giriş YZ dersinin ilk ödevlerinden biri sabit bir ızgarada A* yazmak. Ek puan için “en hızlı A*” yarışması yapılıyor. Yıllar içinde yüzlerce öğrenciden çıkan sonuç:

aynı haritada süre
en hızlılar~200 µs
ortalama~2.500 µs
en yavaşlar20.000 µs’den fazla

Aynı algoritma, aynı sonuç; arada 100 kat. “Nerede olurdunuz?”

Kitaptaki optimizasyonlar
  1. Kaliteli sezgi (önceden hesaplanmış tablolar bile)
  2. Doğru arama uzayı (ızgara mı, navmesh mi, hiyerarşi mi?)
  3. Bütün belleği önceden ayır (arama sırasında new yok)
  4. Abartılı sezgi (ağırlıklı A*) ile daha az düğüm
  5. Açık liste için doğru veri yapısı
  6. Geri dönüşleri önle, komşuları önbelleğe al

Ve “kötü fikir”: on aramayı aynı anda yarım yarım yürütmek; birini bitirip sonrakine geçmek genelde daha hızlı.

Quiz 3 · oyunlar
Oyuncu, birimlerini su ile çevrili ulaşılamaz bir adaya göndermek için tıkladı. Önlem alınmamış bir A* ne yapar?
A* yolun olmadığını ancak açık listesi boşalınca anlar: başlangıçtan ulaşılabilen her düğümü genişletir. Çözüm: haritayı önceden bağlantılı bölgelere ayırıp (Union-Find, flood fill) hedefin aynı bölgede olup olmadığına O(1)’de bakmak; olmadığı durumda hedefe en yakın ulaşılabilir noktayı seçmek.
LEVEL 5
Hızlandırma
hiyerarşi, JPS, akış alanı
  • yol bulma problemi
  • BFS’ten A*’a
  • sezgiler
  • kod ve laboratuvarlar
  • oyunlarda tuzaklar ve hileler
  • hızlandırma
  • kütüphaneler ve entegrasyon

Hiyerarşik yol bulma: önce odalar, sonra adımlar

  • İnsan da böyle düşünür: “Ankara’dan İzmir’e: önce otobana, sonra…” Her sokağı baştan aramayız.
  • Harita bölgelere ayrılır (odalar, parçalar). Önce bölgeler grafında kaba yol, sonra sadece o bölgelerin içinde ayrıntılı yol.
  • Dragon Age: Origins (BioWare): alt seviye ızgaranın üstünde iki soyut ızgara seviyesi. Company of Heroes: üst seviye altıgen ızgara, alt seviye kare ızgara (Rabin & Sturtevant).
Factorio (2019): göl etrafında biter’larTopçu eklenince, oyuncular büyük bir gölün öbür kıyısındaki biter yuvalarını vurmaya başladı; yüzlerce biter gölün etrafından yol aramaya çalıştı ve düz-çizgi sezgili A* kare hızını öldürdü. Çözüm (Friday Facts #317): oyunun 32×32’lik parçalarını (chunk) “içinde serbestçe dolaşılabilen bileşenlere” ayırıp küçük bir soyut graf kurmak. Bu soyut graftaki mesafe, asıl A* için çok daha akıllı bir sezgi oldu: arama gölün etrafından dolaşmayı baştan “biliyor”.

Izgara hileleri: JPS ve önceden hesaplama

Jump Point Search (JPS)Harabor & Grastien (2011): açık bir ızgarada aynı uzunlukta yüzlerce simetrik yol vardır ve A* hepsini açar. JPS, düz çizgide “ilginç bir şey” (bir köşe, engelin ucu) olana kadar sıçrar; aradaki düğümleri listeye hiç koymaz. Sonuç yine en kısa yol.
JPS+ ve Goal BoundingSteve Rabin (GDC 2015, Game AI Pro 2, 14. bölüm): sıçrama mesafelerini önceden hesaplamak (JPS+) — testinde geleneksel A*’dan 116 kat hızlı; bir de “bu yönden gidilince hangi hedeflere varılır” kutularını (goal bounding) ekleyince 1000 kattan fazla. Bedeli: harita statik ve maliyetler tekdüze olmalı.
Hepsini önceden hesaplaKüçük haritalarda bütün düğüm çiftleri için “ilk adım” tablosu (Floyd–Warshall) tutulabilir: yol bulma = tablo okuma. Bellek düğüm sayısının karesiyle büyür.
Her açıda yol: Theta*Arama sırasında görüş hattı varsa ebeveyni “atlayarak” bağlar; sonradan yumuşatmaya gerek kalmadan doğal, kesintisiz açılı yollar (Game AI Pro 2, 16. bölüm).
Binlerce birim tek hedefY7’deki akış alanları: hedeften bir kez Dijkstra, sonra her birim kendi hücresinin okunu izler (Supreme Commander 2, kule savunma oyunları).
Quiz 4 · hızlandırma
Haritası oyun sırasında sürekli değişen (oyuncunun duvar inşa ettiği) bir oyunda hangisi en zor uygulanır?
JPS+ ve goal bounding, harita değişmeyecek varsayımıyla önceden hesaplanan tablolara dayanır; her duvar inşasında tabloları yeniden hesaplamak gerekir. Factorio da bu yüzden kolayca güncellenebilen parça tabanlı bir hiyerarşi seçti. Ağırlıklı A* ve zaman dilimleme haritadan bağımsızdır; bölgeler ise yerel olarak güncellenebilir.
LEVEL 6
Kütüphaneler ve entegrasyon
hazır A*’lar ve kendi oyununuz
  • yol bulma problemi
  • BFS’ten A*’a
  • sezgiler
  • kod ve laboratuvarlar
  • oyunlarda tuzaklar ve hileler
  • hızlandırma
  • kütüphaneler ve entegrasyon

🧰 Kütüphaneler ve araçlar

adplatformne yapar / sınırlarınasıl eklenir
A* Pathfinding ProjectUnity · ücretsiz + ProAron Granberg’in yaygın eklentisi: ızgara, navmesh, nokta grafı; yol yumuşatma, çok iş parçacıklı arama, RVO kaçınması (Pro). Unity NavMesh’ten esnek.Asset Store ya da sitesinden UnityPackage
Godot AStarGrid2D / AStar2DGodot 4 · yerleşikIzgara için hazır A* (çapraz kuralları, sezgi seçimi, ağırlıklı hücreler); AStar2D/3D kendi nokta grafınız için.Kodda AStarGrid2D.new()
Unreal Navigation SystemUnreal · yerleşikRecast/Detour tabanlı navmesh + A*; AI MoveTo ile hazır. Izgara oyunları için kendi A*’ınızı yazarsınız.Haritaya NavMeshBoundsVolume
Recast & DetourC++ · açık kaynakUnreal ve birçok motorun kullandığı navmesh üretici + yol bulucu (Y9).CMake
PathFinding.jsJavaScript · açık kaynakIzgarada A*, Dijkstra, BFS, JPS, iki yönlü arama; görsel demo sayfası ünlü.npm install pathfinding
python-pathfindingPython · açık kaynakPygame projeleri için ızgara A*, Dijkstra, JPS vb.pip install pathfinding
NetworkXPython · açık kaynakGenel graf kütüphanesi; nx.astar_path(G, a, b, heuristic). Prototip ve analiz için.pip install networkx
Moving AI benchmarksveri setiGerçek oyunlardan (Dragon Age, StarCraft vb.) çıkarılmış haritalar ve test senaryoları: kendi A*’ınızı ölçmek için.İndir

Hazır A* ile üç satır

Godot örneğinde dil GDScript; renklendirme için Python sözdizimi kullanılıyor. Sürüm farklarına dikkat: yukarıdaki API’ler Godot 4.2+, A* Pathfinding Project 4.x/5.x içindir.

🧩 Projenize yol bulma eklerken

  1. Gösterimi seçin: 2B ızgara oyunu → ızgara A*; 3B → motorun navmesh’i (Y9).
  2. Yol bulma ≠ hareket: A* nokta listesi verir; karakteri Y7’deki gibi steering/arrive ile yürütün, yolu yumuşatın.
  3. Asenkron: aramayı bir kuyruğa koyun, kare başına süre bütçesi verin; sonuç gelene kadar karakter beklesin ya da hedefe doğru dönsün.
  4. Hata ayıklama: açık/kapalı düğümleri ve yolu Gizmos ile çizin (demodaki gibi). “Neden bu yolu seçti?” sorusunu ancak görerek cevaplarsınız.
  5. Ölçün: en kötü durum (ulaşılamaz hedef, haritanın iki ucu) kaç ms? Profiler ile (Y18).
⚙️ Bütçe örneği60 FPS’te bir karenin 16,6 ms’si var; YZ’ye genelde 1–3 ms düşer. Ortalama arama 0,2 ms ise karede ~10 arama. Daha fazlası kuyruğa.
Tasarım düğmeleriArazi maliyetleri (düşman yolu tercih etsin), “tehlikeli bölge” cezası (Y12), birim türüne göre farklı maliyet (tank bataklıktan kaçınsın, piyade umursamasın).

🤖 Bu konuyu bir YZ kod asistanıyla yazarken

Sık yapılan hatalar — kontrol edin
  • 8 yönlü ızgarada Manhattan sezgisi (abartılı → en kısa değil)
  • Açık listeyi her adımda tam sıralamak (büyük haritada yavaş)
  • Kapalı düğümü yeniden açmak / hiç kapatmamak (sonsuz döngü)
  • Köşelerden çapraz geçişe izin vermek (karakter duvarın içinden geçer)
  • Unity’de .NET sürümünde olmayan PriorityQueue kullanmak
İyi bir istek (prompt) örneği

“Unity 6, C#. 2B ızgara (bool[,] walkable, float[,] cost) için A* yaz: 8 yön, köşe kesme yok, octile sezgisi, kendi ikili yığınını kullan (PriorityQueue kullanma). Ulaşılamaz hedef için önceden flood fill ile bölge kimlikleri hesapla ve farklı bölgedeyse hedefe en yakın ulaşılabilir hücreyi hedef yap. Sonucu string pulling ile yumuşat (Bresenham görüş testi). Aramayı coroutine’de kare başına en fazla 1 ms çalıştır. Açık/kapalı hücreleri ve yolu OnDrawGizmos ile çiz.”

  • Izgara mı, graf mı, navmesh mi; 4 mü 8 yön mü; köşe kesme kuralını açıkça yazın
  • Sezginin hareket kurallarıyla uyumlu olmasını isteyin (8 yön → octile)
  • Yol yoksa ne olacağını (en yakın ulaşılabilir nokta) belirtin
  • Aramayı ana iş parçacığını dondurmadan yapmasını ve sınır koymasını isteyin
  • Yolu bulduktan sonra yumuşatma ve steering ile izleme isteyin

🔬 Araştırma ucu

Çoklu ajan yol bulma (MAPF)Depo robotları gibi yüzlerce ajanın birbirine çarpmadan aynı anda yol bulması: Conflict-Based Search (Sharon vd., 2015) ve türevleri. Oyunlarda RTS birimleri için ilham verici; mapf.info ve Moving AI’da benchmarklar var.
Değişen dünyada: D* LiteKoenig & Likhachev (2002): harita değişince her şeyi baştan aramak yerine eski aramayı onarır. Mars gezginleri gibi robotlarda; oyunlarda yıkılabilir ortamlar için.
Öğrenilmiş sezgiler“Neural A*” (Yonetani vd., 2021) gibi çalışmalar, sezgiyi ya da hangi düğümlerin açılacağını sinir ağıyla öğrenir. Oyun haritalarında ne kadar işe yarar? Açık bir bitirme projesi sorusu.

💬 Tartışma soruları

Yanınızdakiyle 2 dakika konuşun, sonra sınıfça tartışalım
  1. StarCraft ekibi işçilerin birbirinin içinden geçmesine izin vererek sorunu “çözdü”. Bu tembellik mi, iyi mühendislik mi? Oyuncu olarak fark etmiş miydiniz?
  2. Bir strateji oyununda en kısa yol köprüden, ama köprü düşman kulelerinin menzilinde. YZ’nin köprüden kaçınmasını A*’a nasıl “anlatırsınız”? (İpucu: maliyet sadece mesafe olmak zorunda değil.)
  3. %5 daha uzun ama 5 kat hızlı bulunan bir yol mu, kusursuz ama oyunu takılttıran bir yol mu? Hangi tür oyunda cevabınız değişir?
  4. Navigasyon uygulamanız (Google Haritalar vb.) sizce dünyanın bütün sokaklarında düz A* mı çalıştırıyor? Bu dersteki hangi fikirleri kullanıyor olabilir?

🚀 Proje ve araştırma önerileri

  1. [kolay] Kule savunma — p5.js’te ızgara + A*: oyuncu kule koydukça düşmanların yolu değişsin. Tamamen kapatmayı yasaklayın (yol yoksa kuleyi koyma).
  2. [kolay] Kampüs haritası — Fakültenizin kroki planını ızgaraya çevirip binalar arası en kısa yürüyüşü A* ile bulun; merdiven = yüksek maliyet.
  3. [orta] RTS seçimi — 20 birim seçip tıklama: tek A* + formasyon ofsetleri + steering ile kaçınma. StarCraft’ın işçi hilesini deneyin.
  4. [orta] Hiyerarşik ızgara — 128×128 haritayı 16×16 bölgelere ayırıp iki seviyeli arama; düz A* ile süre ve düğüm sayısını karşılaştırın.
  5. [zor] JPS — Harabor & Grastien’in JPS’ini yazıp Moving AI’daki bir StarCraft haritasında A* ile karşılaştırın.
  6. [araştırma] MAPF oyunu — Sıra tabanlı bir bulmaca: 5 robot aynı anda hedeflerine çarpışmadan gitmeli; CBS ile otomatik çözücü yazın.

Neler öğrendik? 🎒

  • Dünya → graf: ızgara, yol noktası, navmesh.
  • BFS → Dijkstra → Greedy → A*: f = g + h.
  • Sezgi: Manhattan (4 yön), octile (8 yön), Öklid (her açı); kabul edilebilirlik; ağırlıklı A*.
  • Kod: öncelik kuyruğu, g tablosu, came_from.
  • Oyunlarda: StarCraft işçi hilesi, Dragoon, yumuşatma, ulaşılamaz hedef, zaman dilimleme, birim boyu.
  • Hızlandırma: hiyerarşi (Dragon Age, Company of Heroes, Factorio), JPS/JPS+, önceden hesaplama, akış alanı.
  • Araçlar: A* Pathfinding Project, AStarGrid2D, Unreal/Recast, PathFinding.js, NetworkX.
  • Sonraki: NavMesh — 3B dünyada yürünebilir alan.

🎮 Bu sunumdaki oyunlar

Adı geçen oyunu tanımıyorsanız: oyuncuların kullandığı wiki sayfası ve oyunu kısaca gösteren bir video. ▶ video slaydın üstünde açılır (Esc ile kapanır); 🎯 işaretli bağlantılar doğrudan bu sunumdaki konuya gider.

StarCraft 1998 / 2010 · gerçek zamanlı strateji
Üç ırkın savaştığı, e-sporu başlatan strateji serisi; StarCraft II, DeepMind’ın AlphaStar’ının sahnesi oldu.
📖 Fandom wikisi · ▶ video 2:26
Dragon Age: Inquisition 2014 · rol yapma
Ekip tabanlı fantastik rol yapma oyunu; ekip arkadaşlarını YZ yönetir.
📖 Fandom wikisi · ▶ video 2:19
Factorio 2020 · fabrika kurma
Uzaylı bir gezegende giderek büyüyen otomatik fabrikalar kurarsınız; yerli böcekler saldırır.
📖 Factorio Wiki · 🎯 düşmanlar (biter’lar) · ▶ video 1:59
Company of Heroes 2006 · gerçek zamanlı strateji
İkinci Dünya Savaşı’nda manga düzeyinde strateji; siper ve görüş hattı çok önemli.
📖 Fandom wikisi · ▶ video 1:59
Supreme Commander 2 2010 · gerçek zamanlı strateji
Yüzlerce birimin aynı anda savaştığı büyük ölçekli strateji; birimleri akış alanlarıyla yürür.
📖 Fandom wikisi · ▶ video 1:23

Kaynaklar: videolar 🎬

A* Pathfinding (E01: algorithm explanation)
Sebastian Lague A* Pathfinding (E03: algorithm implementation)
Sebastian Lague A* (A Star) Search Algorithm
Computerphile Pathfinding — Understanding A* (A star)
Tarodev Path Planning — A* (A-Star)
javidx9 The hidden beauty of the A* algorithm
Polylog

Etkileşimli: Red Blob Games — Introduction to A* (Amit Patel; muhtemelen internetteki en iyi A* anlatımı) · PathFinding.js görsel demo

📄 Akademik okumalar

Hart, Nilsson & Raphael 1968 · A Formal Basis for the Heuristic Determination of Minimum Cost Paths (IEEE Trans. Systems Science and Cybernetics 4(2))
A*’ın doğduğu makale.
Harabor & Grastien 2011 · Online Graph Pruning for Pathfinding on Grid Maps (AAAI 2011)
Jump Point Search.
Rabin & Sturtevant 2013 · Pathfinding Architecture Optimizations (Game AI Pro, Bölüm 17)
DigiPen yarışması, hiyerarşi örnekleri, optimizasyonlar.
Rabin 2015 · JPS+: An Extreme A* Speed Optimization for Static Uniform Cost Grids (Game AI Pro 2, Bölüm 14)
JPS+ ayrıntıları.
Rabin & Sturtevant 2017 · Faster A* with Goal Bounding (Game AI Pro 3, Bölüm 22)
Hedef sınırlama kutuları.
Nash & Koenig 2015 · Theta* for Any-Angle Pathfinding (Game AI Pro 2, Bölüm 16)
Her açılı yollar.
Koenig & Likhachev 2002 · D* Lite (AAAI 2002)
Değişen haritalarda artımlı yeniden planlama.
Yonetani vd. 2021 · Path Planning using Neural A* Search (ICML 2021 / arXiv)
Öğrenilmiş arama.

Kaynaklar: okuma 📚

NEXT LEVEL ▶
NavMesh
Yürünebilir zemini çokgenlerle örtmek: Recast, Unity, Unreal, Godot
SONRAKİ SUNUM ▶