Snake Pathfinding - Akıllı Yılan

Yılanın kendi gövdesine çarpmadan elmaya ulaşması için farklı arama stratejilerini inceleyin.

Algoritma	Adım	Ziyaret Edilen Durum	Çalışma Zamanı (ms)	Maks Bellek (durum)	Durum
BFS	-	-	-	-	-
DFS	-	-	-	-	-
A*	-	-	-	-	-
Greedy	-	-	-	-	-

Problem Tanımı

Snake oyunu, hareket eden gövdenin kendi üzerine kapanmadan hedefe (elma) ulaşması gereken bir yol planlama problemidir. Her hamlede yılanın başı yeni bir hücreye ilerler; elma yenirse kuyruk büyür, aksi halde kuyruk hücresi boşalır.

Durum Temsili: (baş koordinatı, gövde hücreleri sırası)
Geçiş: Başın dört komşusuna hareket; gövde kayarak ilerler, kuyruk gerekli ise çıkarılır.
Bilgi Modeli: Simülasyonda yılan, elmaların konumunu ve kendi gövde durumunu bilir; algoritma bu bilgiyi kullanarak çarpışmasız bir rota üretmeye çalışır.
Plan: Her turda rastgele belirlenen 5 elma sırayla toplanmalıdır; tüm algoritmalar aynı plan üzerinde yarışır.
Amaç: Elmaya ulaşıldığında oyun devam edebilir; bu demoda tek hedefe ulaşan en kısa/güvenli yol araştırılır.

Sezgisel Fonksiyonlar

Yılanın elmaya olan uzaklığı Manhattan distance ile ölçülür. A* bu değeri gerçek adım maliyetiyle birleştirirken, Greedy yaklaşım yalnızca tahmini uzaklığı değerlendirir.

Manhattan Distance:

h(n) = |x_{head} - x_{apple}| + |y_{head} - y_{apple}|

A*:

f(n) = g(n) + h(n)

g(n): Yılanın yaptığı gerçek hamle sayısı
h(n): Hepsini bilinen hedefe Manhattan uzaklık
f(n): Tahmini toplam maliyet – en küçük değer önce genişletilir

Greedy strateji yalnızca h(n) değerini minimize eder; bu yüzden bazen kuyruğu kapatıp tuzağa düşebilir.