- 001
- 002
- 003
- 004
- 005
- 006
- 007
- 008
- 009
- 010
- 011
- 012
- 013
- 014
- 015
- 016
- 017
- 018
- 019
- 020
- 021
- 022
- 023
- 024
- 025
- 026
- 027
- 028
- 029
- 030
- 031
- 032
- 033
- 034
- 035
- 036
- 037
- 038
- 039
- 040
- 041
- 042
- 043
- 044
- 045
- 046
- 047
- 048
- 049
- 050
- 051
- 052
- 053
- 054
- 055
- 056
- 057
- 058
- 059
- 060
- 061
- 062
- 063
- 064
- 065
- 066
- 067
- 068
- 069
- 070
- 071
- 072
- 073
- 074
- 075
- 076
- 077
- 078
- 079
- 080
- 081
- 082
- 083
- 084
- 085
- 086
- 087
- 088
- 089
- 090
- 091
- 092
- 093
- 094
- 095
- 096
- 097
- 098
- 099
- 100
-- Подключим нужные библиотеки
-- http://codepad.org/
-- import Control.Exception
import Data.Array
import Data.Ord
import Data.List
import System.Random
import Control.Arrow
import Text.Printf
--Тестовая карта. Можно менять.
testMapList2D = [
" ",
" X X ",
" X XX XX",
"XX X ",
" X X ",
" XX ",
" X ",
" X "]
--Топографические знаки:
void = ' '
wall = 'X'
step = '*'
-- Не удобно без |> из F#. Няшная же функция. Чего её вдруг нет? Не выдержал, добавил.
infixl 0 $>
($>) = flip ($)
-- Получаем карту произвольного размера WxH. Генератор простейший, но впрочем не годен для генерации красивых лабиринтов.
-- Можно использовать для измерения производительности.
generateList2D wh wallFactor seed =
(randomRs (0, 1000) (mkStdGen seed) ::[Float]) $>
map (\randNumber -> if randNumber/1000 > wallFactor then void else wall ) >>>
listToList2D wh
-- Вспомогательные функции
listToList2D (w, h) =
take (w*h) >>>
iterate (drop w) >>>
take h >>>
map (take w)
widthHeightOfList2D l = (length $ head l, length l)
makeArray2D (w, h) values = listArray ((0,0), (h-1, w-1)) values
list2DToArray2D l = makeArray2D (widthHeightOfList2D l) $ concat l
widthHeightOfArray2D a = let (mx, my) = snd $ bounds a in (mx+1, my+1)
putIntoArray2D valueForInsertion a positionsForInsertion = a // (zip positionsForInsertion $ repeat valueForInsertion)
mapPathAdd map_ path = putIntoArray2D step map_ path
generateMap wh wallFactor seed = list2DToArray2D $ generateList2D wh wallFactor seed
outputArray2D a =
elems a $>
listToList2D (widthHeightOfArray2D a) >>>
mapM print -- В самом конце в последней строке функция outputArray2D стала грязной. Поплачем над её участью и идём дальше.
-- Приступим к функции поиска пути findPath.
-- UB findPath при использовании не прямоугольной карты.
-- UB findPath для карт меньше 2x2 точек (из-за реализации getNearestPoint) (из-за лени добавить одну короткую строчку с учетом того что карт таких не бывает обычно).
-- Также использование неподходящих в карте топографичексих знаков не контролируется.
-- Тесты не писал.
{-
Я честно пытался использовать assert в чистом коде, но возможно из-за лени он работает через раз.
В коде выглдяит отвратительно.
Самое не приятное что он не сообщает ничего подробнее чем то, что произошл ассерт. Не номер строки, не описание ошибки, не выражение. Видимо чисто недоделанная стандартная библиотека.
Пытался написать свой ассерт, чтобы хоть какое-то сообщение выдавал. Ну видимо руки кривые сделали ещё ассерт хуже, тк вообще ни разу проверил. Видимо нужны всякие бенги секи и прочее для форсирования ленивых вычислений. Так что даже не стал пытаться.
-}
-- Функция findPath все ещё чиста как слеза младенца.
findPath map_ (sx, sy) (dx, dy) = getPath $ waveField (-1) initialFieldAndYetNotFindedDestinationPoint (dx, dy)
where
wh = widthHeightOfArray2D map_
(w, h) = wh
fieldMax = w*h+1
initialField = makeArray2D wh $ repeat fieldMax
initialFieldAndYetNotFindedDestinationPoint = (initialField, False)
posibleSteps (cx, cy) = [(cx+1, cy), (cx-1, cy), (cx, cy+1), (cx, cy-1)]
isInMapRange (cx, cy) = cx>=0 && cy>=0 && cx<w && cy<h
getNearestPoint field = (minimumBy (comparing (field!))) . (filter isInMapRange) . posibleSteps
getPath (field, True) = (takeWhile (/=(dx,dy)) $ iterate (getNearestPoint field) (sx,sy)) ++ [(dx, dy)]
getPath (field, False) = []
waveField waveDistance waveFieldWithFindResult (cx, cy)
| not $ isInMapRange (cx, cy) = waveFieldWithFindResult
| map_!(cx, cy) == wall = waveFieldWithFindResult
| ((fst waveFieldWithFindResult) ! (cx, cy)) <= waveDistance = waveFieldWithFindResult
| (cx, cy)==(sx, sy) = ((fst waveFieldWithFindResult) // [((cx, cy), waveDistance+1)], True)
| otherwise =
let waveFieldWithFindResult1 = ((fst waveFieldWithFindResult) // [((cx, cy), waveDistance+1)], snd waveFieldWithFindResult) in
foldl (waveField (waveDistance+1)) waveFieldWithFindResult1 $ posibleSteps (cx, cy)
-- Копипасте-бой
pathView map_ mapName sourcePoint destinationPoint = do
let mapInfo = mapName ++ " with size " ++ (show $ widthHeightOfArray2D map_) ++ ":"
print mapInfo
let sd = (sourcePoint, destinationPoint)
printf "Path for %s: " (show sd)
let path = findPath map_ (fst sd) (snd sd)
print path
let mapWithPath = mapPathAdd map_ path
print "Map with path: "
outputArray2D mapWithPath