How To Write 3d Qbasic Stuff That Actually Works

First rule of 3d design is always to keep it simple!! We're Qbasic programmers, okay? We don't have $10 million budgets and an art department. Who wants to spend 10 hours finding a single bug in the middle of code that looks like a spagetti monster? And a 3d system should not only look good but be easy to work with when time comes to make the actual game you wrote the system for.

I'm sure as a competent Qbasic programmer you've made the typical "Wolfenstein 3d" game where you walk around nice colored blocks of wall segments. Snazzy huh?

The nice thing about this is you can design levels easily, and it doesn't look that bad. But if you could just go one step further, it would have much more possibility and impact.

Look around the room where you are. Chances are that if you're not inside a space capsule, the walls are flat, the floor is flat, and there are windows and doors, which lead outside or to other rooms.

The 3d engine I will talk about making is done in a similar way. It is made up of 3d "rooms" with multiple walls that are connected. Actually, a doorway or window is also a "room", just smaller and sometimes raised in height. These rooms are called "sectors".

Now if you look through a door or window, you'll notice that everything you see through it is inside the frame made by the four corners. If there is another window or door beyond, you can also see everything beyond through it's corners. This seems obvious but it is very important later.

Try this: Make a map of a level for your game. Use only straight lines showing walls, that make up sectors. Now each sector should be convex, that is, without any corners dipping towards the center, but always outward like a square or hexagon. Windows and doors should be smaller sectors. Don't think about heights yet.

Now put an eyeball in the center of one sector. If the eyeball looks around inside that sector, it sees the walls, and every time a wall is a door or window leading to another sector, that part of the other sector is seen only inside the empty space where the door or window is. The computer screen itself is treated as a kind of window for the player, so that the player is "looking" through it.

This leads to a very simple algorithm for doing this kind of 3d:

1. Have the player's eye look at the walls in the sector it is in, based on the current viewing window.
a. for each wall, if it is opaque, draw it to perspective.
b. if it is a door or window or something else
open, then go to the next sector beyond it,
and go to step 1, using the door or window's
corners as the new viewing window.

Basically this continues until the screen is drawn.

Sounds really simple, right? Sounds too simple? Well it actually works perfectly.

In order to draw a wall, what kind of information do you need before it hits the screen as pixels?

Basically, you need the left and right boundaries of the wall on the screen, and the distance to the left and right edges so you can calculate how tall the wall looks on the screen.

So you can use an equation like this, for the top of the left edge of the wall (and for the other three corners also:

(where fov is the size of the field of view on the screen)

y value on screen = fov * height of wall / distance to wall + middle of screen

This will take the top of the wall, put it back according to how far away it is in the field of view, and then make it all relative to the center of the screen, so the wall isn't hanging off the edge somewhere. Fun stuff, right? The way we've always done it right?

Not exactly fun though. Suppose you have a wall that goes BEHIND the player's viewpoint? Then you have to chop the wall in half and only display the part that is visible or you get really bizarre errors that make your program look like a 3rd grade science project.

Then, if the wall sticks up over the top of the screen's edge, or pokes too far to the left because it's close to the viewer, you have to chop THOSE parts off also, and it gets ugly fast, and if the wall is too close and you chop it wrong, you can't see through the sectors beyond, and etc, etc, and who really wants to deal with all that junk anyways???

So I developed a MUCH BETTER, easy system to put a wall from map coordinates to the screen, no questions asked!!!

The skinny is this. If you want to draw part of a wall, you only need the DISTANCE and ANGLE to the left and right edges of the wall, not the actual x,y coordinates of said edges. Although they are useful for texture mapping.

So instead of calculating the part of the wall that is visible, I just made a simple algorithm that takes a wall and sends a ray at it, and then returns the distance the ray travels before hitting the wall, all through simple vector math (don't run!! It's simple!! I promise!!).

So basically, now to start drawing the walls in a sector, do this:

1. send a ray from the farthest left side of your player's viewpoint and see which wall it hits and how far to that wall that it hit.

2. now see how far away the right edge of that wall is.

3. Using the left and right distances, calculate the wall's height at the left and right edges that are visible. Using only this information, you can now draw the wall as a four-sided shape using lines or whatever else is convenient.

To do this, I invented a nifty algorithm!!! I will try to explain it. Feel free to rip me off and copy it, I don't care. Or improve it, or whatever. I know the frustration of debugging this kind of junk from scratch.


By opie_rains, shot with HP
oj6200 at 2008-09-06

FUNCTION getdist! (p1x!, p1y!, p2x!, p2y!, vb)

' find distance to a spot on a wall from p1 to p2 '
' that is hit by a ray vb

dx! = p1x! - p2x!
dy! = p1y! - p2y!

IF ABS(dx!) > .05 THEN

m! = dy! / dx!
b! = p1y! - m! * p1x!
gdist! = b! / (1 - m! * TAN(vb))
oldx = gdist! * TAN(vb)
getdist! = gdist!

ELSE

m! = dx! / dy!
b! = p1x! - m! * p1y!
gdist! = b! / (TAN(vb) - m!)
oldx = gdist! * TAN(vb)
getdist! = gdist!

END IF
END FUNCTION

So what is this doing? It inputs a line, from point (p1x, p1y) to (p2x, p2y) and then cuts it into two pieces with a ray going through it at angle vb. The ray comes from the point (0, 0), at the place where the player is looking from. The return value getdist! is the distance to the line that the ray travels to hit the wall. Actually, it is the distance on the y-axis, because if you use the total distance, then the results look funny on the screen. If needed, oldx can be a global variable which holds the distance along the x-axis.

So now you've hit a wall inside a sector, and you know how far away it is at the point of impact. Now what? If you've set up your rooms so that all the walls are in clockwise order, then the obvious thing to do is just draw the next wall in the list, and then the next, until the next wall hangs over the right side of the screen!!! Piece of cake.

So how do I check if the wall hangs over the right side of the screen, eh? Or over the viewing window made by a door? With a little angular cunning, that's how!!

Traditionally, programmers would put a thing called a "viewing frustum" on the player's viewpoint, which consists of lines that chop up everything that is out of the viewing window. It's kind of like that paper collar your dog had to keep him from scratching his stitches. The only problem is that a frustum is frustrating and complex.

A more simple system is just to set left and right angle boundaries for the viewpoint, and then add a number to the angles to make the viewpoint rotate!! Actually, the cool thing is is that by using the getdist! function, the left boundary has already been established by the angle vb, and you can just forget about it!!!

The right boundary is just as easy.

First, just take the left and right sides of a wall, find the angles that the viewer sees them at, and then see whether those angles are greater or less than the one used for the right-side boundary.

This function will change a set of (x,y) coordinates into an angle in radians: (make sure that radpi is a global variable equal to pi!!!)

Specifically, the angle will always be neatly between 0 and 2 x pi.

As always, feel free to use this function, because it was a pain to write but makes soooo many calculations easier.

FUNCTION angleize% (x AS SINGLE, y AS SINGLE)

'
' take x, y and find an angle between 0 and 2pi rads
'
'

IF ABS(x) < 1 AND ABS(y) < 1 THEN angleize = 0: EXIT FUNCTION

IF x >= 0 AND y >= 0 THEN

IF x > 1 THEN

angleize = ATN(y / x)

ELSE

IF y < .01 THEN angleize = (radpi * .5 - 1.57): EXIT FUNCTION

angleize = ((radpi * .5) - ATN(x / y))

END IF

END IF

IF x < 0 AND y >= 0 THEN

IF x > -1 THEN

angleize = (radpi - ATN(y / -x))

ELSE

IF y < .01 THEN angleize =(radpi * .5 + 1.57): EXIT FUNCTION

angleize = ((radpi * .5) + ATN(x / -y))

END IF

END IF

IF x < 0 AND y < 0 THEN

IF x > -1 THEN

angleize = (radpi + ATN(y / x))

ELSE

IF y > -.01 THEN angleize = (radpi * 1.5 - 1.57): EXIT FUNCTION

angleize = ((radpi * 1.5) - ATN(x / y))

END IF

END IF

IF x >= 0 AND y < 0 THEN

IF x > 1 THEN

angleize = ((2 * radpi) - ATN(y / -x))

ELSE

IF y > -.01 THEN angleize = (radpi * 1.5 - 1.57): EXIT FUNCTION

angleize = ((radpi * 1.5) + ATN(-x / y))

END IF

END IF

END FUNCTION

NOTE: THIS PAGE IS STILL BEING CONSTRUCTED, SO CHECK BACK IN A FEW DAYS FOR LOTS MORE INFO

So once you've got your boundary angles, you've got your wall edge angles, now what? There's got to be a way to compare them.

Fortunately, I've already written yet another function that takes two angles and sees which one is farther clockwise. It's called greater!

FUNCTION greater (a2, a1)
'
' compare two angles (in rads) and see which is farther clockwise
' comparison is based on the shortest angle between them
' angles are fixed to be between 0 to 2pi rads
'
'

an1 = fixtheta(a1)
an2 = fixtheta(a2)

IF ABS(an2 - an1) > pi THEN

an1 = an1 + pi
an2 = an2 + pi

an1 = fixtheta(an1)
an2 = fixtheta(an2)

END IF

IF an2 > an1 THEN greater = 1 ELSE greater = 0
IF an2 = an1 THEN greater = 2

END FUNCTION

Well fixtheta is a very minor function that just makes sure an angle is neatly between 0 and 2 x pi, which is the same as 0 to 360 degrees.

FUNCTION fixtheta (an)

'
' make an angle be between 0 and 2pi rads
'
'
'

a = an

WHILE a > 2 * pi
a = a - 2 * pi
WEND

WHILE a < 0
a = a + 2 * pi
WEND

fixtheta = a

END FUNCTION

Another fine function I should mention is between, which takes two angles and sees if a third one lies between them, according to the closest distance to either side angle. This one is very handy also.

FUNCTION between (a1, a2, a3)

'
' see whether a1! < a2! < a3! in a clockwise way
' comparison is done through the shorter angle between a1! and a3!
' where all are fixed to be within 0 to 2pi rads
'
'

an1 = fixtheta(a1)
an2 = fixtheta(a2)
an3 = fixtheta(a3)

IF ABS(an3 - an1) > pi THEN

an1 = an1 + pi
an3 = an3 + pi
an2 = an2 + pi

an1 = fixtheta(an1)
an2 = fixtheta(an2)
an3 = fixtheta(an3)

END IF

IF an1 <= an2 AND an2 <= an3 THEN between = 1 ELSE between = 0

END FUNCTION

SO what can you do with these handy functions to make great 3d with not much struggle??? Lots!!! Let's try drawing a single room of walls, with no windows or doors in it, where "left" and "right" are
global variables showing the left and right angles of the current viewpoint. left = -.8 and right = .8 are good values.

Also needed are the getx and gety functions, which I will show after. Right now I'm just showing how the algorithm works.


By opie_rains

hit = -1

FOR i = 0 TO sectors(s).numwalls - 1

wi = swalls(s, i)

IF NOT wi = -1 THEN

DIM tx1 AS SINGLE
DIM ty1 AS SINGLE
DIM tx2 AS SINGLE
DIM ty2 AS SINGLE

DIM pt AS SINGLE

p1 = walls(wi).p1
p2 = walls(wi).p2

tx1 = pts(p1).x
ty1 = pts(p1).y

tx2 = pts(p2).x
ty2 = pts(p2).y

a1 = angleize(ty1, tx1)
a2 = angleize(ty2, tx2)

IF greater(a1, a2) = 1 THEN

tp = a1
a1 = a2
a2 = tp

END IF

IF between(a1, left, a2) = 1 THEN hit = i

END IF

NEXT i

I will explain a bit later about the walls() amd swalls() arrays, etc., which hold the 3d map data.

So here is the scoop: we take the current sector, go through each wall, and see if the left-angle boundary of the viewing window fits BETWEEN the left and right angle boundaries of any wall. The one wall that this is true of is the first one to draw. The number of the wall is stored then in the variable "hit".

Now, using the hit variable, we can start drawing from left to right across the walls in the sector, until the rightmost angle boundary of the viewing screen is passed over. Which is when to stop, of course, because you can't draw beyond the edge of the monitor.

lnext = left

WHILE hit <> -1

'
' get wall index from list of walls in sector
'
'

w = swalls(s, hit)

'
' if end of wall list is reached, go to beginning again to continue
' in clockwise order around the sector
'
'

IF w = -1 THEN

hit = 0
w = swalls(s, 0)

END IF

IF w = 0 AND s = 0 THEN

END IF

' color data for wall
'

wcolor = walls(w).wcolor

'
' increment counter
'

hit = hit + 1

'
' get boundary points on wall
'
'

p1 = walls(w).p1
p2 = walls(w).p2

tx1 = pts(p1).x
ty1 = pts(p1).y

tx2 = pts(p2).x
ty2 = pts(p2).y

a1 = angleize(ty1, tx1)
a2 = angleize(ty2, tx2)

' make sure that a2! is clockwise to a1!

IF greater(a1, a2) = 1 THEN

pt = tx1
tx1 = tx2
tx2 = pt

pt = ty1
ty1 = ty2
ty2 = pt

at = a1
a1 = a2
a2 = at

END IF

' move left-hand boundary marker to next position

lmark = lnext

' get viewing distances to start and end of walls

dstart! = getdist!(tx1, ty1, tx2, ty2, lmark)

' make sure that if wall is clipped by right boundary, to make dend! correct
'

IF greater(right, a2) = 1 THEN

' right boundary is beyond wall, use clockwise farthest point of wall

dend! = getdist!(tx1, ty1, tx2, ty2, a2)

r = getx(a2)
lnext = a2

ELSE

' use right boundary to find distance instead

dend! = getdist!(tx1, ty1, tx2, ty2, right)

r = getx(right)
lnext = right

' set drawing on this sector to end because boundary has been reached

hit = -1

END IF

l = getx(lmark)

dx! = r - l

IF dx! < 1 THEN dx! = 1

ltop = gety(sectors(s).c, dstart!)
lbot = gety(sectors(s).f, dstart!)

rtop = gety(sectors(s).c, dend!)
rbot = gety(sectors(s).f, dend!)

dytop! = (rtop - ltop) / dx!
dybot! = (rbot - lbot) / dx!

'
' draw the wall section already!!!
' for now, use very simple lines.
'

line (l, ltop) - (l, lbot) , wcolor
line (r-1, rtop) - (r-1, rbot) , wcolor
line (l, ltop) - (r-1, rtop) , wcolor
line (l, lbot) - (r-1, rbot) , wcolor

WEND

This code isn't that bad, compared to some of the nightmarish rube-goldberg things I've tried writing before to get 3d graphics to work. In fact, it's downright friendly!!! So once we find the first wall to start drawing at from the left boundary, we just draw merrily along until the right boundary is reached, then draw that wall's visible part according to the right-hand angle, and then stop. Zounds!!! Too easy!!!

A few variables are easy to explain. "s" is the current sector to draw, "lmark" is the left-boundary of the CURRENT wall to draw. "lnext" is the left-boundary of the NEXT wall in the list, which happens to always equal the right-boundary of the CURRENT wall, because they meet at a corner. "r" is the right boundary of the current wall also.

The "IF greater(right, a2) = 1 THEN" part of the code simply is checking if the current wall sticks out over the rightside boundary yet, and sets variables accordingly. If the answer is yes, "hit" is set to -1 to signal the loop to end.

Now for the getx and gety functions: They just take the angular data and change it to how you see it on the actual screen. fov is some value like 100, and midx and midy are the center of the screen , which is usually 160 and 100 for screen 13 graphics. Basically take the width and height of the screen and divide in half.

FUNCTION getx (a)

'
' from an angle value, find the x screen position it corresponds to
'

getx = fov * TAN(a) + midx

END FUNCTION

FUNCTION gety (height!, dist!)

'
' find the y position on the screen for a point at a certain height
'

d! = dist!
IF d! < 1 THEN d! = 1

gety = fov * (height! - vh) / d! + midy

END FUNCTION

For gety, height! equals the height of the floor or ceiling of a room ( and therefore of all the walls in that room ), and vh is the player's height. dist! is the distance to a point on a wall, so that the greater distance it is, the smaller and farther away that spot is.

Now about those data arrays I promised:

' 3d world map data

TYPE pt

x AS SINGLE
y AS SINGLE

END TYPE

TYPE wall

p1 AS INTEGER
p2 AS INTEGER
s1 AS INTEGER
s2 AS INTEGER
wcolor AS INTEGER
flag AS INTEGER

END TYPE

TYPE sector

numwalls AS INTEGER
f AS SINGLE
c AS SINGLE
fcolor AS INTEGER
ccolor AS INTEGER
midx AS SINGLE
midy AS SINGLE

END TYPE

' 3d world info

DIM SHARED pts(maxpts) AS pt
DIM SHARED walls(maxwalls) AS wall
DIM SHARED sectors(maxsectors) AS sector
DIM SHARED swalls(maxsectors, maxswalls) AS INTEGER

DIM SHARED numsectors AS INTEGER

Simply put, pts() holds the point data as such:

pt(p1).x = 100 (or whatever)
pt(p1).y = -53.7

walls holds wall data, such as which two points make up the wall, and what color it is, and which rooms are on either side of the wall, if any.

sectors holds sector data, like floor and ceiling height, number of walls, and the middle of the sector, which is not used yet.

Especially important is the swalls array, which works like this:

swalls ( # of sector , # of wall in sector ) = # of wall on the map in the walls( ) array.

Example:

swalls( 10, 3 ) = 5

so, if sectors(10).numwalls = 6 and swalls(10, 3) = 5, then this means sector # 10 has 6 walls, and the #3 wall in its list is actually wall #5 on the whole map, according to the walls() array. This is because each sector only uses some of the walls in the whole map, of course, so it's easier to do it this way.

Here is some sample data:


By opie_rains

pts(0).x = -150
pts(0).y = 150

pts(1).x = 0
pts(1).y = 200

pts(2).x = 150
pts(2).y = 100

pts(3).x = 130
pts(3).y = -100

pts(4).x = -130
pts(4).y = -120

walls(0).p1 = 0
walls(0).p2 = 1
walls(1).p1 = 1
walls(1).p2 = 2
walls(2).p1 = 2
walls(2).p2 = 3
walls(3).p1 = 3
walls(3).p2 = 4
walls(4).p1 = 4
walls(4).p2 = 0

walls(0).wcolor = 1
walls(1).wcolor = 2
walls(2).wcolor = 3
walls(3).wcolor = 2
walls(4).wcolor = 1

sectors(0).numwalls = 5
sectors(0).c = -50
sectors(0).f = 70

swalls(0, 0) = 0
swalls(0, 1) = 1
swalls(0, 2) = 2
swalls(0, 3) = 3
swalls(0, 4) = 4

This makes a 5 - sided room with walls in clockwise order.

NOTE: I WILL ADD MORE STUFF SOON ABOUT HOW TO ADD DOORS AND WINDOWS TO THE ROOM!!!