|====================================| | | | TELEMACHOS proudly presents : | | | | Part 7 of the PXD trainers - | | | | RAYCASTING - WOLFENSTEIN | | STYLE | | | |====================================| ___---__--> The Peroxide Programming Tips <--__---___ <><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><> Intoduction ----------- Hi folks! It's been awhile as usual but here goes - part 7 of the PXDTUT trainer serie. In part 6 I promised to do some SoundBlaster code - but it seems that people are more interrested in some graphical effects so I'll leave the sound code for later. I have also promised to show you how to code the MARS effect (the VOXEL-effect for those of you who has not seen MARS) but that will have to wait until my next tutorial or something.... So, the topic of this tutorial is raycasting. In this particular trainer I'll show you how to do the basic raycasting. This means NO doors, NO floor / ceiling and NO monsters. I thought about including the door-code in this tutorial but I found it to confusing in the raycasting procedures. Doing doors requires you to extend your raycasting procedures quite a bit so I left it out for simplicity. If there is enough interrest I might release another tutorial on doors, floors and ceilings - mail me! If you want to get in contact with me, there are several ways of doing it : 1) E-mail me : tm@image.dk 2) Snail mail me : Kasper Fauerby Saloparken 226 8300 Odder Denmark 3) Call me (Voice ! ) : +45 86 54 07 60 Get this serie from the major demo-related FTP-sites - currently : GARBO ARCHIVES (forgot the address) : /pc/programming/ ftp.teeri.oulu.fi : /msdos/programming/docs/ ftp.cdrom.com : something with demos/incomming/code..... Or grap it from my homepage : Telemachos' Codin' Corner http://www.image.dk/~tm WHAT IS RAYCASTING ? --------------------- OK, as most of you know the classic "3D" games as WOLFENSTEIN and DOOM is'nt 3D at all! They are just 2D games with a faked 3rd dimension. What does this means ? It means that WOLF and DOOM are based on 2D maps - in DOOM this map show where the walls are and how high the walls are. WOLF is much more simple! First of all : In WOLF all walls are ortogonal (ie. at 90 degree angles to each other) and all walls have the same height. If you look at a map from wolfenstein from above it looks like a grid made from square cells - some of the cells are "filled" - others are not. Those which is filled are the walls. Now - the trick is to fool the player into thinking he is walking in a real 3D virtual reality world. This is done in a very clever way called raycasting which involves NO 3D calculations at all! All the walls are just scaled into looking 3D. We need some information on the player to actually make this 3D illusion. First of all we need to know what the player sees of the 2D map. Therefore we need to know how wide his "field of vision" is. In most 3D engines the player has a 60 degree field of vision - so that is the number we'll use too :) So to find out what the player sees of the map we need to know his (X,Y) position on the 2D map and his viewangle. To visualize I'll draw a small ASCII map below. The squares filled with x's are the cells which contains a wall and P symbolizes the player with his field of vision |------------------------------------------------------------| | xxxxxxx | xxxxxxx | xxxxxxx | xxxxxxx | | | | xxxxxxx | xxxxxxx | xxxxxxx | xxxxxxx | | | | xxxxxxx | xxxxxxx | xxxxxxx | xxxxxxx | | | | xxxxxxx | xxxxxxx | xxxxxxx | xxxxxxx | | | |------------------------------------------------------------| | xxxxxxx \ | | xxxxxxx | xxxxxxx | xxxxxxxx | | xxxxxxx | \ | | xxxxxxx | xxxxxxx | xxxxxxxx | | xxxxxxx | \ | | xxxxxxx | xxxxxxx | xxxxxxxx | | xxxxxxx | \ | | xxxxxxx | xxxxxxx | xxxxxxxx | |-----------------\-------------------------------/----------| | xxxxxxx | \ | | / | xxxxxxxx | | xxxxxxx | | \ | | / | xxxxxxxx | | xxxxxxx | | \ | | / | xxxxxxxx | | xxxxxxx | | \ | | / | xxxxxxxx | |---------------------------\-----------/--------------------| | xxxxxxx | | \ / | | | | xxxxxxx | | | \ × / | | | | xxxxxxx | | | P | | | | xxxxxxx | | | | | | |------------------------------------------------------------| So - to render this view we need to find out what part of the 2d map that is in the players field of vision. We do that by tracing along virtual "rays" across the 2D map. Each time a ray enters a new square on the map we check if the ray has hit a cell which contains a wall. Each ray originates from the player but has a different direction. In total we want our rays to cover the 60 degree field of vision we have decided our player should have. If we want our game screen to take up 320 rows of graphic we cast 320 rays within our 60 degree field of vision. This way we get information on what to draw for each of our 320 rows of graphic. When we hit a wall we calculate the distance the wall is from the player and from this information we find out how big this part of the wall should be - the greater distance, the smaller wall. HOW TO CODE IT ! ----------------- First of all we have to decide how big each cell on the 2D map should be in our 3D world - ie how many "units" each cell is on both its X and Y side. The most classic number used is 64 ('cause WOLFENSTEIN used 64X64 cells 8) ) - so 64 is the number we settle for. The size of the cells is important because we move our player around the world using global X and Y coordinates and a viewangle. If our player is positioned at fx. X = 352 Y = 384 ViewAngle = 90 and we have cells which is 64 units on each side we can find out where on the 2D map the player is. In the example above the player would be located at : XMap = 352 / 64 = 5.5 YMap = 384 / 64 = 6.5 ie. the player would be standing in the middle of Map(5,6) looking directly to the south. Speaking of orientation I think it's time to introduce you to how we define our directions on the 2D map : degrees : North map : 270 | --------------> X-axis | West 180 0/360 East | | | | 90 V Y-axis South OK - we have decided to use 320 rows of graphic to cover a 60 degree field of vision. So we start by looking 30 degrees to the LEFT of the direction the player is looking. After each ray we increase the raycasting angle by : 60 degrees / 320 rows = 0.1875 degrees/row This way our 320 rows of graphic covers 60 degrees on the 2D map starting 30 degrees to the left of the player and ending 30 degrees to the right of the player. Great! Now this is pretty easy - we start tracing along the 2D map 30 degrees to the left of the player and continues the ray until it hits a wall. Then we draw the sliver of the wall and increase our raycasting angle by 0.1875 until we have drawn 320 rows of graphic right ?? Now quite! Because if we had to trace along 320 rays - and each ray had to trace along the 2D map and check for a wall-hit for every single X,Y position of the ray the game would run terribly slow. So the first (and most important) optimization we'll make in our 3d-engine is to split the ray-casting procedure up in TWO procedures. On that checks if the ray has hit a cell containing a wall on the X-side - and one checking if the ray has hit a cell containing a wall on the Y-side. Y-side _______ _________ | | | | X-side ---> | | <--- X-side | | |-------| |---------| Y-side Now we can advance the rays in jumps of 64 units and therefore only check if the ray has hit something interresting each time the ray enters a NEW cell. Now we just have to fire TWO rays for each row of graphic - one checking for X-walls and one checking for Y-walls. To visualize how big a optimization this is : Imagine we have world that is 100X100 cells with each cell being 64X64 units. Then the farthest distance on the map would be SQRT((100*64)^2 + (100*64)^2) = 9050 units (the length of the diagonal on the map) - ie. without using two rays we would have to check for wall-hits 9050 times - using the other method each ray would have to check max. 100 times. Lets take a look at the sample world I showed you before. If we consider the two rays drawn on the map as X-rays we would only have to check the ray the places I have marked with a '*' : |------------------------------------------------------------| | xxxxxxx | xxxxxxx | xxxxxxx | xxxxxxx | | | | xxxxxxx | xxxxxxx | xxxxxxx | xxxxxxx | | | | xxxxxxx | xxxxxxx | xxxxxxx | xxxxxxx | | | | xxxxxxx | xxxxxxx | xxxxxxx | xxxxxxx | | | |------------------------------------------------------------| | xxxxxxx * | | xxxxxxx | xxxxxxx | xxxxxxxx | | xxxxxxx | \ | | xxxxxxx | xxxxxxx | xxxxxxxx | | xxxxxxx | \ | | xxxxxxx | xxxxxxx | xxxxxxxx | | xxxxxxx | \ | | xxxxxxx | xxxxxxx | xxxxxxxx | |-----------------\-------------------------------*----------| | xxxxxxx | * | | / | xxxxxxxx | | xxxxxxx | | \ | | / | xxxxxxxx | | xxxxxxx | | \ | | / | xxxxxxxx | | xxxxxxx | | \ | | / | xxxxxxxx | |---------------------------\-----------*--------------------| | xxxxxxx | | * / | | | | xxxxxxx | | | \ × / | | | | xxxxxxx | | | P | | | | xxxxxxx | | | | | | |------------------------------------------------------------| So when we trace along the ray we increase (or decrease if we're looking to the left) the X-position of the ray by 64. Same thing with the Y-rays - but here we only check at Y-borders. THE X-RAY PROCEDURE -------------------- I'll descripe the working of the X-ray procedure. The Y-ray procedure is pretty much the same - so I'll let you figure it out for yourself. The first place to check for a wall-hit is the place where the ray crosses the X-border of the cell where the player is standing. So we calculate our starting X,Y coordinates of the ray like this : The X-coordinate : PlayerX DIV 64 MUL 64. This gives us the world X-coord of the left side of the cell the player is standing in. If the player looks to the right we add 64 to this value. The Y-coordinate : (StartX - PlayerX) * tan(RayAngle) + PlayerY. Well - I guess this needs an explanation :) First of all - All the math I use here is standard trig from school. If you don't know trig I suggest you go get a good book on the subject - 'cause I can't / won't explain it to you in this text :) Lets say we have this square to check : P = player at some position I just made up. (83,106) RA = RayAngle = 225 degrees. V = RA - 180 = 45 degrees. -------------------------- | | * (64, ?? ) | | \ | | /\ | | | V \ (83,106) | (64,106) B-|--- P ----|--- 0 degree | | \ RA / | | \ ___/ | -------------------------- The first thought you get when looking at this is to use the good old formula : |*B| = Tan(V) * |BP| But Tan(V) = Tan(180 + V) so there is no need to calculate V - we just use RA. The clever thing about using tangens here is that you don't have to think about what direction you are looking. If we (as in the case above) is looking up AND to the left (ie. is between 180 and 270 degrees) tangens is always positive. But by calculating |BP| as : StartX - PlayerX we always gets a negative value to multiply the positive tangens with when looking to the left - so the result is the negative length of |*B|. So we just have to add this value (but by adding a negative value we actually subtract it) to PlayerY to get the Y-value of '*'. Had we been looking DOWN but still to the left (ie. is between 90 and 180 degrees) tangens would have been negative - but when multiplied with the negative |BP| the result would have been positive - and a positive value would have been added to PlayerY. Just as it should be ! The same way it fits with the right side. OK... now we know where to start our trace across the map. The next step is to calculate the step-values with which we trace along the map. The X-step : This is easy! If we are looking to the right the X-step is of cause 64 - if we are looking to the left the X-step is -64. The Y-step : The Y-step is calculated as Ystep = 64 * TAN(RayAngle) I'll illustrate this by showing you an example : ----------------------------- | | | | *2 | | \ | | \ | | / \ | | | RA \ | B - - - - - - - - - - - - - - *1 | | ----------------------------- The ray enters the square at '*1' and leaves it at '*2'. Y-step is the length |B*2| - ie. it's amount to add to the Y-position of the ray for each step in the raytrace. |B*2| is calculated exactly the same way as we calculated the starting Y-position above. |B*2| = |B*1| * TAN(RA) = 64 * TAN(RA) There is just one thing to notice here. As we define the length of |B*1| as postive no matter what the RA is we have to make the result negative ourself when looking to the left (In the case above with the starting Y-position we do this by always defining |B*1| as B - *1. So if we are looking to the left Ystep = -YStep. OK.. now we have everything set up for the raytrace. We have an inner loop which traces along the map using the calculated starting X,Y values and the calculated X-Step and Y-Step values. Each time we advance the ray we calculate the XMap,YMap positions on the 2D map and check if we have hit a wall. We calculate the Xmap and Ymap positions like this : The Xmap : Xmap = XRayPos DIV 64. If we are looking to the left we want the square to the LEFT of the X-border we have hit. And so long we define our world as : World : Array[1..Size,1..Size] of byte the formula above works fine. If we are looking to the right we want the square to the RIGHT of the X-border we have hit. Therefore we add one to the Xmap if we are looking to the right. The Ymap : Ymap = YRayPos DIV 64 + 1 - this is ALWAYS true no matter which way we look. If we DON'T hit a wall we advance the ray one step and check again. We keep advancing the ray until we hit a wall or gets outside the borders of the 2D map. IF we have hit a wall there is a few things we need to do. We need to save the information on where we hit the wall - ie. the XRayPos and YRayPos of the hit. These coordinates are used to calculate the distance between the player and the hit. We also need to know the Y-position in the cell we have hit. We use this value to find the X-index in the texturemap. Notice that using raycasting we get texturemapping *WITH CORRECT PERSPECTIVE* - not that shitty linear texturemap- ping we used in tutorial 4 where we texturemapped rotating 3D objects. Anyway - the texture column is : TexCol = YRayPos - ((YMapPos - 1) * 64) Now, using this method all textures will have the same orientation. What does that mean ? It means that if we fx. were looking at a door from one side (fx. looking left on the 2D map) then walks through it, turn around and take a look again (now looking to the right on the 2D map) the door-handle would appear on the same side of the screen on both sides of the door ! Hmm... this won't do - so we decide that if we look to the left we mirror the texture index by doing : TexCol = 64 - (YrayPos - ((YmapPos - 1) * 64)) OK - this is about all there is to say about the X-ray procedure. The Y-ray is pretty much the same besides we now checks on the Y-borders of the 2D map. The trig needed for calculating Xstart, Ystart and Xstep, Ystep is NOT the same as the one needed for the X-ray procedure. Figure it out for yourself (preferrable - also for you) or check out the sample program to get the math needed. Also there are certain angles where it is'nt wise to try and take the Tangens of the value - unless you want to crash your computer :) Check out the sample program if you are having trouble sorting these angles out :) THE RENDER-VIEW PROCEDURE -------------------------- Now - this procedure is the heart of the engine. This is where the rays are fired and the screen drawn. Basicly this procedure is a loop that loops through the 320 rows on the screen and fires the 320 X 2 rays. We start firing rays 30 degrees left of the Players ViewAngle (as mentioned before). For all rows on the screen we fire TWO rays - one for the X-walls and one for the Y-walls. Both of these procedures will probably return information on a hit - so which ray do we use ?? We'll use the closest wall of cause - so we need to calculate the distance to the hit. For now I'll give you the slow but precise way of calculating the distance : Dist := SQRT((XRayXpos - PlayerX)^2 + (XRayYpos - PlayerY)^2); Calculate the distance of both the Xray and the Yray and use the one with the shortest distance. Now we calculate how big the sliver of wall should be based on the distance to it. The greater distance, the smaller wall of cause. Now we do a linear scale of the texture-index we found in the XRay or YRay procedure (centering it around the horizon of cause) - and HEY PRESTO! we have drawn one of the 320 rows of graphic needed to fill our viewport. Now advance the ray 60/320 = 0.1875 degrees and fire two more rays.... THE FISH-EYE EFFECT - AND HOW TO KILL THAT UGLY FISH! ------------------------------------------------------ If you have build your own engine by now (which I guess quite a few of you has'nt 8) ) you'll have discovered that the view is strangly twisted. It looks like the walls "bulge" out towards you in the middle of the screen. No - it's not those 20 beers you just down'ed that twists your vision - or the fun stuff you just smoke :) It's the FISH-EYE EFFECT !! Fish-eye effect happens when you raycast from a fixed point - ie. ONE single eye-point. To visualize the effect : VA -------A-----------------B---------- <-- a wall on the 2D map. \ | / \ | / \ | / \|/ P P is the player that looks straigt ahead at a wall. When one looks straight ahead at a wall it should appear as a square right ?? (Same as if you were looking directly at a CD cover you hold out before you - it sure does'nt "bulge" towards you in the middle right ?? ) But the height of the wall-slivers are calculated by looking at the length of the ray - the father the distance the smaller wall-sliver. And as we all can see the rays are longer near the edges of the wall than in the middle. The father away from the ViewAngle of the Player we get - the greater ray-lengths. Therefore of cause we get the fisheye effect. What we really need is to calculate the distances so |P VA| = |PA| = |PB| Take a look at this new situation : VA = View Angle of the Player V = The angle between the RayAngle and the plane ortogonal on the player. VA -------A-----------------B---------- <-- a wall on the 2D map. | \ | / | | \ V | V / | | \ | / | | U \|/ U | -----C--------P--------D------ When calculating |PA| we actually want |CA|. We get this by : |CA| = |PA| * SIN(U) We get the value U from 90 - V. The Angle V varies from 30 degrees (maximum difference from the ViewAngle) to 0 degrees (when the RayAngle is the same as the ViewAngle) As we ALWAYS use 320 rows for our graphic we know that V can only have 320 different values - 160 of these when tracing to the left of the Player Angle and 160 when tracing to the right of the Player Angle. The easiest way of handling the fish-eye effect is the store these 320 different Sin(U) values in a table we calculate before starting our engine up. We calculate this table like this : Angle = the V-value. angle := 30; for i := 0 to 159 do {i is a counter for the screen coulumn} begin ScaleTable[i] := SinDrg(90-angle); angle := angle - 0.1875; end; for i := 160 to 319 do begin ScaleTable[i] := SinDrg(90-angle); angle := angle + 0.1875; end; Now - when you have decided which ray to use based on the REAL lengths of the rays - ie. before using this table - you just multiply the distance by the value in ScaleTable[ScreenCoulumn]. If fx. we have a hit at ScreenCoulumn 200 at distance 750 we do : Distance := 750 * ScaleTable[200] SOME TALK OF OPTIMIZING - USING TABLES --------------------------------------- The ScaleTable above is the fist of many tables I use in the sample program. When doing a raycasting engine you perform quite alot of calculations for each screen column - and some of the slowest procedures in Pascal are the trig- functions (cos, sin and tan), the Round function and the SQRT function. And in addition using 'reals' are much slower than using integer values. In the raycasting procedures we use quite alot of tangens calculations - plus we use lots of reals. So without using tables the game will run slow - even on a pentium :) In our world we advance the rays by 0.1875 degrees. If we have a total of 360 degrees it gives us a total of : 360 / 0.1875 = 1920 possible angles in the game! In other words - we only use 1920 DIFFERENT tangens values! If we store these 1920 tangens values as reals we use 1920 * 6 = 11520 bytes of memory - but we save ALOT of time. I use the following tables : YnextTable : From the Xray-procedure. It stores the 1920 possible values of 64 * Tangens(ViewAngle) XnextTable : From the Yray-procedure. It stores the 1920 possible values of 64 / Tangens(ViewAngle) TanTable : Guess.... FishEye : Just told you above... Height : This table contains information on how high a wall-sliver should be when at a certain distance. Experiment with this table - I found that using 10000 / dist works OK... MOVEMENT - AND CLIPPING THE PLAYER TO THE WALLS ------------------------------------------------ OK - so now you have your engine up and running and all you need is to be able to move around in it. First some talk of how we handle the keypresses. My first attempt at reading the keys was simply to use the readkey procedure in pascal. If the player pressed FORWARD I would move the player forward and if he pressed turn I would turn him. The problem with this is that when you press a new key the other keypress is no longer visible. If fx. we were walking forward in our world and then - while still pressing forward - we press turn left the player would stop moving and start turning. But in all the famous games you can turn while still moving! The solution is to write a keyboard handler which takes care of the keys used in your game. If you are new to programming keyboard handlers I suggest you take a look at my previous tutorial - PXDTUT6.ZIP - which descripes interrupts, handlers and the PIT closk chip. First of all remember that when we press a key a certain scancode is sent to the keyboards data-port - and when we release the key the same value+128 is sent to the port. If we use these inputs to set (or un-set) some flags we can achive our goal to do both a turn AND a move at the same time. If fx. the player presses forward our handler sets the flag which indicates moving forwards and the inner loop will know it has to move the player. If the player then presses 'turn' a new flag is set - but the old still remains (until the forward key is released) - so the inner loop will know that it has to do BOTH a turn and a move. If a key is released the interrupt un-sets the according flag. OK - this done all we have to is to move the player. We calculate the player movement as DeltaX and DeltaY values - ie. how much has the player moved along the X-plane, and how much has he moved along the Y-plane. We calculate the values by : DeltaX = cos(2*pi * PlayerAngle / 1920) * speed DeltaY = sin(2*pi * PlayerAngle / 1920) * speed We divide by 1920 'cause this is the values of 360 degrees in OUR world. The speed variable is used to scale movement up - the greater speed the greater DeltaX and DeltaY values. I use 8 as a normal speed in my engine. OK - to move the player we just add these Delta values to his X,Y position in the world and updates the graphics according to this new position. Now to the last problem - clipping the player to the walls! This is fortunately VERY easy to do. We just check if the player when moved is in a square containing a wall. If he is - only allow him to move as close to the wall as you desires. In my engine I have a constant called CLOSEST_WALL which is the minimun units I will accept between the player and a wall at any time during play. So when cheking if the player is in a wall you have to add or subtract this constant to the player position you check on. If this gives you trouble take a look at the sample program - it's easier to demonstrate than to explain :) LAST REMARKS ------------ Well, that's about all for now. Hope you found this doc useful - and BTW : If you DO make anything public using these techniques please mention me in your greets or where ever you se fit. I DO love to see my name in a greeting :=) If you find any of the above confusing take a look at the sample program - it has LOTS of comments in it compared to my other sample programs. The engine should run OK on most machines but as it uses lots of reals for simplicity it might run a little slow on older machines. In your own engine you could convert some of the tables/math to fixed point and/or assemler code to get some speed-ups. If you take a look at my first tutorial (the one on doing step-mode 3d-worlds) you'll see that I have used the same world for both engines. But the graphic is looking a little more "ugly" in this new engine. This is because even though I use 128X128 textures in both engines the texture resolution is only 64X64 in this new engine. This is because I use 64X64 cells - and uses the Y/X-positions in these cells as texture index. If I wanted at smoother graphic I should have used 128X128 cells in this engine but as I guessed you would be looking into other engines as well - and as those mostly uses 64X64 textures - I stayed at 64X64 cells in this engine as well. Also you could try and experiment with giving the player a wider field of vision - or not using all 320 rows on the screen for the 3d-view. This would squeeze the walls a little more and make them look better when viewed close up. Anyway - as always send me some mail telling me what to do next.... Keep on codin' Telemachos