( clacking puzzle noises )shalom! how is life, family, circumstances and everything? ah, that's nice. anyway, ♪ ( begins action music )
cli 226 4 color pack, in today's video i am going to showwhat it takes to create a doom-style 3d engine from scratch. first, some important questions. why in the classic pc game of doom
when you make a map, it requiresa slow and expensive process of building a "bsp" before the map can be rendered in 3d, while in duke nukem 3d's build, you can change the mapand render it in real time? why in duke nukem 3d it is possibleto create multi-stair buildings and even non-euclidean geometry,while in doom it is not? first, let's brush up on some basicvector and perspective calculations. ♪ ( changes music to a calm theme )
let's declare a wall,which is a line segment, with two ends.an x and y coordinate for both ends. the player also has an x and y coordinate,and an angle for where he is looking towards. let's create some sample basic codefor visualizing the world we just created. sorry about using suchan obsolete language, but i have found thatin graphical programming, basic still makes for anexcellent prototyping tool. and let's face it:even if you have never programmed in basic,you can probably follow
the meaning of this codevery well for the most part. the yellow line represents the wall,and the white dot is the player, with a small line that indicateswhere the player is looking towards. in order to make a first-person engine,the global view must be transformed into a first-person view. this concept should be familiar toanyone who watched my previous video about opengl programming.in opengl, the camera never moves. instead, the whole world is moved,rotated and shorn around the perfectly immobile camera.
here, we do exactly the same.transform the world. we can see in the second windowhow the player is always in the center, and the world moves around him.this creates an illusion of a first-person view. but this isn't 3d yet. the third important step we need to learnis perspective. to perspective-project 3d coordinates into2-dimensional screen coordinates, you take the x and y coordinatesand divide them with the z coordinate. that's as simple as it is.
as you can see here,the wall seems to get smaller when the player moves away from itand larger when the player gets closer. there is a slight problem though:when the wall is even partially behind the player,something odd happens, because of negative signsthat are produced by the perspective calculations.some additional mathematics needs to be added into the program to address this specificproblem. mathematically speaking,it is the hardest part of this all. frankly, i am not even sure if i am doingit right.
to clip the wall,we need to find out where it intersects withthe player's field of vision. finding these intersections involvesa formula called "vector cross product". the vector cross product is like black magic.i still don't understand what it does, but somehow it ended upall around in my video after i read a few wikipedia articles. the wall only needs to be clippedif it's partially behind the player, i.e. one of its z coordinates is negative.if both are negative, the wall is totally behind the playerand it does not even need to be rendered.
now we can see that even whenthe player gets close to the wall, it is rendered properly. you can change the wireframe wallinto a solid wall by rendering vertical lines in a loop. a meaningful scene should also have many walls,not just one. you can notice that ceiling is always everythingabove the wall, and floor is always everything below the wall.here i have colored the ceiling gray and the floor blue. the only way this differsfrom the previous version is that
there's now five walls instead of one. this works perfectlyas long as your level geometry is completely convex.convex means that there are no dents in it.it's like a rubberband stretched over all the edge points. real world scenes, and indeed 3d game mapsrarely however are convex. here's what happensif we try to apply the same algorithm to a non-convex map.it seems to work all right, until... well, it doesn't work right.
the engine appears to be drawinga far-side wall over a near-side wall. well, that's easy to fix,you might think! let's just reversethe rendering order. and yes, this did fix the error in this veryinstance, but see, there is now another error,that wasn't there before. figuring out how to prevent far-side wallsfrom showing through near-side walls is a problem that every 3d enginein the world must solve. a related problem iswhen you have a huge map that consists of thousandsor millions of walls,
how to render only those wallsthat can possibly contribute to the view, and not spend timefutilely rendering all those walls that are completely behind other walls? unsurprisinglythere are many different ways to solve both problems. ♪ ( fades out music )for the remainder of the video, let's study how duke nukem 3dsolves the latter problem, but could in fact solve both at once,and then create our own 3d engine. ♪ ( begin ambient action music )
this is the duke nukem 3d level editor,called "build". let's create a sample map.so far it's just a simple rectangular room. but suppose we wanted to havethe ceiling in one part higher than in another part?we would have to divide the map into two sections, called "sectors". the ceiling and floor heightsfor different sectors can be adjusted separately. this geometry is still all convex.there are no indents anywhere in the map geometry.
suppose we create some obstacles, though. now the map geometry containsobstacles and corners through which you cannot see something anymore.in other words, it is non-convex. however, each individual sector of the mapis still convex. non-convex geometry is created by joiningseveral convex sectors together. if you pay attention tohow it is all rendered, you will see thatthere are now two types of walls, or sector edges: regular walls,that span from our floor to our ceiling.
and doorways, or portals,which have three segments: a wall that spansfrom our floor to their floor; a window through whichthe next sector can be seen; and finally a wall that spansfrom their ceiling to our ceiling. in the editor you can see the difference moreclearly: a white edge is one where there's nothingbehind, i.e. it's a wall that spans from floor toceiling. and a red edge isan edge between two sectors. we call these red edges, "portals".
now what happensif their floor is lower than the floor of our sector?the lower wall segment just shrinks, until it doesn't get rendered at all.similar thing happens with the ceiling. the upper wall is rendereddownwards beginning from our ceiling, until we reach their ceiling.if their ceiling is higher, we simply start rendering their sector immediately. for the purpose of this video,i created a simple custom map. this map contains multiple sectors,windows between different sectors, staircases, rooms verticallyon top of each others,
and even non-euclidean geometry.perfect for our sample program. going back to my high-tech illustration board, ( paper shuffling noises ) i drew the map on paper,and numbered each vertex and each sector, and having done that, i wrote those numbersand their coordinates into a text file. now i am going to dosomething revolutionary as far as my videos are concerned.i am going to write some c code.
not c++.i know, this sounds incredible. but as i was designing thetutorial program for this video, i thought to myself:why not write c for a change? after all,there are people in my audience who love c, but are totally lostwhen i write c++ code. so today is your day:i am writing code that is strictly c with none of those c++ gimmicks. so the first part of this programdeals with loading the map that i just showed to you,into data structures used by this program.
because the file handling codeis somewhat dull to watch, i sped it up by 200%.rest assured, i won't do that again in the remainder of this video. actually, maybe it's just mewho is the dull one here. maybe i should just shut up andlet the code speak for itself. this is the part wherei regret a little that i chose to write in c. oh well. here is the c versionof the "vector cross product" function. as you can see,it can be used to implement
several other useful functions.i have no idea why it works, but it does,which is the important thing. now we are gettingto the actual drawing code, so please pay attention. remember how i explained beforehow everything is going to be drawn using vertical lines?this vline function will be used to draw ceilings, walls, and floors,i.e. the whole screen. no other graphics functionswill be needed for our prototype 3d engine. the rendering will beginfrom the sector where the player is in.
all edges of this sector will be processed: the edge is first translated and rotatedso it's relative to the player's gaze, and then the signs of the resulting z coordinatesare inspected to determine whether the edge is visiblefrom the player's point of view. once we have a visible edge,we can do perspective transformation. this transformation is accomplishedby these "scale" division calculations. from the perspective transformations,we get screen coordinates: an x coordinate for the left side of the walland an x coordinate for the right side of the wall,and a y coordinate for the floor and ceiling
heightsin both sides of the wall. oh, before that,we must do the clipping trick that i explained at 2:52 in this video. anyway, from those coordinates,drawing the wall is just a matter of linear interpolationand calling vline in a loop. we will draw three vertical lineson each x coordinate: one from top of window to the ceiling height,indicating the ceiling. one from the floor height to the bottom ofthe window, indicating the floor.
and one from the ceiling height to the floorheight, indicating the wall. for now, we draw walls with different colorswhen they are portals or when they are actual walls. here's what it looks like!remember, walls are drawn white. portals are drawn red.the floor is blue, and the ceiling is gray. on the right, you can see the map for reference.observe how a different view gets drawn when the player crosses a sector edge. now the next step isto add the upper and lower walls,
above and below the portal.this was explained at 6:20 in this video, so if you are confused as to what's happening,please watch that part again. ♪ ( music becomes louder as the narrator pauses ) and this is how it changedas a result of this update. the lower wall is drawn in magenta.the upper wall is drawn in white. and the window, or portal, is drawn in red. the only thing remaining isto draw the neighboring sector in that window! to do that, we need three things: first is some means to draw another sector.you could use recursion to do that.
here i used a circular bufferas a queue of pending sector draw requests. second is the window size.by window, i mean the screen area where this sector can be drawn.for the player's sector, this area is the entire screen.for any neighboring sector, it is a smaller view:there is a left edge (sx1), and a right edge (sx2).additionally, there's a top and bottom y coordinate for each column on the screen.this vertical window gets smaller and smaller the deeper you go in the view. and thirdly, you need...
wait, i guess you only needtwo things after all. this clip shows in slow motionhow the screen gets rendered by this algorithm. aside from the familiar colors,it shows the current window in green. you can see quite clearlyhow it considers each edge (green) in turn, drawing either a fully white wall,or a white upper wall, a red portal, and a magenta lower wall.here is another viewpoint. when all edges of the current sector havebeen rendered, it picks one of the remaining red portals,and repeats the process inside that window. this is the rendering at normal speed.
observe how things like tunnels under thestairs, or windows in walls, are supported withoutproblems. on the right, you can see a from-top illustrationof what the player is currently seeing. the current sector is indicated in red shading. any part of a floor or a ceilingthat is currently within the player's view is indicated in green, violet or gray shading,for an effect that looks a bit like a torch beam. now i cheated here a little,because i demonstrated the program before it was even finished.i didn't even add the main program yet!
for the sake of completeness,i will add the remaining parts to the program, so you will not feel cheated. this function, moveplayer,is responsible for making sure that the game always knowswhich sector the player currently is in, even as he moves aroundand crosses the edges of the sectors. calculating the intersectionbetween two lines is a vital part of the algorithm:the game must know when the player crosses an edge between two sectors. if you are currently in collegeor high school, or in gymnasium,
or in some other type of school,where you study geometry and other advanced aspects of mathematics,it is things like this -- calculating the intersectionbetween the player character's movement vector and the edge of the sector --where what you have learned in school becomes crucial to your success. now let me emphasize this:while it is very useful that you learn all these mathematical formulae,the above all, hands down, most important skillthat you should learn is the ability to identify the type of the answer you arelooking for, and then look for it.
in the case of this program:when the player moves from a sector to another sector,you need to identify that you need a way to detectwhether two line segments intersect or not. even if you don't know how to determinewhether two line segments intersect, you can use cool websiteslike wikipedia or wolfram alpha to find your answer, like i did.you don't necessarily need to remember the mathematical formula,though it helps a lot. but if you cannot even identifythe problem you are having, it would be very difficultto find an answer to the problem.
you could then try asking in the internet,on sites like stack overflow, but chances of getting a good answerwould be significantly lower. here's another instance ofwhere i identified the problem and looked for answers in the internet.when the player is pushing against the wall,we need to a formula that produces a vector that is parallel to thewall, but has a length that dependson the angle between the player's movement and the wall's direction. this formula is called "vector projection",and i copied it directly from wikipedia.
this produces the "sliding along the wall"effect that is standard in all thirdperson games today. this simple hack hereadds support for looking up and down, with the restriction thatall walls still remain perfectly vertical. now, suppose we want to addsome depth shading to the walls. a very simple way to do thatis to color the vertical line with a darker colorwhen the wall is farther from the camera, i.e. z coordinate is higher.here is what it looks like in practice. ♪ ( begins sporty action music )
compared to the previous version,the difference is huge, even though it is still alldrawn using vertical lines of single color. now, just for my own entertainment,eventually i also added texture mapping to the program.and feeling that isn't enough, i also added lightmapping. i am however not feelingthat my texture mapping code is particularly presentable,so i won't show that in my video. if you are interested though,you can read the video description: a link to a page containing all thesource code related to this video's programs
is included in the video description,including the code that renders textures and precalculates lightmaps using raytracing. now as usually happens in programming,the devil is in the details: relatively small things can end up consumingthe bulk of the time of the programmer. there are some errors in this program,such as in the collision checks, causing bugs from time to time.i didn't even cover a very important part
of addingobjects and actors to the scene, such as health packs or enemies,because i couldn't yet think of an efficient way to do it.that will remain as another problem to solve.
thanks for watching! see you next time, bye.
