Xojo: Building Comanche 3D in 100 lines

Comanche: Maximum Overkill

Comanche: Maximum Overkill


If you are a child of the 90s, you certainly will remember Comanche: Maximum Overkill. The graphics were awesome and way ahead of its time. Remember, we did’t have fancy 3D accelerated graph cards. They used a technique called voxel space. Using only a picture containing the colors and another one with the depths they displayed wonderful landscapes on your screen. With your Comanche chopper you could fly over this landscape, diving towards the enemy. It was fun! I’ve must have spend hundreds of hours playing with this.

It is surprising how little code is needed to reproduce this experience. In this article, we’ll build the 3D world and will be able to fly, dive etc over the landscape with Xojo in less than 100 lines of code! The code is based on the work of Sebastian Macke.

First some background on the algorithm. Voxel Space is very similar to raycasting (the technique used in games like *Wolfenstein 3D, the old one). The algorithm draws simply perspectively correctly vertical lines by shooting a ray from the camera into the map. This image illustrates this:

Voxel Space Raytracing

Voxel Space Raytracing


*Note: I first had Doom also listed but thedeemon at Reddit pointed out Doom uses another algorithm, BSP trees (binary space partition).

The algorithm goes like this:
1. For every column of the screen define a light ray which starts at the camera and ends at the horizon somewhere far away.
2. Divide the ray into very small segments so that every pixel lying on the map is considered.
3. Load the height and color from the 2D maps corresponding to the position on the ray.
4. Do some clever perspective corrections for the height coordinate. This is the hard part of the algorithm but it uses some easy math.
5. Draw a vertical line with the corresponding color with the height retrieved from the perspective correction.

So we need two pictures to do this. One containing the colors and one with the depth levels (0 – 255). The original Comanche game used 1024×1024 pictures, so that’s what we are going to do. Here is an example of both maps:

Example color and depth maps

Example color and depth maps

Ok, let’s do some code! This is what we’re going to build:

Example screen of what we will build

Example screen of what we will build

In the Open event we initialize some pictures

Sub Open()
  ' initialize the buffers
  mBuffer = new Picture(1024,768,32)
  mBuildBuffer = new Picture(VoxWidth, VoxHeight, 32)
  mBuildBufferRGB = mBuildBuffer.RGBSurface
  
  ' create the chopper picture with the transparent areas
  Chopper = new Picture(1024,768,32)
  Chopper.Graphics.DrawPicture Comanche,0,0
  Chopper.Mask.Graphics.DrawPicture ComancheMask,0,0
  
  ' load a map
  CurrentMap = 1
  LoadMap(CurrentMap)
End Sub

LoadMap is just a simple method to load the maps and reinitialize our start position:

Sub LoadMap(MapID as integer)
  dim x,y as Integer
  'Initialize the position and the lookup/lookdown vars
  xp = 512
  yp = 800
  hp = -50
  vp = -100
  
  ' prebuild the tables holding the pixel data of the map and depthmap to speed things up
  select case MapID
  case 1
    VoxelMapRGB = C1W.RGBSurface
    for y = 0 to 1023
      for x = 0 to 1023
        VoxelHeight(y,x) = C1D.RGBSurface.Pixel(y,x).Red
      next
    next
  case 2
    VoxelMapRGB = C2W.RGBSurface
    for y = 0 to 1023
      for x = 0 to 1023
        VoxelHeight(y,x) = C2D.RGBSurface.Pixel(y,x).Red
      next
    next
  case 3
    VoxelMapRGB = C3W.RGBSurface
    for y = 0 to 1023
      for x = 0 to 1023
        VoxelHeight(y,x) = C3D.RGBSurface.Pixel(y,x).Red
      next
    next
  case 4
    VoxelMapRGB = C4W.RGBSurface
    for y = 0 to 1023
      for x = 0 to 1023
        VoxelHeight(y,x) = C4D.RGBSurface.Pixel(y,x).Red
      next
    next
  end select
  
  ' Draw!
  Update
End Sub

Now, we just have to make our algorithm. The Update function will go over every vertical line and calculate what needs to be drawn to mimic the 3D view.

Sub Update()
  dim i as Integer
  dim x3d, y3d, rotx, roty as Double
  
  ' draw the sky first on the end picture
  mBuildBuffer.Graphics.DrawPicture Sky,0,0
  
  y3d = -VoxDepth
  
  ' update the view. Calculate the rotation and raycast every line
  while i < VoxWidth
    x3d = (i - VoxWidth / 2) * 1.5
    
    rotx =cos(angle) * x3d + sin(angle) * y3d
    roty = -sin(angle) * x3d + cos(angle) * y3d
    
    raycast(i, xp, yp, rotx + xp, roty + yp, y3d / sqrt(x3d * x3d + y3d * y3d))
    i = i + 1
  wend
  
  ' draw the result on the end picture
  mBuffer.Graphics.DrawPicture mBuildBuffer, 0,0, 1024, 512, 0,0,512,256
  ' draw the chopper overlay
  mBuffer.Graphics.DrawPicture Chopper,0,0
  
  ' refresh the canvas
  Canvas1.Refresh(False)
End Sub

And our Raycast method that will build the result:

Sub Raycast(line as integer, x1 as double, y1 as double, x2 as double, y2 as double, d as double)
  ' The magic! Raycast on the current line. 
  
  ' line: vertical line to compute
  ' x1, y1: initial points on map for ray
  ' x2, y2: final points on map for ray
  ' d: correction parameter for the perspective
  
  dim dx,dy as Double
  dx = x2 - x1
  dy = y2 - y1
  
  dim r as Double = sqrt(dx * dx + dy * dy)
  dx = dx / r
  dy = dy / r
  
  dim yMin as Integer = 256
  dim i,k as Integer
  dim h as Integer
  dim ci as Color
  dim y3 as Double
  dim z3 as Integer
  
  while i < r-20
    i = i + 1
    x1 = x1 + dx
    y1 = y1 + dy
    if x1 > 0 and y1 > 0 and x1 < 1024 and y1 < 1024 then
      ' get the height
      h = VoxelHeight(x1, y1)
      ' get the color
      ci = VoxelMapRGB.Pixel(x1, y1)
      
      ' calculate the ray depth. Do some perspective correction for the height.
      h = 256 - h
      h = h - 128 + hp
      y3 = abs(d) * i
      z3 = h / y3 * 100 - vp
      
      if (z3 < 0) then z3 = 0
      if (z3 < voxHeight) then
        k = z3
        While k < ymin
          ' draw a vertical line with the corresponding color with the height retrieved from the perspective correction
          mBuildBufferRGB.Pixel(line, k) = ci
          k = k + 1
        wend
      end if
      
      if (ymin > z3) then
         ymin = z3
      end if
    end if
  wend
End Sub

Finally the key handeling on the Canvas:

Sub KeyDown(Key as String) as Boolean
    elect case key
  case "4" ' left
    angle = angle + 0.1
  case "6" ' right
    angle = angle - 0.1
  case "8" ' forward
    xp = xp - 2.0 * sin(angle)
    yp = yp - 2.0 * cos(angle)
  case "2" ' backward
    xp = xp + 2.0 * sin(angle)
    yp = yp + 2.0 * cos(angle)
  case "7" ' up
    hp = hp + 2
  case "1" ' down
    hp = hp - 2
  case "9" ' look up
    vp = vp + 2
  case "3" ' look down
    vp = vp - 2
  case "m", "M" ' cycle through the maps
    CurrentMap = CurrentMap + 1
    if CurrentMap = 5 then CurrentMap = 1
    LoadMap(CurrentMap)
    Return true
  end select
  
  ' update with the new params
  Update
  
  Return true
End Sub

Note: Alwyn Bester noticed some problems with the key navigation and did this to fix it:

…Just a quick one, not sure if it’s a focus thing on Windows, but I had to move the KeyDown code from the Canvas event to the keydown event of the Form, for the navigation to work…

Done! Here is a video demonstrating what we just build with 100 lines of Xojo code:

Are Voxel engines a thing of the past? I don’t think so. As a matter of fact they are very hot nowadays. Being able to use 3D acceleration is producing some interesting engines like VoxelFarm and Atomontage. Check this last one out if you are interested in such engines.

Note: This is the original version of this article. There is a newer faster version in this article UPDATE

You can download the source code here.
Or the binaries here if you do not have Xojo.

The keys to play with it are:

Use the KeyPad!

Use the KeyPad!


Note: “M” to cycle through the maps!

See ya!

Alwaysbusy

About these ads

About Alwaysbusy

I'm the Senior Software Architect at One-Two. I like to experiment with new technologies like the Kinect, Computer Vision and A.I. Some of my projects are programmed in more exotic languages like RealStudio/Xojo and Basic4Android, but also in C# or java. I'll post some of those projects on this blog and I hope you learn some new exciting stuff! View all posts by Alwaysbusy

One response to “Xojo: Building Comanche 3D in 100 lines

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 419 other followers

%d bloggers like this: