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.

 
 
module Labirent
where
 
 
main = putStrLn (gorsel a)
         where
        a = baslat 1 8
                      
baslat a b =cevrim (yolciz1 (labirentiKodla labirent3) (labirentiCoz (labirentiKodla labirent3) (a,b)) (a,b))
 
gorsel [] = ""
gorsel (x:xs) =  ((show (x)) ++ "\n" ++ gorsel xs)    
 
 
--hucrenin karaktere göre ve işlenmesine göre durumunun tutulduğu veri tipi
data Hucre = Bos
          | Gidildi
          | Duvar
          | Hedef
          deriving (Eq, Show)
 
--hucrelerin, genişlik ve enin tutulduğu veri tipi
data Labirent = Labirent Int            
                         Int           
                         [[Hucre]]      
                deriving Show
 
--koordinat düzlemi
type Pozisyon = (Int, Int)  
 
--gidilebilecek yönleri tutan veri tipi
data Yon = Yukari
           | Asagi
           | Sola
           | Saga
           deriving (Show, Enum, Eq)
 
--izlenen işlemlerin tutuldugu veri tipi
data Yol = Dur
          | Git Yon Yol
          deriving Show
 
 
labirentiCoz :: Labirent -> Pozisyon -> Maybe Yol
labirentiCoz maze here = ara maze here [Yukari .. Saga]
 
 
--hedef durumuna veya tıkanma durumuna gelene kadar arama yapan fonksiyon
ara :: Labirent -> Pozisyon -> [Yon] -> Maybe Yol
ara maze here _          | hucreDurumu maze here == Hedef = Just Dur
ara maze here []                                          = Nothing
ara maze here (dir:dirs)                                  =
  let
    newPos  = git here dir
    newDirs = sil (karsiYon dir) [Yukari .. Saga]
  in
  case hucreBlokemi maze newPos of
    True      -> ara maze here dirs
    otherwise -> case ara (hucreyeGit maze here) newPos newDirs of
               Nothing   -> ara maze here dirs
               Just path -> Just (Git dir path)
 
--Yone göre yeni pozisyonu belirleyen fonksiyon
git :: Pozisyon -> Yon -> Pozisyon
git (x, y) Yukari = (x, y - 1)
git (x, y) Asagi = (x, y + 1)
git (x, y) Sola  = (x - 1, y)
git (x, y) Saga  = (x + 1, y)
 
--labirentte pozisyonu verilen hucrenın durumu
hucreDurumu :: Labirent -> Pozisyon -> Hucre
hucreDurumu (Labirent width height tiles) (x, y)
  | x >= 0 && x < width && y >= 0 && y < height = (tiles!!y)!!x
  | otherwise                                   = Duvar
 
--duvara veya sonuc durumuna gelindimi kontrolu
hucreBlokemi :: Labirent -> Pozisyon -> Bool
hucreBlokemi maze pos = (duvarmi maze pos) || (gelinmismi maze pos)
 
 
hucreyeGit :: Labirent -> Pozisyon -> Labirent
hucreyeGit (Labirent width height tiles) pos =(Labirent width height (hucreGidildi tiles pos))
 
--satirlar arası hücrelerde dolanıyor
hucreGidildi :: [[Hucre]] -> Pozisyon -> [[Hucre]]
hucreGidildi (tl:tls) (x,y)
  | y == 0  = (makeVisitedTileAtRow tl x):tls
  | otherwise = tl:(hucreGidildi tls (x, y - 1))
 
--satir içinde hücrelerde dolanıyor
makeVisitedTileAtRow :: [Hucre] -> Int -> [Hucre]
makeVisitedTileAtRow (cl:cls) column
  | column == 0 = Gidildi:cls
  | otherwise   = cl:(makeVisitedTileAtRow cls (column - 1))
 
--verilen yonun tersini alıyor
karsiYon dir
  | dir == Saga  = Sola
  | dir == Sola  = Saga
  | dir == Asagi = Yukari
  | dir == Yukari = Asagi
 
--duvar kontrolu yapılıyor
duvarmi maze (x,y)
  | hucreDurumu maze (x,y) == Duvar  = True
  | otherwise = False
 
--sonuc durumu kontrolu yapılıyor
gelinmismi maze (x,y)
  | hucreDurumu maze (x,y) == Gidildi = True
  | otherwise                       = False
 
--metni labirente ceviriyor
labirentiKodla :: [String] -> Labirent
labirentiKodla []   = error "Bos Labirent"
labirentiKodla rows =
  let
    height = length rows
    width  = length (head rows)
  in
  Labirent width height (map (map charToTile) rows)
  where
    charToTile '.' = Bos
    charToTile '#' = Duvar
    charToTile '@' = Hedef
    charToTile _   = error "Bilinmeyen Hucre Tespiti"
 
--verilen diziden istenilen değeri siliyorr
sil :: Eq a => a -> [a] -> [a]
sil _ [] = []
sil y (x:xs)
  | (x==y)    = sil y xs
  | otherwise = x:(sil y xs)
 
---------------------------------------------------------------------------------------
 
hareketSayisi Dur = 0
hareketSayisi (Git dir path) = 1 + (hareketSayisi path)
 
yoluGoster Dur = "\n"
yoluGoster (Git dir path) = show dir ++ "\n" ++ yoluGoster path
 
yoluYaz path = putStr("\nHareket sayisi>>" ++ (show (hareketSayisi path)) ++
                         "\n\n" ++ yoluGoster path)
 
hareket Nothing = 0
hareket (Just path) = hareketSayisi path
 
yaz Nothing = putStrLn "Çözüm yok"
yaz (Just path) = yoluYaz path
 
-----------------------------------------------------------------------------------------
 
labirent1 :: [String]
labirent1 =  ["########",
              "#.@..#.#",
              "#.#.##.#",
              "###..#.#",
              "#.##...#",
              "#..##.##",
              "#.#...##",
              "#.###..#",
              "#.....##",
              "########"]
 
 
 
labirent2 = ["#####",
             "##..#",
             "##..#",
             "#####"]
 
 
labirent3 =  ["########",
              "#.@....#",
              "#.#.##.#",
              "###..#.#",
              "#.####.#",
              "#....#.#",
              "#.#..#.#",
              "#.#.##.#",
              "#......#",
              "########"]
 
 
yolCiz :: Labirent -> Yol -> Pozisyon -> Labirent
yolCiz a  Dur _ = a
yolCiz (Labirent genis uzun hucre) (Git a b) (x , y)=
                             case a of
                             Yukari -> yolCiz (hucreyeGit (Labirent genis uzun hucre) (x , y)) b (x,y-1)
                             Asagi -> yolCiz (hucreyeGit (Labirent genis uzun hucre)(x , y)) b (x,y+1)
                             Saga -> yolCiz (hucreyeGit (Labirent genis uzun hucre)(x , y)) b (x+1,y)
                             Sola -> yolCiz (hucreyeGit (Labirent genis uzun hucre)(x , y)) b (x-1,y)
                             
yolciz1 a (Just Dur) c  = yolCiz a Dur c
yolciz1 a (Just b) c = yolCiz a b c
 
cevrim :: Labirent -> [String]
cevrim (Labirent genis uzun hucre) = map (map tileToChar) hucre
                                   where
                                   tileToChar Bos = '.' 
                                   tileToChar Duvar = '#'
                                   tileToChar Hedef = '@'
                                   tileToChar Gidildi = 'o'
 
 

Programın Tamamını Aşağıdaki Linkten İndirebilirsiniz

Linki Görebilmeniz İçin Üye Olmanız Gerekmektedir...

Üye Kayıt