For Coderz - RAYCASTING - сделай себе немного DOOM'a. Алгоритм трассировки 3D лабиринта как в игре WOLF.

<b>For Coderz</b> - RAYCASTING - сделай себе немного DOOM'a. Алгоритм трассировки 3D лабиринта как в игре WOLF.
  Shiru Otaku о рейкастинге
 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)*10; Py = Py+sin(Pa)*10.
   Для движения назад нужно, соответствен-
но,вычитать,а не прибавлять значения.Чтобы
не проходить сквозь стенки,нужно проверять
новую  найденную  точку на предмет наличия
стены,и если там стенка - то или просто не
идти, или - что получше - пробовать умень-
шать 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)