На Хабрахабре есть уже немало хороших статей по хаскелю, но, к сожалению, это по большей части всяческие введения в ФП, разъяснения каких-то теоретических штук (вроде монад, лямбда-исчисления или семейств типов) и совсем немного практических примеров. Ни в коем случае не умаляя их полезности, попробую всё-таки сместить дисбаланс, внести свою лепту в неблагодарное дело популяризации функциональщины и ещё раз показать, что язык пригоден не только для написания факториалов и неэффективных быстрых сортировок в две строчки, но и для вполне практичных вещей вроде быстрого прототипирования.
Статья постарается быть относительно real-world, но при этом не утомлять читателя объёмом или экзотическими предметными областями. «Графика и игры в обучении — это всегда sexy», как завещал великий В. С. Луговский, поэтому я набросаю простую игру, всенародно любимый «Сапёр». Разработка будет вестись «сверху вниз» — это малораспространённая, но заслуживающая пристального внимания (как и сам хаскель) методология, про которую я когда-то давно прочитал в отличной статье о шашках в «Практике функционального программирования», и с тех пор она запала мне в душу.
С головы на ноги
Идея проста: мы начинаем не с нижележащих элементарных типов и функций, объединяя их в более крупные (как обычно делается в повседневной разработке на мейнстримных языках), а наоборот, описываем самые высокоуровневые сущности, постепенно разбивая их на мелкие. Когда код пишется одним-двумя программистами, а постановка задачи известна заранее — или, наоборот, прототипируется непонятная штука, которая сто раз меняется в ходе разработки, — такой подход, на мой взгляд, лучше классического. Во-первых, он позволяет не забредать в тупик кривой реализации, если вдруг мы начали с неправильных примитивов. Во-вторых, он следует принципу KISS (а точнее, методу прогрессивного JPEG) — можно остановиться на любом уровне проработки, если результат устраивает, и не углубляться в лишние детали, которые при «снизу вверх» могут казаться первостепенно важными. В-третьих, в случае гибкого прототипирования он упрощает уточнение задачи и требований по ходу разработки.
(подробнее можно прочитать на Википедии)
Кроме того, отличительной особенностью хаскеля является то, что благодаря ленивости и выводу типов объявления и определения типов и функций можно задавать чуть ли не в любом порядке, и писать код прямолинейно, почти не возвращаясь в начало, чтобы что-то изменить или дописать (разве что импорты модулей). Поэтому подход «сверху вниз» там проявляет себя особенно замечательно — можно легко начинать с верхнеуровневых функций, иногда ставя заглушки и дописывая то, что они вызывают и используют, уже потом. Разработку небольшой программы вести очень просто — пишете в редакторе минимум кода, периодически загружаете в REPL и добиваетесь его успешной компиляции, затем пробуете вызывать реализованные функции, правите выползающие баги и имплементируете необходимые заглушки, и так пока рабочий результат вас не удовлетворит.
Я не буду объяснять синтаксис хаскеля, базовые функции и всё такое прочее, поскольку статья и так вышла подробной и пухловатой. Поэтому она ориентирована на человека, уже имеющего некоторый опыт в языке, а если вы таковым не являетесь, начните с одного из вышеупомянутых введений. Вместо этого я сосредоточусь на демонстрации конкретных библиотек и объяснениях, как мысли, возникающие в процессе реальной разработки (которую я вёл параллельно с написанием статьи), ложатся на код. По той же причине статья может смахивать на поток сознания, и заранее прошу прощения у тех, кому такой стиль претит.
Минное поле
Итак, начнём. Правила «Сапёра» объяснять, думаю, никому не нужно, поэтому сразу приступим к реализации, а ограничения всплывут по ходу дела. Игра должна запускаться полноправным бинарником, поэтому первое, что у нас есть, это точка входа — как и во многих других языках, это функция main. Она должна создать начальное игровое поле и запустить на нём игру:
main :: IO ()
main = do
let field = createField
startGame field
Что делает createField? Каким-то образом создаёт поле, но как, пока непонятно. Пусть для начала оно будет иметь фиксированный размер, которое зададим в константах:
fieldSize@(fieldWidth, fieldHeight) = (15, 15) :: (Int, Int)
mineCount = 40 :: Int
createField :: Field
createField = undefined
startGame :: Field -> IO ()
startGame = undefined
Оставим на месте реализации undefined-заглушку, потому что пока непонятно, что с этими параметрами делать, и подумаем, что же такое Field. Поле в «Сапёре» — это двумерный массив из клеток. В хаскеле массивы, конечно же, есть, но с изменяемыми массивами (а ведь в процессе игры по полю будут непрерывно щёлкать) работать не очень удобно. Поэтому, чтобы не возиться с мутабельностью в монадах IO и ST, используем простую персистентную альтернативу — словарь, где ключами будут позиции клеток, а значениями — их состояния:
type Field = Map Cell CellState --не забудем дописать вначале import Data.Map
type Cell = (Int, Int)
Какие состояния могут быть у клетки?
- Для начала, клетка может быть открыта или закрыта, и на ней может быть мина.
- Если она открыта, на ней может быть либо циферка с числом заминированных соседей, либо подорванная бомба, если сапёр промахнулся.
- Если закрыта, сапёр должен иметь возможность поставить или снять флажок.
Все эти состояния должны быть взаимоисключающими: нельзя, например, поставить флажок на открытую или отрисовывать цифру на закрытой. Напрашивается некий алгебраический тип, конструкторы которого соответствуют возможным состояниям:
data CellState = Closed {hasMine, hasFlag :: Bool} --Закрыта; параметры — стоят ли флаг и мина
| Opened (Maybe Int) --Открыта; параметр — сколько у неё опасных соседей (и Nothing, если мина в ней самой)
Тип получился достаточно корявый, в нём всё свалено в кучу. Такой вариант тоже вполне реализуем; но попробуем ещё подумать, и если получится, пойти другим путём.
Отметим, что тут смешиваются два состояния клетки:
- неизменяемое, изначально генерируемое, внутреннее (есть или нет мина);
- изменяемое визуальное (открыта или нет, есть ли флажок или циферка).
Попробуем отделить визуальное, а наличие мин хранить как-то отдельно. В этом случае закрытое состояние становится ненужным, поскольку пустую клетку можно просто не хранить в словаре (кстати, в массиве пришлось бы хранить всё). Что ж, зафиксируем вышесказанное в коде:
data CellState = Opened Int --Открыта; параметр — циферка, которая будет отображаться
| Mine --Подорвались; без параметров
| Flag --Поставлен флажок
Всё просто! Минимум вариантов, минимум вложенных параметров. И тогда Field в начале игры — это просто пустой Map:
createField = Data.Map.empty
То есть теперь поле — это только то, что видно на экране. Но тогда нужно как-то отдельно хранить внутреннее состояние — набор мин «под» этим полем. А ведь так получается ещё проще: мины определяются просто набором клеток, на которых они стоят, и в процессе игры это значение никак не меняется:
type Mines = Set Cell --не забудем import Data.Set
Проверим, всё ли в порядке с компиляцией — поскольку в коде сплошные объявления и почти никаких определений, проблем пока нет.
В отличие от клеток, стартовый набор мин никак не может быть пустым. Поскольку все хаскельные функции чистые и детерминированные, для создания случайного набора нам придётся работать либо в монаде IO, либо таскать за собой псевдослучайный генератор, либо всю жизнь играть на одном и том же поле. С одной стороны, игру всё равно запускать в IO и дополнительное ограничение особо не мешает; с другой — более обобщённое и чистое решение тоже не повредит. Как лучше — вопрос открытый, так что пусть будет второй вариант. Итак, нам понадобится какой-то случайный генератор (в хаскеле они принадлежат классу типов RandomGen) и координата первой нажатой клетки, чтобы случайно не подрываться на первом ходу:
createMines :: RandomGen g => g -> Cell -> Mines
Как равномерно выбрать n случайных клеток поля — отдельный вопрос. Чтобы не заморачиваться, я не нашёл ничего лучше, как перемешать все возможные клетки и взять n первых. Ну и убрать оттуда стартовую:
createMines g fst = Data.Set.fromList $ take mineCount $ shuffle g $
[(i, j) | i <- [0 .. fieldWidth - 1]
, j <- [0 .. fieldHeight - 1]
, (i, j) /= fst]
Функции shuffle, перемешивающей список, в стандартной поставке компилятора нет. Что ж, нам поможет всеведущий джинн по имени Хугль. Спросим, что он может рассказать по ключевому слову shuffle.
Ага, есть целый небольшой пакетик random-shuffle, решающий конкретно эту задачу. Ставим его:
$> cabal install random-shuffle
и находим функцию, которая в первом приближении делает ровно то, что нужно:
shuffle' :: RandomGen gen => [a] -> Int -> gen -> [a]
У неё даже сигнатура похожа на нашу. Правда, она принимает ещё какой-то лишний аргумент, который при ближайшем рассмотрении оказывается длиной сортируемого списка. Зачем он нужен, я так и не понял (возможно, чтобы не считать length ещё раз, если она известна заранее), так что сделаем обёрточку:
shuffle g l = shuffle' l (fieldWidth * fieldHeight - 1) g
-- import System.Random.Shuffle (shuffle'), чтобы не конфликтовать именами
Теперь это даже можно скомпилировать, запустить и попробовать в REPL:
ghci> do {g <- getStdGen; return $ createMines g (0, 0)}
fromList [(0,1),(1,10),(2,5),(2,7),(2,12),(2,14),(3,8),(4,10),(6,7),(6,10),(7,11),(7,12),(8,4),(8,12),(9,7),(9,12),(10,14),(12,0),(12,5),(13,8)]
Отлично. Теперь можно вернуться к main и заняться запуском игрового процесса. Как показать окошко и отрисовать на нём что-нибудь, сильно зависит от используемого графического фреймворка. Я буду использовать Gloss, предназначенный для создания приложений с простой двумерной векторной графикой.
В библиотеке не так давно слегка поменялись имена некоторых стандартных функций, поэтому, если код у вас не собирается, удостоверьтесь в наличии свежей версии.
Наводим глянец
Вместо классических императивных функций вида «отрисуй то, затем отрисуй сё», которые можно видеть, например, в хаскельных биндингах к OpenGL, SDL и другим популярным графическим API, Gloss использует фирменную ФП-шную идею комбинаторов и композиции функций. То, что Gloss может отрисовать на экране — это Picture, некая абстрактная картинка. У него есть элементарные функции для создания картинок из простых графических примитивов (вроде линий, прямоугольников и растровых картинок), функции для перемещения и масштабирования картинок, объединения нескольких картинок в одну, и т. д., и т. п. В результате получается декларативное построение сложных сцен из более простых (опять «сверху вниз»): отрисовываемая в окне сцена — это картинка, которая состоит из картинок, которые состоят из преобразованных картинок… и так сэмь раз, пока в самом низу не окажутся спрятанные под капотом примитивы OpenGL. Ещё один важный фактор — в Gloss есть маленькая, но очень гордая подсистема для обработки событий пользовательского ввода (что отличает её от концептуально схожей, но чисто статичной Diagrams), что нам очень пригодится. Простые примеры вы можете посмотреть на официальном сайте библиотеки, а я в статье буду сразу использовать всё необходимое.
Для запуска интерактивных сцен (которые, помимо отрисовки, способны ещё и изменяться во времени и реагировать на внешние события) в Gloss есть функция play, обладающая на редкость громоздким 7-арным типом:
play :: Display -> Color -> Int -> world -> (world -> Picture) -> (Event -> world -> world) -> (Float -> world -> world) -> IO ()
Первые два аргумента тривиальны (параметры окна или полноэкранного режима, и цвет фона по умолчанию). А дальше начинаются интересности.
Разберём немного принцип работы этого самого play. Есть сцена, или некий внутренний «мир», состояние которого хранится в значении типа world — это не тип, а переменная типа, поэтому play полиморфна и может работать с любым состоянием, которое мы введём. Для работы с состоянием применяются три callback-функции.
- Когда движку нужно его отрисовать, он вызывает пятый параметр — функцию типа
world -> Picture, которая превращает «состояние мира» в картинку (назовём её отрисовщиком, илиrenderer). - Некоторое число раз в секунду (задаваемое третьим параметром) мир может изменяться, для чего есть седьмой аргумент, принимающий текущее время, старое состояние и возвращающий новое (назовём её обновителем, или
updater). - И, наконец, для обработки внешних событий от пользователя есть шестой аргумент, аналогичным образом принимающий событие, старое состояние и возвращающий новое состояние (её будем звать обработчиком, или
handler).
Обратите внимание — все функции чистые, кроме самой play. Кстати, похожий подход с чистыми функциями, обрабатывающими разные события, использовался в самом хаскеле в домонадную эпоху (почитать можно здесь).
Примечание: если, помимо стандартных событий, нужно реагировать с внешним миром (например, грузить файлы), то есть похожая функция, которая во всех своих обработчиках работает с состоянием мира в монаде IO.
Попробуем описать состояние мира. В нём должны храниться, как минимум, поле клеток и набор мин. Однако, набор мин неизвестен, пока игрок не сделал первый ход, поэтому надо как-то сделать отложенную инициализацию. Самый прямолинейный (и далеко не самый лучший) вариант – это добавить в состояние соответствующий флаг и генератор. Чтобы избежать использования «одноразовых» полей, я придумал небольшой хак:
data GameState = GS
{ field :: Field
, mines :: Either StdGen Mines
}
Тогда, если mines у нас Left, это означает первый ход, и из него мы сгенерируем набор, который станет Right-ом.
Теперь можно запустить игру:
import Graphics.Gloss.Interface.Pure.Game
<...>
startGame :: StdGen -> IO ()
startGame gen = play (InWindow windowSize (240, 160)) (greyN 0.25) 30 (initState gen) renderer handler updater
windowSize = both (* (round cellSize)) fieldSize
cellSize = 24
initState gen = GS createField (Left gen)
both f (a, b) = (f a, f b) --вспомогательная функция, которая ещё пригодится
Игра статичная, поэтому updater ничего не делает. handler пока тоже, но undefined не ставим, чтобы добиться успешного отображения окошка.
updater _ = id
handler _ = id
renderer для начала пусть отрисовывает целое поле с пустыми белыми клеточками:
renderer _ = pictures [uncurry translate (cellToScreen (x, y)) $ color white $ rectangleSolid cellSize cellSize
| x <- [0 .. fieldWidth - 1], y <- [0 .. fieldHeight - 1]]
cellToScreen = both ((* cellSize) . fromIntegral)
Запустим.
Упс – поле уехало в угол. Оказывается, Gloss в качестве системы координат по умолчанию берёт принятую в математике, где точка (0,0) – центр экрана, а ось oy направлена вверх. Тогда как в 2D-графике обычно (0,0) – это левый верхний угол, а oy идёт вниз. По той же причине и все примитивы рисуются относительно центра, а не угла. Разберёмся с этим чуть позже, а сперва попробуем сделать обработку каких-нибудь событий.
Интерактив
Событие в Gloss — это алгебраический тип, конструкторы которого – варианты событий: нажатие всевозможных кнопок (EventKey), перемещение курсора (EventMotion), изменение размера окна (EventResize), каждое из которых несёт в себе ещё какие-то специфические параметры. Благодаря паттерн-матчингу и частичным определениям функции в виде клозов можно организовывать достаточно хитрые обработчики различных частных случаев, и выглядит это почти как методы вида OnClick(MouseEventArgs e) в каком-нибудь WinForms.
Нас в первую очередь интересует реакция на кнопки мыши. Когда поле пустое, мы хотели сгенерировать набор мин:
handler (EventKey (MouseButton LeftButton) Down _ mouse) gs@GS
{ mines = Left gen
} = gs { mines = Right $ createMines gen cell } where
cell = screenToCell mouse
screenToCell = both (round . (/ cellSize)) --тут обе координаты делятся на размер клетки и округляются, тем самым получается её индекс
Запустим. При малейшем движении игра падает с incomplete patterns. Действительно — handler обрабатывает только один частный случай, поэтому нужно оставить самый общий клоз для обработки событий, которые нас не интересуют:
handler _ gs = gs
Теперь игра стабильно работает, но внешне решительно ничего не изменилось, ведь мины не видны. Добавим вскрытие клетки. Вообще, в оригинальном «Сапёре» автоматически вскрывается целая область из клеток с нулями, но для начала (помним — keep it simple!) сделаем обработку лишь одной клетки:
handler (EventKey (MouseButton LeftButton) Down _ mouse) gs@GS
{ field = field
, mines = Right mines
} = gs { field = Data.Map.insert cell opened field } where
cell@(cx, cy) = screenToCell mouse
opened = if cell `Data.Set.member` mines --проверяем, попались ли на мину
then Mine
else Opened neighbours
--Вычисляем число соседей: это все клетки, расстояние до которых от нажатой по обеим осям не более 1
neighbours = length [ () | i <- [-1 .. 1], j <- [-1 .. 1]
, (i, j) /= (0, 0)
, (cx + i, cy + j) `Data.Set.member` mines]
Теперь игру можно запустить и пощёлкать, но клетки по-прежнему никак не отрисовываются. Исправим эту оплошность. Для начала на месте вскрытых клеток будем рисовать цифру (или @, если там бомба):
renderer GS { field = field } = pictures $ [uncurry translate (cellToScreen (x, y)) $ drawCell x y | x <- [0 .. fieldWidth - 1], y <- [0 .. fieldHeight - 1]] where
drawCell x y = case Data.Map.lookup (x, y) field of
Nothing -> color white $ rectangleSolid cellSize cellSize --клетка пустая
Just Mine -> pictures [ color red $ rectangleSolid cellSize cellSize
, scale 0.15 0.15 $ color black $ text "@"
]
Just (Opened n) -> pictures [ color green $ rectangleSolid cellSize cellSize
, scale 0.15 0.15 $ color black $ text $ show n
]
Напомню, что комбинатор pictures объединяет список из нескольких «картинок» в одну, при этом отрисовка идёт слева направо, то есть элементы в хвосте списка будут рисоваться поверх тех, что идут вначале.
Тут ещё стоит отметить, что стандартный векторный шрифт в Gloss откровенно вырвиглазный и слишком большой (поэтому приходится его уменьшать при помощи scale), поэтому при первой возможности следует заменить его на растровые картинки. Но пока это отложим и сперва сделаем остаток игровой логики, чтобы увидеть, наконец, эти изменённые состояния клеток поля. Сначала установку флажков – добавим клоз с обработкой правой кнопки мышки:
handler (EventKey (MouseButton RightButton) Down _ mouse) gs@GS
{ field = field
} = case Data.Map.lookup coord field of
Nothing -> gs { field = Data.Map.insert coord Flag field }
Just Flag -> gs { field = Data.Map.delete coord field }
_ -> gs
where coord = screenToCell mouse
и, соответственно, их отрисовку:
drawCell x y = case M.lookup (x, y) field of
<...>
Just Flag -> pictures [ color yellow $ rectangleSolid cellSize cellSize
, scale 0.15 0.15 $ color black $ text "?"
]
Дублекод с созданием клеток стоило бы порефакторить, но это я оставлю на факультатив.
Клетки вскрываются, но метки тоже смещены, передвинем их вспомогательной функцией, которая будет делать текстовую метку:
label = translate (-5) (-5) . scale 0.15 0.15 . color black . text
Кроме того, пропала сетка — ведь у заполненных геометрических фигур рамки нет. Нужно добавить её отрисовку отдельно, причём поверх клеток, иначе они будут накладываться друг на друга.
renderer GS { field = field } = pictures $ cells ++ grid where
grid = [uncurry translate (cellToScreen (x, y)) $ color black $ rectangleWire cellSize cellSize | x <- [0 .. fieldWidth - 1], y <- [0 .. fieldHeight - 1]]
Проекции координат
Теперь уже стоит поправить координаты. Конечно, можно вручную их переводить из одной системы в другую (и обратно – ведь координаты мышки, получаемые в событиях, привязаны не к окну, а к абсолютной системе координат сцены, что с непривычки может смутить), но это утомительно. К счастью, Gloss включает механизм, делающий это за нас – проекции (viewports). Проекция – это преобразование, согласно которому окно отображается на плоскость сцены, и его можно не только перемещать, но и масштабировать и даже поворачивать. Чтобы поле целиком умещалось на экран, наша проекция должна быть просто сдвинута на половину поля плюс половину клетки (поскольку клетка тоже рисуется из центра, а не из угла):
viewPort = ViewPort (both (negate . (/ 2) . (subtract cellSize)) $ cellToScreen fieldSize) 0 1
--последние два параметра – это поворот и коэффициент масштабирования
При помощи applyViewPortToPicture можно применить проекцию к любой картинке, преобразовав её нужным образом. А для обратного преобразования (из системы координат картинки в систему координат проекции), которое нужно для обработки позиции курсора, есть invertViewPort. Подправим соответствующим образом наш код:
screenToCell = both (round . (/ cellSize)) . invertViewPort viewPort
renderer GS { field = field } = applyViewPortToPicture viewPort <...>
Вуаля! Теперь окно отрисовывается как надо, и в нём можно даже поиграть. Кроме того, в совокупности с проекциями Gloss предоставляет очень простые средства для реализации прокрутки и масштабирования экрана, что позволяет сделать, например, поле 1000х1000 клеток и перемещаться по нему, как в картах.
Однако проиграть по-прежнему нельзя — подрыв на мине ни на что не влияет, и поэтому надо добавить флажок в состояние игры, а в обработчике событий проверять:
data GameState = GS
{ field :: Field
, mines :: Either StdGen Mines
, gameOver :: Bool --На сладкое — сделать enum-ADT с состояниями "в процессе", "проиграли", "выиграли"
}
<...>
handler (EventKey (MouseButton LeftButton) Down _ mouse) gs@GS
{ field = field
, mines = Right mines
, gameOver = False
} = gs
{ field = Data.Map.insert cell opened field
, gameOver = exploded
} where
cell@(cx, cy) = screenToCell mouse
(opened, exploded) =
if cell `Data.Set.member` mines --проверяем, попались ли на мину
then (Mine, True)
else (Opened neighbours, False)
Теперь игра после неосторожного шага не даст сделать ещё один.
Чуточку удобства
Осталось самое интересное – рекурсивное вскрытие целой области из пустых клеток. Сделаем это своеобразным поиском в глубину — симулируем тыканье в соседние клетки, если мин в них точно нет:
handler (EventKey (MouseButton LeftButton) Down _ mouse) gs@GS
{ field = field
, mines = Right mines
, gameOver = False
} = gs
{ field = newField
, gameOver = exploded
} where
newField = click cell field
exploded = case Data.Map.lookup cell newField of --Проигрыш, если последняя вскрытая клетка - мина
Just Mine -> True
_ -> False
cell@(cx, cy) = screenToCell mouse
click :: Cell -> Field -> Field
click c@(cx, cy) f
| c `Data.Map.member` f = f --повторно клетку не обрабатываем
| c `Data.Set.member` mines = put Mine --попались на мину
| otherwise = let nf = put (Opened neighbours) in
if neighbours == 0
then Prelude.foldr click nf neighbourCells --Обойдём соседей
else nf
where
put state = Data.Map.insert c state f
--Вычисляем число соседей: это все клетки, расстояние до которых от нажатой по каждой из осей не более 1
neighbourCells = [ (cx + i, cy + j) | i <- [-1 .. 1], j <- [-1 .. 1] ]
neighbours = length $ Prelude.filter (`Data.Set.member` mines) neighbourCells
Запускаем, тыкаем, и… игра виснет. Как так, ведь она скомпилилась! Увы, даже хаскель не в силах застраховать от всех рантаймовых ошибок. Конкретно такое зависание часто случается, когда программа входит в бесконечный цикл или рекурсию. И точно — мы же ведь никак не проверяем выход за границы поля, поэтому обход соседей будет пытаться обходить всю бесконечную плоскость. Добавим ограничения:
neighbourCells = [ (i, j) | i <- [cx - 1 .. cx + 1], j <- [cy - 1 .. cy + 1]
, 0 <= i && i < fieldWidth
, 0 <= j && j < fieldHeight
] --Жаль, нельзя написать 0 <= i < fieldWidth
Теперь, наконец, можно насладиться результатом:
Эпилог
Конечно, простор для улучшений ещё велик — добавить волшебную комбинацию двух кнопок мыши (для раскрытия соседей клетки, у которой уже есть все флажки), прикрутить нормальную графику (тот же Gloss умеет грузить битмапы), сделать настраиваемыми размер поля и число мин (пробрасывая при помощи монады Reader), и т. д., и т. п. Тем не менее, надеюсь, я смог показать, что бояться хаскеля вовсе не нужно, и запрототипировать на нём в сотню строк что-то несложное и интерактивное — вполне подъёмная задача.
Полный код выложен на Pastebin.
Спасибо за внимание!
Автор: Yuuri
