Q Solutions

3D Mines Development Timeline


While Tcl is not suited for high end 3D computer graphics, this program demonstrates that it would practical to use Tcl for advanced visualisation and other graphic intensive tasks.

Over one weekend I put together the framework for a 3D minesweeper game. The next weekend I added sound and visual effects and added in the game play and documentation to make it a complete application.

The reason why is explained below, a secondary reason was for the software to become part of my portfolio , a showcase if you will.

It all begins with A Sudden rush of blood to the head

I monitor a web site that anounces new software releases. I saw one day an anouncement for a 3D Minesweeper game. I located the web site and looked at the screen shots and blurb.
While the look of the game was enticing, I found that the list of dependant software components was unbelievable. For a moment I thought that the game was written in the Python programming language and I thought that Tcl could do all that without relying on all those extra packages.

It transpires, that the game was in fact written in c++, but I was not going to download megabytes of extensions just to try a game. The use of python and three other libraries was infact just to configure the build environment.
At this I thought that Tcl 1 and I could do better, much better.

And so it begins, The first weekend.

Day 1

Tcl comes with a canvas widget that can render 2D shapes such as rectangles, lines, polygons, and ovals. It has a sophisticated tag reference system that makes updating created objects simple and fast. While it is extensible via C extensions, there is no 3D component available.

I have in the past, used Brian Paul's excellent Togl 2 library to write C extensions to Tcl and the openGL 3D system using Mesa. These days every video card comes with hardware acceleration for this standard so it seems an appropriate base for the 3D components.

Paul Obermeier had just released Tclogl 3, a Tcl extension that gives direct access to the full low level openGL API. This means you have to do everything. From specifing the Projection Matrix, to providing the commands to render the scene when requested,all must be supplied by Tcl code.
This provides a good metric for this project as there are no pre-existing code libraries that could be used as a basis for the game.

The basic infrastructure was coded. We have a Togl window for drawing a scene in 3d. A basic control panel was created to allow the specification of some basic game parameters.
From here we have a 3d axis that can be rotated around with the mouse. Now we have to make some objects to display.

One issue I forsaw was the time to render a complex scene. I decided to use display lists for all drawing functions. This allows us to off load a lot of compute intensive tasks to the openGL server and leave Tcl to run the actual game components.
The basic code was created to allocate and name display lists as it is more natural to use strings in Tcl but we must pass numbers to openGL.

Now we create a number of display lists, one for the Cube that represents an unexplored area of space, one that represents that a mine may be present, and one to represent that a mine had been exposed.
Initially I had two routines to draw the array of cubes. One for displaying the cubes and one for picking a cube with the mouse.

By the end of the day I had the basic display of a NxNxN game cube that could be rotated in space as well as an individual cube could be picked with the mouse and turned into a mine object. I had displayed cubes up to 20x20x20 and was pleased with my decision to use display lists as the update speed was still reasonable even with over 8000 objects on the screen.
(I later reduced the max size to an 12x12x12 cube which I labled as the Borg cube. It was obvious that 12x12x12 cube was far more than the average persion could cope with. It was also apparant that it was almost impossible to see the relationships of the cubes to other cubes as cubes were uncovered. I added a Wire frame cube which I coloured to indicate the number of adjacent cubes that contained mines.
Those in the know will understand the choice of colours for the numbers.

At this point I called it a day.

A new dawn

Day 2

The first part of the day was spent playing with my creation. While it lacked decent game play, the visual appearance was enticing.
It was also apparant that the coloured wire frames would be a usefull teaching aid for children, and would help in improving visualising skills.
I also found in Testing, that with large cubes, it became visually confusing with the mass of wire frames on the screen. The first step at solving this was to create an empty display list and I replaced a wireframe object with an empty one when all adjcent squares had been uncoverd and no longer gave any usefull information.
So now like the 2D counterpart we only have hints next to uncovered cubes.

One aspect of the 2D version is that the spaces use number to indicate the number of mines. While the wireframes look good they also provide a lot of clutter on the screen.
At this point I wanted to put Text on the display. However the raw openGL system does not have any text rendering capability. Some time was spend researching how others managed to get text on the screen. The most common way was to use the inbuilt bitmaps that are included with the glU library and blit them to the screen as 2D bitmaps.
This did not appeal as I was going for the 3D look. The next option was to use a system developed at SGI Labs, this involves sucking the bitmapped glyphs from your X11 server and saving them as a Texture map. Then by using the Texurizing features in openGL, the glyphs can be pasted to GL_QUADS or other facets and displayed, scaled, rotated like any other primative.

Some time was spent in creating my own Font textures but In the end due to copyright considerations I used the generic font texture from SGI. All I had to do was write some Tcl code to read the font texture file and extract the texture coordinates for each character and make procedures to apply a specific character to a face.

If I hadn't got caught out in my testing process this would have only taken a couple of hours to develop. Unfortunately I mad the mistake of trying to test the text functions out ouside of the rest of the system which failed because I was attempting to call openGL functions before I had set up the environment completely.

My first attempt at computing the inverse rotation matrix to make the characters face the viewer was a success. I was surprised that all it took was to apply my view transformations in reverse order.
Now I know thats what anyone would expect to do, but by the same token most software components are not usually that straight forward.
Now we can select to have wireframes or numbers or both to help find the mines.

While the update rate was acceptable, I was sure that drawing each cube position individually was not the most optimal way of doing it. At this point I went to the redbook and consulted the text about vertex arrays and CallLists . I spent some time trying various systems and realised that the way Tcl interfaced to vectors, that vertex arrays would not help much.
It would be of use to use a vector to contruct a call list for displaying the cube objects in one operation.

After we draw each cube we must translate to the next x,y,z position. If we make a display list for each cell we will need 1728 display lists for a order 12 cube. This seems a waste so I came up with a cunning plan. If we render the cube as though we were a vector display device then we can use incremental movements to get us to the next cube. This gives:

  1. To move to the next x we simply translate by x+1
  2. To move in the y direction we translate by y+1 and x -size
  3. To move in the z direction we translate by z+1 and y - size and x - size
This only requires three display lists for any size game cube. We can then create a display list vector where every even position is the display list of the object we want to display for that cell, and every odd position is the display list to move us to the next cell.

Initially there were some cube shapes that spiralled off into the z or x axis, and I had to change the computation from x - size to x - (size - 1), but then we had a really spiffy display routine. One intial call toconstruct the vector and from then on , just one openGL call to display all the cubes.

At this point I realised that I could not use this display list for picking cubes as we need individual cube numbers which the above system does not give. So I left the original nested loop method of display for picking.

All that was left for the end of the day was some tiding up of the UI , adding a selectable background and some more testing.

At this point I placed the code on the Tcl wiki as a deomonstration.
I had no intention at this stage to continue with development and make an actual Game out of the code. Here is a screenshot , showing the features thus far. While it is possible at this stage to play a complete game, having a dialog giving you your percentage error is hardly exciting.


For two days of coding with no code libraries, I feel this demonstrates that Tcl is a real programming language that has capabilities far in excess of what most developers imagine.
It also emphatically demonstrates the development advantage of Scripting over the traditional Edit, Compile and Redo from Start development cycle. Because in the testing phase new code could be sourced into the running appplication and retested without having to restart the application, I have saved at least three days of development time.

After discussion with my harshest critics (my family) I was persuaded to continue the project to add in the features required to make it a playable game. Over afternoon Tea we discussed what features would be needed to make a playable game.

The first problem was in deciding on a theme for the game. One option was to have it under the sea using a submarine as the base. A second was to place the minefield in space.
My daughter favoured underwater and wanted whales to wander past producing whale song.

I choose a space theme due mainly to the fact that I could locate more sound clips with a space theme than an underwater one. While the whale was a big ask, it was doable , and lets face it, even with a space theme, a whale would not be totally out of place to Ford Prefect.
Personally I voted for having the Tardis materialise on the screen. The materialisation sound is such a cool clip, its a shame to not use it.

All ahead warp factor 8, The second weekend.

Day 3

The first addition was sound effects. I have a number of Sound clips and a search of the internet produced some more. Most of day three was spend downloading and sampling the clips.
With the clips we need some way to play them. Fortunately the Snack extension for Tcl runs on most computer platforms so we get an OS independant sound system.

With three lines of code we can make a sound clip play:

	package require sound
	set x [snack::sound -file filename.wav]
	$x play

We add to this a sound cache and a couple of interface functions and we have a complete sound sub system in about 50 source lines of code.

Now when we trip a mine we can have a nice explosion sound. And yes I do know that sound cannot travel through the vaccum of space. And yes I do know that the previous sentence is not a scientifically accurate description, however in my defence , every SCFI program ever made has sound effects in space.

At this point development slowed as there was considerable pressure to relinquish control of the computer to those people who wanted to Test the game.

Adding sound did not enhance the game play as much as I expected. The principal reason is that when you hear a sound effect (such as an explosion) you expect to see some visual consequence.
We need some animation ability to accompany the sounds.

At this point I had decided on the game playaspects. Unlike the traditional 2D version, the aim of the game was not to clear a path, but to locate and defuse the mines. By defuse I mean blow up.
With the sound effects I had located off the net, the game was taking on a distinctly geeky SCIFI theme. So I went with the flow and added references to a well known SCIFI series both in on screen text , and the sound clips.

At this point I was at a loss on how to implement progression through the game. Most games have levels and as you progress through them it gets harder (as if visualising in 3D is not hard enough already!). I added level selection tothe GUI but without any real goal.
In the end I decided to view the game like patience, you play a game round and when that gets too boring you play a harder version of the same.

I had toyed with different shapes for the uncovered regions of space. So I made levels use more visually confusing shapes. I also added the ability to texture map the shapes which also adds to the visual confusion. Due to a mistake I made with the light source normals, I found that when shapes rotate around their axis, they rotate away from the light source. Since this makes a disappearing effect and only effects the upper levels I have left this bug in so now it is a feature. If you think it is hard to visualise the adjacent cubes, try doing it when they keep disappearing.

The next item was some sort of animation system. Since I have used display lists for everthing else It was natural to use them and vectors for a call-list for the animation system.
We keep the system simple and define all the effects a seperate Tcl procs. This way we can create an endless number of effects.

See Animation System for a discription on how easy it was to create an animation sub system with Tcl. All in about 150 lines of code.

With this in place I coded some simple effects. The first one a rotation effect and then one that fades the colour of an object.
By composing display lists it becomes almost childs play to animate existing display objects.

Time for some more game play, Testing. The rotating cubes look cool , as does the rotating pulsating force field around a mine. I am not sure of the point of it but I spent some time in coding it so lets find a reason to put it on the screen.

We now tie in the animations and sound effects with the user interactions by queueing them as time releated events.
Suddenly I realised that I was spending a ridiculous amount of time tweeking effects and timing rather than developing the application.
There is nothing quite like moving pictures with sound to lower productivity.

Its now late in the evening and the game is still lacking something. When we trip a mine it explodes with a nice sound effect. But what else, we need a nice impact effect.
Some quick coding and we have the sfx/Explode animation effect.

This make a red sphere with outer ring expand rapidly outwards towards the viewer. At the moment of impact, we trigger a sfx/Shockware effect. This is a rock the boar type motion adding to the eye-view matrix.
Not the best effect Phil , ... , well actually it barks like a dog. The intent is right , the visual impact is all wrong. It looks like the cube is rocking in space (or jerking like a spastic monkey). And by the way, are we suposed to be circling the cube or does the cube spin in from of us?

We need a point of reference. Enter the starfield, a couple of false starts on what I thought was the correct way of generating a sphere, apparantly is it not z 2 = x2 + y2.
A Sphere is ok but not realistic , so add in some randomness for radius and we have a reasonable star field. Lets try 10,000 points:

    Oh my God!, its full of stars.
And Wow!, now we have some depth perception, and yes it is definately us who are circling the cube (the stars move)

An while we are at it, I figured out how to get the other spikes on my mine. In the first version there are spikes running in the X and Y planes but none in the Z plane. I assumed that if I rotated in both the x and y planes by +-45 degrees I would end up smack in the center of the other spikes. But alas no (Bogus).
I was missing the mark and getting quite frustrated that something so simple as a combined rotation should elude me. I resorted to some pens and a stress ball (how ironic) to help visualise the transformation.
Hmmm, 90 degrees in X and then 45 in Y (Excellent).

Out of the blue and into the black.

Day 4

We are on the home stretch time wise, I am not sure the application will be finished. And I am not happy about the dancing cube effect. I enlisted the help of a passing teenager to test the game play and comment.
As expected they picked up on the rock the boat effect . It just did not fit with what was happening visually. They suggested an alternative of displacing the cubes around the exploded mine. I had concidered this but my super cleaver display system was so optimised it did not appear practical to add this effect in.

While we have a perfectly acceptable display system, I could not get past the fact that I have coded up two routines that do the same thing. One is used for display the other for picking.
It's time to stop and go back and revisit display loop, also I wanted a way to include the displaced cube effect.
Picking up on the vector display model, for picking this becomes problematic as we need a unique number for each cube and that could lead to needing 1700 display lists to be able to pick a cube.

Looking at the XYZ differential translation I had squeezed into just three display lists, it seemed logical that we could extend this model to picking. I had already used seperate x,y,z markers rather than one single number for naming the objects fortunately.
If we now use one list for each x,y,or z we can uniquely identify each cube. This takes a maximum of 36 (3x12) display lists compared with three originally but we also have the advantage of now having one routine for both functions.
So we need 12 display lists for the Z identifiers and z offsets, 12 for the Y identifiers and offsets, and another 12 for the X identifiers and offsets. And we still get to keep the odd/even layout of the list vector. One position to locate and the other to draw the object.

I could also see that we can use animations to do the displacement by replacing the displayed object with an animation that encoded an extra offset and then the original displayed item. If we use up all the animation lists then we just stop displacing the cubes. Simple and quick.

Im getting frustrated at this point because my operating system does not allow me to have two programs accessing the sound device concurrently. This means I can't play my mp3 files while coding.
We have the technology so ..., some buttons a frame, 40 lines of code and ...
We now have a mp3 jutebox as a bonus feature. Also the sound effects are starting to get a bit repititious so we should have a mute button and also add some randomness to the sound that is played.

Another requested feature was the ability to locate adjacent cubes visually. Another animation effect . another button on the GUI and all was done, except sound so another wave file was located and we could cross that feature off the list.

By now there is more Testing than coding and progress slows to tweaks here and there, a couple of bug fixes, another animation effect here and there. Basically a bit of spit and polish before releasing the code.

We need some form of online help so I grabbed the Tkhtml extension to allow displaying html files. This extension is not available on all platforms so I made a fall back to rendering the html as text into a text widget, hiding the tags and applying some low level formating to the html elements such as headings and the like.
Crude but effective.

Game over man!

The last feature was in indicating that the game had finished. I wanted all along to have a rotating text banner , so wizzed up another sfx proc and made a simple but effective sign for winning or losing.
One effect that everyone clamours for these days is gradient fills. Since we had a routine to render a string it shouldnt be to hard to add colour should it?
It literally only took me five minutes to add colour support to the routine that Renders text strings. By default no colour is applied to the text.

Rather than specifing a colour or some complicated gradient structure we simply specify one to four colours that are applied to each vertex of the GL_QUAD that maps the glyph.

So we have a two colour gradient on the front of the Text while on the back side of the text we have a four colour gradient (What a show off!). A Screen shot of the finished application.

As all things time will mend, so this project will end.

In conclusion

Without resorting to a large body of library components with their problems of dependancies and the like we have created a complete application from scratch. We can do this because of the nature of the development platform.

Tcl is not only a scripting language, it is a dynamic language. Its has the ability to be all things to all programmers.

As a died in the wool C programmer I found the transition to Tcl a struggle due to its apparant verboseness, arcane syntax and poor performance.
Now I struggle to take on C development roles due to the verboseness of the language, limitations of a non dynamic language, and the slowness of development.

I have sacrificed the underlying speed of program execution for the speed of development.

When it comes to performance. In the Big picture, Tcl rules.

And yes , in the end we were all assimliated!

Copyright © September 2005