Adventurer #13 31 марта 2002

Программирование

Обмен опытом - Как написать 3D игру типа DOOM.

     (C) Research/Volgasoft

      Как написать 3D игру типа DOOM

     В  этой  статье я собираюсь поведать
(ну и показать рабочий пример, естествен-
но)  о  том,  как  сделать (как делались)
трехмерную  гаму на 3d движке с секторной
организацией.  В  свое  время  Доктор STS
(теперь  более известный как Доктор Луже-
ная Глотка :))) ) занимался этим вопросом
и  написал пару не сильно отличавшихся 3d
движков  (code  name:  ZX  Duke Nukem). В
принципе,  об аналогах я не слышал, может
кто-то  и  сделал  что-то подобное, а раз
таковых нет, то будем рассматривать един-
ственный  существующий экземпляр. Дабы не
дать издохнуть шедевру, я приспособил его
в  дему,  выпущенную  под названием 
Love Gun.
Если Вы ее видели, значит поймете,
о чем идет речь. Сразу хочу сказать огро-
мное  спасибо другому известному <отцу> -
дяде  Darkу  из ныне усопшего X-Trade. Он
тоже в огромной степени причастен к напи-
санию движка, как и STS. В принципе, нем-
ного посодействовал материалами и аппара-
тными  средствами и я. Все, что здесь бу-
дет  затронуто,  базируется на материалах
двух   вышеупомянутых  "трехмерных  пап",
опубликованых в электронном журнале "Spe-
ctrum  Expert".  Начните с него, иначе ни
фига не поймете.
     Итак, приступим:

     В  начале  рассмотрим, что же это за
секторная организация такая.

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



     Итак, имеем уровень, разбитый на се-
ктора.  Как выглядят сектора, Вы уже, на-
верное, догадались. Смотрим на сектор S0.
Он    состоит   из   точек   с   номерами
0,1,2,3,4,5,6,7,8,9,0. Точки соединены по
часовой стрелке и образуют стены: 0-9, 9-
8,  8-7 и т.д. Набросав такой восьмигран-
ник,  мы получим возможность по нему пок-
рутиться. Но: встает проблема, а че даль-
ше?  На  одном секторе игру не построить.
Даже на двух или десяти. Чего от них тол-
ку,  если  это  независимые друг от друга
помещения?  Ведь их как-то сцеплять надо.
Вот  эти  проблемы и выделены на картинке
жирными линиями. Называются они межсекто-
рными  соединениями.  Итак,  наши сектора
имеют  общую грань - 0-9 для S0 и 9-0 для
S1.  А это означает большое ведро гвоздей
в заднице в плане кода и вычислений. При-
мер  -  когда  я  делал  подъем  (сектора
S4-S9), то хотел сделать его гладеньким и
впиндюрил 15 ступенек. Скорпион в резуль-
тате повис в жопу, эмулятор Шалаева выжи-
мающий  300 тысяч тактов за frame (на Cy-
rix200)  решил,  что тут на спектруме mp4
показывают.  Подумав, что это все-таки не
глюк, я обошелся пятью ступеньками. <Нау-
чное> объяснение сего будет ниже.

     Переключаемся  на  исходник  <мирка>
урезанного    под   наш   кусочек   карты
(world5.c).

     Таблица указателей на сектора:

SECTB
 _DW S0,S1,S2,S3,S4,S5,S6,S7,S8,S9

     Указатели располагаются в том же по-
рядке, в котором лежат сами сектора.

     А  вот  и  сектора. Мне понадобилось
какое-то  время, чтобы расрюхать чего там
STS понаделал:

 ORG $^
 SECTORS
 ;FLOOR'z,CIELING'z
 ;SLOPE FLOOR,SLOPE CIELING
 ;HITAG,LOTAG,EXTRA
 ;FLOORPIC,CIELINGPIC
 
 ;пример сектора:
 S0      DW 300,-400,0,0,0,0,0:DB 22,15
 ; шапка сектора 
 ;DW высота потолка, пола, потом 
 ;незадействованные поля (под всякие
 ; спецэффекты), потом:
 ;DB заливка полов, потолка
 ;кстати - потолок <внизу>
 
 ;Затем идет список узлов, из которых состоит 
 сектор
 ; POINT, FIL, NUM, CONNECT, SEC
 ;DW номер точки: DB заливка стены <этот узел - 
 ;следующий за ним>, номер данной стенки,
; номер стенки общей с соседним сектором 
 ;(если 0 - стена не прозрачная) (<сцепка>),
 ; номер сектора с которым происходит сцепка
 ; (-1 - нет соединения).
 
         DW 9:DB 1,0,0,-1
         DW 8:DB 14,1,0,-1
         DW 7:DB 6,2,0,-1
         DW 6:DB 12,3,0,-1
         DW 5:DB 20,4,0,-1
         DW 4:DB 12,5,0,-1
         DW 3:DB 6,6,0,-1
         DW 2:DB 14,7,0,-1
         DW 1:DB 1,8,0,-1
         DW 0:DB 25,9,12,1
 ;соединяемся с 12-м
 ;ребром сектора S1
 
         DW -1; конец сектора, 
 ;соединение 0-го и 9-го узлов
 
 ;пример второго сектора
 S1
 _DW 300,-400,0,0,0,0,0:DB 14,19
 
 _DW 12:DB 13,10,14,2; соединяемся
 ;с 14-м ребром сектора S2
         DW 10:DB 27,11,0,-1
 _DW 9 :DB 4,12,9,0; соединяемся с
 ;9-м ребром сектора S0
 
         DW 0 :DB 27,13,0,-1
         DW -1; конец сектора,
 ;соединение 0-го и 12-го узлов
 
     А вот и сами точки из которых клеят-
ся сектора:

ORG $^
 ;DW X,Y; X=-16384,16383 Y 
 ;тоже, если мне не изменяет 
 ;память
 DOTS    DW 5500,4000;0 S0
         DW 5000,4000
         DW 4000,3000
         DW 4000,1000
         DW 5000,0
         DW 7000,0
         DW 8000,1000
         DW 8000,3000
         DW 7000,4000
         DW 6500,4000;9
 
         DW 6500,6500;10 S1
         DW 5000,6500;11
         DW 5500,5500;12 S2
         DW 5000,5500;13

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

     С  устройством  секторов все. Теперь
переключимся на то, как это все заливает-
ся.

     Сейчас  я  Вам  продемонстрирую пару
картинок:

     Эту  можно назвать <Глазами зрителя>



     А эту <Истина>



     Видите?  Ну, каково, не передернуло?
А  все дело в том, что друг наш спекки не
умеет  быстро  считать.  Да,  да:. Залить
стенку  целиком  от пола до потолка полу-
чается  быстрее,  чем обсчитывать участок
действительно  видимый  зрителю,  и затем
заливать  его,  причем обычно в два раза.
Обдумав  эту  картинку,  STS понял, что в
принципе  для  ускорения  движка, заливок
потребуется две: первая - обычная (проце-
дура fdrpoly), вторая - заливка прямоуго-
льников  от  пола до потолка - специально
для стен (процедура filv). Кстати она це-
ликом  стековая и ускорению фактически не
подлежит.  Про заливки остается добавить,
что  они заливают по столбцам - так быст-
рее, но вынос буфера на экран вида:

_POP BC: LD (HL),C: INC H:LD (HL),B:
INC H

жрет  порядочно  быстродействия.  Это  не

LD HL,#0000: PUSH HL
 или POP HL: LD (SCREEN),HL

какой-нибудь. С другой стороны - это неи-
збежность.  Вот  поэтому-то 15 ступенек и
не получилось.

      Подводим небольшой итог.

     Итак, обработчик секторов использует
самые  прогрессивные  на сегодняшний день
процедуры  для  обсчета (с использованием
логарифмов, примерных вычислений и т.д.).
К  тому же, в нем задействована рекурсия.
Посему  он  оптимизации почти не подлежит
(скорее,  он  подлежит  только  дописке).
Другое  дело блок заливок. Заливки, как и
сортировки,  всегда  были  <русским полем
оптимизации>.  Ведь на мелкие деталюшечки
столько тратится! Было бы, наверное, пра-
вильнее сделать не две, а все три или бо-
лее заливок. Сейчас у меня вертится в го-
лове  одна  идея, тока не знаю, насколько
она реализуема, посему пока промолчу.

     Была,  помнится,  идея  сделать этот
движок проволкой. В принципе, а почему бы
и  нет? Вопрос только в невидимых линиях,
а это опять математика.

     На  последок опять вернемся к исход-
нику.

     Я  оставляю всe as is. Обычно STS не
разбивал  программы  на логические модули
(в  шторме  с  ними работать не больно-то
удобно),  а  напихивал столько, сколько в
текстовую  банку  влазит. Я позволил себе
наглость  нарисовать  некоторые коммента-
рии. Разобраться с тем, что там делается,
дело, наверное, недели (у меня ушло в це-
лом дня четыре).
     Еще  подбрасываю библиотеку GRAFLIB,
составленную  STS'ом из  процедур Дарка и
своих  собственных. Она пригодится любому
3D <писателю>.
     Разжевывать  дальше  не имеет смысла
=> на этом пожалуй все.