Думаю эта статья может быть кому нибудь интересна.
или Зарегистрируйся
Эта статья посвящена тому, как я смог написать 3D-движок игры Doom только на формулах Excel. Я реализовал следующий функционал:
Можете скачать файл и протестировать его самостоятельно!
Поначалу, какой бы мудрой ни казалась эта фраза, упоминание в этом списке Excel выглядело глупо…
Затем, после изучения машины Тьюринга, фраза стала для нас полностью верной, хотя и не вполне реализуемой.
Получив многолетний опыт работы с Excel, мы уже поняли, что единственное ограничение формулы Excel — недостаток способов ввода-вывода.
Но множество задач, решаемых исключительно формулами, по-прежнему выглядит впечатляюще.
Как бы то ни было, эта работа — не просто какое-то хвастовство… У меня были для неё серьёзные причины.
Электронные таблицы — это мощный инструмент, которому должен научиться каждый, ведь его можно использовать почти в любых деловых задачах.
Однако когда большинство людей доходят до решения более сложных задач, они стремятся использовать язык VBA, даже не понимая толком, зачем.
А начав изучать его, они пытаются использовать его для решения любых видов задач, даже для простого поиска или визуализации.
Сегодня я преподаю Excel, поэтому постараюсь объяснить людям, почему написание макроса на VBA для решения любой задачи без хорошего знания программирования — это не только пустая трата времени, но и серьёзный риск снижения качества электронной таблицы.
При использовании в бизнесе формулы обладают следующими преимуществами перед макросами:
Вот так я пришёл к написанию своей игры: она стала наглядной демонстрацией того, что макросы обычно не нужны даже для решения самых сложных задач.
Если конкретнее, то я нашёл всего два случая, когда потребовался VBA:
Можно было создать для неё постоянную, построенную вручную карту, возможно, зацикленную по краям, но она бы потребовала дополнительного места, поисков и изначальной разработки дизайна.
В то же время, гораздо более интересной целью мне казалась идея процедурно генерируемой бесконечной карты.
Для создания случайно генерируемой карты нам нужно быть последовательными, поэтому функцию rand() использовать нельзя, ведь мы не можем контролировать начальное состояние (seed) генератора случайных чисел.
Начальные состояния генератора случайных чисел должны быть позициями (x;y) на карте, чтобы мы могли получать разные значения для каждой позиции, и мы не можем получить результат предыдущего случайного числа как начальное состояние для следующего, или нам придётся хранить всю карту с самого начала.
Обычные хэш-функции, несмотря на обеспечение высокого качества случайных чисел, оказались слишком затратными, поэтому мне нужно было найти другое решение.
Эксперименты с фрактальным генератором тоже оказались довольно затратными и давали интересные результаты только для небольшой части карты.
Тогда я обнаружил метод средних квадратов (middle-square method), который на самом деле не очень «случаен», потому что в нём используются последовательные начальные состояния. Но он подсказал мне идею того, что можно брать десятичную часть любого другого вычисления.
Я выяснил, что если брать десятичные части sin(x)+cos
, то наконец-то получаются красивые числа без какого-либо прослеживаемого паттерна, а время вычислений при этом на удивление малО.
Для получения десятичных частей математические функции mod() и floor() гораздо более эффективны по сравнению с текстовой функцией подстроки mid().
Я стремился сделать карту похожей на крысиный лабиринт, поэтому создавал блоки не сплошными, чтобы они походили не на пещеры (в стиле Minecraft), а на лабиринт.
То есть нам нужны тонкие стены с двумя возможными стенами для каждого квадрата. Тогда мы сможем брать два блока чисел вместе с тем же случайным значением.
Плотностью размещения стен управляют два параметра.
С учётом этих правил мы можем или отображать лабиринт, или тестировать любую стену с заданной позицией с помощью трассировки лучей.
Стоит заметить, что карта «плоская», без подъёмов и спусков. Можно было добавить рельеф с помощью генератора рельефа (подошёл бы алгоритм Diamond-Square, потому что его можно написать без рекурсивной функции), но весь последующий процесс сильно облегчило бы вырезание отверстий в полу и потолке с дополнительным значением уровня.
Так, похоже, мы в аду
Кроме того, трассировщику лучей требуется дополнительный луч, распространяющийся из этой точки (отражения, прозрачность), что напрямую увеличивает вычислительные затраты.
Поскольку лабиринт на самом деле плоский с горизонтальными стенами, то ближайшая найденная стена будет одинаковой для всех пикселей одного столбца.
То есть процесс можно упростить до горизонтального «радара» в одном измерении.
Тогда у нас нет иного выбора, кроме как проверять луч на первой вероятной стене, потом на второй вероятной, и так далее, пока мы не найдём нужную.
Определение того, какую стену нужно проверять — это всего лишь тригонометрическая задача.
И поскольку у нас всего два типа стен, мы можем тестировать оба типа, а потом сохранять только ближайшую.
Одно из ограничений Excel заключается в отсутствии условного цикла и для экономии времени можно только пропускать тело цикла. Поэтому нам нужно ограничить максимальное расстояние проверки, считая, что если на этом расстоянии стена не найдена, то её нет.
Отдельный лист изменяет расстояние до пола или потолка в зависимости от вертикального угла.
Затем для каждого пикселя мы определяем, дальше ли стена, чем потолок или пол, и соответствующим образом задаём цвет пикселя.
Эффективное сравнение реализовано использованием только проекции расстояния до стены и до пола/потолка по оси камеры. Конечное расстояние затем получается с помощью предварительно вычисленного коэффициента расстояния в шейдере расстояний. Постоянные предварительно вычисленные значения нужны для экономии ресурсов.
Когда поверхность точно горизонтальна к лучу света, также добавляется отражение.
Стена может быть только горизонтальной (если добавить наклон, то он просто смещает окно экрана вверх и вниз, не поворачивая камеру)
Для каждого угла радара мы получаем угол между лучом и ближайшей найденной стеной.
Коэффициент отражения — это просто функция угла.
В конце концов освещение становится результатом функции коэффициента расстояния, потолка/пола или разрешения стен, коэффициента отражения и коэффициента шейдера освещения.
Сокрытие значения выполняется форматированием ячейки.
Кроме того, игрок не должен прилипать к стене при контакте с ней. Он должен двигаться, скользя вдоль стены, пока не попадёт в угол.
Также необходимо соблюдать минимальное расстояние между стеной и игроком, чтобы избежать графических проблем и придать стенам толщину.
Оказалось, что довольно сложно обработать все возможные варианты стены и позиций игрока относительно этой стены.
Изучено 25 вариантов и к ним привязано три возможных исхода (для каждой оси смещения), чтобы получать результаты за как можно меньшее количество проверок.
Несмотря на то, что это казалось самой короткой частью игры, таблица смещений стала самой сложной в реализации. (В 10 раз больше, чем карта, в два раза больше кода распознавания стен.)
3D-движок игры Doom, написанный на формулах MS Excel
Для просмотра ссылки ВойдиЭта статья посвящена тому, как я смог написать 3D-движок игры Doom только на формулах Excel. Я реализовал следующий функционал:
- бесконечная процедурно генерируемая карта лабиринта
- рендеринг трассировкой лучей в реальном времени
- вычисление окклюзии
- рендеринг простейшего освещения
- шейдер освещения и вычислений
- движок естественного движения
- в 3D-движке не используются макросы
Можете скачать файл и протестировать его самостоятельно!
Файлы
- Файл без vba: Для просмотра ссылки Войди
или Зарегистрируйся - Файл с vba для перехвата нажатий клавиш: Для просмотра ссылки Войди
или Зарегистрируйся - Файл с vba и высоким разрешением: Для просмотра ссылки Войди
или Зарегистрируйся - Файл с vba и кнопками вместо горячих клавиш: Для просмотра ссылки Войди
или Зарегистрируйся
Контекст
Учитель информатики однажды сказал нам: «любые вычисления можно выполнить в любом языке программирования, даже через формулы электронной таблицы».Поначалу, какой бы мудрой ни казалась эта фраза, упоминание в этом списке Excel выглядело глупо…
Затем, после изучения машины Тьюринга, фраза стала для нас полностью верной, хотя и не вполне реализуемой.
Получив многолетний опыт работы с Excel, мы уже поняли, что единственное ограничение формулы Excel — недостаток способов ввода-вывода.
Но множество задач, решаемых исключительно формулами, по-прежнему выглядит впечатляюще.
Как бы то ни было, эта работа — не просто какое-то хвастовство… У меня были для неё серьёзные причины.
Электронные таблицы — это мощный инструмент, которому должен научиться каждый, ведь его можно использовать почти в любых деловых задачах.
Однако когда большинство людей доходят до решения более сложных задач, они стремятся использовать язык VBA, даже не понимая толком, зачем.
А начав изучать его, они пытаются использовать его для решения любых видов задач, даже для простого поиска или визуализации.
Сегодня я преподаю Excel, поэтому постараюсь объяснить людям, почему написание макроса на VBA для решения любой задачи без хорошего знания программирования — это не только пустая трата времени, но и серьёзный риск снижения качества электронной таблицы.
При использовании в бизнесе формулы обладают следующими преимуществами перед макросами:
- Их быстрее писать для любого человека, если он не профессиональный программист-аналитик
- Их проще поддерживать любому человеку, а не только профессиональному программисту. (Чаще всего макросы становятся бесполезны после ухода их разработчика.)
- Гарантированное качество благодаря постоянной проверке значений. (Принудительное применение техники «разработка через тестирование»)
- Они более эффективны в долговременной перспективе благодаря процессу создания формул в стиле «думай, прежде чем писать».
- И они совершенно точно гораздо лучше интегрированы в сам инструмент создания электронных таблиц и следуют изначальному паттерну разработки электронных таблиц, в то время как макросы часто оказываются специфическими конструкциями, требующими в дальнейшем активной поддержки.
Вот так я пришёл к написанию своей игры: она стала наглядной демонстрацией того, что макросы обычно не нужны даже для решения самых сложных задач.
Если конкретнее, то я нашёл всего два случая, когда потребовался VBA:
- Добавление специфического ввода или вывода (как я сделал здесь для получения событий клавиш), потому что формула всегда ограничена изменениями в самой ячейке
- Некоторые сложные задачи (например, оптимизация), в которых вычисления занимают слишком много времени и/или пространства. Но такие задачи довольно редки в реальной жизни.
Карта
Моя электронная таблица должна была стать игрой в стиле Doom в лабиринте.Можно было создать для неё постоянную, построенную вручную карту, возможно, зацикленную по краям, но она бы потребовала дополнительного места, поисков и изначальной разработки дизайна.
В то же время, гораздо более интересной целью мне казалась идея процедурно генерируемой бесконечной карты.
Для создания случайно генерируемой карты нам нужно быть последовательными, поэтому функцию rand() использовать нельзя, ведь мы не можем контролировать начальное состояние (seed) генератора случайных чисел.
Начальные состояния генератора случайных чисел должны быть позициями (x;y) на карте, чтобы мы могли получать разные значения для каждой позиции, и мы не можем получить результат предыдущего случайного числа как начальное состояние для следующего, или нам придётся хранить всю карту с самого начала.
Обычные хэш-функции, несмотря на обеспечение высокого качества случайных чисел, оказались слишком затратными, поэтому мне нужно было найти другое решение.
Эксперименты с фрактальным генератором тоже оказались довольно затратными и давали интересные результаты только для небольшой части карты.
Тогда я обнаружил метод средних квадратов (middle-square method), который на самом деле не очень «случаен», потому что в нём используются последовательные начальные состояния. Но он подсказал мне идею того, что можно брать десятичную часть любого другого вычисления.
Я выяснил, что если брать десятичные части sin(x)+cos
, то наконец-то получаются красивые числа без какого-либо прослеживаемого паттерна, а время вычислений при этом на удивление малО.Для получения десятичных частей математические функции mod() и floor() гораздо более эффективны по сравнению с текстовой функцией подстроки mid().
Я стремился сделать карту похожей на крысиный лабиринт, поэтому создавал блоки не сплошными, чтобы они походили не на пещеры (в стиле Minecraft), а на лабиринт.
То есть нам нужны тонкие стены с двумя возможными стенами для каждого квадрата. Тогда мы сможем брать два блока чисел вместе с тем же случайным значением.
Плотностью размещения стен управляют два параметра.
С учётом этих правил мы можем или отображать лабиринт, или тестировать любую стену с заданной позицией с помощью трассировки лучей.
Стоит заметить, что карта «плоская», без подъёмов и спусков. Можно было добавить рельеф с помощью генератора рельефа (подошёл бы алгоритм Diamond-Square, потому что его можно написать без рекурсивной функции), но весь последующий процесс сильно облегчило бы вырезание отверстий в полу и потолке с дополнительным значением уровня.
Так, похоже, мы в аду
Трассировщик лучей
Трассировщик лучей должен определять для каждого пикселя экрана, какой первой поверхности касается луч, и получать от неё информацию (расстояние, угол падения света, цвет и т.д.).Кроме того, трассировщику лучей требуется дополнительный луч, распространяющийся из этой точки (отражения, прозрачность), что напрямую увеличивает вычислительные затраты.
Окклюзия
Первым сложным моментом будет нахождение первого объекта на пути каждого луча.Поскольку лабиринт на самом деле плоский с горизонтальными стенами, то ближайшая найденная стена будет одинаковой для всех пикселей одного столбца.
То есть процесс можно упростить до горизонтального «радара» в одном измерении.
Тогда у нас нет иного выбора, кроме как проверять луч на первой вероятной стене, потом на второй вероятной, и так далее, пока мы не найдём нужную.
Определение того, какую стену нужно проверять — это всего лишь тригонометрическая задача.
И поскольку у нас всего два типа стен, мы можем тестировать оба типа, а потом сохранять только ближайшую.
Одно из ограничений Excel заключается в отсутствии условного цикла и для экономии времени можно только пропускать тело цикла. Поэтому нам нужно ограничить максимальное расстояние проверки, считая, что если на этом расстоянии стена не найдена, то её нет.
Пол и потолок
Чтобы определить потолок и пол, нам достаточно определить, где заканчивается стена.Отдельный лист изменяет расстояние до пола или потолка в зависимости от вертикального угла.
Затем для каждого пикселя мы определяем, дальше ли стена, чем потолок или пол, и соответствующим образом задаём цвет пикселя.
Эффективное сравнение реализовано использованием только проекции расстояния до стены и до пола/потолка по оси камеры. Конечное расстояние затем получается с помощью предварительно вычисленного коэффициента расстояния в шейдере расстояний. Постоянные предварительно вычисленные значения нужны для экономии ресурсов.
Освещение
Конечное освещение берётся из шейдера освещения, представляющего собой свет факела, в направлении камеры (и оружия).Когда поверхность точно горизонтальна к лучу света, также добавляется отражение.
Стена может быть только горизонтальной (если добавить наклон, то он просто смещает окно экрана вверх и вниз, не поворачивая камеру)
Для каждого угла радара мы получаем угол между лучом и ближайшей найденной стеной.
Коэффициент отражения — это просто функция угла.
В конце концов освещение становится результатом функции коэффициента расстояния, потолка/пола или разрешения стен, коэффициента отражения и коэффициента шейдера освещения.
Экран дисплея
Эффективный дисплей реализуется с помощью условного форматирования — градиент цвета зависит от значения ячейки.Сокрытие значения выполняется форматированием ячейки.
Коллизии со стенами
Игрок не должен проходить сквозь стены, иначе это разрушит весь смысл лабиринта.Кроме того, игрок не должен прилипать к стене при контакте с ней. Он должен двигаться, скользя вдоль стены, пока не попадёт в угол.
Также необходимо соблюдать минимальное расстояние между стеной и игроком, чтобы избежать графических проблем и придать стенам толщину.
Оказалось, что довольно сложно обработать все возможные варианты стены и позиций игрока относительно этой стены.
Изучено 25 вариантов и к ним привязано три возможных исхода (для каждой оси смещения), чтобы получать результаты за как можно меньшее количество проверок.
Несмотря на то, что это казалось самой короткой частью игры, таблица смещений стала самой сложной в реализации. (В 10 раз больше, чем карта, в два раза больше кода распознавания стен.)
