Рецепты отладки. Позор для математика.

Эта история не является большим секретом, я её озвучивал в своё время на канале #ff и на GDP, но за истечением срока давности (10 лет) за сделанное мною математическое преступление хочется покаяться перед всем читающим меня сообществом и раскрыть страшную правду об одном алгоритме. Речь сегодня пойдет о вещественной арифметике в самом худшем её проявлении – двоичном.

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

В процессе подготовки уровня к игре происходил расчет Y Aligned призм (Y вверх), причем он велся на разных уровнях иерархии сцены – от конкретных мелких объектов до узловых нод, которые собирали под собой целые комнаты или отсеки сцены. С расчётом нижней и верхней границы призмы проблем, очевидно, не возникало, но стоял вопрос: как правильно развернуть сие чудо геометрической мысли относительно вертикальной оси Y.

Имеет место быть теорема, в которой доказывается, что оптимальным вариантом построения такой призмы в 2D проекции на XZ является призма с наименьшим периметром. Ну а такая призма обязательно имеет ребро, на котором находятся минимум 2 вершины множества точек сцены (очевидно, что это будет 2 точки, которые принадлежат выпуклой оболочке).

hull1.jpg

Соответственно, рождается следующий чудо алгоритм – безупречный с точки зрения математики, но, как оказалось потом, совершенно неприемлемый с точки зрения реализации:

1. Взять множество точек на плоскости.
2. Построить для них выпуклую оболочку.
3. Последовательно приложить призму к выпуклой оболочке таким образом, чтобы она “обжала” оболочку и при этом одно из рёбер оболочки лежало на ребре призмы (напомню, речь идёт о проекции на плоскость XZ).
4. Выбрать среди таких призм ту, у которой наименьший периметр.

Чудо задача была реализована (несколько Ч/Д) и запущена в пайплайн преобразования сцен. Вначале все шло хорошо, но как только сцены стали более-менее крупными, обнаружилось 2 ключевые проблемы: алгоритм работал непозволительно долго (это ещё можно было бы стерпеть) и для высокоуровневых нод сцены, когда призма считалась для нескольких десятков или даже сотен тысяч точек, алгоритм начинал давать сбои. Причина была банальна – когда несколько тысяч точек собираются на пятачке размером в пять миллиметров, построить там правильную оболочку банально не получалось из-за проблем с точностью.

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

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

divider.jpg
И еще чуть пониже…
divider.jpg

Итак. Новый алгоритм звучал так:

Для всех углов от 0 до 90 градусов с шагом 0.5:
- построить прямоугольник в основании призмы;
- “обжать” им все множество точек, поступившее на вход;
- проверить периметр на минимальность.

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

На самом деле речь не о том. На этот рассказ меня натолкнули три недавно прошедших события – это рассказ finder про искусственный интеллект, игра в Mass Effect дома и секс на работе, что опятьвашуматьуровеньнепроходим из-за того, что труп на входе в лифт помешал правильной работе системы построения путей.

Посмотрим на Mass Effect. Хороший добротный проект, Unreal Engine 3, все дела. Но обратите внимание, как герой ездит в лифте? Он подходит с дружками к лифту, нажимает кнопку… Вуаля. В следующий момент времени все трое телепортируются в лифт на готовые позиции (герой в центре), камера фиксируется на одном расстоянии от героя, ею можно управлять в пределах сферы, но нельзя двигать ближе или дальше. Отличное решение. Сэкономлено несколько человеко-месяцев на решение проблем с заходом в лифт нескольких персонажей, устранены все проблемы с камерой в лифте, решены вопросы потенциальной непроходимости пространства если что-то там случайно оказалось около дверей.

Посмотрим на игру *****. 100% физичность прохождения пространства (млять, четвертый год объясняю разным командам, что процедура “взрыв освобождает пролом в стене” делается не только физическим воздействием взрывной волны на куски камней, но и обязательной скриптовой расчисткой прохода). Гибкая и практически бесконечная камера, которая при движении лифта успевает задеть за все элементы наружного и внутреннего декора. Ну и сам заход в лифт; он за несколько лет работы математически вылизан на 100%. Только выглядит все равно по идиотски и иногда сообщает, что путь не найден, дверь не может быть открыта, и вообще game over, ибо нефиг сваливать трупы и ящики в этой точке. Кстати, при движении лифта к стенке лучше не подходить – можно вусмерть убиться о полигон шахты.

Еще пример из жизни. В одном из более поздних прототипов делалось залезание персонажа на стены. Автоматическое и ручное тегирование “залезабельных” ребер, автоматическое определение позиции персонажа под ребром и туева хуча ИК и других процедурных доводок для того, чтобы залезание не выглядело как посадка в инвалидную коляску. А вот хрен вам. Одно ребро из сотни на экспорте все равно детектируется неправильно, персонаж ведет себя хуже инвалида, ну а если встать к ребру боком, то, мама дорогая, начинаешь подозревать и главного героя, и программиста, писавшего залезание, в нетрадиционных связях.

Как предлагают делать в мощном и продвинутом движке с официальной стоимостью около полумиллиона недевальвированных долларов? Для реализации процедуры залезания делается геометрический  триггер в форме вертикальной буквы Z. Высота триггера такова, что герой правильно забирается на него по обычной анимации. Далее гейм-дизайнер вставляет триггер в редактор и прислоняет его к стене. Если высота триггера и высота стены не совпадают, он идет бить морду художнику. Если совпадают – то это означает, что в данной точке пространства герой может залезть на стену. Далее все просто. Если герой оказывается на нижней площадке триггера, ему доступна операция “подпрыгнуть и залезть”. При нажатии клавиши герой мягко репозиционируется в правильную точку, заданную в настройках триггера, выполняет анимацию, и оказывается наверху. Слезание с верхней части триггера реализуется аналогично.

z_up.jpg

Решение изящное, простое, и экономит вам месяцы сложных математических рассчетов.

Я не спорю, что математические алгоритмы нужны, и что очень многие вещи в играх делаются интересными именно без подобных “подстав”. Но когда в очередной раз вы отлаживаете математически безупречный, но сбившийся вусмерть алгоритм потомучтосцуко на таком наборе входных данных он ну никак не может отработать правильно (или, например, красиво) для игрока, подумайте, а нужна ли вам правильная математика в этом месте кода?

Приятной вам отладки.

  • CEMEH

    По мне, такие грамотные хаки – и есть важнейшая часть профессионализма. Подозреваю, люди часто занимаются сложной математикой не потому, что так уж к ней стремятся, а потому что не видят простых решений. Делать сложно – просто, делать просто – сложно, как всегда.
    Я вот когда молодой был, придумывал математически сложные алгоритмы для теней, скажем (подозреваю, в родных грузовичках на них до сих пор матерятся). Матерый профессионал бы просто решил проблему.

  • Sergei_am

    Лично имел проблемъ с convex hull-ом у нас, спустя 4-5 месяцев дошол до мъсли что все ето бъло очень ненужно и лишне – кто-то пътался подойти с точки зрения математики к чисто гейм-дизайнерской проблемме (снаппинг обьектов на карте) и въшла гора никому ненужного кода.

    У меня не раз въходило, что специфичнъй хак решал проблему намного бъстрее, качественее и более бъстро в плане времени на имплементацию, чем аналогичное ‘правильное’ движковое решение. В результате ето уже не движок, а движок-под-нашу-игру, но я лично етим скорее доволен, чем наоборот.
    Те же тени – кучи Mathematic-и, несколько версий ‘правильнъх’ алгоритмов, много слайдеров, которъе можно крутить пер-прожект, чтобъ сделать баги алгоритма незаметнъми.
    В конце – один мощнъй хак послал все ето к черту – как обжать облако точек трапецией, чтобъ качество шедоумепа бъло близкое к оптимальному? Ну, так как мъ знаем тип сценъ, вместо чтобъ строить всякие анализъ облака, взяли да спустили камеру на землю внизу, ‘посмотрели’ ей к горизонту и оттуда обжали облако – и етого бъло достаточно.
    Я очень радостно закомитил сорс на минус несколько сот строк.

  • lordmaze

    > а потому что не видят простых решений. Делать сложно – просто, делать просто – сложно, как всегда.

    Ну иногда это просто люди такие – им не надо давать заниматься прикладным задачами вообще. Им надо заниматься R&D и придумывать большое и светлое.

  • Pingback: highly professional scums » Blog Archive » Про Unit тесты вообще и TDD в частности()