Скриншот экрана игры

Эта статья посвящена тому, как я смог написать 3D-движок только на формулах Excel. Я реализовал следующий функционал:

• бесконечная процедурно генерируемая карта лабиринта
• рендеринг трассировкой лучей в реальном времени
• вычисление окклюзии
• рендеринг простейшего освещения
• шейдер освещения и вычислений
• движок естественного движения
• в 3D-движке не используются макросы

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

Можете скачать файл и протестировать его самостоятельно!

Файлы

• Файл без vba: http://public.cbel.free.fr/?file=Doom.xlsx
• Файл с vba для перехвата нажатий клавиш: http://public.cbel.free.fr/?file=Doom.xls-v1.1.xlsm
• Файл с vba и высоким разрешением: http://public.cbel.free.fr/?file=Doom-HD.xls-v1.1.xlsm
• Файл с vba и кнопками вместо горячих клавиш: http://public.cbel.free.fr/downloads/?file=Doom.xls-Buttons-v1.1.xlsm

Контекст

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

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

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

Получив многолетний опыт работы с Excel, мы уже поняли, что единственное ограничение формулы Excel — недостаток способов ввода-вывода.

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

Как бы то ни было, эта работа — не просто какое-то хвастовство… У меня были для неё серьёзные причины.

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

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

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

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

При использовании в бизнесе формулы обладают следующими преимуществами перед макросами:

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

Примечание: эти пункты в основном относятся к процедурам, используемым как макросы; дополнительная функция, написанная на VBA, может увеличить эффективность, не снижая качества.

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

Если конкретнее, то я нашёл всего два случая, когда потребовался VBA:

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

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

Карта

Моя электронная таблица должна была стать игрой в стиле Doom в лабиринте.

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

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

Для создания случайно генерируемой карты нам нужно быть последовательными, поэтому функцию rand() использовать нельзя, ведь мы не можем контролировать начальное состояние (seed) генератора случайных чисел.

Начальные состояния генератора случайных чисел должны быть позициями (x;y) на карте, чтобы мы могли получать разные значения для каждой позиции, и мы не можем получить результат предыдущего случайного числа как начальное состояние для следующего, или нам придётся хранить всю карту с самого начала.

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

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

Тогда я обнаружил метод средних квадратов (middle-square method), который на самом деле не очень «случаен», потому что в нём используются последовательные начальные состояния. Но он подсказал мне идею того, что можно брать десятичную часть любого другого вычисления.

Я выяснил, что если брать десятичные части sin(x)+cos(y), то наконец-то получаются красивые числа без какого-либо прослеживаемого паттерна, а время вычислений при этом на удивление малО.

Для получения десятичных частей математические функции mod() и floor() гораздо более эффективны по сравнению с текстовой функцией подстроки mid().

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

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

Плотностью размещения стен управляют два параметра.

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

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


Так, похоже, мы в аду

Трассировщик лучей

Трассировщик лучей должен определять для каждого пикселя экрана, какой первой поверхности касается луч, и получать от неё информацию (расстояние, угол падения света, цвет и т.д.).

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

Окклюзия

Первым сложным моментом будет нахождение первого объекта на пути каждого луча.

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

То есть процесс можно упростить до горизонтального «радара» в одном измерении.

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

Определение того, какую стену нужно проверять — это всего лишь тригонометрическая задача.

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

Одно из ограничений Excel заключается в отсутствии условного цикла и для экономии времени можно только пропускать тело цикла. Поэтому нам нужно ограничить максимальное расстояние проверки, считая, что если на этом расстоянии стена не найдена, то её нет.

Пол и потолок

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

Отдельный лист изменяет расстояние до пола или потолка в зависимости от вертикального угла.

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

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

Освещение

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

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

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

Для каждого угла радара мы получаем угол между лучом и ближайшей найденной стеной.

Коэффициент отражения — это просто функция угла.

В конце концов освещение становится результатом функции коэффициента расстояния, потолка/пола или разрешения стен, коэффициента отражения и коэффициента шейдера освещения.

Экран дисплея

Эффективный дисплей реализуется с помощью условного форматирования — градиент цвета зависит от значения ячейки.

Сокрытие значения выполняется форматированием ячейки.

Коллизии со стенами

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

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

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

Оказалось, что довольно сложно обработать все возможные варианты стены и позиций игрока относительно этой стены.

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

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

Враги

Привет, красное привидение!

Графический рендеринг

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

Целый отдельный лист посвящён вычислению формы сфер с учётом горизонтального радиуса и вертикальной высоты овоида. Для анимирования существа используется соотношение высоты/ширины.

В рендеринге стен и потолка используется градиент только по одному цвету, однако Excel позволяет использовать два последовательных (не сливающихся) градиента. Поэтому врагов можно отображать другим цветом. Для этого градиента можно использовать диапазон значений ниже 0, при том, что значение 0 — это чёрный цвет.

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

На границе сферы низкая толщина сохраняет только значение цвета по умолчанию стены за ней с отрицательным коэффициентом для превращения его в цвет монстра. Фильтр цвета освещения обеспечивает прозрачность на границе сферы.

Здесь вычисления тоже производятся в горизонтальной плоскости, а максимальный объём вычислений подготавливается перед завершением 3D-вычислений для каждого пикселя.

Поведение врагов

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

Чтобы позиция, скорость и ускорение были непрерывными (для плавного движения), я сделал траекторию своего рода конечным фракталом большого круга с добавленными к нему небольшими круговыми вариациями. Коэффициент соотношения между кругами (и даже соотношение x/y) случаен и ненатурален, поэтому траектория никогда не самозацикливается. Чтобы получить хороший случайный генератор детерминированных траекторий, я создал отдельный лист, отображающий траекторию.

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

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

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

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

Атаки врагов

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

Область видимости каждого монстра вычисляется на вкладке радара с учётом расположения стен.

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

Это создаёт эффект наносимого игроку урона — простой эффект негативного цвета во весь экран.

Добавлен также ещё один эффект — отмена рендеринга всех остальных врагов при нанесении урона игроку.

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

Атаки игрока

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

Эта упрощённая модель позволяет игроку предотвратить атаку врага, снизив его жизнь до нуля.

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

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

Смерть и перезапуск

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

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

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

Сдвигание вниз — это простое смещение шейдера освещения, в который добавлены другие сообщения, например, рекорды (high score) и перезапуск игры.

Очки должны отрисовываться с помощью пикселей шрифтом очень низкого разрешения.

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