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:
*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:
Ok, let’s do some code! This is what we’re going to 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
The keys to play with it are:
Note: “M” to cycle through the maps!