Real Time 3D Interiors

[rain_storm]

Okay this is something I've been at for a while now and I think I'm finally on to something,
Originally my 3D engines where a marriage between the old familiar WORMS demo and the 3D CUBE demo that were included in the PS2 yabasic. Basically the collision map (grid(x, y) in the WORMS demo) held the centre point for the cube which was replotted and redrawn for each grid entry that was considered a wall. That technique yielded some results (25 fps on the PS2 when the grid was a 16x16 array). The were however some short-commings with this approach. The cubes often vanished when you stood with your shoulder to the wall such that your line of sight was paralelle with the wall, this left half the screen taken up with the background when surely there should have been a wall.
 This time I have opted for a different approach. The collision map is only used for detecting collisions and a polygon mesh is used to define the rooms appearance. It was necessary to weed out the non visible walls. To achieve this I calculated the crossproduct of each point relative to both the left extreme of vision and the right extreme of vision. Any wall which had one point within the field of view and one point outside the FOV would have to be cropped. Now we cast out two rays (one for each extreme of vision) & calculate the intersection points. Up to now everything is done in 2D. All that is left is to rotate whats the scene, add a vertical dimension and apply perspective.
 I haven't yet checked out the fps for this algorithm but it doesn't suffer any slowdown (at least not noticeably). I still have to sort out a bug in the lighting effects and everything still has to be cleaned up a lot. But it works... Now where do I go from here?

Code: [Select]

init_game()

label game
 draw_grid(grid)
 ctrl = peek("port1")
 if (ctrl <> 0) ctrl_user(ctrl)
 goto game

sub draw_grid(grid) local x, y, w
 if (intro <= 3) then
  setrgb 1, 255, 255, 000
  text 0,240, message$(intro), "cc"
  count = count + 1
  if (count > display) then
   count = 0
   intro = intro + 1
  fi
 fi
 setdispbuf draw
 draw = 1 - draw
 setdrawbuf draw
 horizon =-256*tn(rotx(0))*2
 setrgb 1, 255,255,255
 setrgb 2, 255,255,255
 setrgb 3, 000,000,000
 gtriangle -320,-256 to 320,-256 to 320,horizon
 setrgb 2, 000,000,000
 gtriangle -320,-256 to -320,horizon to 320,horizon
 setrgb 1, 255,000,000
 setrgb 2, 255,000,000
 setrgb 3, 000,000,000
 gtriangle -320,256 to 320,256 to 320,horizon
 setrgb 2, 000,000,000
 gtriangle -320,256 to -320,horizon to 320,horizon

 for w = 1 to walls
  if (tz(w,1) > 0) and (tz(w,3) > 0) then
   lt1 = lt1(w)
   lt2 = lt2(w)
   setrgb 1, red(w)*lt1, grn(w)*lt1, blu(w)*lt1
   setrgb 2, red(w)*lt1, grn(w)*lt1, blu(w)*lt1
   setrgb 3, red(w)*lt2, grn(w)*lt2, blu(w)*lt2
   gtriangle tx(w,1),ty(w,1) to tx(w,2),ty(w,2) to tx(w,3),ty(w,3)
   setrgb 2, red(w)*lt2, grn(w)*lt2, blu(w)*lt2
   gtriangle tx(w,1),ty(w,1) to tx(w,4),ty(w,4) to tx(w,3),ty(w,3)
  fi
 next
 for y = 1 to gridy
  for x = 0 to gridx
   if (grid(x, y) <> 0) then
    if    (grid(x, y) = wall) then setrgb 1, 100, 100, 100
    elsif (grid(x, y) = door) then setrgb 1, 200, 120, 080
    fi
    fill box x*m-300, y*m-240 to x*m+m-300, y*m+m-240
   fi
  next
 next
 setrgb 1, 000,000,255
 fill circle posx(0)*m-300, posy(0)*m-240, m/2
end sub

sub rota_grid()
 cx = -cs(rotx(0))
 sx = -sn(rotx(0))
 cy = -cs(roty(0))
 sy = -sn(roty(0))
 cz = -ct(rotz(0))
 sz = -tn(rotz(0))
 posx = posx(0)*m
 posy = posy(0)*m
 posz = posz(0)*m
 for w = 1 to walls
  px = ix1(w)*m-posx
  py = iy1(w)*m-posy
  pz =-m/2-posz
  nx = cz*px + sz*py
  ny = cz*py - sz*px
  nz = cy*pz + sy*nx
  tx = cy*nx - sy*pz
  ty = cx*ny + sx*nz
  tz = cx*nz - sx*ny
  tx(w,1) = tx*400/ tz
  ty(w,1) = ty*400/ tz
  tz(w,1) = tz
  pz = m/2-posz
  nz = cy*pz + sy*nx
  tx = cy*nx - sy*pz
  ty = cx*ny + sx*nz
  tz = cx*nz - sx*ny
  tx(w,2) = tx*400/ tz
  ty(w,2) = ty*400/ tz
  tz(w,2) = tz
  px = ix2(w)*m-posx
  py = iy2(w)*m-posy
  pz = m/2-posz
  nx = cz*px + sz*py
  ny = cz*py - sz*px
  nz = cy*pz + sy*nx
  tx = cy*nx - sy*pz
  ty = cx*ny + sx*nz
  tz = cx*nz - sx*ny
  tx(w,3) = tx*400/ tz
  ty(w,3) = ty*400/ tz
  tz(w,3) = tz
  pz =-m/2-posz
  nz = cy*pz + sy*nx
  tx = cy*nx - sy*pz
  ty = cx*ny + sx*nz
  tz = cx*nz - sx*ny
  tx(w,4) = tx*400/ tz
  ty(w,4) = ty*400/ tz
  tz(w,4) = tz
 next
end sub

sub cast_rays()
 leftz = rotz(0) - 32 : if (leftz < 000) leftz = leftz + 255
 rigtz = rotz(0) + 32 : if (rigtz > 255) rigtz = rigtz - 255
 posx = posx(0)
 posy = posy(0)
 cs_lz = cs(leftz)
 sn_lz = sn(leftz)
 cs_rz = cs(rigtz)
 sn_rz = sn(rigtz)
 cslz = cs(leftz) + posx
 snlz = sn(leftz) + posy
 csrz = cs(rigtz) + posx
 snrz = sn(rigtz) + posy
 for w = 1 to walls
  cp1(w) = 0
  cp1 = (posx-wx1(w))*(snlz-wy1(w)) - (cslz-wx1(w))*(posy-wy1(w))
  if (cp1 > 0) then
   cp2 = (posx-wx1(w))*(snrz-wy1(w)) - (csrz-wx1(w))*(posy-wy1(w))
   if (cp2 < 0) then
    cp1(w) = 1
    ix1(w) = wx1(w)
    iy1(w) = wy1(w)
   fi
  fi
  cp2(w) = 0
  cp1 = (posx-wx2(w))*(snlz-wy2(w)) - (cslz-wx2(w))*(posy-wy2(w))
  if (cp1 > 0) then
   cp2 = (posx-wx2(w))*(snrz-wy2(w)) - (csrz-wx2(w))*(posy-wy2(w))
   if (cp2 < 0) then
    cp2(w) = 1
    ix2(w) = wx2(w)
    iy2(w) = wy2(w)
   fi
  fi

  if (cp1(w) = 0) then
   if    (wx1(w) = wx2(w)) then
    opp = wx1(w) - posx
    adj = opp/cs_lz*sn_lz + posy
    if    (adj > wy1(w)) and (adj < wy2(w)) then
     ix1(w) = wx1(w)
     iy1(w) = adj
    elsif (adj < wy1(w)) and (adj > wy2(w)) then
     ix1(w) = wx1(w)
     iy1(w) = adj
    fi
   elsif (wy1(w) = wy2(w)) then
    adj = wy1(w) - posy
    opp = adj/sn_lz*cs_lz + posx
    if    (opp > wx1(w)) and (opp < wx2(w)) then
     ix1(w) = opp
     iy1(w) = wy1(w)
    elsif (opp < wx1(w)) and (opp > wx2(w)) then
     ix1(w) = opp
     iy1(w) = wy1(w)
    fi
   fi
  fi
  if (cp2(w) = 0) then
   if    (wx1(w) = wx2(w)) then
    opp = wx2(w) - posx
    adj = opp/cs_rz*sn_rz + posy
    if    (adj > wy1(w)) and (adj < wy2(w)) then
     ix2(w) = wx2(w)
     iy2(w) = adj
    elsif (adj < wy1(w)) and (adj > wy2(w)) then
     ix2(w) = wx2(w)
     iy2(w) = adj
    fi
   elsif (wy1(w) = wy2(w)) then
    adj = wy2(w) - posy
    opp = adj/sn_rz*cs_rz + posx
    if    (opp > wx1(w)) and (opp < wx2(w)) then
     ix2(w) = opp
     iy2(w) = wy2(w)
    elsif (opp < wx1(w)) and (opp > wx2(w)) then
     ix2(w) = opp
     iy2(w) = wy2(w)
    fi
   fi
  fi
  for l = 1 to light
   opp = ix1(w)-lx(l)
   adj = iy1(w)-ly(l)
   hyp1 = sqrt(sqr(opp)+sqr(adj))/lit(l)
   lt1(w) = 1/hyp1 + lt1(w)
   opp = ix2(w)-lx(l)
   adj = iy2(w)-ly(l)
   hyp2 = sqrt(sqr(opp)+sqr(adj))/lit(l)
   lt2(w) = 1/hyp2 + lt2(w)
  next
  lt1(w) = lt1(w) / 4
  lt2(w) = lt2(w) / 4
  if (lt1(w) > 1) lt1(w) = 1
  if (lt2(w) > 1) lt2(w) = 1
  ? lt1(w),lt2(w)
 next
 ?
end sub

sub ctrl_user(ctrl) local dirx, diry, torx, torz, newx, newy
 if    (and(ctrl, ctrl(cr)) <> 0) then torz = 10*rpm
 elsif (and(ctrl, ctrl(sq)) <> 0) then torz =-10*rpm
 fi
 if    (and(ctrl, ctrl(tr)) <> 0) then torx = 10*rpm
 elsif (and(ctrl, ctrl(ex)) <> 0) then torx =-10*rpm
 fi
 rotz(0) = rotz(0) + torz
 if    (rotz(0) < 000) then rotz(0) = rotz(0) + 255
 elsif (rotz(0) > 255) then rotz(0) = rotz(0) - 255
 fi
 rotx(0) = rotx(0) + torx
 if    (rotx(0) > 128) then rotx(0) = 128
 elsif (rotx(0) < 000) then rotx(0) = 000
 fi

 if    (and(ctrl, ctrl(up)) <> 0) then
  dirx = cs(rotz(0))
  diry = sn(rotz(0))
 elsif (and(ctrl, ctrl(dn)) <> 0) then
  dirx =-cs(rotz(0))
  diry =-sn(rotz(0))
 fi
 if    (and(ctrl, ctrl(rt)) <> 0) then
  dirx = ct(rotz(0)) + dirx
  diry = tn(rotz(0)) + diry
 elsif (and(ctrl, ctrl(lf)) <> 0) then
  dirx =-ct(rotz(0)) + dirx
  diry =-tn(rotz(0)) + diry
 fi
 dirx = dirx*mps/4
 diry = diry*mps/4
 newx = posx(0) + dirx
 newy = posy(0) + diry
 hit = grid(newx, newy)
 if    (hit = door) then
  source = grid
  grid = des(node(newx, newy))
  load_grid(grid)
  newx = posx(0)
  newy = posy(0)
 elsif (hit <> flor) then
  newx = posx(0)
  newy = posy(0)
 fi
 posx(0) = newx
 posy(0) = newy
 cast_rays()
 rota_grid()
end sub

sub load_grid(grid) local x, y, w, g
 find_grid(grid)
 read gridx, gridy
 redim grid(gridx, gridy), node(gridx, gridy)
 for y = 1 to gridy read g
  for x = 0 to gridx grid(x, y) = 0 : node(x, y) = 0
   if (and(g, ctrl(x)) <> 0) grid(x, y) = wall
  next
 next
 read doors : if (doors <> 0) load_door(doors)
 read light : if (light <> 0) load_ligt(light)
 read bots : if (bots <> 0) load_bots(bots)
 for d = 0 to doors
  if (des(d) = source) then
   posx = dropx(d)
   posy = dropy(d)
  fi
 next
 posx(0) = posx + 0.5
 posy(0) = posy + 0.5
 read walls
 redim wx1(walls), wy1(walls), wx2(walls), wy2(walls)
 redim ix1(walls), iy1(walls), ix2(walls), iy2(walls)
 redim red(walls), grn(walls), blu(walls)
 redim lt1(walls), lt2(walls)
 redim cp1(walls), cp2(walls)
 redim tx(walls,4), ty(walls,4), tz(walls,4)
 for w = 1 to walls read wx1(w), wy1(w), wx2(w), wy2(w) next
 for w = 1 to walls read red(w), grn(w), blu(w) next
end sub

sub load_bots(bots)
end sub

sub load_door(doors) redim des(doors), dropx(doors), dropy(doors)
 for d = 1 to doors read dx, dy, dropx(d), dropy(d), des(d)
  grid(dx, dy) = door
  node(dx, dy) = d
 next
end sub

sub load_ligt(light)
 redim lx(light), ly(light), lit(light)
 for l = 1 to light read lx(l), ly(l), lit(l) next
end sub

sub find_grid(grid) on grid goto 01,02,03,04
01 restore grid_01 : return
02 restore grid_02 : return
03 restore grid_03 : return
04 restore grid_04 : return
end sub

sub init_game() local p, n, d, deg, degree
 m = 10
 km = 1000*m
 secs = 50
 mins = 60*secs
 hour = 60*mins
 mps = m/secs
 kph = km/hour
 rpm = 255/mins
 degree = pi / 128
 dim cs(255), sn(255), tn(255), ct(255)
 for d = 0 to 255 deg = d*degree
  cs(d) = cos(deg)
  sn(d) = sin(deg)
  ct(d) = cos(deg+pi/2)
  tn(d) = sin(deg+pi/2)
 next
 dim ctrl(16)
 n = 1
 for p = 1 to 16 ctrl(p) = n : n = n*2 next
 up = 05
 rt = 06
 dn = 07
 lf = 08
 tr = 13
 cr = 14
 ex = 15
 sq = 16
 flor = 0
 wall = 1
 door = 2
 redim posx(1), posy(1), posz(1)
 redim rotx(1), roty(1), rotz(1)
 redim dropx(1), dropy(1)
 dropx(0) = 8
 dropy(0) = 8
 grid = 01
 load_grid(grid)
 open window 640,512
 window origin "cc"
 intro = 0
 count = 0
 display = 8*secs
 dim message$(3)
 message$(0) = "Don't be afraid. Stick your chin up ..."
 message$(1) = "Press [Triangle] to look up"
 message$(2) = "Now step foward and claim your destiny ..."
 message$(3) = "Press [D-Pad] to move around"
end sub

label grid_01
data 16,16
data 65535,32769,32769,32769,32769,32769,32769,32769
data 32769,32769,32769,32769,32769,32769,32769,65535
data 1
data 16,08,15,08,02
data 4
data 0.5,0.5,1.5, 16.5,0.5,1.5, 16.5,16.5,1.5, 0.5,16.5,1.5
data 0
data 9
data 01,01,08,01, 08,01,17,01, 17,01,17,08, 17,08,17,09
data 17,09,17,17, 17,17,08,17, 08,17,01,17, 01,17,01,08
data 01,08,01,01
data 255,255,255, 255,255,255, 255,255,255, 150,120,080
data 255,255,255, 255,255,255, 255,255,255, 255,255,255
data 255,255,255

label grid_02
data 16,16
data 65535,32769,32769,32769,32769,32769,32769,32769
data 32769,32769,32769,32769,32769,32769,32769,65535
data 2
data 01,08,02,08,01, 16,08,15,08,03
data 4
data 8.5,0.5,1.5, 16.5,8.5,1.5, 8.0,16.5,1.5, 0.5,8.5,1.5
data 0
data 10
data 01,01,08,01, 08,01,17,01, 17,01,17,08, 17,08,17,09
data 17,09,17,17, 17,17,08,17, 08,17,01,17, 01,17,01,09
data 01,09,01,08, 01,08,01,01
data 255,255,255, 255,255,255, 255,255,255, 150,120,080
data 255,255,255, 255,255,255, 255,255,255, 255,255,255
data 150,120,080, 255,255,255

label grid_03
data 16,16
data 65535,32769,32769,32769,32769,32769,32769,32769
data 32769,32769,32769,32769,32769,32769,32769,65535
data 2
data 01,08,02,08,02, 16,08,15,08,04
data 4
data 0.5,0.5,1.5, 16.5,0.5,1.5, 16.5,16.5,1.5, 0.5,16.5,1.5
data 0
data 10
data 01,01,08,01, 08,01,17,01, 17,01,17,08, 17,08,17,09
data 17,09,17,17, 17,17,08,17, 08,17,01,17, 01,17,01,09
data 01,09,01,08, 01,08,01,01
data 255,255,255, 255,255,255, 255,255,255, 150,120,080
data 255,255,255, 255,255,255, 255,255,255, 255,255,255
data 150,120,080, 255,255,255

label grid_04
data 16,16
data 65535,32769,32769,32769,32769,32769,32769,32769
data 32769,32769,32769,32769,32769,32769,32769,65535
data 1
data 01,08,02,08,03
data 4
data 8.5,0.5,1.5, 16.5,8.5,1.5, 8.0,16.5,1.5, 0.5,8.5,1.5
data 0
data 9
data 01,01,08,01, 08,01,17,01, 17,01,17,08, 17,08,17,17
data 17,17,08,17, 08,17,01,17, 01,17,01,09, 01,09,01,08
data 01,08,01,01
data 255,255,255, 255,255,255, 255,255,255, 255,255,255
data 255,255,255, 255,255,255, 255,255,255, 150,120,080
data 255,255,255
 


[Jim]

Amazing what you can do in yabasic!  What about adding some other things into the maze?

Jim

[Stonemonkey]

Very nice, are you doing this on the ps2 too?

[rain_storm]

I think my PS2 days will be over just as soon as I have finished transferring the code from my memory card to my PC. (The emulator lets you speed up your code by syncing to the monitors refresh rate, THAT ROCKS BABY!!!). So yes in the past I coded exclusively on the PS2.
As for which direction this little project will go I am undecided. Either a 3D shooter or an action RPG (Like Vagrant Story). But first I want to clean up the code I hate messy spegetti code. And the above code has too many cheap fixes that I'm simply not happy with. Once I have everything optimised then I will get down to turning this engine into a game.

[Shockwave]

I was very surprised when I looked up That's really nice work, it would be great to see the square room turned into a more complicated structure, I like it a lot though, well done. 

[rain_storm]

I'm one step ahead of you Shockwave, I am currently including NPCs which have a field of view (Which Im borrowing from Clankys Unresolved Client) at the moment they are simply positions and are not animated. I would love to use reverse kinematics (Where rotations of the child bones effect their parent bone acting more like a cars suspension) for the animation but it is very complicated so I think I'll end up sticking with the traditional foward kinematics (Where the rotations of the parent bone is added to all child bones) I have increased the complexity of the rooms and should have a working update in the near futer. I hope I have enough processing power left to animate the players charictor so that the game can be played in 3rd person view. Anyhow once the animated NPC are working I'll post an update.

[Shockwave]

You know what, how about an emulator only version? That would be excellent You could put loads of stuff into it.

[rain_storm]

What does emulator only mean are thier commands that only apply to the emulator? Or is it simply a case using a layout of buttons that is intended for use with a keyboard rather than a controller?

[Jim]

It's just massively faster than a PS2, so you can put more in.

Jim

[Clanky]

All the emulator does is pass your program from YaBASIC into a language which the computer can understand... this allows the computer to read the YaBASIC commands, all the functionalities of the PS2 version are there - so use the same commands, values for controls, etc.
It's YaBASIC: for PC!
Also, as Jim already stated, it's alot faster - normally runs at your computers speed, compared with the 200 MHz PS2 processor.

(I THINK???)

[rain_storm]

Okay I discovered a flaw in the program with regards to the order in which objects should be drawn relative to the room. I have sorted it out now. But fixing this has taken up some valueable time that should have been spent on getting the animation up and running. Anyhow no use in beatin' a dead horse. I'm gonna get the animation done asap. This project is gonna take alot of time. There is an updated version but I would rather have this part done before I post it.

Edit -
Alas I had to abandon this project! The code has become so bug-ridden that it was more feasible to start again from scratch. Also I had literally no more speed left for adding in bullets and so on. I could have optimised stuff but the bugs scared me off of this daunting task.

But not to fear as I have decided to go 100% raycaster on the mutha #@(k3r. The change has allowed me to texture map the rooms surfaces and      the boost in speed is enormous. Speed can be further increased simply by casting fewer rays! Of course things will look a little blockier. Anyway check it out for yourself in my latest topic ... Yabasic Rocks !!!