Code Story

Wednesday, May 07, 2008

Plague

Plague, Sam Kerbeck

These screens are taken from Plague, a game which I started work on in 1996 at Eidos Interactive. I developed the 3D and game engines to match a very comprehensive game design by Dave Morris. The game concept was created by Ian Livingstone.

Plague was the first true 3D strategy game of its time and it was presented at E3 (LA) in 1997. It received great press response as it was hailed as one of the major products to watch out for in 1998/1999. PC Gamer selected it as one of four products of 1998 along side Black & White.

Plague contained many new concepts in programming and design and it was very close to our hearts, but unfortunately it never made it to full production. However, the software engine behind it was at the heart of a number of published products.

Thursday, May 01, 2008

Game Art?

Sam Kerbeck


While we were developing a game a few years ago, I was presented with a caricature of me drawn by one of the artists on the team. And all that time I thought he was busy with the interface graphics, I didn't know he dropped the 'inter' and was just working on the 'face'...

Thursday, March 27, 2008

Throw Tantrum

Recently, I had an evening meal with two great techie friends in a nice restaurant which had an open buffet with an impressive selection and variety of food, including Indian, Chinese and Italian.

We talked about a wide range of things, the future of technology, artificial intelligence, politics and how governments are trying to control the Internet, the current state of programmers and programming and of course women, amongst other things. After a few beers, we discovered the ultimate code which we are convinced is at the core of female operating systems:

unsafe {
while (married) {
try {
if (_nag() == FAILED)
if (_nag_more() == FAILED)
if (_nag_even_more() == FAILED)
throw tantrum();
} catch (Mood* behaviour)
(behaviour->*hide_reason)();
}
}

Thursday, March 20, 2008

Resurrection

I have just discovered that Warzone 2100 is now an open source project under the title Warzone 2100 Resurrection Project.

I downloaded the Linux version and I am really impressed by the efforts of the team. They have done a great job. I wish them success and look forward to future versions.

The game was originally developed by Pumpkin Studios of Eidos Plc and featured the first ever PC 3D terrain engine I wrote back in 1995: iVi/S. Pumpkin Studios were also the first team to use my PC-based software engines. I think it was 1996-1997 when I gave them the first version. We had a lot of meetings going over the code together. It was good fun and I will resurrect some of these stories in due course.

Wednesday, June 20, 2007

Smoke me a ‘Clipper’ I’ll be back for Breakfast

When we observe the world we live in, we see things more or less in order. Generally, objects which are closer to us look bigger than those which are far away from us. We see opaque objects close to us obscure objects behind them, as they should. We take these features of our real-world visual system for granted. The developer is quite simply awesome.

Just imagine for one second that on an average day, while you are walking down the street, and without being under the influence of anything, you see a car, for example, which is quite far from you showing through a building which is right in front of you, or you see a tree which is behind a wall showing right through the wall. I’m sure someone out there would say that this is normal and that’s what they see all the time, but I’m talking about the majority of people who are awake and not the exceptional supermen and superwomen with x-ray vision. Nor am I talking about Ace Rimmer from Red Dwarf, the super version of Arnold Rimmer, who would simply say: “You can’t see through objects? Smoke me a kipper can you do that? I’ll be back for breakfast.”, what a guy!

Enter the world of solid 3D graphics development before the introduction of hardware acceleration with fast ZBuffers or WBuffers.

Just before these Buffers were efficient enough for use in interactive 3D products, we had to sort the scene by time-consuming software techniques (or by hand as we called it), or find clever tricks to avoid this situation altogether for rendering and viewing a moving 3D scene.

The idea is very simple; realtime interactive 3D graphics systems normally generate 20-30 frames per second for smooth animation. When a frame is ready to be drawn on screen a distance value for each 3D polygon is kept for sorting it within the scene according to its depth or distance from the viewer. This way, we can draw the farthest polygons first, then the nearest last. This is called the Painter’s algorithm, which relied on fast sorting algorithms such as Hash Tables, I'm not talking about the more complex algorithms that became popular later such as Binary Space Partitioning Trees or BSP Trees for short, these were slightly different and didn't fall exactly into the painter's algorithm technique. The Painter’s algorithm kind of worked, but caused problems when there was a discrepancy in polygon sizes and orientations. You could sometimes see a small far polygon showing through a larger one in front of it! Not a pretty sight, nor is it reassuring. I mean it doesn’t give you confidence if you see a flying plane with parts of its cockpit showing through the under-carriage. Just imagine if this happened in real life on a normal flight from London to New York. But there were many 3D products out there that had this problem which created very surreal environments indeed.

There are ways to avoid this problem by splitting the large polygons to make them smaller and ensuring most polygons are roughly the same size, or using other mathematical techniques; however, this needed more processing power at the time when it was scarce.

Some programmers tried to solve this problem in the most peculiar way. One of the very successful flight simulator products I later worked on used Bubble Sort for its Painter’s algorithm! Bubble Sort was mainly used to teach the concept of sorting to new programmers and is applied mainly on small lists of objects. But to use it for sorting 3D scenes of thousands of polygons many times a second was just crazy. Bubble Sort needs many passes through the lists to complete the task, the programmer who came up with this ”ingenious” method to reduce the processing time required per frame must be presented with the award: “I don’t give a damn” for coding. The code would do one pass per frame meaning that it would take a while before any object is completely sorted. You could actually see the 3D object rearranging itself every time you rotated the scene. It was really funny to watch. I had never seen an F16 or SU27 looking like a chicken shaking water out of its feathers when this Bubble Sorting kicked in for a few seconds. I can’t believe this was acceptable for a commercial product and no one even complained! I still have a copy of the original code which I keep for its entertainment value.

As I was working to better these techniques, a 3D graphics modeller joined my team as an apprentice. He was introduced to the team and was told I was the lead-developer and the one who was responsible for the technology. This meant that he would come to interrupt me every few minutes with a new question about the technology which he was using. It made it worse that he sounded like he was constantly under the influence of something or another! I mean, he sounded like Ozzy Ozbourne on Valium. Every sentence of his had to include one or more from the following subset: Duuuuuuuuuuuuude, Whatevaaa, Yeaaaaaah Riiiiiight, Cooooooooooool and Yaaaaa Maaaaaaaaan. He would often sing Satisfaction by the Rolling Stones with his face close right up to the fan because “it made a coooooooool noise maaaaaaaaan”. Don't ask. Just ignore this, as we all did.

While I was working on a 3D morphing concept which I had read about in one of ACM SigGraph publications, and was still trying to work out what on Earth Barycentric Coordinates were, the graphics modeller came over to my desk and said (Ozzy style):

Modeller: Hi maaaaaan, the clipping doesn’t work
Me: The clipping?
Modeller: Yeah maaaaaan, come and have a look duuuuude
Me: Look “maaaaaan”, this is called the sorting….
Modeller: Whateva
Me:…not the clipping. You have a small polygon next to a very large one. Cut the large polygon in half, can you do that?

Modeller: [in shock]

He went to his desk and 15 minutes later he came back:

Modeller: Heeey maaaaan, the clipping doesn’t work.
Me: It’s the sorting…
Modeller: Whateva

I went to his computer to see what he was on about. I was surprised to see that he now had two large polygons, not one, next to a very small one, which obviously would cause problems for the primitive sorting algorithms, so I said:

Me: If someone gives you a long piece of wood and says it is too long, cut it in half, what would you do? Do you cut it long ways so you end up with *two* long pieces?

Modeller: [in shock].

He seemed that he could not get no satisfaction from my answer.

Me: Cut the polygon across, not long ways! Then I went into Ace Rimmer mode just to confuse him and pay him back for all his Rolling Stones stunts, and said: “You can’t do that? Smoke me a kipper can you do that? I’ll be back for breakfast.”

Modeller: [long pause] then shouting at the top of his voice: THIS GUY IS WEIRD MAAAAAAAAAAAAAAAAAAN.

I’m weird?

Well, gradually he understood what I was on about, but still could not understand why our planes looked like ruffled chickens every now and then. I honestly didn’t want to get into the sorting algorithms with him, I mean he thought I was weird telling him to cut long polygons in half to get the sorting to work properly, what would he have said if I started talking about Bubble Sort or worse: Binary Space Partitioning Trees. I’d rather smoke him a smegging kipper.

Monday, October 02, 2006

An Eye (Vi) Short of a Graphics Engine

Learning 3D transformations for game development can be a painful exercise. You will need to know 3D matrix and vector operations including dot and cross products, vector addition, subtraction, scaling and of course transformations, to name the basics. There is a lot to learn, lots of tricks and pitfalls.

Where is the pain in that, I hear you ask. Isn’t this like learning anything else? Why is it painful? I’ll explain…

I have designed and written quite a few 3D graphics engines and APIs in my life, and I still do. In addition to writing the stuff I had to provide it to other development teams and further explain what this 3D business is all about. I’ll take one case of a development house in the south of England, who were writing a 3D strategy game which needed 3D capabilities and they didn’t have the necessary expertise, even though they had over £1M in investment. It goes to show that it is not what you know, but who you know.

On my first visit to their nice empty offices (5 people present in a place that could house 30) that overlooked a beautiful stream and lots of green things (trees), quite a contrast from our offices in London, I installed the latest graphics terrain engine I was working on on the lead programmer’s computer. The engine named iVi, which was partly Roman for 4: IV (ie version 4 of the engine) then I added an ‘i’ for Interactive, clever or what? Therefore, I had the very imaginative and media savvy name iVi. You’ll be hard pressed to get a name better than that. Don’t throw in my face B-Render or Render(Under)Ware or RenderMorphics or The Reality Engine or even Demis Hassabis’ Totality Engine. iVi is the final word in 3D Graphics Engine naming and that’s that.

Sorry I got side-tracked there; back to the story, after the installation, including the source code of course, the lead-programmer asked me to explain to him 3D viewing transformations. Wait, you mean, what is your average 3D viewing transformation for your average terrain system? Oh easy, easy peasy, right down my particular field of expertise that is. You wouldn't prefer a space question?

Well I could have explained the transformations as a set of three coordinate systems, the world coordinate system, the system that represents the entire 3D world, the objects/models coordinate system, which is the local representation of the objects in the world, and last but not least (or could be least I don’t know), the screen coordinate system.

Initially we transform our objects in their local space then concatenate the transformations with those of the world’s so the objects appear in their right position, then we apply the viewing transformations. The viewing transformations take into account what the viewer is looking at, and his/her orientation. We transform our world coordinates with the viewer’s matrix (this is basically multiplying two matrices or two quaternions or whatever’s your poison, together) and finally we apply perspective projection on the resulting coordinates to translate them from 3D coordinates to 2D (screen) coordinates, this is when our final image can be rendered on the flat screen giving the appearance that the whole thing is actually 3D. There!

Sometimes, things can be even simpler. For example, some implementations don’t require the viewer to change their orientation; they will always be looking down the world at a fixed angle. You must’ve seen many products like that, particularly strategy titles. In this case, we can skip a lot of operations, saving along the way, a few multiplies here and there. Well a few thousand actually.

In the case of our developer, their game had what we call a fixed viewer; I was explaining all this to the lead programmer who was sitting to my right as I was facing the computer ahead. I had my arm fully extended in front of me representing a vector from the eye of the viewer to the centre of projection (the screen), I was explaining that when the view is fixed the eye doesn’t move (my head stays fixed towards the screen), it’s really the vector (my arm) that rotates inversely to the world orientation. In this case, inversely meant that I rotated, with speed and force, my arm (the eye vector), to the right, without moving my head, so I didn’t realise when I heard a scream that my eye vector (arm) had landed straight onto the face of the lead programmer. I looked and he had his face in his hands in agony.

WOOOooops! I should’ve used pen and paper to explain, that would have been better! Not knowing exactly how to respond to this turn of events, I simply turned to the programmer and told him while he was still holding his eye and nose, “You won’t forget the fixed-viewing transformations now will you.” I left the offices with haste shortly after that. Although I was invited to the offices many times after that and everybody was very pleasant but I could see a certain look on the lead programmer’s face, and he always stood a few feet distance to my left. I don’t think he ever forgave me!

A while later, there was a review in Edge Magazine about the same game that was using my graphics engine iV(awesome)i. The head of the development studio was interviewed and he said: “The best thing about our game is the 3D Graphics Engine…” Cool, that’s me, how nice of them. But wait, he continued, “…which has been written by our lead programmer.” Oh! I see. No mention of the man who actually spent years writing it then! Come to think of it, I don’t blame them, since the lead programmer probably still has a black eye from my fixed viewing lesson and has endured physical pain with evidence to prove what he went through using iVi. But as far as I am concerned, he was still one black eye (Vi) short of a graphics engine. If I see him again, I’ll give him another black eye for his blatant lie, only then can he claim that he wrote the engine, he would have truly earned it.

Oh I forgot, I did get a "Special thanks to Sam kerbeck" in the game's documentation, which is still a lot more than other teams I could mention.

Thursday, September 22, 2005

AC-AXIS Rotate

In the 1980s when 3D graphics on personal computers was in its infancy, and when no PC graphics card had a usable resolution beyond 320x200, let alone 3D graphics capability. When a Play Station was something you find in kindergartens, and when the only good book that covered the subject of 3D was ”Interactive Computer Graphics” by Foley and Van Dam. We were busy innovating the latest and fastest 3D rendering engine primitives. I wrote Bresenham's line scan converters that averaged 1 and ½ machine code instructions per pixel, oh yes, and a triangle routine that would render 3D triangles at the fastest possible speed the computers of the day allowed. I used self-generating code. Look Up Tables for fast access, unrolled code to produce the most peculiar hand-crafted set of assembler instructions you've ever seen. We were creative with programming mathematical equations. I even knew what a Quaternion was, and how to interpolate Quaternions. The stuff we worked on then is embedded in the latest 3D hardware and software of today. We lived and breathed 3D graphics. We ruled!

Back then, I was invited for an interview by a games developer in the south of England. I had heard of this development team since they were one of the very few unfortunate developers who accepted writing 3D games and Flightsims for the British Archimedes computer made by Acorn, which I happened to have.

I was interviewed by the technical and research directors of the company. After passing the barrage of questions with flying colours, the research director started asking me about 3D rotations and compilers (I could not see the relationship between the two), which I could answer with ease. Bring it on...

Then half way through the interview, he looked at me with an evil-eye and asked: "How would you do AC AXIS ROTATE then?"...

Excuse me? A C? A C AXIS? ROTATE?!! WHAT? I went through every filed section in my memory for an “A” Matrix, “C” Matrix, “AC” Matrix multiplication? Alternating Current AXIS? Inverse XY = AC? What is he on about? Damn Foley and Van Dam for not mentioning this in their Computer Graphics book. They don't know everything, I knew it. I will never read their books again. Still, I had to find an answer to the question, I'll come back to Foley et al later. My brain told me to use the following string as an answer: "I'm sorry, I don't know!!!"

Soon the interview ended and I was on my way driving back home. The journey took just over an hour. I didn't enjoy the scenic route I took. AC AXIS ROTATE? What the? I know nothing!

A few weeks later I was offered a job by the company as the lead programmer for one of their new and exciting projects. A large-scale 3D space game for the PC . Which I accepted.

When I started my new position, I was going through existing code and got to the graphics engine section which was written by the same Mr research director.

Scrolling down the code, I could not believe my eyes. I found the following text with the familiar name: ac_axis_rotate...

I MEAN. NO WAY!!! ac_axis huh? You must be kidding me right? So, AC-AXIS ROTATE or shall I say ac_axis_rotate, is a name of a function the research director wrote? How the hell am I supposed to know that? I mean, how am I supposed to know what function names he had in his code? He might as well had asked me about the contents of his pockets. Was he having fun at my expense? I mentioned this to one of the programmers at the company and after laughing hysterically for what seemed like 10 minutes he said, "fun, I don't think so, I bet he meant it!"

Well I must respect that, from now on, I promise, I will be doing the same when I start interviewing people (the ones I don't like of course). Let me see: "How would you do adjustMACHNO?", "Do you know QMRvel?", "Can you normaliseMV huh? Can you punk? Well can ya?" I have a whole list of function names, and I don't mean the ones which I have published as open source. These are secret ones, no one will know them, in fact I haven't even written the code, I'll just invent the names. I must get someone else to suffer like I did. ac_axis_rotate? *%##(@!!*#@!%%!

ac_axis rotate turned out to be at the heart of the graphics engine code. Flight and space sims require free movement in 3D space. You need to be able to rotate about all three principal axes: X, Y and Z. Since computer games do not have to be accurate when representing rotations, programmers tended to use simple Euler angle additions to achieve 3D animation. This of course is incorrect, and problems start to occur in certain situations particularly when you are pitched right up near 90 degrees, you start rotating in the wrong direction. This is referred to as Gimbal Lock. The research director decided to incorrectly represent his rotations as an easy way out and try to fix the problem when it occurred by brute force, or more precisely, by his function ac_axis_rotate. If you played a Flightsim which used this code and you did a loop-the-loop, your aircraft wobbled strangely half way through. That wobble, ladies and gentlemen is ac_axis_rotate at work, trying desperately to fix the problem of Gimbal Lock and saving you from going in the wrong direction eventually heading straight to the ground. Had the rotations been represented by cumulative matrix or quaternion multiplications, it would have been a correct and wobble-free representation and you could do your loop-the-loop smoothly without the need for ac_axis_rotate altogether.

Gimbal Lock may be OK in computer games, but, if you watched Apollo 13, when things went wrong while the crew were in space, one of of the Shuttle crew shouted: "Don't get into Gimbal Lock!" - You mean NASA equipped their Shuttle with software that represented rotation in space using Euler angles? If I knew, I would have sent them a copy of ac_axis_rotate, it may cause the Shuttle to have weird wobbles but at least they won't be too scared getting into Gimbal Lock. Although the effect of ac_axis_rotate and real gravitational forces may be as fatal as crashing!

So for NASA's sake or in case you are interested (I would fully understand if you are not), here is the full listing of the ac_axis_rotate code. I am sure you might find a good use for it. I personally am planning on printing it on T-Shirts and giving them away free to people I know who are prone to Gimbal Locking. An apparent symptom after a heavy drinking session. I knew I would finally find a good use for this code.

Note: All questions relating to this function should be directed to the research director who wrote it. Don't expect a comprehensible answer and don't be surprised if you end up talking about compiler theory either!


void ac_axis_rotate(Svector *r, Svector *dr)
{
int rr, pr, yr;
int tanrx, srz, crz, crx;
int pitch;

srz = SIN(r->z);
crz = COS(r->z);
crx = COS(r->x);

pitch = ABS((short)r->x);

if (pitch <= DEG(88)) {
tanrx = TAN(r->x);
rr = dr->z +
(int)TRIG_SHIFT(MUL(
(int) TRIG_SHIFT(MUL(dr->x,tanrx)),srz)) -
(int)TRIG_SHIFT(MUL(
(int) TRIG_SHIFT(MUL(dr->y,tanrx)), crz));

pr = (int)TRIG_SHIFT((MUL(dr->x,crz) + MUL(dr->y,srz)));

if (crx != 0)
yr = MULDIV(dr->y,crz,crx) - MULDIV(dr->x,srz,crx);
else
yr = 0;
} else {
pr = (int)TRIG_SHIFT((MUL(dr->x,crz) + MUL(dr->y,srz)));
rr = dr->z;
yr = 0;
}

r->x = ADDANGLE(r->x,pr);
r->y = ADDANGLE(r->y,yr);
r->z = ADDANGLE(r->z,rr);
pitch = (short)r->x;

if (ABS(pitch) > DEG_90) {
if (pitch > 0)
r->x = DEG_90 - (pitch - DEG_90) - DEG_1;
else
r->x = -DEG_90 + (pitch + DEG_90) + DEG_1;
r->y = ADDANGLE(r->y, DEG_180);
r->z = ADDANGLE(r->z, DEG_180);
}
}

Creative Binary

No serious programmer does not know what the binary number system is, how to use it, count, add, subtract, XOR, OR, shift and AND in it. They can even do a lot more than that, human creativity is endless, unlike computers'.

For computers, binary operations are the lowest level the computer "understands". Computers are not clever at using binary. In fact, they are very dumb. If computers were designed to use the decimal system, I cannot imagine the heat that the Pentium Processor would generate. You could possibly use it instead of your central heating system.

The binary number system was chosen for computers precisely because of its simplicity, and to keep the Pentium fan small-ish. It's much easier to design circuits and represent digits electronically that have only two states or symbols: 0 or 1, true or false, on or off, ie binary.

When it comes to humans or programmers more specifically, the situation is somewhat different. A friend of mine used to insert binary notation in his normal everyday sentences: "I am active-low today", meaning: I am at binary 1 when I do not have a current through me!! Don't ask. Or, “I went to the cash machine and it returned FALSE” - i.e. it wouldn't give him money (and we all know why, don't we), or my favorite, is my mathematician programmer friend who used to advertise the fact that the pin codes for his credit cards are arranged as a "tree" in binary digits! Since pin codes normally comprise four decimal digits, then to make a tree in binary, I guess he would have written his pin code down something like this:


You might think that these don't look like trees, but you will have to be a machine code programmer to see it. Just like in the Matrix.

So, does this mean that real trees are pin codes for some global bank? I'll have to think about that!

Having been encouraged by the “usefulness” of binary in everyday life I decided to do the same. I started writing down my pin codes and passwords in binary safe in the knowledge that not everyone is a programmer and therefore, no one will be able to decipher my code. In fact, it would make my note book look cool and important, But wait, what if a pick-pocket pinched my wallet and he happened to be a top class 6502 machine-code programmer or even worse, 68000? This is worrying. I must do something about this, I can't just write my pin code down in "straight" binary! Maybe I can apply binary arithmetic and logical operations to it to make it more secure. I could XOR the bits or AND them with something. That's what I'll do, this way they'll never find out.

A year or so down the line I forgot my pin code for my cash card. No problemo, I knew I had it written down somewhere, in binary no less. I looked for my note book and sure enough I had the following entries:

1101 1010 0011 0111 1100
0001 1011 1100 1010 1111

Great, this is 13 10 3 7 12 1 11 12 10 15 !!!? This didn't look anything like any of my pin codes!! Wait, maybe I shifted the bits left by 1. What did I do with the carry bit? Where is the Status-Register when you need it? Maybe, I XORed all the bits with 11111111 then shifted them right (logical shifts of course, I hate arithmetic shifts). No? Did I ROR the bits into some other fictitious bits? I tried every operation I could think of but could not get my pin code back. I ran out of options. Well, I could write a program which would systematically go through all possible combinations, but I had a feeling that it would not work either and it would take ages to write the program. I needed my cash urgently. The only option left was to pick up the phone and call the bank: "I lost my pin code, could you please send me a new one?"

A few days later I received my new pin code. It was very reassuring to see that they had sent it in straight decimal without dividing it or multiplying it by some weird number.

That evening, I wrote one more thing in my note book next to my binary coded indecipherable pin code: “Don't use binary unless you are a dumb computer and however dumb computers are, they are damn right better at using binary than you. Stick to decimal”