
Мы ковыряли поиск пути через A*
на протяжении двух глав и при этом были сосредоточены на синтаксических изысках F#. В этой главе мы отдохнём от синтаксиса и посмотрим на то, как этот алгоритм мог бы развиваться в более функциональном стиле.
Оглавление
Приквел
Шестидесятилетний заключённый и лабораторная крыса. F# на Godot
Путь ФП
В 6 главе мы остановились на следующем алгоритме поиска:
let tryFindPath mapSize isObstacle start goal =
if not ^ inMap mapSize goal then Result.Error OutOfBounds
elif isObstacle goal then Result.Error Obstacle else
let frontier = PriorityStack.singleton 0 start
let cameFrom = Dictionary.singleton start start
let costSoFar = Dictionary.singleton start 0
let rec tryFind () =
match frontier.TryTake () with
| None -> Result.Error Unreachable
| Some (Eq goal) ->
let path = Stack()
path.Push goal
let rec buildPath current =
if current <> start then
let current = cameFrom.[current]
path.Push current
buildPath current
buildPath goal
Ok {|
Path = List.ofSeq path
Cost = costSoFar.[goal]
Start = start
Goal = goal
CostSoFar = costSoFar.AsReadOnly()
CameFrom = cameFrom.AsReadOnly()
Frontier = List.ofSeq ^ frontier.AsSeq()
|}
| Some current ->
let newCost = costSoFar.[current] + 1
for next in neighbours mapSize isObstacle current do
match costSoFar.TryGetValue next with
| true, oldCost when newCost >= oldCost -> ()
| _ ->
costSoFar.[next] <- newCost
frontier.Put (newCost + heuristic goal next) next
cameFrom.[next] <- current
tryFind ()
tryFind ()
Сейчас в нём надо обратить внимание на коллекцию cameFrom : Dictionary<Vector2I, Vector2I>
. Каждый её элемент хранит переход из точки value
в соседнюю точку key
. Это единичный шаг, который является последним в цепочке наиболее оптимального из найденных путей (start => key
). Такой формат хранения дёшев, но неудобен тем, что для вывода результата путь необходимо восстанавливать отдельным алгоритмом, который не особо соображает, что делает. Если при построении cameFrom
будет допущена ошибка, то buildPath
может зациклиться и приложение зависнет в бесконечном ожидании, несмотря на якобы найденное решение. Звучит не слишком страшно, но я тут поковырял поиск пути в условиях, когда на поле есть зоны контроля противника, конюшни (восполнение стамины), телепорты и прочие вроде как классические механики, и обнаружил, что при столкновении с багами, недра cameFrom
вызывают слишком много подозрений при почти нулевых возможностях диагностики. На мой взгляд, от этой проблемы можно и нужно избавиться, для чего нам пригодится функциональная парадигма.
Проблему можно извести на корню, если вместо отдельных шагов хранить сразу полный путь из start
в key
в виде строго конечной структуры данных. Мы такое уже делали, когда анимировали передвижение корабля. Тогда у нас был Vector2I list
вида [start; ... ; key]
. Откусывая очередную голову (первый элемент), мы получали следующую точку и продолжение пути в остатке:
match motion with
| [] -> ...
| next :: remain -> ...
При инкрементальном построении пути нам надо не забирать голову, а добавлять новый элемент в самый конец списка:
путь до `n + 1` = путь до `n` + координаты `n + 1`
Однако эта операция может дорого нам обойтись в силу внутреннего устройства 'a list
:
// Классическая реализация `list`:
type 'a List =
| Nil
| Cons of (Head : 'a) * (Tail : 'a List)
list
умеет быстро за O(1)
«добавлять» и «удалять» голову, но аналогичная операция с хвостом потребует полной пересборки всего списка за O(n)
. Поэтому надо развернуть путь задом наперёд (речь исключительно о форме хранения), тогда key
будет приходиться на голову:
paths.[next] <- next :: paths.[current]
Это рабочее, я бы даже сказал, стандартное решение. Мы прибегаем к нему во многих рекурсивных алгоритмах, так что его можно брать на вооружение. Главное — на последующих стадиях не забывать, что эти пути инвертированы и их надо реинвертировать обратно перед использованием по назначению. В многослойных алгоритмах (не наш случай) всегда сохраняется шанс ошибиться в «чётности» List.rev
, во избежание чего можно подстраховаться при помощи SCDU вида:
// Примитивный вариант:
type 'a RevList = {
AsReversedList : 'a list
}
with
member this.AsList = List.rev this.AsReversedList
static member create reversedList = { AsReversedList = reversedList }
...
// "Умный" вариант с кешированием.
// `equality` и `comparison` отвалятся,
// так что при необходимости их надо будет добавлять отдельно.
type 'a RevListCached = private {
asReversedList : 'a list
asList : 'a list Lazy
}
with
member this.AsReversedList = this.asReversedList
member this.AsList = this.asList.Value
static member create reversedList = {
asReversedList = reversedList
asList = lazy(List.rev reversedList)
}
...
Можно поступить круче, если взять иммутабельную структуру, умеющую расти с конца. В пакете FSharpx.Collections
есть 'a PersistentVector
. Он ведёт себя как линейная коллекция, но под его капотом прячется иммутабельное дерево, которое умеет сравнительно дёшево:
Добавлять новый элемент в свой конец —
Conj
(по аналогии сCons
);Выдёргивать его —
Initial, Last
(по аналогии сHead, Tail
);А также «искать» и заменять элемент по индексу —
nth
/индексатор иupdate
соответственно.
Если говорить языком аналогий, то в народе распространено мнение, что list
— это иммутабельный эквивалент Stack
, а PersistentVector
— иммутабельный эквивалент ResizeArray
(List
в C#).
'a PersistentVector
пригодится нам не только для cameFrom
, но и для коллекции стоимостей costSoFar
. Она хранит иную информацию, но механизм её заполнения идентичен до такой степени, что обе коллекции можно слить в одну, если в качестве 'a
взять тупл или рекорд:
let tryFindPath mapSize isObstacle start goal =
if not ^ inMap mapSize goal then Result.Error OutOfBounds
elif isObstacle goal then Result.Error Obstacle else
let frontier = PriorityStack.singleton 0 start
// Базовый элемент коллекции:
let createStep position cost = {|
Position = position
Cost = cost
|}
let paths =
createStep start 0
|> PersistentVector.singleton
|> Dictionary.singleton start
let rec tryFind () =
match frontier.TryTake () with
| None -> Result.Error Unreachable
| Some (Eq goal) ->
Ok {|
Path = paths.[goal]
Cost = paths.[goal].Last.Cost
Goal = goal
Start = start
Paths = paths.AsReadOnly()
Frontier = List.ofSeq ^ frontier.AsSeq()
|}
| Some current ->
let currentPath = paths.[current]
let newCost = currentPath.Last.Cost + 1
for next in neighbours mapSize isObstacle current do
match paths.TryGetValue next with
| true, PersistentVector.Conj (_, old) when newCost >= old.Cost -> ()
| _ ->
frontier.Put (newCost + heuristic goal next) next
paths.[next] <- currentPath.Conj ^ createStep next newCost
tryFind ()
tryFind ()
В каждом paths.[key]
окажется PersistentVector
следующего вида:
{| Position = start; Cost = 0 |}
{| Position = сосед start; Cost = 1 |}
...
{| Position = сосед key; Cost = finalCost - 1 |}
{| Position = key; Cost = finalCost |}
Важно, что полученные пути будут содержать в себе точку старта, которую раньше buildPath
принудительно выбрасывал. Это не побочный эффект перехода на PersistentVector
, а сознательное решение. Мне такое поведение было на руку, и именно поэтому я начинал paths
с singleton
. Если вместо него взять PersistentVector.empty
, пути приобретут изначальную «безголовую» форму.
Конкретно в этих «правилах игры» не существует клеток со стоимостью движения отличной от нуля, поэтому Cost
здесь всегда будет совпадать с индексом своего элемента. Cost
последнего элемента будет итоговой стоимостью пути, и её можно будет вычислить как persistentVector.Length - 1
. Эта операция будет стоить O(1)
, так как PersistentVector
хранит свою длину в готовом виде (в отличие от list
). Основываясь на этом, можно избавиться от рекорда в пользу Vector2I
(Vector2I PersistentVector
).
Однако я так не делаю независимо от стоимости ландшафта, так как в рекордах можно хранить много сопутствующей информации. Например, стоимость конкретных шагов (т. е. дельту) или любое другое накопленное состояние, типа «попал в зону контроля врага» и т. д.
В первой версии статьи я пытался отвадить читателей от запихивания в рекорд информации, не относящейся к процессу поиска пути, но мне очень быстро накидали целую панамку кейсов (некоторые из моих же выступлений на капустниках), где этот критерий ощутимо вредил и разрабу, и игроку. Так что можете запихивать туда что угодно, если знаете, зачем.
Многоразовый поиск пути
PersistentVector
практически неизвестен за пределами ФП-сообществ, но в нашем случае он пришёлся очень к месту, так как нам надо было хранить множество коллекций с общим генеалогическим прошлым. Чисто из спортивного интереса мы сможем разыграть карту родства повторно, если грамотно сохраним и перенесём накопленные данные из одной попытки поиска в другую. Для этого надо определиться с тем, какие данные вообще подлежат переносу.
Хуже всего дела обстоят у frontier
. Эта коллекция заполняется парами, одна половина которых — это точка на поле, которая была достигнута из точки start
в границах mapSize
и в условиях obstacles
. А вторая половина — это сумма из пройденного расстояния и эвристической оценки близости к конкретному goal
. Получается, что frontier
жёстко зависим сразу от всех входных параметров, и при смене любого из них коллекцию можно выбрасывать.
paths
выглядит более «объективно», так как содержит пройденные пути и их стоимость. Может показаться, что эта информация не зависит от конкретных goal
и поэтому может быть механически расшарена между разными целями, но данное ощущение ложно. Это должно быть ясно из следующего контрпримера:

Тут представлены два независимых поиска пути (к OrangeRed
-клеткам 4
и 5
). Обратим внимание на самый первый шаг. Он в представленных кейсах различается. При этом позиции 2
, 3
и 4
идентичны.
В глобальном плане разница между итоговыми путями кажется незначительной. Однако она может быть очень неприятна для игрока, если мы просто так попытаемся заимствовать значения paths
из одной попытки поиска в другую, так как шаг 1
для всех подпутей со 2
по 5
будет закреплён за тем вариантом, который игрок проверит первым. Такая ситуация на длинных дистанциях может повторяться несколько раз с кумулятивным эффектом, что обескураживает пользователя, так как получающийся путь начинает выглядеть как продукт рандома.
Однако случайностей в этом деле нет, весь процесс очень детерминирован. Алгоритм всегда «выбирает» наиболее близкий к цели вариант хода. Причём близость выражается в манхэттенском расстоянии, поэтому в первом случае (слева) оба доступных варианта равнозначны (heuristic
оба раза даёт 4
), а во втором случае (справа) движение на «северо-запад» значительно выгоднее, чем на «северо-восток» (heuristic
даёт 3
против 5
). Когда у нас есть несколько вариантов с одинаковым priority
, то выбран будет тот, что последним попал во frontier
(вспоминает возню с LIFO
в 6 главе). Их последовательность зависит от определения neighbors
:
let neighbors mapSize isObstacle pos =
[
Vector2I.Left
Vector2I.Right
Vector2I.Up
Vector2I.Down
]
|> Seq.map ^ fun p -> p + pos
|> Seq.filter ^ canStand mapSize isObstacle
Формально все соседи равнозначны, и их порядок не зафиксирован, так что в зависимости от вашей реализации, какие-то элементы контрпримера придётся разворачивать на 90 или 180 градусов, но суть от этого не поменяется. Мы всё так же не сможем некритически заимствовать результаты paths
из предыдущей попытки поиска. Нам надо будет аккуратно извлекать из него значения, оценивать их с позиции текущего goal
и в тех случаях, когда они не будут удовлетворять нашим потребностям, перезаписывать их более подходящими данными. Это, в свою очередь, означает, что данные предыдущих goal
могут быть потеряны безвозвратно, так что их следует сохранять в отдельной коллекции (ready
) и извлекать при повторных запросах.
Мемоизация
Подключить словарь ready
проще всего:
let memoTryFindPath mapSize isObstacle start =
let ready = Dictionary()
fun goal ->
ready.TryFind goal
|> Option.defaultWith ^ fun () ->
let result = tryFindPath mapSize isObstacle start goal
match result with
| Result.Error OutOfBounds ->
// Пространство за пределами поля безгранично.
()
| _ -> ready.[goal] <- result
result
memoTryFindPath
— это функция, возвращающая функцию от goal
. У возвращённой функции есть состояние, поэтому её надо сохранить где-то в недрах сцены и использовать до тех пор, пока какой-нибудь из параметров memoTryFindPath
не изменится, после чего процедуру нужно будет повторить:
let mutable tryFindPath =
PathFinder.memoTryFindPath mapSize units.Blocks starship.Position
...
pathSrc <- tryFindPath goal
Такой механизм называется мемоизацией и он распространён настолько широко, что я периодически встречаю в чужих проектах готовые функции-хелперы с сигнатурой (f : 'a -> 'b) -> ('a -> 'b)
. В целом концепцией я пользуюсь, она безусловно торт, но попытки её обобщить и вынести в Utils
не понимаю. Это оптимизация, и её можно радикально улучшить, если максимально возможным образом подстроиться под особенности облекаемой функции.
В качестве примера лёгкой и очевидной оптимизации мемоизации можно посмотреть на отсечение ошибки OutOfBounds
, которая означает, что целевая клетка находится за пределами поля. Если «игровая доска» невелика, то таких точек может оказаться на пару порядков больше, чем точек в границах поля. Без этого фильтра коллекция ready
будет забита набором бесполезных ошибок, которые экономичнее исключить арифметически, чем найти в словаре. В идеале ready
вообще не надо трогать, пока цель не будет проверена через inMap
, но для этого нужно встроить мемоизацию непосредственно в алгоритм:
if not ^ inMap mapSize goal then Result.Error OutOfBounds
elif isObstacle goal then Result.Error Obstacle else
match ready.TryFind goal with
| Some result -> result
| None ->
...
let result = tryFind ()
ready.[goal] <- result
result
Фильтрация paths
В paths
содержатся пути, которые существуют независимо от новых goal
. Не факт, что эти пути будут взяты на вооружение, но точно можно утверждать, что если у нас есть путь с Cost = n
, то нам нет смысла рассматривать пути со стоимостью > n
. В этом плане данные из paths
работают на ускорение алгоритма:
match paths.TryFind next with
| Some (PersistentVector.Conj (_, old)) when newCost > old.Cost -> ()
Пути с эквивалентной стоимостью придётся разбирать по более сложной процедуре. Для начала следует уяснить, что в paths
значения попадают только после того, как соответствующие клетки были помещены во frontier
. Очевидно, что, если позиция уже во фронтире, а newCost = old.Cost
, то нет смысла добавлять его туда ещё раз. Также очевидно, что при многоразовом поиске, связка «присутствует в paths
=> был/есть во frontier
» разрушается, так как фронтир у нас каждый раз новый. Из этого следует, что учёт входящих во frontier
точек надо вести отдельно:
let frontier = PriorityStack.singleton 0 start
let traversed = HashSet.singleton start
let put cost next =
ignore ^ traversed.Add next
frontier.Put (cost + heuristic goal next) next
И отдельно проверять этот факт перед отбрасыванием эквивалентного пути:
| Some (PersistentVector.Conj (previous, old)) when newCost = old.Cost ->
if not ^ traversed.Contains next then
put newCost next
Далее необходимо понять, соответствует ли извлечённый из словаря путь текущему currentPath
, то есть currentPath = previous
. Если да, то старый путь можно оставить, если нет, то его надо будет заменить, чтобы убрать негативное влияние прошлых поисков:
| Some (PersistentVector.Conj (previous, old)) when newCost = old.Cost ->
if not ^ traversed.Contains next then
put newCost next
if previous <> currentPath then
paths.[next] <- currentPath.Conj ^ createStep next newCost
Трудности <>
Операция сравнения на коллекциях может приводить к перебору всех элементов за O(n)
, что дороже, чем создание нового экземпляра через Conj
(документация заявляет O(1)
, но я по старинке исходил O(log32n)
). Если подумать, то нас интересует не полная неэквивалентность, а факт того, что path.[next]
не был создан на основе path.[current]
:
path.[next] <- path.[current].Conj old
Этот момент надо устанавливать максимально быстро, даже в ущерб «случайной» эквивалентности. Быстрее всего мог бы сработать следующий предикат:
System.Object.ReferenceEquals(
path.[next].Initial // Вектор без последнего элемента.
, path.[current]
)
Но PersistentVector
не сохраняет ссылку на своего предка, как это делает list
, для которого эквивалентность Tail
-ов — одна из суперсил:
property {
let! tail =
Range.constantBounded()
|> Gen.int32
|> Gen.list ^ Range.constant 0 10
let! head =
Range.constantBounded()
|> Gen.int32
return System.Object.ReferenceEquals(
tail
, (head :: tail).Tail
)
}
Объект Initial
в PersistentVector
всегда отличается от того объекта, что послужил базой текущему (за исключением редких оптимизаций PersistentVector.empty
):
property {
let! initial =
Range.constantBounded()
|> Gen.int32
|> Gen.list ^ Range.constant 0 10
let! last =
Range.constantBounded()
|> Gen.int32
let initial = PersistentVector.ofSeq initial
return not ^ System.Object.ReferenceEquals(
initial
, initial.Conj(last).Initial
)
}
Хуже того, Initial
генерируется при каждом запросе, так что он не будет равен «самому себе»:
property {
let! initial =
Range.constantBounded()
|> Gen.int32
|> Gen.list ^ Range.constant 1 10
let! last =
Range.constantBounded()
|> Gen.int32
let vector =
PersistentVector.ofSeq(initial).Conj last
return not ^ System.Object.ReferenceEquals(
vector.Initial
, vector.Initial
)
}
Заменой ссылочной эквивалентности мог бы выступить внешний ключ, уникальный для каждого шага. Как правило, для таких задач я использую Guid
, но здесь взял int
, так как последовательная генерация ключей здесь принесёт больше пользы. Благодаря этому Id : int
сможет свидетельствовать о возрасте пути (в статье это не понадобится, но направление мысли должно быть понятно):
let createStep =
let mutable nextId = 0
fun position cost -> {|
Position = position
Cost = cost
Id =
let result = nextId
nextId <- nextId + 1
result
|}
Ускоренная проверка отцовства будет сводиться к previous.Last.Id <> currentPath.Last.Id
. Это сильно быстрее, чем поэлементное сравнение, но можно пойти ещё дальше и избавиться от генерации previous
(O(log32n)
), если сохранять previous.Id
в каждом новом шаге:
let addStep =
let mutable nextId = 0
fun position cost path ->
path
|> PersistentVector.conj {|
Position = position
Cost = cost
Id =
let result = nextId
nextId <- nextId + 1
result
PreviousId =
// Задумайтесь на досуге, как ХМ выводит типы `path` и `p`
path.TryLast
|> Option.map ^ fun p -> p.Id
|}
Итоговый алгоритм со встроенной мемоизацией будет выглядеть так:
module PersistentVector =
let (|Last|_|) vector = PersistentVector.tryLast vector
let createPathFinder mapSize isObstacle start =
let createStep =
let mutable nextId = 0
fun position cost -> {|
Position = position
Cost = cost
Id =
let result = nextId
nextId <- nextId + 1
result
|}
let paths =
PersistentVector.empty
|> addStep start 0
|> Dictionary.singleton start
let ready = Dictionary()
let readOnlyPaths = paths.AsReadOnly()
fun goal ->
if not ^ inMap mapSize goal then Result.Error OutOfBounds
elif isObstacle goal then Result.Error Obstacle else
match ready.TryFind goal with
| Some result -> result
| None ->
let frontier = PriorityStack.singleton 0 start
let traversed = HashSet.singleton start
let put cost next =
ignore ^ traversed.Add next
frontier.Put (cost + heuristic goal next) next
let rec tryFind () =
match frontier.TryTake () with
| None -> Result.Error Unreachable
| Some (Eq goal) ->
let path = paths.[goal]
Ok {|
Path = path
Cost = path.Last.Cost
Goal = goal
Start = start
Paths = this.Paths
Traversed = traversed :> _ IReadOnlySet
Frontier = List.ofSeq ^ frontier.AsSeq()
|}
| Some current ->
let currentPath = paths.[current]
let newCost = currentPath.Last.Cost + 1
for next in neighbours mapSize isObstacle current do
match paths.TryFind next with
| Some (PersistentVector.Last old) when newCost > old.Cost -> ()
| Some (PersistentVector.Last old) when newCost = old.Cost ->
if not ^ traversed.Contains next then
put newCost next
if old.PreviousId <> Some currentPath.Last.Id then
paths.[next] <- addStep next newCost currentPath
| _ ->
put newCost next
paths.[next] <- addStep next newCost currentPath
tryFind ()
let result = tryFind ()
ready.[goal] <- result
result
Структурно он повторяет одноразовый поиск, но его результат содержит чуть больше данных. В нём лежит новый traversed
, а также readOnlyPaths
, который является несамостоятельным фасадом мутабельной коллекции, вследствие чего его содержимое будет расширяться и переписываться с каждой новой попыткой поиска. Если этот момент не устраивает, то слепок данных можно собрать самостоятельно. Если отфильтровать его traversed
, мы получим словарь, очень близкий по своему содержанию к одноразовой версии:
pathFound.Paths
|> Seq.filter ^ fun p -> pathFound.Traversed.Contains p.Key
|> Seq.map ^ fun p -> p.Key, p.Value
|> readOnlyDict
Собирать его можно снаружи (после вызова алгоритма), если не затягивать процесс до следующего вызова. Но в этом случае мы окажемся за бортом мемоизации, так что об этой штуке стоит подумать заранее. Если уверены в конечном наборе данных (мне не свойственно), то фиксируйте. Если не уверены, то найдите способ контролировать мемоизацию непосредственно на проекте либо через включение исходников, либо через создание соответствующих дженерик-нычек.
Планирование задом наперёд
При чтении данной главы может возникнуть ощущение, что я действовал по заранее подготовленному плану. Дескать, сначала я задумался о корнер-кейсах, нашёл необходимые контрпримеры, продумал алгоритм, закодил его и потом проверил на сотне запусков. Это ощущение ложно, последовательность действий была иной.
Мне было понятно, что с наивной реализацией будет что-то не так, но не было ясно, что именно. Поэтому я всё равно её закодил, погонял в «реальном приложении», понял, какие моменты не соответствуют ожиданиям и приступил к тестам. Тесты дали мне контрпримеры и корнер-кейсы, а они в свою очередь привели к пониманию нового алгоритма. Лишь при оптимизации сравнения PersistentVector
во мне взыграл визионер, так как до ощутимой нагрузки на железо я не дошёл.
Фразу "Тесты дали мне контрпримеры и корнер-кейсы"
надо понимать буквально. Речь не о некоей осознанности, которую нам обещает TDD и ей подобные идеологии. Я буквально получил в руки контрпримеры, из которых чередой логических умозаключений пришёл к корнер-кейсам, а от них — к финальной версии алгоритма. Этот «дар» значительно ускорил процесс разработки, так что процесс его получения стоит рассмотреть подробнее.
Несколько раз в этой и прошлых статьях я без каких-либо комментариев приводил примеры кода с билдером property
. Среди моих альфачей альфа-тестеров были люди, которые считали, что так делать не стоит, но я решил провести эксперимент. Всё-таки примеры были достаточно простыми, чтобы их смысл можно было понять непосредственно из кода. К тому же они были размещены в тексте, который практически исключал возможность разночтения.
property
— это билдер из пакета Hedgehog
, который работает с некоторым рандомным набором данных и «проверяет», что эти данные удовлетворяют заданному предикату. Можно сказать, что так в сжатом виде выглядит описание идеологии Property Based Testing
. Теоретический аспект в этом цикле разбираться не будет, я сразу перейду к практическим ходам и следствиям. Но если кому надо, то AI Яндекса даёт вполне вменяемое описание PBT, а за подробностями можно обратиться к соответствующему циклу и к документации Hedgehog или FsCheck.
Наряду с property
в Hedgehog
есть билдер gen
, который позволяет описать процедуру генерации рандомных данных отдельно от итоговых предикатов. Например, так выглядит генерация поля 4 на 4, в котором четверть тайлов заняты препятствиями, а среди остальных выбраны точка start
и 5 целей:
open Hedgehog
let mapSize = Vector2I.One * 4
let genInput = gen {
let! rnd =
Range.constantBounded()
|> Gen.int32
|> Gen.map System.Random
let obstacles, spaces =
[
for x in 0..mapSize.X-1 do
for y in 0..mapSize.Y-1 do
Vector2I(x, y)
]
|> List.randomShuffleWith rnd
|> List.splitAt (mapSize.X * mapSize.Y / 4)
match spaces with
| start :: goals ->
return {|
Start = start
Goals = List.take 5 goals
Obstacles = obstacles |> List.sortBy ^ fun p -> p.X, p.Y
|}
| unexpected ->
return failwith $"Unexpected: %A{unexpected}"
}
Крайне важно генерировать данные, которые потом можно перетащить в сцену и воспроизвести в рантайме. Для этого данные возвращаются в виде анонимного рекорда в готовом к сериализации виде (int * int
вместо Vector2I
и так далее). Конкретно в нашем случае размер коллекций предельно мал, поэтому при принте в логи рекорд будет выведен целиком, так что его можно будет скопипастить в исходник сцены. Это счастливое исключение. Обычно прорабатывать механизмы переноса приходится самостоятельно, но начинайте с чего-нибудь простого. Скажем, сериализуйте в json
и выведите его в логи теста, чтобы потом руками десериализовать его из строки в коде сцены.
Следующим тестом мы можем проверить, что многоразовая и одноразовые версии генерируют один и тот же путь к цели:
property {
let! data = genInput
let obstacles = HashSet data.Obstacles
let tryFind = createPathFinder mapSize obstacles.Contains data.Start
let result =
data.Goals
|> List.map ^ fun goal ->
goal
, tryFind goal
|> Result.map ^ fun p ->
p.Path
|> Seq.map ^ fun p -> p.Cost, p.Position
|> List.ofSeq
, tryFindPath mapSize obstacles.Contains data.Start goal
|> Result.map ^ fun p ->
p.Path
|> Seq.map ^ fun p -> p.Cost, p.Position
|> List.ofSeq
counterexample(
String.concat " \n" ^ seq {
for index, (goal, actual, expected) in Seq.indexed result do
$"#%i{index}:"
$"Goal: %A{goal}"
$"%A{actual}"
$"%A{expected}"
}
)
return
result
|> List.forall ^ fun (_, actual, expected) -> actual = expected
}
// Где-то в `Ready` секции сцены/ноды.
|> Property.render
|> GD.print
Это, в общем-то, главный тест вечера. С помощью него я набрёл на кейс с 4 vs 5
из начала статьи и на несколько кейсов поменьше.
Так как у нас нет тестовых ассертов, всю необходимую для диагностики информацию надо выводить в counterexample
(туда же можно принтить вышеупомянутый json
). Оттуда она пойдёт дальше, если конкретная тестовая посылка завалится. Именно поэтому у нас появляется привязка result
. Если бы данных было меньше, то мы бы вызывали List.forall
сразу над data.Goals
.
Следующий тест проверит, что поиск на одну и ту же цель будет возвращать один и тот же путь независимо от того, какие цели были до этого:
property {
let! data = gen {
let! data = genInput
let! goals =
Gen.item data.Goals
|> Gen.list ^ Range.singleton (2 * data.Goals.Length)
return {| data with Goals = goals |}
}
let obstacles = HashSet data.Obstacles
let tryFind = memoTryFindPath mapSize obstacles.Contains data.Start
let result =
data.Goals
|> List.map ^ fun goal ->
goal
, tryFind goal
|> Result.map ^ fun p ->
p.Path
|> Seq.map ^ fun p -> p.Cost, p.Position
|> List.ofSeq
|> List.groupBy fst
|> List.map ^ fun (goal, items) ->
goal, List.map snd items
counterexample(
String.concat " \n" ^ seq {
for index, (goal, path) in Seq.indexed result do
$"#%i{index}:"
$"Goal: %A{goal}"
$"%A{path}"
}
)
return
result
|> List.forall ^ fun (_, results) ->
let actual =
results
|> List.distinct
|> List.length
actual = 1
}
Этот тест гарантированно заставит сделать ready
словарём (с путями), а не множеством идентификаторов, как было в одной из моих первых версий.
Приведённые тесты и генераторы нельзя назвать близкими к идеалу. Их шринкеры (что это, изучайте самостоятельно) фактически не работают. Размеры поля, количество препятствий и целей фиксированы. Всё это легко исправить, если ознакомиться с азами PBT. Но я оставил всё как есть, так как мне нужно было влезть в статью даже такой дубовый вариант тестов работает лучше и быстрее, чем большинство программистов.
Ещё одним важным фактором тестирования было то, что я выводил уйму информации на игровое поле. Мне был виден не только путь, но и побочный продукт поиска в виде клеток traversed
, frontier
и paths
. Например, на открытом пространстве алгоритм строит путь в виде буквы Г
и попутно складывает всех соседей во frontier
. Когда он начинает заглядывать в точки за пределами предсказанной области, это повод для беспокойства. Скажем, неправильная обработка эквивалентных Cost
в тех же условиях может приводить к закраске области прямоугольником (как в примере с PriorityQueue
в 6 главе).
Путь может получиться точно таким же, но алгоритм заглянет в x * y
точек, что в разы больше, чем каноничные x + y - 1
. Имея такую математическую формулировку, вы можете легко написать ещё один property
-тест, но перед этим надо вообще вспомнить о данном факте, для чего и нужна утяжелённая визуализация. Она работает как дополнительное средство диагностики, и команда разработчиков точно от неё выигрывает. Главное — дотащить всё это дело до UI и прикрутить ручку вкл/выкл
.
Вообще на месте инди-разрабов я бы призадумался над тем, сколько информации теряет игрок из-за неинтерактивных или вовсе отсутствующих подсказок. Я уже почти смирился с тем, что грубейшая недокументированность почему-то преподносится как некая механика «открытия». Предположу, что она вызвана банальным недостатком человеко-часов, которые лучше выделить на поиск и закрытие багов. Но мне кажется очевидным, что обычному пользователю обнаружить баг через интерактивную подсказку гораздо проще, чем в результате прямого действия. Например, я не имею привычки отслеживать полумашинальные действия, что рождает во мне серьёзные сомнения при встрече с неожиданным поведением в игре: «Это меня память подводит, или игра делает то, что не должна делать?» А когда я играю в roguelike, то у меня ещё и пропадает возможность воспроизвести ситуацию в лабораторных условиях, так что я почти не рапортую о багах.
Промежуточное заключение
В этой статье я попытался показать, как может происходить оптимизация в functional-first системах. Я не прибегал к пляскам с массивами, спанами и прочей фигнёй, которую так любят байтолюбы. Более того, я считаю их вредными для большинства прикладных задач, так как обычно такие машинные оптимизации отсекают наиболее удобные дорожки для реализации новых фич. Они оказываются настолько сбоку, что иногда совокупный выигрыш не покрывает раздельное выполнение. Настаиваю на том, что нужно быть поближе к земле и склоняться к тем ходам, что вытекают из самой логики моделируемых событий. В большинстве своём это означает буквальное следование за человеческим сознанием, которое само по себе любит отслеживать экстремальные кейсы, ранжирует почти всё, что попадает в поле зрения, пытается кешировать вычисления.

У него, правда, нифига не получается. Утверждаю это как человек, который пробовал отслеживать все действия пользователей с профильной вышкой. Даже намаханные инженеры ведут себя как люди с практически отсутствующей краткосрочной памятью. Машины этих дефектов лишены. Они могут помочь, но у них тухло с целеполаганием, так что их нужно подводить к каждой проблеме вручную, для чего желательно, чтобы код работал с той же моделью, что и пользователь. Получается довольно неожиданная причинно-следственная связь: в системах, которые ассистируют пользователю и призваны предвосхищать его действия, производительность достигается за счёт следования DDD.
С ростом автоматизации пользователь может выпасть из процесса, и тогда необходимость в ветвистых моделях сойдёт на нет. Это абсурдный сценарий, если говорить об играх, но он вполне вероятен для любого прикладного ПО. На этой стадии можно вернуться к массивам и т. п. динозаврам, однако их надо как-то тестировать. В этом месте развесистые модели в сочетании с PBT выстреливают ещё раз, так как мы всегда можем наклепать кучу property
-тестов вида «быстрая версия выдаёт тот же результат, что и медленная». Мы только что видели схожий процесс с многоразовым и одноразовым поисками пути. В этом нет ничего сложного, это буквально самая тупая разновидность тестов, где у нас есть готовый оракул, который очень легко читается и не нуждается в оптимизации.
На этом экскурс в абстрактное ФП закончен. В следующей главе мы вернёмся к изучению синтаксиса F# и механизмов Godot.
НЛО прилетело и оставило здесь промокод для читателей нашего блога:
-15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.