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

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

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

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

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

Да, это фото! На телефон. В 2020 году. Но другого выхода нет из-за строгой политики безопасности.
Да, это фото! На телефон. В 2020 году. Но другого выхода нет из-за строгой политики безопасности.

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

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

Создание уровня

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

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

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

За почерк извините=)
За почерк извините=)

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

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

В первой версии движка каждую итерацию луч проверял столкновение со всеми имеющимися отрезками. Не трудно предположить, что это закончилось полным провалом. Процесс отрисовки изображения занимал несколько минут. Сейчас карта состоит из 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, а также метод, который создаёт вектор.

Option Explicit Public X As Variant, Y As Variant Sub createVector(X1 As Variant, Y1 As Variant, X2 As Variant, Y2 As Variant) X = X2 - X1 Y = Y2 - Y1 End Sub

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

Option Explicit Public Vector1 As New Vector, Vector2 As New Vector 'скалярное произведение векторов Public Function getScalarProd() As Variant getScalarProd = Vector1.X * Vector2.X + Vector1.Y * Vector2.Y End Function 'косое произведение векторов Public Function getCrossProd() As Variant getCrossProd = Vector1.X * Vector2.Y - Vector2.X * Vector1.Y End Function

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

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

Option Explicit Public Const ED = "EDITOR" Public Const M = "MAP" Public Const CONF = "CONFIG" Public Const REND = "RENDER" Public Config As New Game, Elf As New Player Sub initializeVariables() 'настройка конфигурации Config.MapNumber = Sheets(CONF).Range("B10") Config.rayLength = Sheets(CONF).Range("B9") Config.RayStep = Sheets(CONF).Range("B8") Config.ScreenHeight = Sheets(CONF).Range("B1") Config.ScreenWidth = Sheets(CONF).Range("B2") Config.SectorHeight = Sheets(CONF).Range("B7") 'Настройка игрового экрана Set Config.renderField = Sheets(REND).Range(Sheets(REND).Cells(2, 2), _ Sheets(REND).Cells(Config.ScreenHeight + 1, Config.ScreenWidth + 1)) 'настройка карты Set Config.Map = Usefull.getRangeFromSheet(M & Config.MapNumber, 1, 1) Set Config.Sectors = Usefull.getRangeFromSheet(M & Config.MapNumber, 1, 8) 'настройка игрока Elf.FOV = Sheets(CONF).Range("B6") Elf.POV = Sheets(CONF).Range("B5") Elf.X = Sheets(CONF).Range("B3") Elf.Y = Sheets(CONF).Range("B4") End Sub

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

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

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

'ядро рейкастинга Public Sub getRenderArray() Dim countRays As Integer, rayPOV As Single, rayDist As Single, rayX As Single, rayY As Single, _ sectorX As Integer, sectorY As Integer, arrEmpty() As Variant, arrRender() As Variant, iSeg As Integer On Error Resume Next arrEmpty() = Config.Sectors.Value ReDim arrRender(1, Config.ScreenWidth) For countRays = 1 To Config.ScreenWidth - 1 rayPOV = (Elf.POV - Elf.FOV / 2) + (countRays * (Elf.FOV / Config.ScreenWidth)) For rayDist = Config.RayStep To Config.rayLength Step Config.RayStep rayX = Elf.X + rayDist * Cos(rayPOV) rayY = Elf.Y + rayDist * Sin(rayPOV) sectorX = Fix(rayX / Config.SectorHeight) + 1 sectorY = Fix(rayY / Config.SectorHeight) + 1 'проверка, в каком секторе находится луч If arrEmpty(sectorY, sectorX) = True Then 'проверка на столкновения iSeg = getIntersect(rayX, rayY, sectorX - 1, sectorY - 1) If iSeg > 0 Then arrRender(0, countRays - 1) = iSeg arrRender(1, countRays - 1) = Application.WorksheetFunction.RoundDown((Config.ScreenHeight * 24 / rayDist / Cos(Elf.POV - rayPOV)), 0) Exit For End If End If Next Next Render.createImage arrRender() End Sub

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

'проверка на столкновение с отрезками Private Function getIntersect(rayX As Single, rayY As Single, sectorX As Integer, sectorY As Integer) As Long Dim Vector1 As New Vector, Vector2 As New Vector, VectorAct As New VectorActions, arrSegs() As Variant, _ countSegs As Integer, X1 As Single, X2 As Single, Y1 As Single, Y2 As Single, scalarProd As Single, crossProd As Single arrSegs() = Config.Map.Value For countSegs = 1 To UBound(arrSegs(), 1) If arrSegs(countSegs, 5) = sectorX And arrSegs(countSegs, 6) = sectorY Then X1 = arrSegs(countSegs, 1) Y1 = arrSegs(countSegs, 2) X2 = arrSegs(countSegs, 3) Y2 = arrSegs(countSegs, 4) Vector1.createVector rayX, rayY, X1, Y1 Vector2.createVector rayX, rayY, X2, Y2 Set VectorAct.Vector1 = Vector1 Set VectorAct.Vector2 = Vector2 scalarProd = VectorAct.getScalarProd crossProd = VectorAct.getCrossProd If scalarProd <= 0 And (crossProd > -1 And crossProd < 1) Then getIntersect = countSegs Exit Function End If End If Next End Function

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

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

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

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

Итоги

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

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

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

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

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

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

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

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

5151
10 комментариев

Советую ещё этот канал посмотреть (:

8
Ответить

Больше всего впечатлило видео про рейтрейсинг.

5
Ответить

Удивительно, что я это не видел:)

4
Ответить

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

1
Ответить

До этого мне еще далеко) изучаю, так сказать, все с истоков
Когда-нибудь я и до этого дойду

Ответить

Комментарий недоступен

Ответить