LABİRENTTE YOLUN BULUNMASI
Labirent içerisinde bir hedef hücre vardır. Amaç labirent içerisinde verilen hücreden bu hedef hücreye ulaşıp, verilen hücre ile hedef hücre arasındaki yolu bulmaktır. Çözüm yöntemi Lee algoritmasına benzer bir yolla labirenti çözmeye çalışır.
Başlangıç olarak 4 farklı yönde arama işlemi yapılır. Hedef durumuna ulaşmak için bu 4 yöne bakılır.
Bir yönde hareket yapılırken özyinelmeli olarak arama fonksiyonu çağrılır. Başlangıçta B noktası için 4 yönde de fonksiyon çağrılır. Diyelim ki ilk olarak fonksiyon aşağı yön içi çağrıldı. Fonksiyonun bu kademesinde bu hücreye gelinen yön gidilecek yönler arasından çıkarılır. Örneğin fonksiyonun aşağı yönde çağrıldığında gideceği yönler aşağıdaki şekilde gösterilmiştir.
Eğer bir hücre fonksiyonun bir kademesinde işlenmişse bu hücre “Gidildi” olarak işaretlenir. Böylelikle fonksiyonun diğer kademelerinde tekrar bu düğüme bakılmaz. Hücre eğer duvarsa daha önce gidilmiş hücre ile aynı muameleyi görür.
Bu şekilde gelinen hücrelerden herhangi birisi hedef durumu ise algoritma geriye doğru işleyerek gidilecek yönleri oluşturur.
VERİ YAPILARI
Hucre ( data Hucre = Bos | Gidildi | Duvar | Hedef )
Labirent içerisindeki hücreleri temsil etmek için kullanılan veri tipidir. Dört farklı değer alabilir. Eğer değeri “Hedef” ise gidilmesi istenen hedef hücre olduğu anlamına gelir. Değeri “Duvar” ise bu hücrenin bir duvar olduğunu ve bu hücre üzerinden gidilemeyeceğini belirtir. Değeri “Bos” ise arama yapılırken bu hücreden geçilebileceği anlamına gelir. Değeri “Gidildi” ise arama yapılırken bu hücreden daha önce geçildiği anlamına gelir. Böylelikle arama esnasında tekrar bu hücreye bakılmaz.
Yon ( data Yon = Yukari | Asagi | Sola | Saga )
Yönleri belirlemek için kullanılan veri tipidir. Labirentte arama yapılırken yönlere bakılarak arama yapılır. Bir pozisyonun komşularına bakılırken ve hedefe giden yol oluşturulurken yönler kullanılır.
Pozisyon ( type Pozisyon = (Int, Int) )
Labirentin bulunduğu ızgara üzerindeki koordinatları belirlemek için kullanılan tip tanımlamasıdır. İlk değer x eksenine, ikinci değer de y eksenine karşılık gelir.
Labirent ( data Labirent = Labirent Int Int [[Hucre]] )
Labirenti temsil eden veri tipidir. İlk tamsayı değeri labirentin genişliğini, ikincisi ise yüksekliğini temsil eder. En son elemanı da hücrelerin tutulduğu iki bir dizi gibi düşünebiliriz. Sonuçta bu eleman listelerin listesidir. Labirent verileri bu eleman içindedir. Yapılması gereken herhangi bir değişiklik bu listenin içindeki elemanların değiştirilmesiyle sağlanır.
Yol ( data Yol = Dur | Git Yon Yol )
Verilen hücreden istenilen hücreye gidilecek yolun tutulduğu özyinelemeli veri tipidir. Hedefe ulaşıldığını “Dur” verisi belirtir.
FONKSİYONLAR
Sil (sil :: Eq a => a -> [a] -> [a] )
Verilen listedeki bir elemanı siler.
karsiYon ( karsiYon::Yon->Yon )
Verilen yönlerin zıt yönünü döndüren fonksiyondur.
git (git :: Pozisyon -> Yon -> Pozisyon )
Verilen bir koordinattan belirli bir yönde ilerleyince hangi koordinata ulaşılacağını gösteren fonksiyondur.
hucreDurumu ( hucreDurumu :: Labirent -> Pozisyon -> Hucre )
Labirent içerisindeki verilen bir koordinattaki hücreyi geri veren fonksiyondur. Eğer istenilen pozisyon labirent sınırları dışında ise “Duvar” döndürür. Diğer durumlarda labirentin veri tipinin içinde hücrelerin bulunduğu iki boyutlu Hucre listesinde gerekli değeri döndürür.
gelinmismi ( gelinmismi::Labirent->Pozisyon->Bool )
Labirent içerisinde verilen pozisyondaki hücrenin hücre durumuna bakar. Eğer buradaki hücre “Gidildi” ise doğru, diğer durumlarda yanlış döndürür.
duvarmi (duvarmi::Labirent->Pozisyon->Bool )
gelinmismi fonksiyonuna benzerdir. Fark olarak hücre durumu “Duvar” ise doğru, diğer durumlarda yanlış döndürür.
hucreBlokemi (hucreBlokemi :: Labirent -> Pozisyon -> Bool )
Eğer labirentte verilen pozisyondaki hücre duvarsa veya daha önce ziyaret edilmişse doğru, aksi hallerde yanlış döndüren fonksiyondur.
hareketSayisi (hareketSayisi::Yol->Int )
Bir “Yol” içerisinde hedefe ulaşmak için kaç hareket yapılması gerektiğini bulan fonksiyondur.
hucreyeGit (hucreyeGit :: Labirent -> Pozisyon -> Labirent )
Labirentteki verilen koordinattaki hücreyi “Gidildi” olarak değiştiren fonksiyondur.
ara (ara :: Labirent -> Pozisyon -> [Yon] -> Maybe Yol )
Labirentteki arama işlemini gerçekleştiren özyinelemeli fonksiyondur. Argüman olarak “Labirent”, “Pozisyon” ve “Yon” listesi alır ve geriye “Maybe Yol” elemanını döndürür. Eğer verilen pozisyondaki hücre “Hedef” hücresi ise “Just Dur” verisini döndürür. Eğer gelen “Yon” listesi boş bir liste ise “Nothing” verisini döndürür. Bu ikisi de değilse arama işlemi özyinelemeli olarak devam edecektir.
İlk olarak yeni pozisyon ve bu pozisyondan gidilecek yönler hesaplanır. Yeni pozisyon verilen pozisyondan verilen yönde gidilerek bulunur. Gidilecek yönler bütün yönlerden gelinen yönün tersi çıkarılarak bulunur. Böylelikle arama işlemi yapılırken gelinen yöne tekrar bakılmaz ve program sonsuz döngüden kurtulur. Yeni pozisyonundaki hücrenin bloke olup olmadığına bakılarak özyinelemeli olarak gidilecek yönler arama fonksiyonuna iletilir. Eğer yeni pozisyondaki hücre bloke değilse bu hücre “Gidildi” olarak işaretlenir ve diğer yönler arama fonksiyonuna yeni pozisyon ile iletilir.
Çözüm bulunması durumunda “Hedef” durumundan geriye doğru özyineleme içerisinde yollar oluşturulur.
labirentiCoz ( labirentiCoz :: Labirent -> Pozisyon -> Maybe Yol )
Arama işlemi başlangıcında çağrılan fonksiyondur. Dalga algoritmasına göre başlangıç pozisyonundan bütün yönler için ara fonksiyonunu çağırır.
labirentiKodla ( labirentiKodla :: [String] -> Labirent )
labirentiCoz fonksiyonu argüman olarak “Labirent” tipinde bir veri alır.Kullanıcının elle bu veritipini oluşturması karmaşık bir işlemdir.Bu fonksiyon string listelerinden Labirent veritipine dönüşüm yapar.Aşağıda bu string listelerinden bir tanesi verilmiştir.
| Yorumlar |
|