Dungeon Crawlers-Before true 3d.

[Pixel_Outlaw]

Does anyone know how to set up the walls and such from a pseudo-3D first person dungeon crawler?

I'm talking games like

Phantasy Star 1 (the game had 3D dungeons)
Dungeon Master (series)
Sword of Vermillion (outside areas)


They all seem to work from "one vanishing point perspective" but I've only been givin a rough overview of the concept in a geometrical sense. Coding seems to work more on algebra than visual geometry. If possible I would like to take textures and stretch them onto the walls as polygons. There is really no modern 3d here. To find the points I was taking the 3d point (x,y,z) and plotting it as (x/z,y/z). It seemed to work untill I started moving forward and backward. This is just a snippet of code to show the projection.

Code: [Select]

Strict
' perspective test
GLGraphics 640, 480 
glMatrixMode (GL_PROJECTION)
glOrtho(0, 640, 480, 0, - 1000, 1000)
glMatrixMode(GL_MODELVIEW)
' set up camera
Global camera_x:Float = 320.0
Global camera_y:Float = 240.0
Global camera_z:Float = 0.0
Global points:TList = New TList

' make a point type
Type point
Field x:Float, y:Float, z:Float, px:Float, py:Float ' px and py are projected x and y from x,y,z

Function Create(x:Float, y:Float, z:Float)
Local p:point = New point
p.x = x
p.y = y
p.z = z
p.update
ListAddLast(points, p)
End Function

Method update()


Local scale:Double = camera_z / z

Local x_dis:Float = camera_x - x
Local y_dis:Float = camera_y - y
px = camera_x + (x_dis * scale)
py = camera_y + (y_dis * scale)
End Method
End Type


For Local z:Float = 0 To 100 ' 100 z depths
For Local i:Float = 0 To 3 ' 4 points per depth level
point.Create(camera_x + Cos(i * 90 + 45) * 128, camera_y + Sin(i * 90 + 45) * 128, z * 50)
Next
Next



While Not KeyDown(KEY_ESCAPE) 
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT)


glPolygonMode(GL_FRONT_AND_BACK, GL_LINE)
glBegin GL_QUADS

For Local i:point = EachIn(points)
i.update() 
glVertex2f i.px, i.py
Next
glEnd

' move z value
If KeyDown(KEY_UP)
camera_z:+0.1
End If
If KeyDown(KEY_DOWN)
camera_z:-0.1
End If
glPolygonMode(GL_FRONT_AND_BACK, GL_FILL)
GLDrawText("Camera  z" + camera_z, 12, 12)
Flip

Wend


[zawran]

I am thinking that you don't need to do "real" 3D for this. You could have predrawn dungeon pieces (left, right and front facing walls at different depths) and then go through the array in the direction the player is facing with the furtherst most field first and then closer to the player.

[edit] Here is a quick idea of how to use polys to draw walls. You would need a textured poly function ofcause, this one is using the regular one.

Code: [Select]

Graphics 640,480
Cls

Global wallLeft0:Float[] = [0.0,0.0,32.0,16.0,32.0,144.0,0.0,160.0]
Global wallLeft1:Float[] = [32.0,16.0,64.0,32.0,64.0,128.0,32.0,144.0]
Global wallLeft2:Float[] = [64.0,32.0,96.0,48.0,96.0,112.0,64.0,128.0]
Global wallMid2:Float[] = [96.0,48.0,160.0,48.0,160.0,112.0,96.0,112.0]
Global wallRight2:Float[] = [160.0,48.0,192.0,32.0,192.0,128.0,160.0,112.0]
Global wallRight1:Float[] = [192.0,32.0,224.0,16.0,224.0,144.0,192.0,128.0]
Global wallRight0:Float[] = [224.0,16.0,256.0,0.0,256.0,160.0,224.0,144.0]

SetScale 2.0,2.0
SetColor(255,255,255)
DrawPoly(wallLeft0)
SetColor(208,208,208)
DrawPoly(wallLeft1)
SetColor(160,160,160)
DrawPoly(wallLeft2)
SetColor(112,112,112)
DrawPoly(wallMid2)
SetColor(160,160,160)
DrawPoly(wallRight2)
SetColor(208,208,208)
DrawPoly(wallRight1)
SetColor(255,255,255)
DrawPoly(wallRight0)

Flip
WaitKey
End

Another example:

Code: [Select]

Graphics 640,480
Cls

Global wallLeft0a:Float[] = [0.0,0.0,32.0,16.0,32.0,144.0,0.0,160.0]
Global wallLeft1a:Float[] = [32.0,16.0,64.0,32.0,64.0,128.0,32.0,144.0]
Global wallLeft2a:Float[] = [64.0,32.0,96.0,48.0,96.0,112.0,64.0,128.0]
Global wallMid2:Float[] = [96.0,48.0,160.0,48.0,160.0,112.0,96.0,112.0]
Global wallRight2a:Float[] = [160.0,48.0,192.0,32.0,192.0,128.0,160.0,112.0]
Global wallRight1a:Float[] = [192.0,32.0,224.0,16.0,224.0,144.0,192.0,128.0]
Global wallRight0a:Float[] = [224.0,16.0,256.0,0.0,256.0,160.0,224.0,144.0]

Global wallLeft0b:Float[] = [0.0,16.0,32.0,16.0,32.0,144.0,0.0,144.0]
Global wallLeft1b:Float[] = [32.0,32.0,64.0,32.0,64.0,128.0,32.0,128.0]
Global wallLeft2b:Float[] = [64.0,48.0,96.0,48.0,96.0,112.0,64.0,112.0]
Global wallRight2b:Float[] = [160.0,48.0,192.0,48.0,192.0,112.0,160.0,112.0]
Global wallRight1b:Float[] = [192.0,32.0,224.0,32.0,224.0,128.0,192.0,128.0]
Global wallRight0b:Float[] = [224.0,16.0,256.0,16.0,256.0,144.0,224.0,144.0]

SetScale 2.0,2.0

'ceiling
SetColor 0,0,255
DrawRect 0,0,256,80
'floor
SetColor 0,0,128
DrawRect 0,160,256,80

'walls
SetColor(255,255,255)
DrawPoly(wallLeft0b)
SetColor(208,208,208)
DrawPoly(wallLeft1a)
SetColor(160,160,160)
DrawPoly(wallLeft2b)
SetColor(112,112,112)
DrawPoly(wallMid2)
SetColor(160,160,160)
DrawPoly(wallRight2b)
SetColor(208,208,208)
DrawPoly(wallRight1a)
SetColor(255,255,255)
DrawPoly(wallRight0b)

Flip
WaitKey
End


[Pixel_Outlaw]

I did try that but I really would like attention to the wall's widths. Most primative games did keep attention to the way the walls widths change as they get further from the viewer.

I guess my question is what is the relation to apparent size as an object moves from the camera?

[zawran]

How about a scale relation of 1.5, 1.0, 0.75 ?  So that if you can view 3 levels out, then your middle wall would have a width of 1.0, then wall closest to you would have a widht of 1.5 and the one furtherst away would have a widht of 0.75. If I draw that on paper it looks alright to me.

Here is an example showing equal wall widths versus the relation described above (equal on the left, relation on the right):

[Pixel_Outlaw]

I may have cracked it geometrically. I'm not sure that the circle is the correct approach but it seems to give a very good result.
Hell, I feel like a Renaissance artist. I kind of went on gut instinct with the circle. The red line is a projection plain and the blue lines are projection lines where the verticies cross the projection plain. They are then distended down into the frontal pictorial view. Like I said, I'm an amature draftsman going on gut instinct. This could be incorrect. The top drawing is a top down view and the lines must intersect the circle the width of the viewing plain while heading toward the viewer's eye.

[zawran]

That looks closer to something like raycasting, which could be used ofcause, I am just not sure thats what they used. I think that they faked it and just drew predrawn graphics where the walls should be. The reason that they could easily get away with doing this is that the player movement was fixed to N,E,S,W movements and the dungeon was made up of square "rooms" put together. So where ever the player viewed, the perspective would never change and so the walls would always have the same dimensions.

If you have a more freely motion control system, somewhat like with castle wolfenstein and doom, then you would need to use some math to figure it out because walls would also be viewed at angles other than those 4 (0,90,180,270).

[Shockwave]

I think Zawran is right. Games like Dungeon Master and Captive etc must have faked thier wall displays somehow... Whether the images were loaded in or precalculated.

 There was no way that an Amiga 500 could have rendered those fairly detailed displays in real time.

There's no reason why you should not write a raycaster however. Plenty of people here can help you do that if you get stuck.

[rain_storm]

the use of a circle there is gonna cause problems because the monitor is a flat surface. Those intercept points should all be plotted along the projection plane which is flat also. They probably didnt use rays to define these walls if they did use rays then it seems insane that they didnt also use textures for the walls since raycasting makes texturing such a cheap process

[Jim]

it seems insane that they didnt also use textures for the walls since raycasting makes texturing such a cheap process

The Amiga 500 didn't have any fast way of drawing individual pixels, and in particular, no way of drawing textured vertical strips which would be needed for raycasting - each pixel per scanline would have needed a blit to be set up, or up to 5 read+and+or+write operations.  The screen was arranged in planes of 1bit per pixel.  If you used more than one plane you got double the number of colours for each plane.  2planes=4cols, 3=8, 4=16, 5=32.  This meant the hardware was cheap to scale.  To set a single pixel colour on a 5 bitplane screen, you'd have to set 5 bits on or off, one in each plane, but since the pixels are bits, you had to read the byte or word containing the bit, modify the bit, and store it back down.  Way too slow.  The A500 had hardware to accelerate drawing to this kind of display, but it was only good for horizontal and block-wise stuff.  The A1200 had some pixel-to-planar hardware that let later games do this kind of trick.

Jim

[Pixel_Outlaw]

Thanks for all of your thoughts gentilmen.

I do plan to use textured quads for this but no 3D Z coordinates. I plan to find the relation between distance from the eye and scale of the object. I will be drawing polygons but probably won't do any ray tracing. With that said I've always wanted to see a maze game done in a very wide angle lens. I think that the walls must be porportionate to each other and using a set scaling system should be the key to this.

I assume raycasting and setting all the rays to have a universal length would produce a wide lens effect.

[Stonemonkey]

Hi Pixel_Outlaw, something I tried before was to draw walls (from 2D map) to a 1D z-buffer. Gave similar results to raycasting but much faster (compared to my own raycaster) and allowed for textured walls positioned at any angle.

[Pixel_Outlaw]

Would you have a snippet of source sir?

[Stonemonkey]

Can't find anything atm but i'll keep looking or write an example. It's not dissimilar from what you'd do in 3D except you only need to do 2D transforms to get the x and z coordinates then render that into a 1D z-buffer (1.0/z) and a tex_coord(u) buffer that are the width of the display interpolating 1.0/z and 1.0/u and storing those values if z passes. The height of the wall for that pixel column on the screen can be calculated from the z value. I'm thinking that there could be a few ways of dealing with the textures but I think I'd probably go for one wide texture with all the wall textures stored in it otherwise another buffer might be required to store what texture each column is to read from and also might make it sideways to be more cache friendly.

[Pixel_Outlaw]

Here is my progress and I think this is exactly correct. I first constructed a canvas. The square. I then made a top-down view of each of the cube walls. I then decided that I would rotate the field of view (blue cone) to make the player look at the cube walls from the front. The axis of rotation for the field of view needed to be exactly in the middle of the field of view cone. I decided that the rays would intersect the axis visually from any angle of rotation equally. I then found the points where the edge rays intersected the field of view's rotation axis. Damn powerful math! This was just to construct proper cubes for my game and see if I can find a 2d relationship between them. By all means please feel free to discuss pseudo 3d. Even this projection is not correct because aside from looking head on at a cube you would never see 100% of any face and still see the others.

[Stonemonkey]

Couldn't find my old code so wrote another example, sorry but couldn't be bothered to make any maps for it .

Freebasic Source and Exe included. It runs fairly fast but there's a lot that could be done to improve it further.

EDIT: attachment edited and moved to post further on.

[Pixel_Outlaw]

This is really cool! Have some karma.

[Stonemonkey]

Thanks Pixel_Outlaw, there was a bit of a bug in the texturing but it's fixed now.

[Voltage]

@Stonemonkey: That rocks, with and without the texturing bug.  Nice concept, nice code, very nice demo.

I just had a great idea! If you have 2 minutes maybe you could add mipmapping, a nice map, some floors and a roof, some collision detection, some game logic, some monsters, some traps, some treasure, a nice fight engine, some nice textures......  you know...... if you have 2 minutes.

[Stonemonkey]

Thought about mipmapping, would be nice and fairly easy. Floors and roof, not sure the best way to go about that but if anyone's done that with raycasting would the same techniques be able to be applied here? Moveable doors would be easy and sprites/3d objects/monsters should be possible to fit in without too much hastle.

[rain_storm]

Lol two minutes But seriously great stuff there, are you using the dotproduct to calculate the Z depth?

Code: [Select]

if (z0<z_clip) then
   x0+=((x1-x0)/(z1-z0))*(z_clip-z0)
   u0+=((u1-u0)/(z1-z0))*(z_clip-z0)
   z0=z_clip
end if

is the above the same as the dot product that Im used to ...

Code: [Select]

  denom  = (y2-y1)*(nx-px) - (x2-x1)*(ny-py)
  nume_a = ((x2-x1)*(py-y1) - (y2-y1)*(px-x1)) / denom