Inferno #05 30 апреля 2004

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

For Coderz - RAYCASTING - make yourself a little DOOM'a. Tracing algorithm 3D maze in the game WOLF.

  Shiru Otaku on reykastinge
 RAYCASTING - make yourself a little DOOM'a.

  Shiru Otaku


   It has long, very long I dream about that
anyone ever do the same on
Speccy toy genre full 3d action
- Not Doom, of course, or there Duke, but khotyaby analog 
Wolf3d. At this moment there are very good attempt - Wolf3d  
demo (by Alone Coder), Citadel. 

   Ed.: The game engine Citadel is not based on
reykastinge, so we no longer mention it
will not.

   Surprising just why they (attempt) so
small compared with the amount of writing
brethren. Maybe it's just a lack of
knowledge (in my time, I also burned the idea
write something similar, but not enough
it is knowledge - and now do not have the desire)? Based on 
this assumption, I decided to dash off an article that 
describes the method used in the original Wolf3d by ID 
Software, as well as dozens of similar Toy of the time. The 
method is called raycasting (not to be confused with 
raytracing'om) and was previously used for fast rendering of 
pseudo-Space toys genre 3d action. At the moment it is believed 
that this method is obsolete because it imposed restrictions on 
the complexity of the display space, but he still used on 
machines with limited processing power - Such as Palm Pilot, 
GameBoy Advance. Think that this method is quite suitable for

implementation actually playable analogue
Wolf3d and Speccy (which proves itself,
For example, Wolf3d demo - it uses
a special case of reykastinga).

   I describe a method reykastinga in its simplest form (the 
walls of the same height with the texture only at right angles 
to each other, gender and ceiling without textures). I will not 
give kakielibo specific solutions - only general principles, 
algorithms, formulas. Specific solutions depends upon the 
encoder implements These algorithms - than optimal code had 
come, the better the result (there is no limit to perfection, 
giving 15fps at 3.5 MHz:) I warn once - like all morochki with 
3d-graphics, all described hereafter will require some 
knowledge - the Pythagorean theorem and other mathematics at 
secondary school level. 



          WHAT IS RAYCASTING?

   Reykasting - a method of converting
limited form of data (a very simple
Map of floors) in a three-dimensional projection by tracing 
rays from the viewpoint of volume of the review. It is not I 
clever to express, just read of the book:) In general, the 
following figure, I think, will explain more clearly: 



   It should be noted that the application reykastinga not 
limited to the construction such a projection - it can be used, 
for example in the construction of voxel surfaces (a la the 
background in the Commanche to the PC). Defining property 
reykastinga is that the rays are traced from the viewpoint of

volume - as opposed to ray tracing, where rays are traced from 
the objects in the scene to the point review. Also, if a ray 
tracing rays traced for each point of the screen, then

reykastinge always perpendicular to the wall
sex, and so it is possible to trace only one beam to a column 
of the screen - which is why reykasting and is the fastest 
method for constructing  three-dimensional projection.


   Ed.: If you compare the speed all
Possible applications of pseudo-then
faster reykastinka will be two methods
visualization of the road surface for racing: Line (usually for 
ZX) and a projective plane. 



    2.5D OR LIMITATION RAYCASTING'a.

   Benefits reykastinga in high-speed rendering of space, but 
for this rate to be paid - to pay heavy restrictions and 
simplifying the display of the world. His are not even the 
really three-dimensional - because in reality it is only a 
three-dimensional projection of the usual flat map. In the 
original method reykastinga does not allow split-level floor 
and raznovysotnye wall. In fact, this it is still possible - 
see Doom or Duke3d (maximum capacity reykastinga), but, of 
course, it requires no longer such a small computational 
resources. On the other hand, during the 286-s processors, 
where three-dimensional graphics in real time was

possible except on the SGI, these simplifications
were insignificant price. They will not
great price and for Speccy.

   The main limitation reykastinga - wall to the floor / 
ceiling must be only at right angles (otherwise lost

the possibility of tracing a single ray in
column, and lost all the advantage in speed).

   Also, usually, the wall can only be
two kinds - vertical and horizontal
(If you look at the map above). This restriction is necessary, 
but it complicates and slows program (hence the diagonal wall 
is not in the same Wolf3d).




    THIS SQUARE, SQUARE WORLD ...

   Thus, when considering the principles reykastinga we will 
abide by the following schimi constraints of our world: 

  - The walls are always at right angles with respect to gender.

  - The walls are the equilateral triangle of bricks.

  - Paul is always flat (one level).

   The size of each cube, we take for 64h64h
x64 conventional units. Of course, it could
be any other number that is the power of two (this is to be 
there at all using a shift operation). The more

size of the cube - the greater the simplicity of the space 
(large cubes), but higher speed, and vice versa - with small 
cubes tracing process will take longer. The size of the cubes 
is to choose, based on the estimated amount of future textures 
- if they are 32x32 (which most logical for Speccy) - then the 
size of the cubes should choose 32h32h32, it will simplify the 
calculations. In general, our world would look like this: 



   WARNING! Before continuing, it is necessary to determine the 
very important thing - coordinate system. Further 
clarifications will be used the following system of coordinates 
(Cartesian): 



   That is, X - the horizontal axis, positive values ​​- the 
right; Y - vertical, positive value - from the bottom. 0 
degrees - to the right, and then Counterclockwise arrows (top 
90, left 180, bottom 270). This should be taken into account 
when considering the reasons mentioned below - otherwise there 
will be unnecessary glitches. 

   Now on. We define some more
 things:

  - The viewing angle (field of view, Field of
view, FOV), the coordinates of the player (point obzo pa).

  - Dimensions of projection plane (projection of the plan - it 
sounds ugly, I'd rather have used English term). 

  - The relationship between the player and the projection
plane.

   The player sees what is before him.
His field of vision has a certain angle
(FOV). Angle determines how much the
player sees the world around him. People have
viewing angle of 90 degrees or more (Eds:
170 ° - can check it yourself
spreading his arms and moving his fingers), but
best form on the screen we will FOV for
60 degrees. By the way, if you change the FOV in a wide range 
(up to 120 degrees Celsius) - can be get amusing effects, such 
as "fish-eye" - as in Duke3d, when the Duke gives a pop 
reducers. 

   Ed.: I like the angle of 90 °. This corner of the screen 
still does not match any of the proposed values ​​- it is less 
than 40 °, which is obviously not applicable as the FOV. 

   To move a player in the space
it must have three coordinates - Y, X on
two-dimensional map (seen above), and
and point of view (POV) - "point of view,"
Although it is logical to say - line of sight, in degrees. If 
the POV is 0 degrees - player looks right on the map (again,

if you look at the map above).

   That explains this picture (for those who do not
understood) that the FOV and a POV, and shows where to look and 
what to see player, if its FOV = 60 degrees, and POV =

= 45 degrees.



   The last - we need to define our
projection plane, that is, roughly speaking,
size in points (not pixels, since at
Speccy points may be, eg, chunks)
our window where we will draw
projection. In the dock, in explanation of which I write
this article, it was designed for standard resolution VGA 
320x200, therefore, not to be confused myself, I will leave 
just such window sizes - 320 columns, each 200 pixels in height 
(after all it is theoretical example, and not practical), but

for the real problem, of course, have to choose
a more reasonable size - for example, 64 * 48
points. Keep in mind that the wider the projection plane, the 
more rays will trace, and hence the slower

work program. Height of the projection
plane does not affect the rate of trace
rays, but can affect performance
scaling procedure column. Coordinates of points on the 
projection plane are common - the origin (0,0) is at the top

left corner.



              "CAST A RAY".

   Now that all the initial parameters are defined, you can 
begin to describe the principle of constructing the projection. 
To start small, but nice chertezhik (hell-whack;): 



    From all this we know:

  - The size of projection plane is 320x200
 points.

  - The Center is located in the projection plane
 160.100.

  - The distance to the projection plane = 277
units (half the width of the projection plane /
 tangent of half the FOV).

  - The angle between adjacent rays = 60/320
degrees (60 degrees FOV / width of the projection plane).

   These values ​​are constants, they
will not change further (unless you do not
want to make a variable in realtime FOV
:), So if you wonder where are the
different values ​​- you can not wrestle, but just use them. 
The angle between neighboring rays - is the same as the angle 
between adjacent columns, we will use this value for the 
transition from the column to a column in the trace. Distance to

projection plane will be needed to get a picture of a normal 
scale. 

   Our projection (wall display) can be regarded as a 320 
(width of the projection plane) of vertical columns. For each 
of them we traced a single beam. Leftmost column is fitting the 
angle POV-(FOV / 2) for the rightmost POV + (FOV / 2). From 
column to column, you can move, adding to the initial value of 
POV-(FOV / 2) at each iteration FOV/320.


   Thus, an algorithm for constructing the projection is as 
follows:  1. Subtracted from the current POV half FOV -

 This is our corner of the current beam.
 2. Starting from column 0 (left):

     - "Cast a ray", as they say amerikosy

      ;) - Emit luch.Luch proceeds of which
      ordinate in the direction of the player POV.

     - Go to the ray cells, while not a priest
      We introduce into the cell with the wall.

    - Remember the length of the resulting beam.
3. Adding to the corner of the current beam FOV/320.
 4. And so all the columns (320 times in our case).

   While everything is simple, but there are two important 
momenta.Pervy - need to be sure that the beam will sooner or 
later will meet stenku.To has at least the entire map of the 
perimeter wall must be fringed. Also do not forget that the 
further necessary to trace the beam - the slower the 
construction of the projection as a whole. Therefore it is 
necessary to limit the range of reasonable review of the limit 
formulas (pick up by eye). 

   Ed.: This limitation will add little
velocity in the Wolf-like games - well
planned labyrinths contain no halls where on one wall can not 
see the opposite. Restriction helps in games open landscape.


   The second important point - we do not need
take each point of each cell (accuracy is required - otherwise, 
do not build a projection), enough to check the boundary cells 
- Figure: 



   We are only interested in points A, B, C, D, E, F
We have to go through them one by one, checking for the 
presence / absence of the wall in the cage. The simplest (but 
not the fastest) way - to trace the beam twice, checking

at first only horizontal, and then only vertical intersection; 
remember both found the distance to the walls, and select

blizhayshee.Razumeetsya of them, you can check
and merge, but it is much more complex algorithm for ray 
tracing (and maybe add speed, but maybe not;). I will describe 
simple way to separate. 

   The whole trick is that the distance between
all horizontal (or vertical)
odinakovy.Eto intersections can be seen
from the figure (on the left for horizontal, right for vertical 
intersection): 



   We call the vertical distance to the next point, Ya, 
horizontal Xa. Will find all horizontal crossings. Ya

easy to find - is the height of the cell (64 in our case). Xa 
can be found by the formula Xa = = 64/tan (beam angle). Of 
course, for Speccy tan every time considered too expensive, but 
you can find a sign for all possible angles in advance. To find 
the vertical intersection Xa is the width of the cell, Ya = 64 
* * Tan (angle beam).


   Now a more detailed algorithm. WARNING! Remember the used 
coordinate system! Y-axis positive values  is at the bottom, 
and negative - on top! 

   Ed.: If you write a program, but not
guess this sign (which, I fear, has happened in
this article;), try to take corners curled not against it, or 
clockwise. 

   Tracing the intersection of horizontal (position player Py, 
Px; coordinates  inspected point Ay, Ax):


  1. Find the first nearest intersection (point A). If the beam 
goes up - Ay = int (Py / 64) * 64 - 1, if the down -

Ay = int (Py / 64) * 64 + 64. Ax is
after calculating the Ay: Ax = Px + (Py-Ay) /
 / Tan (angle beam).

  2. Find Ya. It is the height of the cell,
ie 64 in our case. If the beam should be
traced upwards - Ya must be of negative if down - yes.

   3. Find Xa. Xa = 64/tan (beam angle).

  4. Check the intersection for the presence of the wall. To 
check the current position to convert the coordinates of the 
cells - that is, divided by cell size (shift)

In our case, to check the cell in the coordinates Ay/64, Ax/64. 
If the wall is - remember the distance of Py, Px to Ay, Ax and  
stop the cycle. 

  5. If the wall does not - go to the next intersection. Ax = 
Ax + Xa, Ay = Ay + Ya, and way to victory.


   Trace of vertical intersection is not much different 
(position player Py, Px; coordinates of the points tested By,  
Bx): 

  1. Find the first nearest intersection (point B). If the beam 
goes to the right - Bx = int (Px / 64) * 64 + 64, if the left -

Bx = int (Px / 64) * 64 - 1. Further, By =
 = Py + (Px - Bx) * tan (angle beam).

  2. Find Xa. It is equal to the width of the cell,
ie 64 in our case. If the beam should be
trace left - Xa must be of negative, if the right - yes.

   3. Find Ya. Ya = 64 * tan (angle beam).

  4. Check the intersection for the presence of the wall. If 
the wall is - remember the distance yanie of Py, Px to By, Bx, 
and stop the cycle. 

  5. If the wall does not - go to the next intersection. Bx = 
Bx + Xa, By = By + Ya. 

   After two traces choose that point which is closer (Compare 
the distance), for her and we will draw a column. In the above 
example, it is in the pictures is the point E. 

   Need to elaborate on how
find the distance from the player to the wall. There
several ways. I'll tell you about the two. Lack of them is that 
one must assume square root, and in another - the sine and 
cosine. Can simply calculate the distance (X = X2-X1, Y = 
Y2-Y1), but it will be harder to deal with distortions (for 
them - next section).


   The first way - the distance from Px, Py to
endpoint Ex, Ey = sqrt ((Px-Ex) ^ 2 +
+ (Py-Ey) ^ 2). This method is inconvenient,
that a lot of slow operations - two of multiplication and 
taking the square root. 

   The second method - distance = abs (Px -
Ex) / cos (a) = abs (Py - Ey) / sin (a), where a =
beam angle. This method is convenient in that sign of the 
cosine and sine can be calculated in advance, and from slow 
operations - one division. 

   Once we found the distance to
columns, you can already begin drawing projections.



          CHANGES file.

   But there is one "but." If right now
draw the columns (no texture) to found the distances to them, 
we can greatly break off - instead of, say, a straight wall, we 
see something like this: 



   Ed.: Think of the game Doom Mania.

   This is because we do not take into account the singularity
monitor screen. The fact that he, unlike the human eye is not 
spherical, and flat. And therefore, if the distance from

point of view to straight wall in the middle
one, the distance from the point of view to the edge
View area - another. So, we need to adjust the distances to the 
column, given that fact. 

   Distortion is easy to remove by this formula: distance = 
correct the distorted distance * cos (a), where a - angle of 
the current beam. The value of cos (a) can be calculated in 
advance for each of the columns, then we have get a plate of 
320 numbers (the angle a varies from 30 to -30 degrees - do you 
remember about our coordinate system!), and all found

distances need to be multiplied by the values ​​of this plate.

   Ed.: Do not forget that we remove this
only vertical, but horizontal
iskazheniya.Tekstury at the edges of the screen compared to the 
center will be compressed horizontally. In the Wolf demo for ZX 
do not, because not applicable arithmetic method and scanning 
ahead, the scale has been adjusted in the "fan" vertorov scan 
(periphery of the screen is scanned over major steps, the ends 
of scan vectors, collected in one bundle, indicate points 
uniformly located on the same Line).


   In general, for Speccy these multiplications - a big loss of 
speed, and therefore worth trying to remove or turn down the 
distortion kakimlibo other sposobom.Nu yes it's already on your 
discretion:). And now, finally ... 



              BUILD THE WALL.

   Yes, now we need to - to draw
on the screen of columns desired height (which
You can learn from the distance found for
each column). Well, so let's draw. Until
You can draw just completed one
color bars to see the corridors,
later add texture.

   The height of the column is as follows: height
Textures / distance to the column * 277 (I hope you remember 
where it came from a 277 - I mentioned this at the beginning). 
The top point on the screen with which to draw

column is even simpler - the height of projection plane / 2 
minus column height / 2. You can draw.


   But we must point out one pitfall.
If you do everything as written above,
can observe small distortions
seemingly straight walls, as if to pull on
their texture (see below) - sometimes on the flat lines will be 
visible teeth - the closer to the wall, so they bolshe.Chestno 
speaking, I did not understand from where they arise, but to 
get rid of this effect is simple, if you round off the height 
of the column to an even number (Was 31 - will be 30, etc.). It 
is almost completely removes the effect of teeth (a bit

remain, but this is due to errors District leniya).

   Ed.: Indeed, the steps can be
kill the rounded heights of up to a multiple of 2. But
it lowers the accuracy of scale! Therefore it is better to 
scale each column from the middle - may even be fractional 
height. 



     Sticking WALLPAPERS (Texture on the wall).

   It remains quite a bit - pull on
wall teksturu.Eto very prosto.Nam need
only to find out which of the columns of the texture
you want to display for each of the columns of the screen, then 
pull it through a scaling procedure (I will not tell you how to 
write such a procedure - it is much easier than the algorithm 
reykastinga, so that help themselves). And to know quite easy - 
we take the coordinate Y, if was found by a column of vertical 
walls, or X, if the column is horizontal trims

it, for example, AND'om, leaving the last 6
bit (cell size 64) - it will be necessary shift in the texture. 
Remains to derive the column texture, stretching it vertically 
to the desired size. 



      FIRST STEPS IN A SQUARE WORLD.

   Well, now we have a wonderful
wall, with a texture, without distortion. But while
We consider only one point, not having
opportunity to wander through the okrestnostyam.Nado
still make the normal movement of the player
in prostranstve.Normalnoe - is when your left and right players 
are deploying around its axis, and forward-backward allow move 
in this direction. Yes More would be nice to not be like a ghost

and yet not go through stenki.Eto too easy.

   We have the coordinates of the player Px, Py, and the angle
Pa (POV). We still need two parameters - the speed of movement 
and speed Pspd reversal Prot. On your left and right

changes need to hang Pa - add and
diminish its value to the Prot. At the same time
a good idea to make sure that Pa was in the range of 0-359. To 
move forward (key up), we need to find the next point on

vector Pa, at a distance from the current Pspd.
 We find:

  Px = Px + cos (Pa) * 10; Py = Py + sin (Pa) * 10.

   To move backward to, respectively, subtract, not add 
znacheniya.Chtoby not pass through walls, you need to check

new point found for the presence of
wall, and if there is a wall - that or just do not
go, or - even better - to try to reduce Pspd, until a free 
point of the. 

   Ed.: It is recommended to consider the wall space, separated 
from the real wall is closer than on the "radius of character." 
This is due to the fact that the wall at zero distance visible 
in the infinite (in any case, large and unaesthetic) 
magnification. 

   You can also add inertia when walking
and the turn - but that's not me you
to teach:).



           Sit down on the track.

   You can add our engine features such as the effect of jump 
squats or player. To do this, merely to shift the center of 
projection plane in the calculation of the top of the output 
column - if reduce, then sit down, increase - jump. Very simple.


   Not just as simple and portray glance
floor or potolok.Dlya this when calculating the highest point 
to take away from half the height of projection plane is not 
half the height of column, and a third or a quarter - in 
general, Experiment on health.




              And about the object.

   The result was almost a game - there are
three-dimensional maze, it is possible to wander. But apart 
from the walls did not, but it is not very interesting. Need 
enemies, many enemies, and some pistols:) Yes and no doors

would have prevented. Only now I'm very tired
writing this article, therefore, briefly discuss
general ideas, and you really think out for yourself.

   Door a la the original Wolf3d. They can be made as follows. 
If, ray tracing was in a cage with a door -

this cell, we will be tracing the point-wise. If at some point 
in the beam cross the cage in the middle - the place where the 
door - then this point we take as found distance. The door will 
then be like in the opening half the width of the wall

(Itself the door will, of course, "cardboard" -
thickness of a pixel, but it is invisible, because
not often prhoditsya watch the door in the butt
;).

   Objects - the enemies, all sorts of vases and night
Other utensils - can be displayed using
conventional methods of 3D-graphics. That is stored
their X, Y coordinates, and when you turn the player
rotated around the axis of all these coordinates, with
output using the usual projection
3D-point on the plane (3D coordinate X = X
in our space, Y = 0, Z = coordinate
X our level). The main conclusions of those too
on the vertical columns, given the distance to the wall - if 
the wall is closer than some of the columns of the object - 
display wall, then - display wall first, then on top of her 
column object. 

   If possible (for the derivation
screen using chunks, for example) - is
use change in the brightness of columns in
Depending on the distance - can improve
intelligibility of the picture (the farther wall,
those "dark").



              IN CONCLUSION.

   Well, all I enlighten you - now let's go
All rivet Woolf and the Duma:) I also want to
notice that the engine can be really fast
done only if a well thought golovoy.Napisat ray tracing can be 
dozens of ways, there are many opportunities minimize the 
number of required realtime-computing, simplifying the 
algorithm etc., etc. So it all depends on you:)


   Behind the scenes there are many themes, for example,
rendering using textures reykastinga
floor and ceiling - I did not describe this
process, since for Speccy he clearly is not acceptable because 
of speed - even on the PC it does not work very quickly 
(because the original Mr. Wolf3d and no textures on the floor / 
ceiling) 

   Ed.: The cost of floor and ceiling are more
the cost of scaling the walls - which
itself occupies about half of all time
algorithm. That is, from the floor and ceiling slowly two times.

   Nevertheless, if something interesting -
necessary information without any problems in
Network. For example, I can recommend chapter
of the PC-GPE "Doom technique", or referred to the line below 
the dock. 

   This is all based on the dock
"Ray-Casting Tutorial" by F. Permadi, (C)
1996-01 (English original can be found
on http://permadi.com/tutorial/raycast/),
for which I was self taught, and is arbitrary
a translation / paraphrase of his words,
greatly shortened and my doubt is very valuable additions;)



        Shiru Otaku/ANGEL2 (shiru@mail.ru)