Wednesday, October 27

UML, OO models and Abstraction

There's a hierarchy of sorts of abstraction away from machine hardware - you start with assembler - working with resigsters, raw memory, I/O ports, interrupts etc, but it gets more wooly and disintegrates into something resembling a spaghetti ATN the further you work your way up.

C takes you one layer from that - it gives you functions, typing and normal maths notation, but you are still working with raw lumps of memory (structs) and there's a pretty much one to one mapping between expressions and machine instructions - the size assembler output is going to be roughly proportional to source input.

"C with classes" C++ gives you some more layers - You can take a hunk of raw memory and associate it with a set of defined operations and acess it through those operations. You can do this in the above lanuages, too with sufficently disciplined programming, but C++ gives you encapsulation and operator overloading to make it more syntatically "nice". You still have to worry about the consequences of allocating things in memory and where they live - stack, heap, static..

"Polymorphic/OO C++" gives you other tools: the ability to pretend one set of objects are all the same thing - polymorphism, virtual functions, interfaces, inheritance. This saves a lot of repeat coding and lets you abstract away implementation details - for example a car, a character, a prop are all "objects in the world" and can be manipulated via a common "objects in the world" interface : no specific per - case coding.

This leads to..

"Template/Boost/STL C++" gives you the ability to do something like polymorphism at compile time - templates that take parameters, which leads to a lot of compile-time optimisations, and for the first time in the C++ learing curve, code which outperforms C (if written *properly*). Also, the STL takes the level of abstraction offered by the previous level one step further, seperating data and algorthims - on the one hand there's a set of containers: list, vector, map; and on the other hand a set of sorting, searching algorithims that work for every container and don't have
to be specialised for particular containers. STL has a weakness that's inherent to C++ - it has to manage memory allocation and does so nearly exclusively on the heap, although there is a mechanism to abstract away the allocations (an allocator object) and make the code independent of memory-management mechanisms (ie, not care wether the container is on the heap, static, or on the stack), it's flawed..(or at least so it's claimed by people who should know).

Python gives you a slightly different set of abstractions that do the same thing as C++: it doesn't do static typing, pushes function call and object resolution to run time, so if you use object.method() as long as your object implements method() it won't care what object it is. Also it frees you from the problem of allocating/deallocating raw memory, which C++ doesn't. It's
implemented to be easily interfaceable to C++/C and read like "executable pseudo code". It's therefore an ideal prototyping langugage.

Lisp takes a completely different apporach to providing these abstractions, one that is still boiling my brain. Rather than trying to provide abstrations that decouple code and data, code *is* data - a function is just a list of instructions, manipulable by list manipulating primitives, assignable to variables, etc. I suspect it to be ideal for genetic programming and self-modifying structures at a high level of abstraction thus it's niche in AI and 'hard' research problems. The nice thing about this apporoach is that the upshot is - like C++ you degree of abstraction is entirely up to you - you can go with typless programming ala Python, or you can declare your variables typed, and get full on C-type optimisation. You
can construct code in lists at compile time that have the same effect as template expansion. I haven't got into the object system, yet..but I fully expect to find it already doing things the ways it took C/C++ the last 20 years to discover.

Finally: I'm saying that the mechanism that the language uses to provide abstraction away from the machine hardware has consequcnces and it's inescapable, and it may also close off other possible abstractions

Where does UML fit into this hierarchy? It's another step up, isn't it, away from the machine? The fact it's OO oriented troubles me though. LISP, Python, C++ all have differences in the way the implement OO - I can't see UML being free of assumptions about how OO is implemented.

C++ has private members, Python makes everything public, LISP allows you to decide the precedence of multiply inherited classes on a case-by-case basis, Java doesn't do multiple inheritance it's like the old days when everyone had their own BASIC - everyone has their own OO model.

Wotta pain. Ouch!

Tuesday, September 14

Things I'd do if I had the time.

I want to write a game about an ecology of self illuminating metaballs that
fly over implausibly coloured and pulsating landscapes to feed from
spontaneously erupting particle fountains.

Monday, September 13

Software renderer in Lisp

I'm seized by the insane urge to write a software renderer in Lisp. I don't know where this came from: actually, I think I do - fond memories of Apple II shape tables and the disire to test the lisperati's claim that it's performace is parallel to that of C, and also a desire to find out exactly what high - performance lisp is like.

I've alread created an sbcl binding to the PTC. I really must stick it into a CVS repository somewhere - it may be useful for someone else.

Sunday, September 5

Building Graphics3D-CPP with Scons

G3d-cpp is an ideal (IMHO) library for working with when constructing 3d testbeds or demos: it doesn't aim to be an over-arching SDK that handles every last detail of OS/Game interaction (it delegates most of those tasks to the SDL), and it uses C++ very effectively in abstracting the render device, windows, geometry and all the things you normally have to deal with in finicky detail in C. If I have to deal with Bjarnes monster, this is the arena I'd chose to fight in :)

Here is the SConstruct. At present I'm supporting release build only: and my architecture optimisation flags are set for up an AMD64 and the resulting binary may not be happy on anything less than a P4/SSE2 capable - chip. It also assumes we are linking with a version of SDL & zlib built by the scripts in the two blog entries below.

# Sconstruct file for G3D
import sys

# microsoft tool kit environment
env = Environment(tools = [ 'mstoolkit' ])

env['CPPPATH'] = [ "#\\include\\", "#\\include\\G3D", "#\\include\\GLG3D", "#\\include\\glh", "#\\include\\zlib", "..\\SDL-1.2.7\\include" ]
env['LIBPATH'] = [ "#\\win32-lib", "..\\SDL-1.2.7", '..\\zlib' ]
env['LIBS'] = [ "kernel32.lib", "user32.lib", "gdi32.lib", "winspool.lib", "comdlg32.lib", "advapi32.lib", "shell32.lib", "ole32.lib", "oleaut32.lib", "uuid.lib", "winmm.lib", "opengl32.lib", "glu32.lib", "ddraw.lib", "dinput.lib", "dxguid.lib", "zlib.lib", "version.lib" ]

#if project_config == 'debug':
# env['LIBS'] = env['LIBS'] + [ "SDLd.lib", "SDLmaind.lib" ]
# program_name = [ "#\\demos\\GLG3D_DemoD.exe" ]
# library_name = [ "#\\win32-lib\GLG3D-debug.lib" ]
# graphics_library_name = [ "#\\win32-lib\G3D-debug.lib" ]
# env['CCFLAGS'] = [ '/nologo', '/W3', '/Zi', '/Od', '/MTd' ]
# env['LINKFLAGS'] = [ '/subsystem:windows', '/machine:x86' ]

#if project_config == 'release':
# env['LIBS'] = env['LIBS'] + [ 'SDL.lib', 'SDLmain.lib' ] # [ "G3D", "GLG3D", "SDL.lib", "SDLmain.lib" ]

program_name = [ "#\demos\\GLG3D_Demo.exe" ]
library_name = [ "#\\win32-lib\GLG3D.lib" ]
graphics_library_name = [ "#\\win32-lib\G3D.lib" ]
jpeg_library_name = [ "#\\win32-lib\libjpeg.lib" ]

env['CCFLAGS'] = [ '/nologo', '/W3', '/GF', '/G7', '/Ox', '/arch:SSE2', '/Gy', '/EHsc', '/MT' ]
env['LINKFLAGS'] = [ '/subsystem:windows', '/machine:x86' ]

# library
env.StaticLibrary( library_name, [

env.StaticLibrary( graphics_library_name, [


env['LIBS'] = env['LIBS'] + [ "GLG3D.lib", "G3D.lib", "libjpeg.lib", "SDL.lib", "SDL_main.lib" ]

# demos
env.Program( program_name, [ r'#\demos\GLG3D_Demo\main.cpp' ] )

Building the SDL with SCons

Just as easy, another SConstruct in the root directory. Not SCons best practice, but certianly the simplest way and all that's needed for such relatively small (compared to say, the Linux Kernel) projects.

Note that I'm building static libraries - this is because the toolkit doesn't support the DLL versions of the C/C++ runtime libraries.

# Sconstruct file for SDL-1.2.7.
import sys

# microsoft tool kit environment
env = Environment(tools = [ 'mstoolkit' ])

# debug or release
project_config = ARGUMENTS.get('config', 'debug')
project_stdio = ARGUMENTS.get('stdio', 'yes' )

if not project_config in [ 'debug', 'release' ]:
print 'Invalid configuration - should be release or debug'

if not project_stdio in [ 'yes', 'no' ]:
print 'Invalid stdio - must be yes or no'

if project_config == 'debug':
library_names = [ "SDLd.lib", 'SDL_maind.lib' ]
env['CCFLAGS'] = [ '/nologo', '/W3', '/Zi', '/Od', '/MTd' ]
project_stdio = 'no'

if project_config == 'release':
library_names = [ "SDL.lib", 'SDL_main.lib' ]
if project_stdio == 'no':
env['CCFLAGS'] = [ '/nologo', '/W3', '/GF', '/MT', '/G7', '/Ox', '/arch:SSE2', '/Gy' ]

env['CPPPATH'] = [ r'#\src', r'#\src\audio', r'#\src\video', r'src\video\wincommon', r'#\src\video\windx5',
r'#\src\events', r'#\src\joystick', r'#\src\cdrom', r'#\src\thread', r'#\src\thread\win32',
r'#\src\timer', r'#\include', r'#\include\SDL']

env.StaticLibrary( library_names[0], [
r"#\src\video\SDL_stretch.c" ] )

env.StaticLibrary(library_names[1], [ r"#\src\Main\Win32\SDL_win32_main.c" ])

Building Zlib With Scons

The First library we need: a lot of other packages link with it. I insall all my libaries under a single root directory (C:\Projects\libraries in my case) and the build scripts assume you do it, too. All it takes is a single SConstruct:

# Sconstruct file for SDL-1.2.7.
import sys

# microsoft tool kit environment
env = Environment(tools = [ 'mstoolkit' ])

# debug or release
project_config = ARGUMENTS.get('config', 'release')

if not project_config in [ 'debug', 'release' ]:
print 'Invalid configuration - should be release or debug'

if project_config == 'debug':
library_name = [ "zlibd.lib" ]
env['CCFLAGS'] = [ '/nologo', '/W3', '/Zi', '/Od', '/MTd' ]

if project_config == 'release':
library_name = [ "zlib.lib" ]
env['CCFLAGS'] = [ '/nologo', '/W3', '/GF', '/MT', '/G7', '/Ox', '/arch:SSE2', '/Gy' ]

env['CPPPATH'] = [ r'#' ]

env.StaticLibrary( library_name, [ "adler32.c", "compress.c", "crc32.c", "deflate.c", "gzio.c", "infback.c", "inffast.c", "inflate.c", "inftrees.c", "trees.c", "uncompr.c", "zutil.c" ])

Cut price Win32 Graphics Coding.

Ever since Microsoft released their VC/C++ 2003 compiler command line tools free (as in beer) I've been using it for my coding at home. I've built a number of ibraries with it on the Win32 system including g3d-cpp and the SDL. What follows is a quick HOWTO.

First, catch your hare. You will need the command line compiler itself. You will then need the SDKS that enable coding on Win32: The Platform SDK and the Direct X SDK. You could also get the .NET Framework while you were are at it, but I haven't used with any of the graphics libraries that I build.

Secondly, you will need the tools that you are going to build the libraries with Python (if you don't already have it) - any recent version will do and Scons via this link 0.96.1 . Scons is "a better make" - it's based on a classic perl build call Cons and builds just about anything on any platform with any tool. The developers have paid great attention to maintaining "build correctess: it pre-computes all the dependencies before building and rebuilds only exactly what needs to be build. In addition the build scripts it uses are signinficantly easier to use than make and it supports parallel building out of the box. It's gradually becoming the build tool of choice for a lot of projects."

Unzip the scons zip into an arbitary directory - we will call it %SCONS%. Scons doesn't support the vc toolkit "out of the box" just yet, but I've written an Scons tool script to support it which you need to copy to your %SCONS%\scons-0.96.1\engine\SCons\tool directory in the fresh Scons you just unzipped. Go to %SCONS%\scons-0.96.1 and type "python install" and it will all be installed. You should be all set for vc toolkit development with SCons.

Tuesday, July 27

Game Du Jour

TrackBalls: a Marble Madness clone for Win32 and Linux (and from what I see, could easily port to Mac OS X). Marble Madness was one of my favourtie arcade games ever, so I expect this one to result in quite a bit of lost productivity..

Monday, July 26

BlogTidy - HTMLTidy for Blogger

I've been spending my time knocking together a version of HTML-Tidy that understands Blogger block tags. It's an out and out hack, but it seems to work ok, for all it's potential template mangling properties that might be a consequence of redefining the blogger tags to be part of the table content model.

If you are feeling brave, the sources live here and the binaries live here. Note that you will need SCons to build it, although modifying the SConstruct script to your taste should be trivial.

Sunday, July 11

Language Comparisons


I found it interesting that the LISP forced me to decompose the code into much smaller functions. You can see just how radically *different* LISP is, and you can see the parallels between Python and C that make the two languages such a close fit, including the fact that Python delegates much of the performance - related work to C...I'll add Java, C++ with the next post; but it does highlight the fact that LISP is a completely different approach to the process of compiling and composing programs when compared to block - structure of languages like Java, C and Pascal. I'm not sure that this is the best illustrative code possible. I think something animating a set of different but similar objects - boids, would be the best test case to see if a language is "game-worthy"..does anyone have any more suggestions?

Incidentally, in the course of preparing this post, I discovered the insanely handy TOhtml vim plugin for tranforming source code to HTML. I wonder if Emacs has anything similar?

Saturday, July 10

Language Complexity

"Simple things should be simple. Difficult things should be possible." This is the hallmark of any good computer programming language. If it is hard to do a simple thing, then the language is poorly designed.

I don't know who this quote is attributable to, but it is language design in a nutshell. The devil, however, is in the details, as ever. I'd like to start this series of posts about language complexity by taking aim at two canards within the game development community:

One: Garbage collection is evil. There's a myth that garbage collected languages are unsuitable for game development because games are soft real-time applications and a decent framerate is one of their prime requirements. The pauses due to garbage collection are often cited as a reason for not using such languages as Java and Lisp or Python. Each has separate issues that are problematic for game development, but Garbage Collection isn't among them. Typically a soft real time game allocates all the resources it needs prior to entering a main loop and then does NO MORE ALLOCATION. It's at this point garbage collection is moot as no more garbage is being created for collection, providing the compiler has a mechanism for creating function-local variables on the stack frame or in registers rather than the heap - which both Java and Lisp compilers can do. So the recipe for a game would be: pre-allocate all arrays, globals, etc needed for resource tracking in the main loop, switch off garbage collection, make any heap allocations an exception (so they don't creep in by accident), then when the main loop (shooting the aliens, driving round the city, flying the spaceship, whatever) is done, switch off the exception and switch garbage collection back on. Yes, it's really that simple. It's dynamic allocation and heap walking that is the true problem for a soft-real time system..that's all. More information can be found in the Garbage Collection FAQ.

Two: Static typechecking is a win. Yes it is, but only in a language like C++ where the cost of compilation is HUGE. Compile times of an hour were common on Driv3r. However, your typical Python or Lisp program is composed interactively, and run instantly. In this case, pushing type checking to run-time is no big loss. Which is Python's approach. The other approach is the Lisp approach - to pick out a single, versatile data structure and operate on it as much as possible as in : "It's better to have 100 functions operating on 1 data type than 10 functions operating on 10 data types.". Further discussion of this can be found *here* on Bruce Eckels Weblog .

I'm going to follow up this post with the implementation of a name-generation algorithm in a number of different languages, starting with the original, in Python. It's better that the languages speak for themselves.

Wednesday, June 30

On Lisp

As part of the language complexity article I'm writing I'd thought I'd look at lisp. Getting back to lisp is tougher than I thought. Maybe it's because of
the beta-ish nature of the implementation I'm using (Steel Bank Common
). Nothing seems to 'just work', in the manner you'd expect from
the more common configure; make; make install triad. I understand that
SBCL was actually an attempt to address this and make LISP much easier
to compile and bootstrap onto other platforms. If so, it's a step in
the right direction.

The other issue is the asdf system. Some thought has gone into it, but
I still had problems with it. It took me about half an hour to figure
out how to use asdf-install to configure a package. There were
websites about the internals of asdf, but not an idiots guide. It took
me awhile to realise that installing cl-ncurses was as simple as
typing (asdf-install '"cl-ncurses") but when I did, I was very
impressed - a simple way of downloading definitive packages off the
web. Definitely one of the things lisp needs.

The other problem I'm having is with the packages themselves: cl-sdl
crashes after awhile when an sdl app is running. I'm told this is a
drawback fixed with 1.2.7, so I'm off to try that. And cl-nucurses apps
just can't be used from SLIME for love or money. (initwin) causes the
SLIME prompt to hang. Problems, problems. Meanwhile, pygame works
flawlessy...LISP has a lot of catching up to do, but at least it's
headed in the right direction.

I upgraded from SBCL 0.8.8 to 0.8.11 to try and deal with all
this. Now cl-sdl and cl-ncurses refuse to load because the .fasl files
contain out-of date versions of the compiled bytecode. How the hell do
I recompile? If only I could find a page that dealt with all this for
newbies. It's the sort of thing one could pick up in an hour - or -
two's conversation with a lispmeister, but such people are hard to

Tuesday, June 8


There's one fringe benefit to working in Free Software land, and that's that sometimes (just sometimes) the documentation has a sense of humour. Witness the strfry function.

Ok, so the gag is spread all around the net. But it's still new to me

Monday, June 7

Quantity of Art.

This is our first, and particularly thorny problem. Procedural techniques are the mooted solution. They can be used effectively as this demo shows. However, the tool used to create this is the product of several years on/off work.

Here are some examples of procedural techniques at work: firstly for textures.

The Unreal engine uses procedural textures to animate fire and other things in real time. Perlin noise is the old standby for generating textures for wood, marble, and fire, but has become something of an artistic cliche.

The most interesting technique I have seen on my travels around the web recently is that of using Steerable Pyramids which seems to be able to synthesize a promising range of textures.

Secondly: landscapes.

landscapes are another natural subject for procedural generation as they are closely related to textures - indeed, a terrain can easily be seen as a huge bumpmap. I am only point to a couple of open source tools here: Terraform and Demeter as terrain generation techniques are already well known and plastered all over the web.

Thirdly: interiors.

Interiors are a subset of cityscapes, a city being a set of interiors. The classic "interior" however, is the dungeon crawl dungeon.

There's a nice a-life technique for carving out 'interesting' dungeons and a 3d counterpart.
I suspect the former technique could be extended to 3d by having the ai creatures carve out voxels on a 3d grid instead of rectangles on a 2d grid, or perhaps a different approach via extruding a floor plan, similar to this Doom level generator would be more fruitful?

Fourthly: cityscapes.

Not much seems to be extant in this area. This strikes me as strange, as buildings are regular structures and should be inherently easier to model procedurally than the 'organic' forms of terrain, clouds, and fire which are often modeled procedurally.

The virtual terrain project has a set of notes on the subject which indicate the magnitude of the problem.

It must be said that they are setting their sights pretty high by trying to model the architecture of all possible schools in all areas of the world over all history. A more limited means range may be achievable via a set of suitable shape grammars. Just to prove I'm not talking out of my hat here, I can point to a paper written by some researchers who have actually implemented this to generate a viable cityscape.

Fifthly: and most importantly...Characters

For generating and manipulating character models there are plenty of tools available commercially that could conceivably save a procedural representation of a generated character: Character Studio, Poser and Creature Creator to name a few.
Blender also has the open source "make human" script. However, these don't deal with the thorny issue of animating the results. Inverse Kinematics is a nice technique for procedural animation, but constraining it to realistic - looking solutions is a non-trivial problem. I suspect the solution lies in the domain of
evolutionary computing or genetic algorithms, but until a good, cheap procedural model of bipedal and quadripedal locomotion comes along (and it's a hot research topic) I don't know.

Managers should be up to the job.

I've come across several interpretations of the role of "project manager" in the industry - it seems to vary a great deal from shop to shop, and sometimes even from project to project. The range covers the completely hands - off: "sit in the back room and play quake all day" to the completely hands - on: "necromancy the developers with daily reports from them and double - check all their decisions". Needless to say, somewhere between these extremes lies the ideal.

There are some things project managers *must* have - recent development experience: they should have been through two or three projects as a developer, otherwise they can't really understand the process they have to manage, and the results are hopeless. They must also play the current crop of games so that they have a good idea of the playability and visual quality required of the project so that they can identify what is lacking. Anyone who doesn't meet these requirements is bad news.

The worst case scenario is a 43 old bowling alley manager who knows nothing about games leading the team because he looks "safer" at shareholder meetings. Ok, this never happened to me, but I have seen enough similar things in the past to lead me to believe that particular horror story

Of course, never having managed a project myself, I would not presume to offer a critique of others who have managed me, but I can point to an excellent source of advice for such people.

Game development

Cutting edge game development is bloody complicated, expensive and now, nearly impossible. This is a truism. Only large publishers and mega-developers can produce games in this day and age. There are several problems entwined.

1. Quantity of art.

It can take six people a year to fill a 600 MB CD with artwork. They will need good knowldege of a suitable tool such as 3DS Max, Maya, Gamespace, Blender, whatever, plus artistic talent. These people are not easy to find or particularly cheap to hire.

2. Managers need to be shot.

Oh, the management is crap. Another truism. Most projects suck. Are over-time, and over-budget? So, what else is new? The person leading the team has to be multi-skilled. They have to manage in the classical sense of scheduling. They have to be able to program, they have to be able to tell when people are bullshiting them about schedules, and spot possible dependencies well in advance. They should also be able to design a little - it helps if they can spot easy wins that enhance the game and can structure or steer the codebase to obtain them. In short, they need to be superhuman. The strongest industry franchieses - at least on the PC are those with a strong programmer/designer figure at the helm.

3.Workflow is crap.

We use monolithic tools. Max, VisualStudio, and usually a custom per-game editor application. Remember the old days when Spreadsheet, Database, and Wordprocessor used to be seperate apps? Why are these seperate apps?

4.Language complexity.

C++ is an order of magnitude more complex than C and supports about five different programming paragadims. Which is great, but not when you have thirty programmers mixing them at will.

5. The base functionality you need is more complex.

In 1987 a sprite blitter engine was sufficent. In 1999 something that drew
textured triangles really fast cut the mustard. Now you need something that can still draw triangles fast, but also needs to be able to animate objects, do numerical integration to do realtime physics on them, plus
collision detection, and scene management...

I will deal with each of these problems and their solution one by one in individual posts, but now we have another deadline to hit today, for Driver Three I really shouldn't be writing this...bye..!