как написать 3d игру типа doom (c) research/volgasoft

в этой статье я собираюсь поведать (ну и показать рабочий пример, естественно) о том, как сделать (как делались) трехмерную гаму на 3d движке с секторной организацией. в свое время доктор sts (теперь более известный как доктор луженая глотка :) )) ) занимался этим вопросом и написал пару не сильно отличавшихся 3d движков (code name: zx duke nukem). в принципе, об аналогах я не слышал, может кто-то и сделал что-то подобное, а раз таковых нет, то будем рассматривать единственный существующий экземпляр. дабы не дать издохнуть шедевру, я приспособил его в дему, выпущенную под названием "lovegun". если вы ее видели, значит поймете, о чем идет речь. сразу хочу сказать огромное спасибо другому известному <отцу> дяде darkу из ныне усопшего x-trade. он тоже в огромной степени причастен к написанию движка, как и sts. в принципе, немного посодействовал материалами и аппаратными средствами и я. все, что здесь будет затронуто, базируется на материалах двух вышеупомянутых "трехмерных пап", опубликованых в электронном журнале "spectrum expert". начните с него, иначе ни фига не поймете. итак, приступим:

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

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

итак, имеем уровень, разбитый на сектора. как выглядят сектора, вы уже, наверное, догадались. смотрим на сектор s0. он состоит из точек с номерами 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0. точки соединены по часовой стрелке и образуют стены: 0-9, 98, 8-7 и т.д. набросав такой восьмигранник, мы получим возможность по нему покрутиться. но: встает проблема, а че дальше? на одном секторе игру не построить. даже на двух или десяти. чего от них толку, если это независимые друг от друга помещения? ведь их как-то сцеплять надо. вот эти проблемы и выделены на картинке жирными линиями. называются они межсекторными соединениями. итак, наши сектора имеют общую грань - 0-9 для s0 и 9-0 для s1. а это означает большое ведро гвоздей в заднице в плане кода и вычислений. пример - когда я делал подъем (сектора s4-s9), то хотел сделать его гладеньким и впиндюрил 15 ступенек. скорпион в результате повис в жопу, эмулятор шалаева выжимающий 300 тысяч тактов за frame (на cyrix200) решил, что тут на спектруме 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 <писателю>. разжевывать дальше не имеет смысла => на этом пожалуй все.