Из журнала Inferno Guide #5,
Рязань/Самара, Май 2004
(в текст внесены исправления из Errata IG#7)
Внимание: функции sin, cos и tan в статье
подразумевают значения в градусах на входе
и выходе.
RAYCASTING - сделай себе немного DOOM'a.
Shiru Otaku
Давно, очень давно я мечтаю о том, что
кто-нибудь, когда-нибудь сделает-таки на
Speccy полноценную игрушку жанра 3d action
- не Doom, конечно, или там Duke, но хотя-
бы аналог Wolf3d. На данный момент уже су-
ществуют очень неплохие попытки - Wolf3d
demo (by Alone Coder), Citadel.
Ред.: Движок игры Citadel основан не на
рейкастинге,поэтому её мы больше упоминать
не будем.
Удивляет лишь, почему их (попыток) так
мало по сравнению с количеством пишущей
братии. Может быть, дело лишь в недостатке
знаний (в своё время я тоже горел идеей
написать что-то подобное, но не хватило
именно знаний - а сейчас не хватает жела-
ния)? Руководствуясь этим предположением,
я решил накатать статейку, описывающую ме-
тод, использованный в оригинальном Wolf3d
by ID Software, а также десятках подобных
игрушек того времени. Метод называется
raycasting (не нужно путать с raytracing-
'ом) и ранее использовался для быстрой от-
рисовки псевдотрёхмерного пространства в
игрушках жанра 3d action. На текущий мо-
мент считается, что этот метод давно уста-
рел из-за налагаемых им ограничений на
сложность отображаемого пространства, од-
нако он и по сей день применяется на ма-
шинах с ограниченной мощностью процессора
- типа Palm Pilot, GameBoy Advance. Думаю,
что именно этот метод вполне пригоден для
реализации реально играбельного аналога
Wolf3d и на Speccy (что доказывает собой,
например, Wolf3d demo - там используется
один из частных случаев рейкастинга).
Я опишу метод рейкастинга в самом прос-
том виде (стены одной высоты с текстурой,
только под прямым углом друг к другу,пол и
потолок без текстур).Не буду давать какие-
либо конкретные решения - только общие
принципы,алгоритмы,формулы. Конкретные ре-
шения зависят уже от кодера, реализующего
эти алгоритмы - чем оптимальнее у него вы-
йдет код, тем лучше будет результат (а со-
вершенству нет предела, даёшь 15fps на 3.5
МГц:) Сразу предупреждаю - как и все моро-
чки с 3d-графикой,всё нижеописанное потре-
бует некоторых знаний - теоремы Пифагора и
прочей математики на уровне средней школы.
ЧТО ТАКОЕ RAYCASTING?
Рейкастинг - это метод преобразования
ограниченной формы данных (очень простая
карта этажа) в трёхмерную проекцию с помо-
щью трассировки лучей из точки обзора в
объём обзора. Это не я так умно выражаюсь,
просто в книжке вычитал:) В общем,нижесле-
дующий рисунок, думается, объяснит всё бо-
лее понятно:
Надо заметить, что применение рейкасти-
нга не ограничивается только построением
такой проекции - его можно применять, нап-
ример при построении воксельных поверхнос-
тей (а-ля фон в Commanche на РС). Опреде-
ляющим свойством рейкастинга является то,
что лучи трассируются из точки обзора в
объём - в отличие от рейтрейсинга, где лу-
чи трассируются от объектов сцены к точке
обзора. Также, если в рейтрейсинге лучи
трассируются для каждой точки экрана, то в
рейкастинге стены всегда перпендикулярны
полу, и поэтому есть возможность трассиро-
вать всего один луч для целого столбца эк-
рана - именно поэтому рейкастинг и являет-
ся наиболее быстрым методом построения
трёхмерной проекции.
Ред.: Если сравнивать по скорости все
возможные применения псевдотрёхмерности,то
быстрее рейкастинка окажутся два метода
визуализации поверхности дороги для авто-
гонок: построчный (обычный для ZX) и плос-
костной проективный.
2.5D ИЛИ ОГРАНИЧЕНИЯ RAYCASTING'a.
Преимущества рейкастинга в высокой ско-
рости отрисовки пространства, но за эту
скорость приходится платить - платить си-
льными ограничениями и упрощениями отобра-
жаемого мира. Его даже нельзя назвать по-
настоящему трёхмерным - ведь на деле это
всего лишь трёхмерная проекция обычной
плоской карты. В оригинале метод рейкасти-
нга не позволяет делать разноуровневый пол
и разновысотные стены. На самом деле это
всё же возможно - см. Doom или Duke3d (ма-
ксимум возможностей рейкастинга),но,понят-
ное дело, это требует уже не таких малень-
ких вычислительных ресурсов. С другой сто-
роны, во времена 286-х процессоров, когда
трёхмерная графика в реальном времени была
возможна разве что на SGI, эти упрощения
были незначительной ценой. Не будут они
значительной ценой и для Speccy.
Главное ограничение рейкастинга - стен-
ки по отношению к полу/потолку должны быть
только под прямым углом (иначе теряется
возможность трассировки одного луча на
столбец,и пропадёт всё преимущество в ско-
рости).
Также, обычно, стенки могут быть только
двух видов - вертикальные и горизонтальные
(если смотреть на карту сверху). Это огра-
ничение обходимо, но усложняет и замедляет
программу (поэтому диагональных стенок нет
в том же Wolf3d).
ЭТОТ КВАДРАТНЫЙ, КВАДРАТНЫЙ МИР...
Итак, при рассмотрении принципов рейка-
стинга мы будем руководствоваться следую-
щими ограничениями нашего мира:
- Стенки всегда под прямым углом относи-
тельно пола.
- Стенки представляют собой равносторон-
ние кубики.
- Пол всегда плоский (на одном уровне).
Размер каждого куба мы примем за 64х64х
x64 условных единицы. Разумеется,это может
быть и любое другое число, являющееся сте-
пенью двойки (это чтобы можно было вовсю
использовать операции сдвига). Чем больше
размер куба - тем больше будет упрощён-
ность пространства (большие кубы), но выше
скорость, и наоборот - при маленьких куби-
ках процесс трассировки будет занимать бо-
льше времени. Размер кубов стоит выбирать,
основываясь на предполагаемом размере бу-
дущих текстур - если они будут 32х32 (что
наиболее логично для Speccy) - то и раз-
мер кубов стоит выбрать 32х32х32, это уп-
ростит расчёты. В общем, наш мир будет вы-
глядеть примерно так:
ВНИМАНИЕ! Перед тем как продолжать, ну-
жно определиться с очень важной вещью -
системой координат. В дальнейших разьясне-
ниях будет использоваться следующая систе-
ма координат (картезианская):
То есть, X - горизонтальная ось,положи-
тельные значения - справа; Y - вертикаль-
ная, положительные значения - СНИЗУ. 0
градусов - справа, и далее ПРОТИВ часовой
стрелки (сверху 90, слева 180, снизу 270).
Это нужно учитывать при рассмотрении ниже-
сказанного - иначе будут лишние глюки.
Теперь далее. Определим ещё несколько
вещей:
- Угол обзора (поле зрения, Field of
view, FOV), координаты игрока (точки обзо-
ра).
- Размеры projection plane (плана прое-
кции - звучит коряво, я лучше буду исполь-
зовать английский термин).
- Зависимость между игроком и projection
plane.
Игрок видит то,что находится перед ним.
Его поле зрения имеет определённый угол
(FOV). Угол определяет, насколько широко
игрок видит мир вокруг себя. Люди имеют
угол обзора 90 и более градусов (Ред.:
около 170° - можете проверить это сами,
разведя руки и пошевелив пальцами), но для
наилучшего вида на экране мы примем FOV за
60 градусов. Кстати, если менять FOV в ши-
роких пределах (до 120 градусов) - можно
получить занятные эффекты,наподобие "рыбь-
его глаза" - как в Duke3d, когда Дюк попа-
дает под уменьшитель.
Ред.: Я предпочитаю угол в 90°. Настоя-
щий угол обзора экрана всё равно не соот-
ветствует ни одному из предложенных значе-
ний - он меньше 40°, что, очевидно, непри-
менимо в качестве FOV.
Для перемещения игрока в пространстве
он должен иметь три координаты - Y, X на
двухмерной карте (если смотреть сверху), а
также point of view (POV) -"точку зрения",
хотя логичнее сказать - направление взгля-
да,в градусах. Если POV равен 0 градусов -
игрок смотрит вправо по карте (опять-таки,
если смотреть на карту сверху).
Вот эта картинка поясняет (если кто не
понял), что такое FOV и POV, а также пока-
зывает, куда будет смотреть и что увидит
игрок, если его FOV = 60 градусам, а POV =
= 45 градусам.
Последнее - нам нужно определить наш
projection plane, то есть, грубо говоря,
размеры в точках (не пикселей, т. к. на
Speccy точками могут быть, например,чанки)
нашего окна, куда мы будем отрисовывать
проекцию. В доке,по мотивам которой я пишу
эту статью, всё было рассчитано на станда-
ртное разрешение VGA 320x200, поэтому,
чтобы не запутаться самому,я оставлю имен-
но такие размеры окна - 320 столбцов, каж-
дый 200 пикселей в высоту (всё-таки это
теоретический пример,а не практический),но
для реальной задачи, конечно,нужно выбрать
более разумные размеры - например, 64*48
точек. Нужно учитывать, что чем шире pro-
jection plane, тем больше лучей придётся
трассировать, а значит,тем медленнее будет
работать программа. Высота же projection
plane не влияет на скорость трассировки
лучей,но может повлиять на скорость работы
процедуры масштабирования столбца. Коорди-
наты точек на projection plane обычны -
начало координат (0,0) находится в верхнем
левом углу.
"CAST A RAY".
Теперь,когда все исходные параметры оп-
ределены,можно приступить к описанию прин-
ципа построения проекции. Для начала небо-
льшой,но симпатичный чертёжик(чёрт-ёжик;):
Из этого всего нам известно:
- Размер projection plane равен 320x200
точек.
- Центр projection plane находится в
160,100.
- Расстояние до projection plane = 277
единиц (половина ширины projection plane /
тангенс половины FOV).
- Угол между соседними лучами = 60/320
градусов (60 градусов FOV / ширина projec-
tion plane).
Эти значения являются константами, они
не будут меняться далее (разве что вы не
захотите сделать изменяемый в realtime FOV
:), так что если непонятно, откуда берутся
те или иные значения - можно не ломать го-
лову, а просто использовать их. Угол между
соседними лучами - всё равно что угол меж-
ду соседними столбцами, мы будем использо-
вать это значение для перехода от столбца
к столбцу при трассировке. Расстояние до
projection plane понадобится нам для нор-
мального масштабирования получаемой карти-
нки.
Нашу проекцию (отображаемые стенки) мо-
жно рассматривать как 320 (ширина projec-
tion plane) вертикальных столбцов. Для ка-
ждого из них мы будем трассировать отдель-
ный луч. Крайнему левому столбцу будет со-
ответстовать угол POV-(FOV/2), для крайне-
го правого POV+(FOV/2). От столбца к стол-
бцу можно переходить,добавляя к начальному
значению POV-(FOV/2) на каждой итерации
FOV/320.
Итак, алгоритм построения проекции та-
ков:
1. Вычитаем из текущего POV половину FOV -
это наш угол текущего луча.
2. Начиная от столбца 0 (левого):
- "cast a ray", как говорят америкосы
;) - испускаем луч.Луч исходит из ко-
ординат игрока в направлении POV.
- идём лучом по клеткам,пока не попа-
дём в клетку со стенкой.
- запоминаем длину полученного луча.
3. Добавляем к углу текущего луча FOV/320.
4. И так все столбцы (320 раз в нашем слу-
чае).
Пока всё просто, но есть два важных мо-
мента.Первый - необходимо быть уверенным в
том, что луч рано или поздно встретит сте-
нку.То есть,как минимум вся карта по пери-
метру должна быть окантована стеной. Также
не стоит забывать, что чем дальше приходи-
тся трассировать луч - тем медленнее пост-
роение проекции в целом. Поэтому стоит ог-
раничить дальность обзора разумными преде-
лами (подобрать на глазок).
Ред.: Это ограничение слабо прибавит
скорости в Wolf-подобных играх - хорошо
спланированные лабиринты не содержат за-
лов,в которых от одной стены не видно про-
тивоположную. Ограничение поможет в играх
с открытым ландшафтом.
Второй важный момент - нам не нужно
проходить каждую точку каждой клетки (точ-
ность необходима - иначе не построить про-
екцию),достаточно проверять границы клеток
- см. рисунок:
Нас интересуют только точки A,B,C,D,E,F
Мы должны пройти через них поочерёдно,про-
веряя на наличие/отсутствие стены в клет-
ке. Наиболее простой (но не самый быстрый)
способ - трассировать луч дважды, проверяя
сначала только горизонтальные, а затем то-
лько вертикальные пересечения; запомнить
оба расстояния до найденных стен,и выбрать
из них ближайшее.Разумеется,проверки можно
и объединить, но это сильно усложнит алго-
ритм трассировки луча (и, может быть, при-
бавит скорость, а может, и нет ;). Я опишу
простой, раздельный способ.
Вся фишка в том, что расстояния между
всеми горизонтальными (и вертикальными)
пересечениями одинаковы.Это можно заметить
из следующего рисунка (слева для горизон-
тальных, справа для вертикальных пересече-
ний):
Назовём вертикальное расстояние до сле-
дующей точки Ya, горизонтальное Xa. Будем
искать все горизонтальные пересечения. Ya
найти легко - это высота клетки (64 в на-
шем случае). Xa можно найти по формуле Xa=
=64/tan(угол луча). Разумеется, для Speccy
тангенс каждый раз считать накладно,но мо-
жно посчитать табличку для всех возможных
углов заранее. Для поиска вертикальных пе-
ресечений Xa равен ширине клетки, Ya = 64*
*tan(угол луча).
Теперь более подробный алгоритм. ВНИМА-
НИЕ! Помните про используемую систему ко-
ординат! По оси Y положительные значения
находятся СНИЗУ, отрицательные - СВЕРХУ!
Ред.: Если вы напишете программу, но не
угадаете этот знак (что, боюсь,произошло в
этой статье;), попробуйте считать углы за-
крученными не против,а ПО часовой стрелке.
Трассировка для горизонтальных пересе-
чений (координаты игрока Py,Px; координаты
проверяемой точки Ay,Ax):
1. Находим первое ближайшее пересече-
ние (точка А ). Если луч идёт вверх -
Ay = int (Py / 64) * 64 - 1; если вниз -
Ay = int (Py / 64) * 64 + 64. Ax находится
после вычисления Ay: Ax = Px + (Py-Ay) /
/ tan(угол луча).
2. Находим Ya. Оно равно высоте клетки,
то есть 64 в нашем случае. Если луч надо
трассировать вверх - Ya должно быть отри-
цательным, если вниз - положительным.
3. Находим Xa. Xa = 64/tan(угол луча).
4. Проверяем пересечение на наличие сте-
нки. Для проверки нужно текущие координаты
преобразовать в координаты клеток - то
есть,разделить на размер клетки (сдвигом),
в нашем случае проверить клетку в коорди-
натах Ay/64, Ax/64. Если стенка есть - за-
поминаем расстояние от Py,Px до Ay,Ax и
прекращаем цикл.
5. Если стены нет - переходим к следую-
щему пересечению. Ax=Ax+Xa, Ay=Ay+Ya, и
так до победного.
Трассировка для вертикальных пересече-
ний не сильно отличается (координаты игро-
ка Py,Px; координаты проверяемой точки By,
Bx):
1. Находим первое ближайшее пересече-
ние (точка B ). Если луч идёт вправо -
Bx = int (Px / 64) * 64 + 64; если влево -
Bx = int (Px / 64) * 64 - 1. Далее, By =
= Py + (Px - Bx) * tan(угол луча).
2. Находим Xa. Оно равно ширине клетки,
то есть 64 в нашем случае. Если луч надо
трассировать влево - Xa должно быть отри-
цательным,если вправо - положительным.
3. Находим Ya. Ya = 64 * tan(угол луча).
4. Проверяем пересечение на наличие сте-
нки. Если стенка есть - запоминаем рассто-
яние от Py,Px до By,Bx и прекращаем цикл.
5. Если стены нет - переходим к следую-
щему пересечению. Bx = Bx+Xa, By = By+Ya.
После двух трассировок выбираем ту точ-
ку, которая ближе (сравнив найденные рас-
стояния),для неё и будем рисовать столбец.
В приведённом на картинках примере это бу-
дет точка E.
Нужно бы подробнее рассказать о том,как
найти расстояние от игрока до стенки. Есть
несколько способов. Расскажу о двух. Недо-
статок их в том, что в одном нужно считать
квадратный корень,а в другом - синус и ко-
синус. Можно и просто посчитать расстояние
(X=X2-X1, Y=Y2-Y1), но будет сложнее боро-
ться с искажениями (о них - в следующем
разделе).
Первый способ - расстояние от Px, Py до
конечной точки Ex, Ey = sqrt ( (Px-Ex)^2 +
+ (Py-Ey)^2 ). Этот способ неудобен тем,
что много медленных операций - два умноже-
ния и взятие квадратного корня.
Второй способ - расстояние = abs (Px -
Ex)/cos(a) = abs (Py - Ey)/sin(a), где a =
угол луча. Этот способ удобнее тем,что та-
бличку косинуса и синуса можно посчитать
заранее,а из медленных операций - одно де-
ление.
После того, как мы нашли расстояние до
столбцов, можно уже и приступить к отрисо-
вке проекции.
ДОРАБОТКА НАПИЛЬНИКОМ.
Но тут есть одно "но".Если прямо сейчас
нарисовать столбцы (без текстуры) по най-
денным расстояниям до них, то можно сильно
обломаться - вместо, например, прямой сте-
нки мы увидим нечто наподобие этого:
Ред.: Вспомните игру Doom Mania.
Это потому, что мы не учли особенность
экрана монитора. Дело в том,что он,в отли-
чие от человеческого глаза,не сферический,
а плоский. И поэтому, если расстояние от
точки обзора до прямой стены посередине
одно,то расстояние от точки обзора до края
зоны обзора - другое. Значит, нужно откор-
ректировать значения расстояний до столб-
цов, учитывая этот факт.
Искажение убрать несложно по такой фор-
муле: правильное расстояние = искажённое
расстояние * cos(a), где a - угол текущего
луча. Значение cos(a) можно посчитать за-
ранее для каждого из столбцов,значит,у нас
получится табличка в 320 чисел (угол a ме-
няется от 30 до -30 градусов - помните про
нашу систему координат!), и все найденные
расстояния нужно будет умножить на значе-
ния этой таблички.
Ред.: Не забудьте, что этим мы убираем
только вертикальные, но не горизонтальные
искажения.Текстуры на краях экрана по сра-
внению с центром будут сжаты по горизонта-
ли. В Wolf demo на ZX этого нет, поскольку
применён не арифметический метод, а скани-
рование "напролом", масштабы скорректиро-
ваны уже в самом "веере" верторов сканиро-
вания (периферия экрана сканируется более
крупными шагами, концы векторов сканирова-
ния, собранные в один пучок, указывают на
точки, РАВНОМЕРНО расположенные НА ОДНОЙ
ЛИНИИ).
Вообще,для Speccy эти умножения - боль-
шая потеря скорости, и поэтому стоит попы-
таться убрать или убавить искажения каким-
либо другим способом.Ну да это уже на ваше
усмотрение:). А теперь, наконец-то...
СТРОИМ СТЕНКИ.
Да, дело осталось за малым - нарисовать
на экране столбы нужной высоты (которую
можно узнать из найденного расстояния для
каждого столбца). Ну, так и нарисуем. Пока
можно нарисовать просто заполненные одним
цветом столбики, чтобы увидеть коридоры,
позже добавим текстуру.
Высота столбца находится так: высота
текстуры / расстояние до столбца *277 (на-
деюсь, вы помните,откуда взялось это 277 -
я упоминал об этом вначале). Верхняя точка
на экране, с которой нужно отрисовывать
столбец, находится ещё проще - высота pro-
jection plane / 2 минус высота столбца /2.
Можно рисовать.
Но надо отметить один подводный камень.
Если сделать всё так,как написано выше, то
можно будет наблюдать небольшие искажения
вроде бы прямых стенок; а если натянуть на
них текстуру (см.далее) - то иногда на ро-
вных линиях будут заметны зубцы - чем бли-
же к стенке,тем они больше.Честно говоря,я
не разобрался, откуда они возникают,но из-
бавиться от этого эффекта просто, если ок-
руглить высоту столбца до чётного числа
(была 31 - станет 30, и т.д.). Это почти
полностью уберёт эффект зубцов (немного
останется, но это уже из-за ошибок округ-
ления).
Ред.: Действительно, ступеньки можно
убить округлением высоты до кратной 2. Hо
это понижает точность масштабирования! По-
этому лучше масштабировать каждый столбик
от середины - могут быть даже дробные вы-
соты.
КЛЕИМ ОБОИ (ТЕКСТУРЫ НА СТЕНАХ).
Осталось совсем немного - натянуть на
стенки текстуру.Это очень просто.Нам нужно
только узнать, какой из столбцов текстуры
нужно выводить для каждого из столбцов эк-
рана, после чего вывести его с помощью ка-
кой-либо процедуры масштабирования (не бу-
ду рассказывать, как написать такую проце-
дуру - это гораздо проще,чем алгоритм рей-
кастинга,так что справитесь сами).А узнать
совсем несложно - берём координату Y, если
был найден столбец вертикальной стенки,или
X, если столбец горизонтальной, урезаем
его,к примеру, AND'ом, оставив последние 6
бит (размер клетки 64) - это и будет необ-
ходимое смещение в текстуре. Останется вы-
вести этот столбец текстуры, растянув его
по вертикали до требуемых размеров.
ПЕРВЫЕ ШАГИ В КВАДРАТНОМ МИРЕ.
Ну вот, теперь у нас есть замечательные
стенки, с текстурой,без искажений. Но пока
мы смотрим только из одной точки, не имея
возможности побродить по окрестностям.Надо
ещё сделать нормальное перемещение игрока
в пространстве.Нормальное - это когда кла-
виши влево-вправо разворачивают игрока во-
круг своей оси, а вперёд-назад позволяют
передвигаться в выбранном направлении. Да
ещё неплохо бы не уподобляться привидению,
и всё-таки не ходить сквозь стенки.Это то-
же несложно.
Мы имеем координаты игрока Px,Py и угол
Pa (POV). Нам понадобятся ещё два парамет-
ра - скорость передвижения Pspd и скорость
разворота Prot. На клавиши влево-вправо
нужно повесить изменение Pa - прибавлять и
убавлять его на значение Prot. При этом
неплохо бы следить, чтобы Pa был в диапа-
зоне 0-359. Для движения вперёд (клавиша
вверх) нам нужно найти следующую точку на
векторе Pa, на расстоянии Pspd от текущей.
Находим:
Px = Px+cos(Pa)*Pspd; Py = Py+sin(Pa)*Pspd.
Для движения назад нужно, соответствен-
но,вычитать,а не прибавлять значения.Чтобы
не проходить сквозь стенки,нужно проверять
новую найденную точку на предмет наличия
стены,и если там стенка - то или просто не
идти, или - что получше - пробовать умень-
шать Pspd, пока не найдётся свободная точ-
ка.
Ред.: Рекомендуется считать стеной мес-
та, отстоящие от реальной стены ближе чем
на параметр "радиус персонажа". Это связа-
но с тем, что стенка на нулевом расстоянии
видна в бесконечном (во всяком случае, бо-
льшом и неэстетичном) увеличении.
Можно также добавить инерцию при ходьбе
и развороте - ну да это уже не мне вас
учить:).
ПРИСЯДЕМ НА ДОРОЖКУ.
Можно дополнить наш движок такими воз-
можностями, как эффект приседания или пры-
жка игрока. Для этого всего-навсего нужно
сместить центр projection plane при расчё-
те верхней точки выводимого столбца - если
уменьшим, то присядем, увеличим - подпрыг-
нем. Очень просто.
Не менее просто и изобразить взгляд в
пол или потолок.Для этого при расчёте вер-
хней точки нужно отнимать от половины вы-
соты projection plane не половину высоты
столбца, а треть или четверть - в общем,
экспериментируйте на здоровье.
И ОБ ОБЪЕКТАХ.
В итоге получилась почти игра - есть
трёхмерный лабиринт, по нему можно побро-
дить. Но кроме стенок ничего нет, а это не
очень интересно. Нужны враги,МНОГО врагов,
и какой-нибудь пистолетик:) Да и двери не
помешали бы. Только вот я очень утомился
писать эту статью,поэтому коротко расскажу
общие идеи, а вы уж додумывайте сами.
Двери а-ля оригинальный Wolf3d. Их мож-
но сделать следующим образом. Если при
трассировке луч попал в клетку с дверью -
эту клетку мы будем трассировать поточеч-
но. Если в какой-то момент луч пересечёт
эту клетку посередине - в месте, где нахо-
дится дверь - то эту точку мы и берём как
найденное расстояние. Дверь при этом будет
как бы в проёме в половину ширины стены
(сама дверь будет, конечно, "картонной" -
толщиной в пиксель, но это незаметно, ведь
не часто прходится смотреть дверям в торец
;).
Объекты - враги, всякие ночные вазы и
прочая утварь - можно выводить, используя
обычные методы 3D-графики. То есть хранить
их координаты X, Y и при повороте игрока
вокруг оси вращать все эти координаты; при
выводе использовать обычное проецирование
3D-точки на плоскость (3D координата Х = Х
в нашем пространстве, Y=0, Z = координате
X нашего уровня). Главное выводить их тоже
по вертикальным столбцам, учитывая рассто-
яние до стенки - если стенка ближе,чем ка-
кой-то из столбцов объекта - выводить сте-
нку,дальше - выводить сначала стенку,потом
поверх неё столбец объекта.
Если есть такая возможность (при выводе
экрана с помощью чанков, например) - стоит
использовать изменение яркости столбцов в
зависимости от расстояния - может улучшить
разборчивость картинки (чем дальше стенка,
тем "темнее").
В ЗАКЛЮЧЕНИЕ.
Ну, всё, я вас просветил - теперь айда
все клепать Вульфы и Думы!:) Хочу также
заметить, что реально быстрый движок можно
сделать, только если хорошо подумать голо-
вой.Написать трассировку лучей можно деся-
тком способов, есть множество возможностей
максимально уменьшить количество необходи-
мых realtime-вычислений,упростить алгоритм
и т.д.,и т.п. Так что всё зависит от вас:)
За кадром осталось немало тем,например,
отрисовка с помощью рейкастинга текстур на
полу и потолке - я не стал описывать этот
процесс, т. к. для Speccy он явно неприем-
лем из-за скорости - даже на РС это рабо-
тает не очень быстро (потому в оригиналь-
ном Wolf3d и нет текстур на полу/потолках)
Ред.: затраты на пол и потолок больше
затрат на масштабирование стен - которое
само занимает около половины всего времени
работы алгоритма. То есть,с полом и потол-
ком медленнее раза в два.
Тем не менее, если что-то интересно -
нужная информация без проблем находится в
Сети. Например,могу порекомендовать раздел
из PC-GPE "Doom technique", либо упомяну-
тую строкой ниже доку.
Всё вышенаписанное основано на доке
"Ray-Casting Tutorial" by F. Permadi, (C)
1996-01 (англоязычный оригинал можно найти
на http://permadi.com/tutorial/raycast/ ),
по которой я учился сам,и является вольным
её переводом/пересказом своими словами, в
сильно сокращённом варианте и с моими не-
сомненно очень ценными дополнениями;)
Shiru Otaku/ANGEL2 (shiru#mail.ru)
Raycasting note
Статья Shiru Otaku про рейкастинг была
изъята из неопубликованного материала
Adventurer #14. В соответствии с традиция-
ми нашего издания (а точнее,его Guide-час-
ти ;), она также снабжена моими ремарками.
Разумеется, моё мнение не является истиной
в последней инстанции. Кстати,данный мате-
риал, достаточно сдобренный личным непони-
манием со стороны лекторов, преподаётся
на курсе "Компьютерной графики" в районе
третьего курса специальности "Программное
обеспечение чего-то чего-то и чего-то че-
го-то". Спектрумистам учиться в ВУЗе по
данной специальности не советую.
Изначально в статье содержалось мнение,
что персонаж нельзя вращать по оси, перпе-
ндикулярной экрану. Вот так:
Однако я со своей стороны полагаю, что
это возможно. Для этого нужно строить кар-
тинку, будто герой не вращался около этой
оси, а потом переносить картинку на экран
в повёрнутом виде.
Конечно, это редко может потребоваться,
но вдруг? В demo, например...
Стены под 45° (т.е. с СВ на ЮЗ или с СЗ
на ЮВ ) можно реализовать и в стандартном
рейкастинге,и в моём варианте,где сканиро-
вание сплошное. Во втором случае это отни-
ет не так много процессорного времени, но
это число теоретически.Поскольку цикл ска-
нирования станет очень сложным. При входе
в каждый кубик нужно проверить,есть ли там
диагональная стенка, и если да, то какая -
в соответствии с её типом должен произойти
переход на нужный вариант внутреннего цик-
ла. При обработке диагональных вариантов
одна из координат должна быть искажена:
X=X+Y, или X=X-Y, или Y=X+Y, или Y=X-Y, в
зависимости от типа стенки и направления
входа в кубик. То же нужно сделать с пере-
менными, содержащими шаг. Тогда цикл будет
работать как обычный, т.е.сложение с выхо-
дом по переполнению.
Собственно,и в стандартном рейкастинге,
если тип кубика со стенкой знать заранее,
скорость упадёт вовсе не в 2 раза. Но ал-
горитм, видимо, ещё мудрёнее.
Alone Coder