Основы простого графического 3D движка в Excel (вспоминаем геометрию)

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

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

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

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

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

Для написания кода пришлось со скрипом вспоминать школьную геометрию (читай — учить с нуля). В этом очень помогли статьи с Хабра, которые я буду приводить а тексте по мере их актуальности.

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

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

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

Перенесем координаты отрезков на отдельный лист в порядке X1, Y1, X2, Y2

В первой версии движка каждую итерацию луч проверял столкновение со всеми имеющимися отрезками. Не трудно предположить, что это закончилось полным провалом. Процесс отрисовки изображения занимал несколько минут. Сейчас карта состоит из 35 отрезков. А если бы она состояла из тысячи? Согласитесь, это выглядит более правдоподобно в формате компьютерных игр. Катастрофа.

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

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

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

Для прохода по координатам отрезка я использовал следующую формулу:

X(Y) = X1(Y1) * (1 — STEP) + X2(Y2) * STEP,

где STEP — коэффициент, который определяет длину одного шага между координатами отрезка.

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

Код получился слишком длинным, поэтому выкладывать его в чистом виде не очень оправданно. В конце статьи я приложу Excel файл, в котором можно будет лицезреть все своими глазами (модуль Editor).

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

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

Наконец, полученные значения направляются на отдельный лист в порядке: X1, Y1, X2, Y2, Сектор по оси X, Сектор по оси Y. Рядом выводятся данные из массива с наполнением секторов. Получается следующее:

Теперь карта состоит аж из 201 отрезка, но разбиение на секторы позволит программе работать быстрее.

На этом формирование данных уровня закончено. По крайней мере сейчас, когда нет ни дверей, ни активных стен, ни предметов, ни врагов etc.

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

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

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

Для начала нужно создать два вектора от точки луча к начальным и конечным точкам каждого отрезка в секторе. Далее, посчитать скалярное и псевдоскаларное произведения этих двух векторов. Если скалярное произведение <= 0 и псевдоскалярное произведение == 0, то это значит, что точка лежит на отрезке.

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

Для поиска столкновений создал два класса. Класс Vector, который содержит два поля X, Y, а также метод, который создаёт вектор.

А также класс VectorActions, который считает произведения векторов:

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

Сперва необходимо инициализировать некоторые переменные, которые понадобятся для рендеринга. Для этого я создал два класса: Config и Game. В модуле Main надо прописать такой код:

Все данные берутся с отдельного листа:

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

Следующая процедура проверяет столкновения точки с отрезками:

Функция возвращает целочисленное значение (номер отрезка в массиве), которое определяет цвет стены при рендеринге.

Пришлось перенести карту с бумаги в Doom Builder (очень странные манипуляции), чтобы показать итоги.

Разрешение: 240Х320.

Ради интереса я установил разрешение 800Х600:

Да, этот движок генерирует какое-то псевдотрехмерное изображение. Но имеются и проблемы.

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

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

В настоящее время, когда луч встречает пустой сектор, он не пропускает его, а просто движется дальше и каждую итерацию проверяет один и тот же сектор. Для того, чтобы этого избежать, я пишу алгоритм, который будет вообще пропускать пустые сектора. Это значительно сократит количество итераций. Для этого необходимо высчитывать тангенс или котангенс угла между лучом и проекцией на ось X или Y. Когда-нибудь я напишу и об этом. Опять же, если кто-нибудь посоветует еще какие-нибудь способы сделать работу алгоритма быстрее, пишите.

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

Признаться, я это все потихоньку переписываю на C # с фреймворком MonoGame и уже начинаю выгорать. Хочется бросить и уйти копаться в Unity. Но хобби есть хобби:)

Прикладываю файл:

До скорых встреч!