В последнее время я работал над второстепенным проектом, который стал забавным упражнением как в теории графов, так и в генетических алгоритмах. Это история того опыта.
Начало
Недавно я взял перерыв в работе, чтобы восстановить свое волнение и чувство удивления о мире. Во время этого перерыва я закончил создание настольной игры. В этой игре игроки перемещаются по лабиринту, построенному из кусочков лабиринта на шестиугольных плитках, так что, когда эти плитки перемешиваются и соединяются случайным образом, они строят полный лабиринт на такой сетке:
Я совсем не был уверен, что смогу построить очень хороший лабиринт путем случайного размещения плиток. Тем не менее, я решил, что могу взорвать его и посмотреть, что произошло, и я это сделал.
Попытка №1: делать самое простое
Лабиринты - это почти идеальное приложение теории графов. граф (и здесь я всегда имею в виду неориентированный граф) - это набор вершин, соединенных ребрами. С другой стороны, лабиринт - это набор локаций, соединенных путями. Одно и то же, разные слова!
В этом случае моя первоначальная идея заключалась в том, что шестиугольные плитки были местоположениями (то есть вершинами), и каждая из шести сторон плитки была либо открыта, либо заблокирована, потенциально создавая путь к соседней плитке. Тогда вопрос заключался в том, какое из этих краев следует заблокировать. Я руководствовался двумя опасениями:
- Лабиринт должен быть разрешен. То есть должен быть (хотя бы с большой вероятностью) открытый путь от старта до финиша.
- Решение лабиринта не должно быть тривиальным. То есть, движение в любом направлении вообще не должно приводить к от начала до конца.
Ключевым моментом здесь является то, что добавление ребра в граф всегда выполняет одно из двух: оно либо соединяет два ранее не связанных компонента графа, либо создает цикл (путь от вершины обратно к самой себе без повторения ребра) посредством соединяя две ранее соединенные вершины вторым способом. Таким образом, две проблемы говорят о том, что мы хотим сделать первое, если это вообще возможно, но избегаем второго. К сожалению, поскольку наши края указывают в случайных направлениях, непонятно, как мы можем их различить!
Но, по крайней мере, мы можем попытаться получить нужное количество ребер в нашем графе. Мы хотим, чтобы граф был ацикличным (т.е. не содержал никаких циклов), но был связным. Такой граф называется деревом. Мы несколько раз воспользуемся следующим простым фактом:
Предложение: В любом ациклическом графе количество ребер всегда равно количеству вершин за вычетом количества связанных компонентов. (Доказательство: Индукцией по количеству ребер: если ребер нет, то каждая вершина является ее собственной компонентой связности. Если ребра есть, удаление любого ребра сохраняет граф ацикличным, поэтому равенство выполняется , но при повторном добавлении этого ребра добавляется одно ребро и удаляется один компонент связности, сохраняя равенство.)
Следствие. У дерева на одно ребро меньше, чем вершин. (Доказательство: все дерево представляет собой один компонент связности. Примените предложение выше.)
Итак, я подумал: У меня двадцать шестигранных плиток, потому что именно столько пустых плиток попало в коробку. Если я буду рассматривать каждую из них как вершину, тогда мне понадобится 19 связей между ними.
Есть еще одна сложность. Чтобы путь был открытым, он не должен быть заблокирован с любой стороны, а внешняя граница лабиринта всегда блокируется. Таким образом, не каждое открытое ребро плитки добавляет вершину к графу. Это легко решается небольшим изменением ракурса. Вместо подсчета количества ребер можно было подсчитать желаемую вероятность открытия ребра.
В выбранной мной конфигурации плиток было 43 внутренних границы между плитками, не считая внешней границы всего лабиринта. Поэтому я хотел примерно 19/43 (или около 43%) вероятности преимущества на каждой из этих границ. Поскольку обе плитки нуждаются в открытой стороне для создания этого края, если каждое ребро выбирается независимо, вероятность того, что плитка имеет открытый край, должна быть квадратным корнем из этого, или около 66%. Поскольку у каждой из 20 плиток по 6 краев на каждой из двух сторон, получается 240 краев, и случайные 160 из них (то есть 240 * sqrt (19/43)) должны быть открыты, а оставшиеся 80 должны быть заблокированы.
Вы можете увидеть симуляцию этого здесь. Эта простая симуляция не выбирает плитки. К сожалению, этот эксперимент не удался. если вы попробуете это несколько раз, то заметите:
- Лабиринты слишком просты. Двадцати мест в лабиринте просто недостаточно.
- Слишком часто открытые края оказываются в неправильных местах, и вы не можете пройти от начала до конца.
Не обязательно, чтобы лабиринт был ацикличным, чтобы я мог (и на практике увеличивал) вероятность открытого края для решения второй проблемы ... но это только усугубило бы первую проблему. Не существует выбора вероятности, которая решала бы обе проблемы одновременно.
Попытка №2: более интересные плитки
Честно говоря, я ожидал, что эта первая попытка не удастся. Я даже не рисовал плитки, а просто моделировал достаточно, чтобы быть уверенным, что это не сработает. Ясно, что мне нужно было больше структурировать тайлы карты.
Одна вещь, которая могла бы сделать результат выглядеть более убедительным, - это нарисовать интересные (но статические) лабиринты на каждой плитке, которые все связаны между собой и имеют выходы во всех направлениях с соответствующими вероятностями. Впрочем, это все дым и зеркала. В конечном итоге это сводится к той же системе, что и выше. При достаточно повышенной вероятности открытого края это удовлетворило бы мои требования.
Но это похоже на обман. Я хочу, чтобы высокоуровневая структура лабиринта была интересна сама по себе. И как бы я ни разбирался в плитках, предыдущий раздел показал, что в этой модели это невозможно.
Остающийся вариант состоит в том, чтобы учесть, что каждая плитка вместо того, чтобы быть одним местоположением с несколькими выходами, на самом деле содержит несколько местоположений с различными связями. Поскольку я не хочу добавлять искусственную сложность внутри плитки, они просто соединят края по желанию. Некоторые плитки теперь выглядят так:
На первый взгляд, анализ соединения лабиринта становится сложнее, потому что количество вершин в графе меняется! Три из вышеперечисленных плиток имеют два местоположения, а последний - только одно. Есть даже плитки с тремя разными путями.
Но не бойтесь: еще одна смена ракурса упрощает дело. Вместо рассмотрения графа, в котором каждая плитка или путь является вершиной, мы рассмотрим двойственный граф, где каждая граница является вершиной, например:
Теперь у нас снова есть фиксированное количество вершин (77 из них) и плитки, которые определяют ребра между этими вершинами. Таким образом, для соединения этого графа требуется не менее 76 ребер, распределенных по 20 плиткам, или около 3,8 ребер на плитку. Может быть, даже несколько больше, так как полученный граф обязательно будет содержать несколько циклов, так что давайте назовем его 4 на плитку.
Вот ошибка, которую я совершил, когда впервые рассмотрел этот график. Последняя плитка в наборе из четырех приведенных выше примеров соединяет вместе пять разных вершин, так что можно проходить напрямую между любой парой из них. Наивно, вы можете подумать, что это соответствует 10 ребрам: по одному на каждую пару соединенных вершин. Это соответствовало моей интуиции, что соединение пяти из шести сторон должно быть намного выше среднего, что касается соединений на плитке. Я подумал об этом и разработал полный набор плиток, исходя из этого предположения, прежде чем понял, что полученные лабиринты были недостаточно соединены.
Вот в чем проблема: эти 10 ребер будут содержать довольно большое количество циклов. Требование наличия минимум 76 ребер предназначалось для ациклического графа. Мы неизбежно получим несколько циклов между плитками, но нам следует по крайней мере избегать подсчета циклов внутри плитки. Для соединения этих пяти вершин с ациклическим графом требуется четыре ребра, а не десять. Для нас не имеет значения, какие это четыре ребра; они существуют только теоретически и не меняют способ рисования плитки. Но важно считать их всего четыре.
Теперь 76 граней кажутся непомерным количеством граней! Если мы должны усреднить, соединяя почти пять из шести сторон каждой плитки, кажется, что можно будет перемещаться почти куда угодно. Но, если подумать, это не безосновательно. Почти половина этих вершин находится на внешней границе лабиринта! Все, что требуется, - это один заблокированный путь в неудачном месте, чтобы изолировать одну из этих вершин. Даже шанс один из шести изолирует около шести из них. Те шесть ребер, которые не используются для соединения графа, затем пойдут на добавление лишних путей в оставшиеся части!
Тот факт, что вершины на ребрах графа могут быть изолированы, является проблемой. Я решил творчески смягчить эту проблему, добавив некоторые из этих 76 граней не на плитку, а на доску. Что-то вроде этого:
С этими 14 ребрами на внешней стороне лабиринта (помните, что соединение трех вершин считается только двумя ребрами), нам нужно только 64 на внутренней стороне, что чуть больше 3 на плитку. Более того, вероятность того, что плитки на краю будут изолированы в лабиринте, значительно ниже.
На этом этапе я нарисовал набор плиток, немного повторил их, выкладывая лабиринты и ощущая, когда они были слишком легкими, слишком сложными и т. Д. В итоге я получил механику, которая меня больше всего устраивала. Вот настоящая игровая доска со случайным расположением лабиринта. Макет немного отличается от приведенных выше примеров из-за необходимости работать с другими элементами игрового процесса, но идея по сути та же.
Если вы присмотритесь, вы увидите, что полученный лабиринт не полностью связан: есть две короткие отсоединенные секции в нижнем левом и нижнем правом плитках. Он определенно содержит циклы, потому что отключенные компоненты освобождают ребра, вызывающие циклы, и потому, что я включил больше, чем минимальное количество ребер, необходимое для соединения лабиринта в любом случае.
Но он нетривиальный, визуально интересный и в целом в довольно хорошем состоянии. Это кажется довольно простым, когда все расположено таким образом, но в реальной игре игроки открывают плитки только тогда, когда они достигают их, и опыт определенно очень похож на навигацию по лабиринту, где вы не уверены, куда приведет след, пока вы следуй за ним. В общем, успех.
Попытка №3: Использование генетических алгоритмов
Я не был недоволен этой попыткой, но подозревал, что смогу добиться большего с помощью компьютерного моделирования. Я немного покопался и нашел библиотеку Haskell под названием moo, которая предоставляет строительные блоки для генетических алгоритмов.
Идея генетических алгоритмов проста: вы начинаете с начальной совокупности ответов, которые иногда генерируются случайным образом, и оцениваете их в соответствии с функцией приспособленности. Вы берете лучшие ответы из этого набора, а затем расширяете его, генерируя случайные мутации и скрещивания этой популяции. Это дает новую популяцию, которую оценивают, мутируют, скрещивают и т. Д.
Начнем с импорта:
import Algebra.Graph.AdjacencyMap.Algorithm (scc) import Algebra.Graph.ToGraph import qualified Algebra.Graph.Undirected as U import Control.Monad import Data.Containers.ListUtils import Data.Function (on) import Data.List import Moo.GeneticAlgorithm.Binary import System.IO.Unsafe import System.Random import System.Random.Shuffle
И некоторые виды:
data Direction = N | NE | SE | S | SW | NW deriving (Show, Eq, Ord, Enum) type Trail = [Direction] data Tile = Tile [Trail] [Trail] deriving (Show, Eq)
Direction - одно из шести сторон света в шестнадцатеричном мире, расположенное по часовой стрелке. Trail - это единственный след от одного из дизайнов плитки. Он представлен в виде списка направлений, по которым можно выйти из плитки по этой тропе. Все, кроме визуального оформления. И, наконец, у Tile есть верхняя и нижняя стороны, и у каждого из них есть некоторый список Trail.
Библиотека moo требует некоторого способа кодирования или декодирования значений в битовые строки, которые играют роль ДНК в генетическом алгоритме. Платформа будет вносить несколько произвольные изменения в эти битовые строки, и ожидается, что вы сможете читать эти измененные строки и получать разумные значения. Фактически ожидается, что небольшие изменения в битовой строке приведут к аналогичным небольшим изменениям в закодированном значении.
Вот что я сделал. Каждая сторона тайла кодируется шестью числами, каждое из которых идентифицирует след, связанный с направлением тайла. Если на тайле нет следа, уходящего в каком-то направлении, тогда это направление будет иметь уникальный номер следа, так что по сути это становится тупиком. Предполагая, что нам не нужен трейл только с одним не ветвящимся путем (а мы этого не делаем!), Достаточно оставить место для четырех номеров трейлов, что требует только два бита в строке. Тогда стороне нужно 12 бит, двустороннему тайлу - 24 бита, а полному набору из 20 тайлов - 480 бит.
Вот код для кодирования стека плиток таким образом, начиная с более раннего представления:
encodeTile :: Tile -> [Bool]
encodeTile (Tile a b) =
concat
[ encodeBinary (0 :: Int, 3) (trailNum side dir)
| side <- [a, b],
dir <- [N .. NW]
]
where
trailNum trails d =
case [i | (t, i) <- zip trails [0 .. 3], d `elem` t] of
[i] -> i
_ -> error "Duplicate or missing dir on tile"
encodeTiles :: [Tile] -> [Bool]
encodeTiles = concat . map encodeTile
Функция encodeBinary является частью moo и просто кодирует двоичное число в список bools с заданным диапазоном. Остальная часть просто сопоставляет следы с номерами следов и объединяет их кодировки.
Декодирование немного сложнее, в основном потому, что мы хотим сделать некоторую нормализацию, которая пригодится в будущем. Сначала вспомогательная функция:
clockwise :: Direction -> Direction clockwise N = NE clockwise NE = SE clockwise SE = S clockwise S = SW clockwise SW = NW clockwise NW = N
Теперь расшифровка:
decodeTile :: [Bool] -> Tile
decodeTile bs = Tile (postproc a) (postproc b)
where
trailNums =
map
(decodeBinary (0 :: Int, 3))
(splitEvery trailSize bs)
trail nums n = [d | (d, i) <- zip [N .. NW] nums, i == n]
a = map (trail (take 6 trailNums)) [0 .. 3]
b = map (trail (drop 6 trailNums)) [0 .. 3]
postproc :: [Trail] -> [Trail]
postproc = normalize . filter (not . null)
where
normalize trails =
minimum
[ simplify ts
| ts <- take 6 (iterate (map (map clockwise)) trails)
]
simplify = sort . map sort
decodeTiles :: [Bool] -> [Tile]
decodeTiles = map decodeTile . splitEvery tileSize
trailSize :: Int
trailSize = bitsNeeded (0 :: Int, 3)
tileSize :: Int
tileSize = 12 * trailSize
Опять же, некоторые из функций (например, decodeBinary, bitsNeeded и splitEvery) являются служебными функциями, предоставляемыми moo. Функция postproc применяет небольшую нормализацию к дизайну плитки. Так как переупорядочивание выходов следа, следов и вращение тайла не меняют его значения, мы просто делаем последовательный выбор здесь, так что равные тайлы будут сравниваться как равные.
Следующее, что нам нужно, это способ забить набор плиток, чтобы можно было выбрать лучшее. С самого начала мы знаем, что подсчет очков будет включать перемешивание плиток, что на самом деле включает три вида рандомизации:
- Перемещение плиток в разные места на доске.
- Вращение плиток в произвольном направлении.
- Переверните плитки так, чтобы обе стороны были видны с одинаковой вероятностью.
Вот этот код:
rotateTile :: Int -> Tile -> Tile
rotateTile n
| n > 0 = rotateTile (n - 1) . rot
| n < 0 = rotateTile (n + 6)
| otherwise = id
where
rot (Tile top bottom) =
Tile (map (map clockwise) top) bottom
flipTile :: Tile -> Tile
flipTile (Tile top bottom) = Tile bottom top
randomizeTile :: RandomGen g => g -> Tile -> (g, Tile)
randomizeTile g t
| flipped = (g3, rotateTile rots (flipTile t))
| otherwise = (g3, rotateTile rots t)
where
(flipped, g2) = random g
(rots, g3) = randomR (0, 5) g2
shuffleTiles :: RandomGen g => g -> [Tile] -> (g, [Tile])
shuffleTiles g tiles = (g3, result)
where
(g1, g2) = split g
shuffledTiles = shuffle' tiles (length tiles) g1
(g3, result) = mapAccumL randomizeTile g2 shuffledTiles
Чтобы оценивать случайное расположение плиток, полезно иметь библиотеку графиков. В данном случае я выбрал Алгу для задачи, главным образом потому, что она позволяет создавать графы с произвольным типом узлов (которые я хочу здесь), это, кажется, вызывает некоторое волнение, и у меня не было возможности поиграть с это еще. Alga представляет неориентированные графы с другим типом Graph (раздражающе называемым одним и тем же) в подпакете, отсюда и квалифицированный импорт.
Чтобы поделиться реальным кодом, я перехожу на настоящую игровую доску, как показано на фотографии выше. Есть определенные фиксированные места, о которых я забочусь, потому что игрокам нужно будет добраться до них в игре: хижина ведьмы, колодец желаний, логово монстра, фруктовый сад, родник и выход. Они получают свои собственные именованные узлы. Плитки имеют названия от «1» до «20». И, наконец, поскольку каждая плитка может иметь несколько трейлов, узел состоит из имени и номера трейла (который всегда равен 0 для встроенных местоположений). Вот код для построения графика из списка плиток:
topSide :: Tile -> [[Direction]]
topSide (Tile top _) = top
tileGraph :: [Tile] -> U.Graph (String, Int)
tileGraph tiles =
U.edges $
[ ((show a, trailNum a dira), (show b, trailNum b dirb))
| (a, dira, b, dirb) <- connections
]
++ [ (("Well", 0), (show c, trailNum c dir))
| (c, dir) <-
[ (6, SE),
(7, NE),
(10, S),
(11, N),
(14, SW),
(15, NW)
]
]
++ [ (("Hut", 0), (show c, trailNum c dir))
| (c, dir) <- [(1, NE), (5, N), (9, NW)]
]
++ [ (("Spring", 0), (show c, trailNum c dir))
| (c, dir) <- [(4, S), (8, SW)]
]
++ [ (("Orchard", 0), (show c, trailNum c dir))
| (c, dir) <- [(13, NE), (17, N)]
]
++ [ (("Lair", 0), (show c, trailNum c dir))
| (c, dir) <- [(12, SE), (16, S), (20, SW)]
]
++ [ (("Exit", 0), (show c, trailNum c dir))
| (c, dir) <- [(19, SE), (20, NE), (20, SE)]
]
where
trailNum n dir =
head
[ i
| (exits, i) <- zip (topSide (tiles !! (n - 1))) [0 ..],
dir `elem` exits
]
connections =
[ (1, S, 2, N),
(1, SW, 2, NW),
(1, SE, 5, NW),
(2, NE, 5, SW),
(2, SE, 6, NW),
(2, S, 3, N),
(2, SW, 3, NW),
(3, NE, 6, SW),
(3, SE, 7, NW),
(3, S, 4, N),
(3, SW, 4, NW),
(4, NE, 7, SW),
(4, SE, 8, NW),
(5, NE, 9, SW),
(5, SE, 10, NW),
(5, S, 6, N),
(6, NE, 10, SW),
(6, S, 7, N),
(7, SE, 11, NW),
(7, S, 8, N),
(8, NE, 11, SW),
(8, SE, 12, NW),
(8, S, 12, SW),
(9, NE, 13, N),
(9, SE, 13, NW),
(9, S, 10, N),
(10, NE, 13, SW),
(10, SE, 14, NW),
(11, NE, 15, SW),
(11, SE, 16, NW),
(11, S, 12, N),
(12, NE, 16, SW),
(13, SE, 17, NW),
(13, S, 14, N),
(14, NE, 17, SW),
(14, SE, 18, NW),
(14, S, 15, N),
(15, NE, 18, SW),
(15, SE, 19, NW),
(15, S, 16, N),
(16, NE, 19, SW),
(16, SE, 20, NW),
(17, SE, 18, NE),
(17, S, 18, N),
(18, SE, 19, NE),
(18, S, 19, N),
(19, S, 20, N)
]
Утомительно, но работает! Теперь я могу оценить один из этих графиков. Есть два типа вещей, которые меня волнуют: вероятность того, что я смогу попасть между любыми двумя встроенными местоположениями, и количество «лишних» ребер, которые создают множественные пути.
hasPath :: String -> String -> U.Graph (String, Int) -> Bool
hasPath a b g =
(b, 0) `elem` reachable (a, 0 :: Int) (U.fromUndirected g)
extraEdges :: Ord a => U.Graph a -> Int
extraEdges g = edges - (vertices - components)
where
vertices = U.vertexCount g
edges = U.edgeCount g
components =
vertexCount (scc (toAdjacencyMap (U.fromUndirected g)))
scoreGraph :: U.Graph (String, Int) -> [Double]
scoreGraph g =
[ -0.1 * fromIntegral (extraEdges g),
if hasPath "Hut" "Well" g then 1.0 else 0.0,
if hasPath "Hut" "Spring" g then 1.0 else 0.0,
if hasPath "Hut" "Lair" g then 1.0 else 0.0,
if hasPath "Hut" "Orchard" g then 1.0 else 0.0,
if hasPath "Hut" "Exit" g then 1.0 else 0.0,
if hasPath "Well" "Spring" g then 1.0 else 0.0,
if hasPath "Well" "Lair" g then 1.0 else 0.0,
if hasPath "Well" "Orchard" g then 1.0 else 0.0,
if hasPath "Well" "Exit" g then 1.0 else 0.0,
if hasPath "Spring" "Lair" g then 1.0 else 0.0,
if hasPath "Spring" "Orchard" g then 1.0 else 0.0,
if hasPath "Spring" "Exit" g then 1.0 else 0.0,
if hasPath "Lair" "Orchard" g then 1.0 else 0.0,
if hasPath "Lair" "Exit" g then 1.0 else 0.0,
if hasPath "Orchard" "Exit" g then 1.0 else 0.0
]
Результатом подсчета очков является список индивидуальных оценок, которые будут суммироваться для определения общей пригодности. Я добавил небольшой отрицательный вес к дополнительным краям, чтобы выразить тот факт, что они плохие, но гораздо меньше, чем невозможность добраться до важного игрового места. (Однако недостижимость не фатальна, поскольку в игре также есть механизмы, с помощью которых лабиринт со временем меняется… это мой запасной план.)
Теперь мне просто нужно подсчитать сами плитки, сгенерировав кучу случайных графиков игровых полей и усреднив оценки для этих графиков. Однако когда я это сделал, я обнаружил, что были и другие проблемы с оптимизированными плитками:
- Алгоритм снова и снова использовал одни и те же конструкции, делая игру менее случайной. Чтобы исправить это, я добавил небольшую стоимость, связанную с суммой квадратов числа каждого уникального дизайна плитки. Вот почему было удобно нормализовать плитки, чтобы я мог найти дубликаты. Некоторые дубликаты - это нормально, но к тому времени, когда мы получим четыре или пять одинаковых дизайнов, добавление дополнительных дубликатов станет очень дорогостоящим.
- Алгоритм сгенерировал множество тайлов, которым нужны мосты. Подобно соли, мосты делают карту более интересной в небольших количествах, таких как пять мостов на фотографии выше, всего из 20 плиток. Но я получал наборы плиток, для которых требовались перемычки почти на каждой плитке, а иногда даже их стопки! Чтобы исправить это, я добавил небольшую стоимость за каждый мост в окончательном наборе плиток.
- Плитки включали плитку со всеми шестью направлениями, соединенными друг с другом. По эстетическим соображениям я хотел, чтобы колодец желаний был единственным местом на карте с таким уровнем связи. Поэтому я добавил большую отрицательную стоимость, связанную с использованием этого конкретного дизайна плитки.
Вот получившийся код.
needsBridge :: [Trail] -> Bool
needsBridge trails =
or [conflicts a b | a <- trails, b <- trails, a /= b]
where
conflicts t1 t2 =
or [d > minimum t1 && d < maximum t1 | d <- t2]
&& or [d > minimum t2 && d < maximum t2 | d <- t1]
numBridges :: [Tile] -> Int
numBridges tiles =
length
[ () | Tile a _ <- tiles ++ map flipTile tiles, needsBridge a
]
dupScore :: [Tile] -> Int
dupScore tiles =
sum (map ((^ 2) . length) (group (sort sides)))
where
sides = map topSide tiles ++ map (topSide . flipTile) tiles
numFullyConnected :: [Tile] -> Int
numFullyConnected tiles =
length [() | Tile a b <- tiles, length a == 1 || length b == 1]
scoreTiles :: RandomGen g => g -> Int -> [Tile] -> [Double]
scoreTiles g n tiles =
[ -0.05 * fromIntegral (numBridges tiles),
-0.02 * fromIntegral (dupScore tiles),
-1 * fromIntegral (numFullyConnected tiles)
]
++ map (/ fromIntegral n) graphScores
where
(graphScores, _) = foldl' next (repeat 0, g) (replicate n tiles)
next (soFar, g1) tiles =
let (g2, shuffled) = shuffleTiles g1 tiles
in (zipWith (+) soFar (scoreGraph (tileGraph shuffled)), g2)
Вот и все. Отсюда я просто прошу библиотеку moo запустить оптимизацию. Я был слишком ленив, чтобы придумать, как передать генерацию случайных чисел через moo, поэтому я обманул там unsafePerformIO. Я понимаю, что это означает, что меня выгнали из сообщества Haskell, но я рискну, что никто не дочитает до этого места.
Вот остальная часть шаблона. Большая часть этого скопирована без понимания из примеров, распространяемых с помощью moo. Возможно, есть настройка гиперпараметров, которая улучшит ситуацию, но я доволен тем, что у меня есть!
main :: IO ()
main = do
void $ runIO initialize $
loopIO
[DoEvery 10 logStats, TimeLimit (12 * 3600)]
(Generations maxBound)
nextGen
initialize =
return (replicate popsize (encodeTiles originalTiles))
logStats n pop = do
let best =
decodeTiles
$ head
$ map takeGenome
$ bestFirst Maximizing pop
putStrLn $ show n ++ ":"
mapM_ print best
g <- newStdGen
print $ scoreTiles g 500 best
nextGen =
nextGeneration
Maximizing
objective
select
elitesize
(onePointCrossover 0.5)
(pointMutate 0.5)
select = tournamentSelect Maximizing 2 (popsize - elitesize)
popsize = 20
elitesize = 5
objective :: Genome Bool -> Double
objective gen = unsafePerformIO $ do
g <- newStdGen
return $ sum $ scoreTiles g 500 $ decodeTiles gen
Окончательный результат
Используя moo, я смог сохранить или улучшить все компоненты оценки.
Для плиток, которые я нарисовал в попытке №2:
- Потребовалось 13 мостов через 40 мозаичных конструкций.
- Оценка дублирования (сумма квадратов подсчета каждого уникального дизайна) составила 106, что указывает на несколько дизайнов, которые были дублированы четыре и пять раз.
- В среднем было 9,1 дополнительных ребра, создающих циклы в лабиринте.
- Вероятность пути к ключевым точкам составила около 93%.
Для недавно оптимизированных плиток:
- Потребовалось всего 11 мостов, что позволило сэкономить два моста по сравнению с первоначальной конструкцией.
- Оценка дубликата составила 72, что указывало на гораздо меньшее количество копий одного и того же дизайна и никогда не более трех копий дизайна.
- В лабиринте было в среднем 8,4 дополнительных ребра, создающих циклы, что почти на один меньше, чем в оригинале.
- Вероятность пути к ключевым точкам составила около 92%, что практически совпадает с исходным.
По большей части, тем не менее, я думаю, что узнал, что плитки, которые я ранее разработал, были выбраны довольно хорошо, но я все же получил постепенное улучшение, сделав лабиринт более сложным, без значительного ущерба для возможности успеха.
Обложка нового набора плиток еще не такая красивая, как у старого, но вот лабиринт, выложенный новыми плитками.
Так что насчет остальной части игры? Было проделано много работы! На самом деле создание лабиринта было довольно маленькой частью. Существует множество деталей, касающихся создания персонажей (каждый игрок выбирает одного из шести персонажей с уникальной личностью, историей и способностями), другой механики (есть монстр, который случайным образом перемещается по лабиринту, квесты, которые переносят персонажей в разные места, чтобы собирать предметы, волшебный туман, который скрывает и меняет части лабиринта во время игры и т. д.), а также произведения искусства.
К сожалению, завтра я возвращаюсь к своей постоянной работе, и у меня может не быть свободного времени для преследования несерьезных целей. Но кто знает ... возможно, я найду время, нажму на Kickstarter и завершу работу. В любом случае, я кое-чему научился и хорошо провел время, и надеюсь, вам понравился рассказ.
