Exchange of experience - How to write a 3D game such as DOOM.

<b>Exchange of experience</b> - How to write a 3D game such as DOOM.

     (C) Research / Volgasoft


      How to write a 3D game such as DOOM


     In this article I am going to tell
(Well, and show a working example, of course) about how to make 
(as made) three-dimensional din the 3d engine with a pie

organization. At the time, Dr. STS
(Now better known as Dr. Tin Throat:)))) dealt with this issue
and wrote a couple is not much different 3d
engine (code name: ZX Duke Nukem). In
principle of analogues I have not heard, may
someone did something like that, and once
there are none, then we will consider only existing copy. Lest
give izdohnut masterpiece, I've adapted it
in DeMouy, released under the name <Love
Gun>. If you saw it, then realize
what is at stake. Just want to say a huge thanks to another 
well-known <Father> - Darku uncle of the now deceased X-Trade. 
He also greatly involved in the writing of the engine, as well 
as STS. In principle, a bit part in the escalation of materials 
and hardware, and myself. All that is here to be affected, 
based on materials two above-mentioned "three-dads"

electronic publishing magazine "Spectrum Expert". Start with 
it, otherwise no fig do not understand.


     Let's start:


     In early look at what kind of
Sector organization exists.


     By sectors, we understand some
closed three-dimensional shape, from any point that seamlessly 
see other point of this figure. Roughly speaking, these are two

piles, one of which is driven into the floor, and another in 
the ceiling, and all are covered with wallpaper, and we are 
inside the remaining space between the piles. Sector is 
described by the coordinates of points from which it is 
composed of height (Coordinates) of the ceiling height 
(coordinate) floors, the connection diagram points (Walls), and 
of course, numbers of fill each wall (face), floors and ceiling.

Here's a piece of card LoveGun.



     Thus, we have the level, divided into sectors. Look like 
the sector, you've probably already guessed. We look at the 
sector S0. It consists of points with indices

0,1,2,3,4,5,6,7,8,9,0. Points are connected by
clockwise direction and form a wall: 0-9, 98, 08/07, etc. 
Sketched an octahedron, we get an opportunity for him whirl. 
But: there is a problem, as Che's next? On one sector does not 
build the game. Even two or ten. What they were confusing, if 
it is independent from each other premises? After all, they 
somehow have to concatenate. These issues and highlighted in 
the picture thick lines. They are called cross-cutting 
connections. Thus, our sector have a common face - 0-9 to 9-0 
for S0 and S1. And that means a large bucket of nails

in the ass in terms of code and algorithms. Example - when I 
did lift (sector S4-S9), you would like to make it Gorny and

vpindyuril 15 steps. Scorpio is a result of hanging in the ass, 
squeezing emulator Shalaeva 300,000 cycles per frame (at 
Cyrix200) decided that here in the Spectrum mp4 show. Thinking 
that it is still not glitch, I walked five steps.  
explanation of this will be lower. 


     Switch to the source <microcosm>
truncated by a piece of our map
(World5.c).


     Table of pointers to the sectors:

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


     Pointers located in the same order in which lie the 
sectors themselves. 


     And here is the sector. It took me
some time to rasryuhat which there
STS ponadelal:

 ORG $ ^
 SECTORS
 ; FLOOR'z, CIELING'z
 ; SLOPE FLOOR, SLOPE CIELING
 ; HITAG, LOTAG, EXTRA
 ; FLOORPIC, CIELINGPIC

 ; Example of the sector:
 S0 DW 300, -400,0,0,0,0,0: DB 22,15
 ; Cap sector
 ; DW, ceiling height, sex, and then
 ; Unused field (under any
 ; Special effects), then:
 ; DB pouring floors, ceiling
 , By the way - the ceiling 

 , Followed by a list of nodes that comprise
 Sector
 ; POINT, FIL, NUM, CONNECT, SEC
 ; DW point number: DB die wall <the node -
 , Following it>, the number of this wall,
; Room wall shared with adjacent sectors
 , (If 0 - a wall not clear) ()
 ; Number of sectors with which the coupling
 , (-1 - No connection).


         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
 ; Connect with the 12-m
 ; Edge of the sector S1


         DW -1; the end of the sector,
 ; Compound 0-th and 9 th node

 ; Example of the second sector
 S1
 _DW 300, -400,0,0,0,0,0: DB 14,19

 _DW 1912: DB 13,10,14,2; unite
 , With a 14-m edge sector S2

         DW 1910: DB 27,11,0, -1
 _DW 9: DB 4,12,9,0; connect with the
 , 9 th rib sector S0


         DW 0: DB 27,13,0, -1

         DW -1; the end of the sector,
 ; Compound 0-th and 12 th nodes


     And here is the points themselves of which are glued 
sector: 

ORG $ ^
 ; DW X, Y; X =- 16384,16383 Y
 , Too, if I am not
 ; Memory
 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


     As was noted above, such
an idea borrowed from the organization pisyuka
Natural and Improved the opportunity for
Spectrum.


     With all sectors of the device. Now
moved on to how it is poured.


     Now I'll show you a couple of
Images:


     This can be called <viewer's eyes>



     And this <Truth>



     See? Well, what is not shudder?
And the thing that is not our friend Speccy
able to quickly assume. Yes, yes:. Pour
entire wall from floor to ceiling is faster than a cheat site
actually see the audience, and then
fill it, and usually twice.
Ponder this image, STS realized that
principle, to accelerate the engine, fills
take two: the first - the usual (procedure fdrpoly), second - 
fill rectangles, from floor to ceiling - especially Wall 
(procedure filv). By the way it all stack, and accelerate 
virtually no subject. About casting remains to add,

they fill in the columns - it's faster, but the removal of the 
buffer to the screen like this: 

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

eating decent performance. This is not

LD HL, # 0000: PUSH HL
 or POP HL: LD (SCREEN), HL

some. On the other hand - this is inevitable. That's why about 
15 steps and did not happen.



      Summing up a little.


     Thus, the handler uses the sectors
the most progressive to date
procedures for calculation (using
logarithms, the approximate calculations, etc.).
In addition, it enabled recursion.
Therefore it is almost not subject to optimization
(Rather, it is subject only dopiske).
Another thing the block fills. Fill as
sort, has always been "Russian field
optimization>. After all, the small detalyushechki
so much is wasted! It would probably be more correct to do, not 
two, but all three or more fills. Now I have hanging up with an 
idea, the current does not know how it is realizable, 
therefore, still silent. 


     There was, remember, the idea of doing this
engine wire. In principle, why
not? The only question is invisible lines
and this again mathematics.


     Lastly, go back to the source.


     Vse I leave as is. STS is usually not
broke the program into logical units
(In the storm to work with them does not hurt a
convenient), and cram as much in
text intermeddle bank. I allowed myself
the audacity to draw a few comments. Deal with the fact that 
there is, it is probably a week (it took me a whole day of 
four). 

     Another toss library GRAFLIB,
STS'om composed of Dark and procedures
their own. It is useful to any
3D .

     Chew on it makes no sense
=> This perhaps all.