Небольшой экскурс в кроличью нору по выравниванию террейна в RTS игре

Всё что строится в Knights Province, дороги, поля, дома, рельеф требует выравнивания террейна. Это небольшая деталь почти не влияет на геймплей, но, как мне субъективно кажется, делает игровой мир заметно отзывчивее и живее. Дороги и здания буквально врезаются в поверхность земли. Игрок ставит план дома, приходит строитель, выравнивает землю по клеточкам, строит дом, все довольны. Иногда, если склон оказывается слишком крутым, игра показывает, что здание там просто нельзя разместить. Вот собственно и все вводные.

Как это часто бывает в разработке игр, простая снаружи задача оказалась куда сложнее и глубже, стоило только начать в ней разбираться. Статья ниже - мои приключения в этой кроличьей норе на протяжение предыдущих 3-4 недель.

Оригинальный подход

Выравнивание рельефа существует в игре еще со времен первой Альфы (да и было задолго до неё тоже). Большую часть своей жизни подход справлялся вполне нормально. Он работал с каждым тайлом отдельно. Получив тайл, который нужно выровнять, алгоритм смотрел на высоты точек по углам тайла и у соседних тайлов, вычислял среднее значение и менял высоты углов тайла так, чтобы поверхность стала ровнее. Если при этом портился рельеф рядом, то его тоже выравнивало.

У этого алгоритма было две серьезных проблемы и одна косметическая.

Первая серьезная проблема заключалась в том, что выравнивание одного тайла не происходит в пустоте. Пока строитель занят работой над тайлом, вокруг ходят другие юниты, рядом могут начать строить новую дорогу, соседний участок рельефа может измениться, рядом может начаться строительство другого здания и так далее. Засада в том, что если выровнять один тайл, то соседний может стать слишком крутым и непроходимым. В таком случае, алгоритм пытался рекурсивно выровнять всё то, что стало неровным по результатам его работы. Алгоритм справлялся с этим в основном нормально, но иногда, в результате неудачного стечения обстоятельств и проверок, какой-нибудь невезучий юнит мог застрять на внезапно ставшем непроходимым тайле, вследствии чего игра падала.

Вторая серьезная проблема - зацикливание выравнивания. Алгоритм рекурсивный, он выравнивал один тайл, из-за чего соседний мог стать слишком крутым. В таком случае алгоритм исправлял соседний тайл и, иногда, снова портил исходный. Достаточно повторить этот манёвр примерно 5800 раз и игра упадёт с переполнением стека.

Третья проблема - косметическая состояла в том, что иногда поверхность так и не становилась визуально достаточно ровной. На геймплей это не влияет, но углы здания, висящие в воздухе, выглядят «не очень».

Получается, что у алгоритма две противоречивых цели. С одной стороны, алгоритм должен быть достаточно надежным, чтобы не крашить игру, не ломать проходимость и не застревать в бесконечных циклах. С другой, после его работы, рельеф должен выглядеть достаточно ровным. Возводя в абсолют, лучшее выравнивание не приводящее к ошибкам - то которое ничего не трогает. Лучшая ровность - приведение всего рельефа к одной (нулевой) высоте. Конфликт интересов налицо.

Ошибки при выравнивании происходили достаточно редко, чтобы не требовать немедленного исправления, а визуальный дефект не слишком сильно бросался в глаза. Но обе проблемы преследовали проект уже больше 10 лет ... Вдобавок старый код за годы оброс множеством исключений и костылей. Он работает, но разбираться в нём тяжело, а результат вмешательств не всегда получается красивым, стабильным или предсказуемым.

Итак, лето, отпуск, пора что-то менять! Вижу цель, не вижу препятствий: надо просто сделать выравнивание рельефа более надежным и покрасивее. Как обычно, основная проблема тут в недооценке что такое «просто», но без этого не было бы и статьи, так что поехали!

Попытка №1: «Можно всё красиво запланировать заранее»

С дорогами и полями все более-менее просто - в момент постройки они занимают один тайл, а одиночный тайл почти всегда легко сделать хотя бы немного ровнее. Самое интересное - здания. Под зданием выравнивается сразу участок от 2х3 до 4х4 тайлов. И как-раз таки здания требуют визуальной ровности площадки под ними.

Первоначальная идея состояла в том, чтобы сделать алгоритм поумнее и заставить его планировать выравнивание всего участка под зданием как единое целое, ещё до начала работы. Вместо канители по одному тайлу за раз - логично сначала прикинуть всю площадь прямоугольника дома, посчитать идеальную высоту, составить план выравнивания, а затем просто выполнять его по мере движения строителя по тайлам участка. Ну и заодно хотелось бы избавиться от ошибок, которые приводили к падениям, но это в первой попытке было вторично. Красота она в каждом втором матче, а ошибки - раз в 1000 игр.

Есть правда небольшой нюанс: план выполняется в «реальном» игровом мире. Его ограничивают рельеф, который нельзя менять, например горы, водоёмы или уже стоящие рядом здания. Сам мир тоже постоянно меняется. Носильщик может пройти мимо стройки или встать на тайл, который еще не успели выровнять. Рядом могут проложить дорогу или поставить еще одно здание. Строителя могут убить, или он может умереть от голода прямо во время работы. Получается, что даже тщательно подготовленный план опирается на внешние, относительно него условия, которые могут измениться в любой тик игры. И тогда его исходные предположения перестают работать. В дополнение к этому, сам факт выравнивания сразу к целевой высоте может сделать следующий в очереди тайл непроходимым, и строитель просто не сможет на него встать чтобы его выровнять. 

Предварительное планирование всей операции хорошо выглядит в теории, но не решает главную проблему: устойчивость алгоритма к внешним событиям и изменениям во времени. Планирование отлично отвечает на вопрос «какой рельеф я хочу получить под этим домом здесь и сейчас?», но не отвечает на другой: «как это всё будет стыковаться со всем остальным происходящим вокруг?», и «будет ли выравнивание непротиворечивым в любой момент времени на протяжении этого времени». А именно там и возникало большинство старых ошибок.

Отступление №1: тесты

Примерно в этот момент я понял, что мне нужны синтетические игровые тесты для выравнивания. Например:

• Выровнять площадку под дом на холме

• Выровнять площадку под дом на крутом склоне

• Выровнять рельеф рядом со стоящим юнитом

• Выровнять рельеф возле горы

Тесты проверяли алгоритм в контролируемой и воспроизводимой среде, то есть помогали искать и воспроизводить ошибки за 2-3 клика, вместо запуска полной версии игры. Заодно они показывали работу алгоритма в чистом виде и с отладочной информацией, чтобы быстро оценивать результат как визуально, так и с технической стороны.

С тестами, итерации разработки нового алгоритма тоже стали гораздо менее мучительными. Вместо того чтобы вручную воспроизводить какую-либо конфигурацию рельефа в редакторе карт и отыгрывать ей в настоящем матче, я смог снова и снова запускать один и тот же сценарий с отладчиком и сразу видеть, исправило ли изменение в коде проблему или просто передвинуло её в другое место. Появились первые метрики - выравнивание площадки считается «красивым», если дельта между минимум и максимумом высоты меньше 18 (цифра условная, главная что она есть).

В этой же попытке мне пришлось сделать выравнивание площадки под дом более итеративным. Раньше строитель один раз проходил по всей площади и считал, что на этом работа закончена. Проблема была в том, что на крутых склонах полное выравнивание какого-либо тайла к целевой высоте могло сделать соседние тайлы слишком крутыми и непроходимыми. Теперь строитель стал сначала умеренно выравнивать все тайлы, а затем еще раз возвращался к самым неровным и довыравнивал их. Это решило проблему с соседями, и отчасти и проблему качества.

В некотором смысле подход сработал, выравнивание стало более «умным» в синтетических тестах. Но не в игре.. Из-за описанных выше динамических условий, в реальной игре он так и не «взлетел». Возможных проблемных ситуаций оказалось слишком много, а пытаться предусмотреть каждую из них заранее или динамически корректировать план оказалось слишком сложно. Первая попытка провалилась. Задача оказалась сложнее, чем выглядела.

Попытка №2: «Давайте попробуем ИИ»

В этот момент я подумал: выравнивание - это же хорошая изолированная задача. Есть ограниченные входные данные - высоты рельефа, пара свойств, и тайлы, которые нужно выровнять. Есть понятный результат - получить более ровные тайлы. Наверняка есть алгоритмы решения этой задачи - я не первый кто делает игру с тайлами и строительством здания. Почему бы просто не попробовать ИИ? Конечно, запрос был бы немного сложнее, чем «сделай мне алгоритм выравнивания получше», но и я не вайбкодер.

Первым делом пришлось сформулировать спецификацию. Что именно алгоритм получает на вход и что ему разрешено менять? К какому конкретному и измеримому результату он должен стремиться? Какие ситуации обязан обрабатывать? На что может рассчитывать? Чего не должен делать ни при каких обстоятельствах? Что произойдет, если какой-то участок рельефа выровнять невозможно? Что важнее: итоговая форма поверхности или безопасность процесса? И так далее. Уже само перечисление и расстановка приоритетов среди требований оказались полезны.

Когда первичные требования были записаны, я прошелся по ним вместе с ИИ еще раз. Ничего ли я не забыл? Не повторяют ли некоторые пункты одно и то же? Нет ли противоречий или расплывчатых формулировок? Что является жестким ограничением, а что всего лишь пожеланием? После нескольких итераций получилось нечто, уже похожее на нормальную спецификацию. Дописал параграф про API по которому поступают данные на вход, и куда пишутся выходные данные.

Это, пожалуй, был первый полезный результат эксперимента с ИИ, независимо от того, что потом произошло с кодом (ок-ок, без спойлеров). Игра использовала систему выравнивания рельефа много лет, но до сих пор мне ни разу не приходилось в одном месте формулировать, что именно означает «хорошее выравнивание рельефа».

Спека есть, теперь пришло время выбрать алгоритм. Я запросил у ИИ несколько возможных подходов и сравнить их по различным критериям: соответствуют ли они всем требованиям, какая у них O(n) сложность, насколько они надежны, каков примерный объем кода реализации, и, что особенно важно, насколько простой получится реализация. Мне бы не хотелось получить магический алгоритм, который я не смогу понять и тем более отладить в будущем.

Не буду утомлять названиями алгоритмов и их сложностью в O(n). Как выяснилось позже, важно было не это. Достаточно лишь сказать, что задача выравнивания тайлового рельефа в целом известна, но все же не настолько тривиальна, как пузырьковая сортировка, или А*.

Один из подходов выглядел довольно многообещающе. Не слишком сложный и не слишком нестабильный. Следующий шаг был очевиден: попросить ИИ реализовать его. Естественно не с первого раза всё получилось идеально, пришлось поправить какие-то типы данных, юниты в uses. Но, что удивительно, после исправления этих мелких проблем сгенерированный код заработал в синтетических тестах довольно хорошо. Даже очень хорошо.

Была только одна крошечная проблема. Он работал медленно. Только не просто медленно, а катастрофически медленно. Он был примерно в 10 00 раз медленнее старого алгоритма. Выравнивание площадки под один дом лесоруба на карте размера XL занимало около 10 секунд вместо былых 14 миллисекунд (время указано для всех тайлов площадки в сумме). Такое не оптимизируешь .. И тут я понял, что производительности в спецификации вообще не было. Чтож .. сам виноват, xD.

Для справки, обычный тик в игре равен 100 мсек, но игра должна приемлемо работать на скоростях до 300%, так что реальный бюджет на тик примерно 30 мсек, из которых примерно 2/3 уже заняты другими вещами. Было бы неразумно выделять более 1 мсек на выравнивание рельефа, когда есть более приоритетные потребители (типа ИИ соперников или просчёта путей).

Технически ИИ сделал именно то, о чем его попросили. Просто количество вычислений оказалось совершенно неприемлемым для проекта. Неплохое напоминание о неприятном свойстве спецификаций: все, что вы забыли указать, имеет привычку становиться проблемой позже.

Отступление №2: Заменяемые алгоритмы выравнивания

К этому моменту стало понятно, что я, скорее всего, перепробую ещё не один вариант реализации. Поэтому, перед продолжением, стоило привести в порядок взаимоотношения кода выравнивания с его партнёрами и пользователями. Изначально он был достаточно тесно связан со всем вокруг. Он знал о рельефе, рельеф отчасти знал о нём. Строители обращались к нему напрямую, когда хотели выровнять тайл. Изменения в рельефе триггерили обновление буферов для рендера, и т.п. и т.д. Смена реализации требовала изменений в большем количестве мест, чем хотелось бы. Пришла пора добавить немного абстракций, перераскидать часть ответственностей, да и в целом немного прибраться в зависимостях, чтобы разные алгоритмы можно было легко подключать и отключать «в один клик».

Заодно это позволило оставить старую реализацию в качестве точки отсчета. Забегая вперёд, позже это оказалось очень полезно.

Теперь один и тот же тестовый сценарий можно было прогнать и на «старом» коде, и на  «хрупком планировщике», и на «супер-медленном», и на любой другой новой экспериментальной реализации. Небольшое инфраструктурное изменение, но с ним сравнение алгоритмов стало гораздо менее субъективным.

Также заметно снизилось и накопившееся давление, связанное с попыткой создать «Самый Лучший Алгоритм, здесь и сейчас». Любой неудачный прототип или реализацию стало можно просто отставить для будущего сравнения и справки. Это гораздо удобнее, чем каждый раз вырывать старый код и потом вставлять его обратно (прыгая между git ветками).

Попытка №3: дадим ИИ второй шанс, теперь с учетом производительности!

Ладно. Еще раз та же идея, только теперь производительность явно прописана и является одним из главных требований ТЗ. Уж теперь-то всё должно получиться как надо. Я обновил спецификацию и дал ИИ второй шанс.

У ИИ заскрипели шестерёнки и начал появляться новый код. Сначала около 400 строк для MVP с заглушками. Потом добавился код для нескольких последовательных проходов выравнивания. Кода стало около 700 строк. Затем выяснилось, что в первой версии кое-чего не хватает, и строк стало под 1100. Тесты почти проходили, но находились новые крайние случаи, и реализация продолжала расти. Сложно сказать, была ли это проблема слишком большого или недостаточно детального ТЗ, или слабого ИИ, но код пух как на дрожжах. 

Что интересно, у каждой отдельной доработки обычно был свой повод и она делала разумные дополнения к коду, но целиком систему понимать становилось всё труднее. В какой-то момент появились все признаки того, что она вот-вот рухнет под собственным весом - слишком много связанных правил, слишком много особых случаев, слишком много мест, где просьба к ИИ изменить одно поведение приводила не к совращению или генерализации кода, а к правкам сразу в трех взаимозависимых участках. Ничего хорошего это не сулило.

Именно в этот момент аргумент «ИИ знает больше меня и пишет быстрее меня» перестал быть привлекательным. Примерно как в том анекдоте про «да, печатаю 1000 знаков в минуту при слепом наборе .. но такая фигня получается!». Сгенерировать еще сотню строк было легко. Понять пост-фактум, зачем они нужны, не дублируют ли уже существующую логику и что сломается после их изменения, было гораздо сложнее. Искусство промта начинало требовать несоразмерных усилий, и не приводило к желаемым результатам.

В каком-то смысле это была полная противоположность попытки №2. У первой ИИ-реализации была простая и понятная проблема: она работала нереально медленно. Текущий вариант был тоже не супер-быстрым, но приемлемым. Главная проблема была куда хуже - с точки зрения долгосрочной поддержки, алгоритм превращался в монстра. Я начинал явственно ощущать, что вообще не понимаю код, который, вообще-то, собираюсь ещё поддерживать в будущем.

Все синтетические тесты этот вариант так и не прошёл по причине того, что доработки и исправления требовали экспоненциально больше кода и сложности. Вариант отправился на ту же скамейку запасных, что и предыдущие.

Попытка №4: ладно, сделаю всё сам

После трёх неудач, каждая из которых походила на попытку съесть слишком большой кусок пирога за один укус, я решил попробовать не изобретать велосипед. А именно - взять старый алгоритм и поработать над ним вручную. В конце концов, на протяжение многих лет этот алгоритм работал почти как часы, падая менее чем в 0,1% всех партий. Возможно, он был не так уж плох и вместо полной переделки нуждался лишь в небольшой «доработке напильником». Почему бы не отрефакторить существующий код, найти слабые места, покрыть их тестами и аккуратно починить.

Сначала всё шло неплохо. Пара раундов рефакторинга, переработка проблемных мест, добавление итеративного выравнивания (зарекомендовавшего себя в прошлых попытках). К сожалению, здесь я допустил еще одну ошибку. По ходу работы я рефакторил код и добавлял новые функции, но недостаточно тщательно проверял каждое изменение. Реализация становилась сложнее, а когда она дошла до состояния, в котором имело смысл запустить нормальные тесты, выяснилось, что она... сложная, медленная и немножко сломанная. Другой маршрут, удивительно похожий результат. «Да тут место проклятое!» - возможно, но это ещё не конец.

И все же, работа над «новым-старым» алгоритмом не была полностью бесполезной. Она помогла изучить несколько перспективных направлений и показала, какие изменения имеют смысл, а на какие, скорее всего, не стоит тратить время. В старом алгоритме есть немало хорошего и его действительно можно взять за основу. Но выпускать его в составе следующего билда игры было явно нельзя.

Отступление №3: тестирование в настоящей игре

По итогам всей проделанной работы (и провалов), появилось ещё одно знание - подход к тестированию нужно серьезно усилить. Небольшие синтетические тесты, конечно, очень полезны, особенно когда нужно воспроизвести конкретный краевой случай. Но выравнивание рельефа связано со слишком большим количеством систем, чтобы полагаться только на простые тесты. Алгоритм может успешно пройти тест «построить дом на склоне», а затем сломаться через 40 минут настоящей игры, потому что два носильщика решили поменяться местами рядом со стройкой, на дороге возле горы, ровно в самый неподходящий момент.

Поэтому основной тестовый стенд я переключил с проверки десятка изолированных случаев на общую стабильность игры. Хорошо, что как-раз на этот случай, у меня есть в распоряжении пара рабочих станций, способных автономно прогнать порядка 10 000 пару-часовых игровых партий за один вечер (и ИИ в игре).

Идея простая - перестать пытаться самостоятельно придумать каждую невероятную комбинацию, а позволить игре воткнуться в них самой. Тысячи симуляций охотно обнаружат ситуации, которые мне никогда не пришло бы в голову оформить как отдельные тесты. Заодно я понял, что нужно искать общие надежные решения, а не собирать коллекцию заплаток всех форм и размеров для каждого конкретного случая.

Следующий вопрос: а каковы реальные цифры, как часто вообще ломается выравнивание рельефа? Ведь если будет сделано исправление, его надо как-то доказать в общем случае, а не в одном конкретном. Игра по своей сути случайна, если горожанин пройдет мимо стройплощадки на тик позже, и не застрянет, игра не крашнется. Нужно опираться на статистику, а не на единичные события.

После нескольких тысяч партий на всех стандартных картах особенно проблемной оказалась «Around the Mountain», а за ней, с большим отрывом, шла «Jealous Neighbours» (впрочем, конкретные названия не так важны). Важно, что это было вполне логично - карт с большим количеством склонов, тесными стартовыми участками и стартовыми позициями рядом с горами не так уж много. На таких картах алгоритм выравнивания работал в поте лица и, соответственно, совершал больше ошибок.

Проблемная карта очень полезна, когда пытаешься избавиться от проблемы. Поэтому я начал собирать более подробные исходные данные для сравнения именно на ней. На старом алгоритме я прогнал около 2700 партий. Код, связанный с выравниванием рельефа, упал 22 раза. Это уже статистически достоверные значения, и они гораздо полезнее, чем ощущение «я тут прогнал десяток матчей руками на разных картах и кажется, новая версия стала падать пореже».

Интересно что подавляющее число падений пришлось на первые 40 минут игры, что логично, ведь после 40-50 минут города в основном уже отстроены и начинается боевая фаза игры. Это позволило сократить длительность тестов до 45минут (взял значение с небольшим с запасом).

Теперь уже можно будет обоснованно говорить, например: «с новым алгоритмом падений стало вдвое меньше». При этом, разумеется, нужно будет следить и за другими ключевыми показателями. Как несложно прикинуть, алгоритм, который вообще ничего не делает и блокирует развитие города - падать не будет, а его итоговый показатель числа крашей окажется равен нулю. Поэтому я также проверял, не пострадали ли основные показатели - развитие города и экономика, число голодных смертей, размеры нанятой армии.

И вот наконец, все варианты алгоритмов выравнивания стало можно сравнивать по показателям, которые действительно отражают упомянутые в начале статьи серьезные проблемы - процент числа падений и типы ошибок. Плюсом, к ним добавилась скорость работы.

Пришлось, конечно, потратить время на автоматизацию и доработку запуска игр на двух рабочих станциях, по локальной сети, но это история для другого раза.

Для полной красоты, оставалось ещё добавить показатель качества выравнивания: насколько ровной была площадка под зданием. Расчёт довольно простой. Берем разницу между самой высокой и самой низкой вершиной внутри площади дома. Чем показатель меньше, тем лучше. У идеально ровной поверхности разница будет равна нулю, а у сильно наклоненной может доходить и до 50. Конечно, одно число точно не описывает внешний вид рельефа, но оно простое, детерминированное и вполне подходит для сравнения тысяч строительных площадок. Абсолютные значения здесь не так важны, важна относительная разница между алгоритмами. Теперь стало можно объективно сравнивать алгоритмы как в среднем, так и, например, по 90-му процентилю (ведь лучше не всегда тот, который в среднем 9 вместо 10, а скорее тот который реже выдает 15).

Попытка №5: сделаю всё сам, но аккуратно

Прошло всего 3 недели и вот мы добрались до текущей попытки. Вместо полной замены старого алгоритма я снова работаю со старыми исходниками. Но теперь у меня есть несколько полезных выводов и инструментов, оставшихся после всех предыдущих попыток. ИИ курит в сторонке. 

Эксперименты с ИИ помогли гораздо точнее сформулировать, что алгоритм должен и не должен делать. Ручные попытки подсказали несколько полезных направлений и вернули веру в костяк старое решения. Синтетические тесты дали быструю обратную связь по конкретным краевым случаям. А массовые автоматические прогоны игры обеспечили стабильную базу и точку отсчета.

Теперь план работ стал довольно скучным, и это, пожалуй, хороший знак. Берём старый алгоритм. Делаем один сравнительно небольшой рефакторинг или улучшение. Запускаем короткие тесты (в роли смуок тестов). Время от времени запускаем автоматические прогоны на стабильность и общую скорость работы. Проверяем, стало ли на самом деле лучше (или не хуже). Повторяем пока не получится. Никаких огромных переписываний и никаких попыток за один заход создать идеальный алгоритм выравнивания рельефа - это всё в прошлом.

Важное отличие этого процесса в том, что теперь каждое изменение должно себя оправдать. Если некое хитроумное улучшение делает поверхность на 1% ровнее, но удваивает время выполнения или повышает частоту падений, то это «не то улучшение которое нам нужно». Если можно что-то убрать и не ухудшить качество - это плюс.

Опыт получился совсем не таким, как в предыдущих попытках. Вместо одного большого нового алгоритма, который либо «работает», либо «не работает», я мог наблюдать, как отдельные изменения двигают отдельные показатели. Некоторые не давали ничего и откатывались. Другие улучшали качество, но портили производительность. Третьи исправляли один синтетический тест, но никак не проявлялись в массовых прогонах. А иногда небольшая правка давала совершенно очевидный скачок вперёд.

Что именно изменилось в алгоритме:

1. Максимальное отделение логики выравнивателя от игры, но без фанатизма. Простой публичный интерфейс.

2. Общий рефакторинг без изменения логики сделал код понятнее и читаемее, не говоря о том, что сам факт ручного рефакторинга является «глубоким чтением» приводящим к лучшему пониманию.

3. Постепенное выравнивание заметно улучшило внешний вид площадок под домами. В некоторых случаях сам процесс стал занимать больше времени, но для неровного рельефа это скорее даже хорошо - сложная неровная местность должна быть частью игры.

4. Алгоритм больше не оценивает вершины, находящиеся за непроходимыми тайлами. Это не входило в первоначальным алгоритм, но дало неплохое улучшение.

5. Алгоритм теперь тщательнее проверяет соседние тайлы, которые были проходимыми.

Сейчас все тесты проходят. В автоматических прогонах старый алгоритм падал примерно 30 раз на 6000 прогонов (большинство карт ровные и там ошибок не было), новый - ни разу. Качество выравнивания улучшилось на 5%. Благодаря простоте исходного алгоритма производительность осталась примерно на первоначальном уровне.

Конечно, ноль падений в 6000 прогонах не означает, что падений не осталось вовсе. Выравнивание рельефа уже показало, как хорошо оно умеет прятать редкие краевые случаи. Но, по сравнению с исходной ситуацией, текущий результат выглядит довольно обнадеживающе. Я настроен осторожно оптимистично.

Конечно, я бы хотел внести ещё несколько улучшений и попробовать пару идей, прежде чем считать работу законченной, но пора уже где-то остановится и зафиксировать улучшение. Если не появится очередной увлекательный кейс, эта версия должна попасть в следующую сборку игры.

Сейчас, оглядываясь назад, я думаю, что главным результатом всей этой эскапады оказался не сам новый алгоритм. Куда важнее - опыт работы с ИИ и спецификациями, тестовые стенды и правильно подобранные метрики. Сам алгоритм можно улучшить или даже вообще заменить. Но теперь решения можно будет принимать на основе базы, а не по нескольким случайным свидетельствам и расплывчатым ощущениям.

Уф. Неплохое получилось путешествие, и всё ради того чтобы некоторые полигоны стали немного ровнее своих соседей :)