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