Главная » Хабрахабр » [Перевод] Проблема Небраски

[Перевод] Проблема Небраски

image

Кейси Муратори — один из программистов игры The Witness. В процессе разработки игры он публиковал в своём блоге посты о технических задачах, которые перед ним вставали. Ниже представлен перевод одного из таких постов.

Это происходило всегда, от создания простых программных конструкций до высокоуровневых алгоритмов. На протяжении всей моей карьеры программиста неизменным оставался один принцип: я всегда уделяю время тому, чтобы спросить себя — почему я делаю что-то именно так, как делаю? Даже глубоко укоренившиеся идеи часто бывают ошибочными, и подвергая эти идеи сомнениям, мы можем прийти к удивительным и важным открытиям.

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

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

Как я упоминал в первой статье о траве, у него есть приятные глазу свойства. Вопрос «почему» в этом случае достаточно прост: почему мы используем для размещения травы синий шум?
Синий шум — это отличный шумовой паттерн. Но кто сказал, что он принял хорошее решение, выбрав синий шум? Но когда я изменил систему травы The Witness для более эффективного создания синего шума, я просто повторил за тем, кто писал код изначально. В прошлом я использовал синий шум для таких вещей, как трава, но был ли я уверен, что в нынешних условиях он будет оптимальной стратегией расположения? Какую именно задачу он хотел решить, и был ли синий шум лучшим решением?

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

Ряды кукурузы

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

Вот как эти паттерны выглядят с точки зрения обычного игрока:

А вот, наконец, как выглядят паттерны, в каждой точке которых расположены биллборды флоры:

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

На более высоком уровне задача распределения травы может быть сформулирована как «использовать минимальное количество точек для создания визуально приятного покрытия нужной области». Интуитивно мне казалось, что синий шум достаточно эффективно покрывает пространство. Чем меньше затрат, тем больше остаётся сил графической системы для рендеринга других вещей. Я говорю «минимальное количество точек» потому что, как и в случае любой другой задачи рендеринга в реальном времени, чем меньше нужно точек для адекватного с визуальной точки зрения покрытия пространства, тем меньше затрат придётся на рендеринг травы в каждом кадре. А в The Witness есть куча других вещей, которые нужно рендерить в каждом кадре, уж поверьте мне.

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

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

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

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

Если посмотреть из окна на кукурузные поля, то можно заметить, что ряды кукурузы имеют одинаковое свойство: со множества углов они выглядят как кукурузные поля, но взглянув под правильным углом, мы увидим, что они внезапно становятся очень повторяющимися. По причинам, которые я не буду сейчас раскрывать, мне пришлось потратить какое-то время, сидя на заднем сиденье автомобиля в Небраске, путешествуя по самой скучной автостраде в мире (так можно назвать почти любую дорогу в Небраске). Это вполне нормально для кукурузного поля, но не совсем хорошо, когда нужно создать иллюзию плотно растущей травы. Видны длинные и узкие разрывы между рядами.

Из-за похожести на такое свойство кукурузного поля я назвал эту проблему с синим шумом «проблемой Небраски».

Насколько мне известно, это теоретическая проблема, потому что в самих алгоритмах синего шума нет ничего ошибочного. Я не хотел, чтобы проблема Небраски мешала распределению травы. В этом случае практика абсолютно правильна, неадекватна только теория.

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

Экспериментируем с коэффициентом упаковки

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

В предыдущей статье я не вдавался в подробности того, как этот алгоритм выбирает проверяемые точки. Первое, что я попробовал — изменил способ выбора точек алгоритмом подбора соседей. Я просто сделал так, чтобы он брал случайную точку «от r до 2r» в случайном направлении от базовой точки.

Самый простой — единообразно выбирать угол и расстояние в интервале от r до 2r и непосредственно использовать их. Это можно делать разными способами. Но если наносить выбранные таким образом точки, то можно увидеть, что у них есть заметное отклонение к центру окружности:

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

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

Вместо подбора точек в промежутке на расстоянии от r до 2r от базовой точки, я сделал параметр равным 2. Поэтому я решил ввести концепцию «коэффициента упаковки». Таким образом я могу заставить все выбранные точки быть ближе к базовым точкам, теоретически снижая среднее расстояние паттерна и создавая более плотную упаковку:

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

Рассматриваем пробелы

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

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

То есть хотя устранение пробелов в изначальном паттерне может принести плоды, я мог сразу увидеть, как заставить этот способ работать эффективно: на самом деле он увеличивал количество точек, а не устранял проблему с распределением уже имеющихся точек.

Высаживаем траву вдоль линий

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

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

Селективное удаление

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

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

что происходит, но этого не случилось. В тот момент я уже должен был догадаться. Я думаю недостаточно чётко. Стоит учесть, что скорее всего это было в середине среды и я понимал, что ни за что не успею до своего дедлайна среды Witness, поэтому начал немного психовать. Продолжать ли мне напирать или просто позвонить и сказать: «так, у меня есть проблема с алгоритмом, и будь я проклят, если знаю, как её решать. Что мне делать? РОЖДЕСТВО ОТМЕНЯЕТСЯ!». Хорошей вам среды.

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

Рождество не отменяется. Нет, конечно же нет, и я решил — Рождество нельзя отменить. РОЖДЕСТВО ПРОСТО СЛЕГКА ОТКЛАДЫВАЕТСЯ.

Релаксация

Так, ну ладно, никаких проблем. Рождество откладывается. Была среда, так что оно, возможно, состоится в четверг. Или в пятницу. Возвращаемся к работе.

Не можешь расположить точки там, где они нужны? Если вы читали статьи по исследованиям графики, то наверно согласитесь с тем, что я скажу: если люди попадают в ситуацию, когда алгоритм очевидно просто не работает, то обязательно нужно выполнить релаксацию. Если не можешь найти способ поставить точки там, где они необходимы, позволь им разобраться в этом самим. Релаксируй!

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

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

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

Но это была необычная среда, поэтому и ужин тоже должен был стать необычным. Это был вечер среды, и настало время ужина. На самом деле, это была Безумная Среда, то есть настало время безумного ужина среды.

Ограничения по направлениям

Безумная Среда — это особый день недели (часто они случаются даже не по средам, но я не буду говорить, почему), когда Шон Барретт, Фэбиен Гисен, Джефф Робертс и я собираемся, чтобы совершенно безумно провести время: четыре программиста сидят вокруг столика в ресторане и в течение часа обсуждают подробности конкретной технической проблемы. И если это звучит для вас недостаточно безумно, то конкретно в ту Безумную Среду у нас был особый гость — Томми Рефенес, поэтому я знал, что она будет ещё более Безумной, чем раньше.

Так и случилось. Посещение Безумной Среды будет полезным, потому что я смогу обсудить проблему с другими ребятами, и, возможно, у меня появится свежий взгляд.

Если исходный алгоритм случайной генерации не будет создавать ряды, то в результате можно получить паттерны лучше, чем после исправления рядов после процесса, потому что устранение рядов — это глобальная проблема: нужно перемещать точки так, что паттерн при таком изменении может сильно изменяться. После того, как я объяснил им проблему, Фэбиен и Шон пришли к заключению, что в первую очередь лучше всего препятствовать исходному алгоритму подбора соседей создавать линии, таким образом избежав задачи по исправлению паттерна. Если не создавать рядов изначально, то весь паттерн будет безрядным, то есть глобальная проблема просто исчезает.

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

К сожалению, я всё равно получал проблему Небраски. Даже никакая непосредственная ветвь алгоритма подбора соседей не создавала рядов, похоже, соседние ветви сговаривались между собой и всё равно создавали ряды!

Как получается, что каждый алгоритм даёт один и тот же артефакт? Это уже начинало становиться смешным. Что происходит?

Искривлённая шестигранная упаковка

Хотя меня всё ещё не настигло серьёзное озарение, я начал понимать, в чём ошибка. Я сделал шаг назад и задумался о том, что может быть необходимым для создания паттерна без кукурузных рядов, который бы не использовал слишком большого количества точек. Я стал приходить к выводу, что на самом деле мне нужны кривые. Я хотел сделать так, чтобы генерируемые линии всегда придавали точкам изгибы, потому что два кривых ряда точек — это тот паттерн, в котором никогда не будет видно линейных пробелов. Любая случайная расстановка на самом деле может создать взаимное влияние точек, создающее соседние линии, даже на каждой из сторон всего по три точки — этого достаточно, чтобы проявилась проблема Небраски. Поэтому алгоритм, создающий гарантированное отсутствие пробелов, возможно, вообще не случаен, а постоянен.

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

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

Я знал, что наиболее плотной упаковкой для кругов обладают шестиугольные упаковки:

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

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

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

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

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

Смещённая концентрическая упаковка пересечений

Ну ладно, две оси кривизны, никаких проблем. Я просто возьму две окружности и расположу точки по моему паттерну, в котором пересекаются концентрические кольца этих окружностей:

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

Бинго. Именно такое покрытие мне и нужно! Плотное видимое покрытие и абсолютная невозможность заметить пробелы за исключением того места, где вы стоите (что, разумеется, никак не исправить никаким паттерном, кроме как увеличением количества точек и в буквальном смысле полным покрытием пространства). Удалось полностью устранить проблемные области обзора, которые появлялись в алгоритме без смещений:

Есть ещё и бонус — можно использовать гораздо меньше точек, чем я брал для синего шума с пробелами, получать визуально более качественное покрытие:

Почему так много неудач?

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

Но если вспомнить, что такое случайность и как она работает, то можно осознать довольно очевидную истину: случайность никогда не оптимальна. Я начал с довольно хорошего случайного покрытия — с синего шума, и хотел усовершенствовать его. Если взять 100 кубиков и бросить их, то вы не получите 600. Для любого множества критериев чрезвычайно мала вероятность того, что можно подобрать случайным образом множество оптимальных входных данных. Также невозможно никаким образом ограничить случайность. Возможно никогда (можно конечно использовать кости D20, но я хочу, чтобы эта метафора была понятна и не играющим в D&D). Даже если сделать так и перебросить все пятёрки, то придётся делать это семь раз, пока не получите все шестёрки. Даже если взять все кубики и заменить все единицы, двойки, тройки и четвёрки на шестёрки, то есть на кубике останутся только пятёрки и шестёрки, то вы всё равно почти никогда не выбросите 600.

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

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

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

Ниндзя, ловящий червей

Так чему же мы научились, ниндзя программирования? Думаю, тому, что, как говорит пословица, «настойчивый ниндзя всегда ловит червя». Если эта поговорка вам незнакома, то вы скорее всего не так хорошо знаете историческую японскую литературу, как я. И это нормально. Лето уже близко, и вы можете внести в свой летний список чтения кембриджский курс по истории Японии.

Я не знаю точно, будет ли необходимо применять новый паттерн в играх, и не уверен, стоит ли использовать его в The Witness из-за потенциальных проблем работы с другой растительностью. Мне кажется, что в моём случае ловли червя ситуация с паттернами стала моей одержимостью. Но как я объяснял в предыдущем разделе, я многому научился из этого опыта, как это всегда случается, когда я приступаю к технической задаче и отказываюсь сдаваться.

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


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Что случилось с парадоксом Ферми

Парадокс Ферми заключается в том, что вероятность возникновения внеземной цивилизации обычно оценивается довольно высоко, а признаков её существования что-то не видать. Недавно на arxiv появился препринт Сандерса с соавторами «Dissolving the Fermi paradox», который уже успели интерпретировать как отмену этого ...

[Из песочницы] Несколько причин забыть PascalABC.Net

Времена старого и доброго Pascal закончились. Пришло время новых сред разработки под этот язык. Появилось множество диалектов этого языка. Хотя все они имели что-нибудь общее. Сегодня поговорим о диалекте PascalABC.Net и о том почему же стоит от него отказаться, если ...