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 [] = Nothing let newPos = git here dir 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 --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 hucreyeGit :: Labirent -> Pozisyon -> Labirent --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 --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 --verilen diziden istenilen de?eri siliyorr sil :: Eq a => a -> [a] -> [a] sil y (x:xs) | (x==y) = sil y xs | otherwise = x:(sil y xs) --------------------------------------------------------------------------------------- hareketSayisi Dur = 0 yoluGoster Dur = "\n" 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