Мы ковыряли поиск пути через A* на протяжении двух глав и при этом были сосредоточены на синтаксических изысках F#. В этой главе мы отдохнём от синтаксиса и посмотрим на то, как этот алгоритм мог бы развиваться в более функциональном стиле.

Путь ФП

В 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.