Programlama | Programlama Dilleri | C Programlama Dili |C++

Anasayfa Programlama Haskell Labirentte Yolun Bulunması


Labirentte Yolun Bulunması

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.

Labirentte dörtlü hareket yönü

            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.

Labirentte dörtlü hareket yönü

            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.

  1.  
  2.  
  3. module Labirent
  4. where
  5.  
  6.  
  7. main = putStrLn (gorsel a)
  8.          where
  9.         a = baslat 1 8
  10.                      
  11. baslat a b =cevrim (yolciz1 (labirentiKodla labirent3) (labirentiCoz (labirentiKodla labirent3) (a,b)) (a,b))
  12.  
  13. gorsel [] = ""
  14. gorsel (x:xs) =  ((show (x)) ++ "\n" ++ gorsel xs)   
  15.  
  16.  
  17. --hucrenin karaktere göre ve işlenmesine göre durumunun tutulduğu veri tipi
  18. data Hucre = Bos
  19.           | Gidildi
  20.           | Duvar
  21.           | Hedef
  22.           deriving (Eq, Show)
  23.  
  24. --hucrelerin, genişlik ve enin tutulduğu veri tipi
  25. data Labirent = Labirent Int           
  26.                          Int          
  27.                          [[Hucre]]     
  28.                 deriving Show
  29.  
  30. --koordinat düzlemi
  31. type Pozisyon = (Int, Int) 
  32.  
  33. --gidilebilecek yönleri tutan veri tipi
  34. data Yon = Yukari
  35.            | Asagi
  36.            | Sola
  37.            | Saga
  38.            deriving (Show, Enum, Eq)
  39.  
  40. --izlenen işlemlerin tutuldugu veri tipi
  41. data Yol = Dur
  42.           | Git Yon Yol
  43.           deriving Show
  44.  
  45.  
  46. labirentiCoz :: Labirent -> Pozisyon -> Maybe Yol
  47. labirentiCoz maze here = ara maze here [Yukari .. Saga]
  48.  
  49.  
  50. --hedef durumuna veya tıkanma durumuna gelene kadar arama yapan fonksiyon
  51. ara :: Labirent -> Pozisyon -> [Yon] -> Maybe Yol
  52. ara maze here _          | hucreDurumu maze here == Hedef = Just Dur
  53. ara maze here []                                          = Nothing
  54. ara maze here (dir:dirs)                                  =
  55.   let
  56.     newPos  = git here dir
  57.     newDirs = sil (karsiYon dir) [Yukari .. Saga]
  58.   in
  59.   case hucreBlokemi maze newPos of
  60.     True      -> ara maze here dirs
  61.     otherwise -> case ara (hucreyeGit maze here) newPos newDirs of
  62.                Nothing   -> ara maze here dirs
  63.                Just path -> Just (Git dir path)
  64.  
  65. --Yone göre yeni pozisyonu belirleyen fonksiyon
  66. git :: Pozisyon -> Yon -> Pozisyon
  67. git (x, y) Yukari = (x, y - 1)
  68. git (x, y) Asagi = (x, y + 1)
  69. git (x, y) Sola  = (x - 1, y)
  70. git (x, y) Saga  = (x + 1, y)
  71.  
  72. --labirentte pozisyonu verilen hucrenın durumu
  73. hucreDurumu :: Labirent -> Pozisyon -> Hucre
  74. hucreDurumu (Labirent width height tiles) (x, y)
  75.   | x >= 0 && x < width && y >= 0 && y < height = (tiles!!y)!!x
  76.   | otherwise                                   = Duvar
  77.  
  78. --duvara veya sonuc durumuna gelindimi kontrolu
  79. hucreBlokemi :: Labirent -> Pozisyon -> Bool
  80. hucreBlokemi maze pos = (duvarmi maze pos) || (gelinmismi maze pos)
  81.  
  82.  
  83. hucreyeGit :: Labirent -> Pozisyon -> Labirent
  84. hucreyeGit (Labirent width height tiles) pos =(Labirent width height (hucreGidildi tiles pos))
  85.  
  86. --satirlar arası hücrelerde dolanıyor
  87. hucreGidildi :: [[Hucre]] -> Pozisyon -> [[Hucre]]
  88. hucreGidildi (tl:tls) (x,y)
  89.   | y == 0  = (makeVisitedTileAtRow tl x):tls
  90.   | otherwise = tl:(hucreGidildi tls (x, y - 1))
  91.  
  92. --satir içinde hücrelerde dolanıyor
  93. makeVisitedTileAtRow :: [Hucre] -> Int -> [Hucre]
  94. makeVisitedTileAtRow (cl:cls) column
  95.   | column == 0 = Gidildi:cls
  96.   | otherwise   = cl:(makeVisitedTileAtRow cls (column - 1))
  97.  
  98. --verilen yonun tersini alıyor
  99. karsiYon dir
  100.   | dir == Saga  = Sola
  101.   | dir == Sola  = Saga
  102.   | dir == Asagi = Yukari
  103.   | dir == Yukari = Asagi
  104.  
  105. --duvar kontrolu yapılıyor
  106. duvarmi maze (x,y)
  107.   | hucreDurumu maze (x,y) == Duvar  = True
  108.   | otherwise = False
  109.  
  110. --sonuc durumu kontrolu yapılıyor
  111. gelinmismi maze (x,y)
  112.   | hucreDurumu maze (x,y) == Gidildi = True
  113.   | otherwise                       = False
  114.  
  115. --metni labirente ceviriyor
  116. labirentiKodla :: [String] -> Labirent
  117. labirentiKodla []   = error "Bos Labirent"
  118. labirentiKodla rows =
  119.   let
  120.     height = length rows
  121.     width  = length (head rows)
  122.   in
  123.   Labirent width height (map (map charToTile) rows)
  124.   where
  125.     charToTile '.' = Bos
  126.     charToTile '#' = Duvar
  127.     charToTile '@' = Hedef
  128.     charToTile _   = error "Bilinmeyen Hucre Tespiti"
  129.  
  130. --verilen diziden istenilen değeri siliyorr
  131. sil :: Eq a => a -> [a] -> [a]
  132. sil _ [] = []
  133. sil y (x:xs)
  134.   | (x==y)    = sil y xs
  135.   | otherwise = x:(sil y xs)
  136.  
  137. ---------------------------------------------------------------------------------------
  138.  
  139. hareketSayisi Dur = 0
  140. hareketSayisi (Git dir path) = 1 + (hareketSayisi path)
  141.  
  142. yoluGoster Dur = "\n"
  143. yoluGoster (Git dir path) = show dir ++ "\n" ++ yoluGoster path
  144.  
  145. yoluYaz path = putStr("\nHareket sayisi>>" ++ (show (hareketSayisi path)) ++
  146.                          "\n\n" ++ yoluGoster path)
  147.  
  148. hareket Nothing = 0
  149. hareket (Just path) = hareketSayisi path
  150.  
  151. yaz Nothing = putStrLn "Çözüm yok"
  152. yaz (Just path) = yoluYaz path
  153.  
  154. -----------------------------------------------------------------------------------------
  155.  
  156. labirent1 :: [String]
  157. labirent1 =  ["########",
  158.               "#.@..#.#",
  159.               "#.#.##.#",
  160.               "###..#.#",
  161.               "#.##...#",
  162.               "#..##.##",
  163.               "#.#...##",
  164.               "#.###..#",
  165.               "#.....##",
  166.               "########"]
  167.  
  168.  
  169.  
  170. labirent2 = ["#####",
  171.              "##..#",
  172.              "##..#",
  173.              "#####"]
  174.  
  175.  
  176. labirent3 =  ["########",
  177.               "#.@....#",
  178.               "#.#.##.#",
  179.               "###..#.#",
  180.               "#.####.#",
  181.               "#....#.#",
  182.               "#.#..#.#",
  183.               "#.#.##.#",
  184.               "#......#",
  185.               "########"]
  186.  
  187.  
  188. yolCiz :: Labirent -> Yol -> Pozisyon -> Labirent
  189. yolCiz a  Dur _ = a
  190. yolCiz (Labirent genis uzun hucre) (Git a b) (x , y)=
  191.                              case a of
  192.                              Yukari -> yolCiz (hucreyeGit (Labirent genis uzun hucre) (x , y)) b (x,y-1)
  193.                              Asagi -> yolCiz (hucreyeGit (Labirent genis uzun hucre)(x , y)) b (x,y+1)
  194.                              Saga -> yolCiz (hucreyeGit (Labirent genis uzun hucre)(x , y)) b (x+1,y)
  195.                              Sola -> yolCiz (hucreyeGit (Labirent genis uzun hucre)(x , y)) b (x-1,y)
  196.                             
  197. yolciz1 a (Just Dur)= yolCiz a Dur c
  198. yolciz1 a (Just b) c = yolCiz a b c
  199.  
  200. cevrim :: Labirent -> [String]
  201. cevrim (Labirent genis uzun hucre) = map (map tileToChar) hucre
  202.                                    where
  203.                                    tileToChar Bos = '.'
  204.                                    tileToChar Duvar = '#'
  205.                                    tileToChar Hedef = '@'
  206.                                    tileToChar Gidildi = 'o'
  207.  
  208.  

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

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

Üye Kayıt

 

 

Dictionary
x
+
?
Null.
Dictionary
x
+
?
Null.
Dictionary
x
+
?
Null.
Yorumlar (0)
Sadece kayıtlı kullanıcılar yorum yazabilir!
Son Güncelleme ( Salı, 27 Eylül 2011 03:46 )  
amınıza koyayım amınıza koyayım amınıza koyayım amınıza koyayım amınıza koyayım amınıza koyayım