Friday, November 9, 2007

The dawn of 3D games...

I was recently drawn to look back at my first paid programming job, Alpha Waves, which apparently may also have been the first 3D platform game.

Others writing about this game after more than 15 years helped me realize that my recollection of that time might be an interesting bit of computer history worth sharing (If you don't care about such old geezer's stuff, skip that article!) Some of it is documented elsewhere. Some of it may well never have been written before.

Anyway, this is the kind of story that might interest my kids, if only them...

Update: One of my kids, reading the article, asked me why I had been calling Alpha Waves "the first real 3D game", since Starglider 2 had been released more than one year earlier. And it's true that the static screen snapshots below don't do justice to the difference between the state of the art at the time and what Alpha Waves brought to the gaming experience. It's only watching a video of Starglider 2 that my son realized how bad 3D was back then. Videos convey the point much better than words or static pictures:


Starglider 2


Alpha Waves

By the way, Google video really rocks!

Inspiration: Starglider 2

One thing I remember is my inspiration for writing Alpha Waves. It all started with a game called Starglider 2, which for the first time on Atari ST and Amiga (and in microcomputer history, for all I know1), featured somewhat realistic 3D graphics. What made them realistic was that for the first time, this game showed animated flat-shaded graphics. Earlier games like the original Starglider only drew lines. Hiding the lines for back-facing polygons was considered highly advanced stuff. So flat-shaded polygons? That was almost surreal.

My first reaction when seeing Starglider 2 was: "Wow!" My second reaction was: "How do they do that?". Finally, this would turn into: "Can I beat that?". As you can see on the picture, Starglider 2 displayed 3D graphics in a small region of the screen, and only a small number of objects were visible at once. So the next steps, obviously, were to see how large of a screen region you could use for 3D graphics, and how many objects you could draw at the same time.

Today's 3D graphics are generated by hardware capable of filling petagazillions of pixels per second, so young readers may not realize that the memory bandwidth at the time made the simple task of filling the screen with polygons more than a few times per second a challenge in itself. Starglider 2 was smooth!... which, at the time, did not mean 60fps like today, more like 10-15 when the screen got crowded. Remember, this was the time where the boink demo was considered extremely cool.

In summary, doing better than Starglider meant something like filling two thirds of the screen, having 15 objects on screen instead of 4, and remaining above 10 frames per second. Ultimately, Alpha Waves would far exceed this initial objective: full screen, not a single bitmap sprite on screen (even the player was drawn in 3D), and sometimes as many as 50 objects on screen. The Atari ST even ended up with a dual-player mode where two players would compete on screen simultaneously (a feature that never made it to the PC version).

Elaborating 3D algorithms

Obviously, to best Starglider, I had to first understand how one would draw 3D graphics on screen. I quickly rediscovered the mathematical formulas, but they were only the beginning. The real question was how to do it fast. Again, to understand the problem, you have to remember that we are talking about a time where the Motorola 68000 used in the Atari ST and Amiga was considered a relatively fast processor. This processor not only had no built-in floating point capability, it was actually very expensive to do a multiplication! So I ended up reformulating the problem as: "How can I draw 3D using mostly additions?."

The solution would seem extraordinarily obsolete today. The code pre-computed displacement along the X, Y or Z axis, so that it could rotate these vectors only once, and then describe all objects using an encoding that looked like: "go one step right, then two steps up, then one step back". Each individual step was recorded in a temporary array, and then the final 3D object was created by connecting some of these recorded points. Again, this may seem like a very silly algorithm when, today, 3D routinely uses things like quaternions to compute coordinate transforms. But boy! was it fast!

Of course, there were a few other tricks along the way. For example, without floating-point capabilities there was obviously no way to compute a cosine. This was easily solved by storing a pre-computed sine/cosine tables returning integer amplitudes (-32767..32767). That made it possible to use another micro-optimization. On the 68000, the multiplication operation took two 16-bit arguments and returned a 32-bit value. Multiply a 16-bit signed coordinate by a 16-bit signed amplitude gave me a 32-bit signed coordinate. Anybody today would shift that down to obtain a 16-bit value, but the 68000 had no barrel shifter, which meant that shifting down would have been expensive. On the other hand, it had a swap instruction exchanging the high and low 16-bit parts of a 32-bit register. So after applying swap to the result of the multiplication, I was getting a 14-bit coordinate.

Drawing polygons

The problem of coordinate transforms being solved, the next most difficult problem was drawing polygons quickly on screen. This involved a number of steps: clipping, decomposing the result in a number of triangles and trapezoids, and drawing each piece. The details of the kind of techniques used are now well known, and illustrated here (see figure 9.6 in that article).

My original polygon drawing algorithm was already relatively fast, but the Infogrames folks later insisted that I use their in-house routines to facilitate the porting to Amiga (where they had these routines already available). They had at least a couple of people dedicated to the in-house library of graphics routines on a variety of machines, and they were slowly switching to C for the high-level game architecture, using C a little bit like we use scripting languages today, for the slow stuff. And honestly, the Atari ST version of their polygon routine was a little bit faster than mine, using self-modifying code to optimize the inner loop as it ran.

Well, that optimization made it incompatible with the new and amazing 68020-based Atari TT (because you needed to tell the instruction-side of the processor to re-fetch the data you had just written on the data side, which that code did not do). Being pretty annoyed at the 2% difference between their code and mine, I created a best-of-breed combined routine using an assembler variant of Duff's device, which if my memory is correct, bested their code quite handily, and also ran on the Atari TT. But that all happened much later, when we were in the final phase of the game development.

From polygons to worlds

Earlier stages of the development of Alpha Waves were much more modest. I was only starting to be able to draw and rotate simple 3D objects. It began with a big cube showing the limits of the 16-bit coordinate space, the limits of my "world". Then, inside that cube, I placed another one, and one more to test how objects were hiding one another, and so on.

Soon, I had something like a dozen cubes floating in space. And more, and more. And that's when it slowly became clear that I was close to achieving my original dream. This was definitely faster than Starglider. Even with all these objects drawn on screen, on the entire screen no less, this was still smooth. I was thrilled, I was proud! This may seem ridiculous when today anybody can run Second Life and access some 24 terabytes of stored world information, but at the time, this was world-class 3D graphics.

But all things considered, rotating cubes on a screen gets pretty boring pretty fast. So to test my graphic routines, I started exploring ways to move inside my little 3D worlds. The first one was the most obvious possible: some kind of flight simulator that would let you fly through the world. You'd turn left and right or up and down with the joystick, and move forward by firing the joystick. That allowed me to test all possible rotation angles. To avoid the bugs when coordinates exceeded the 16-bit space, I added code that would keep me inside the coordinates cube. It was as if you bounced on the walls, on the ceiling or on the floor.

Believe it or not, I thought it was fun to bounce against the walls, and started testing all kinds of funny dynamics. The next obvious step was to bounce against the cubes inside the world instead of flying right through them as was then the de-facto industry standard... The cubes acted like big repellers, and so bouncing off one would allow you to quickly accelerate, for instance to climb to the top of the world. Add a little gravity, some platforms on the floor to start bouncing when you fell, and Alpha Waves was born!

In my mind, I was sort of recreating the experience of being a smurf, which in the comics bounce from the floor to reach a table, and so on. And I was starting to think that I might build some kind of smurf-based adventure game around that graphics technology. To that end, I started creating a little mechanism to switch from one "room" of the game to the next, through "doors" located on the walls. The trick was to reach the door, and you would switch to the next room. This way, I could explore an even larger world.

I was certainly starting to see some game potential in my code, but I was still not considering that little toy demo as a game, more like the foundation for what might one day be a real great adventure game in 3D. Sure, I had a lot of fun bouncing around, but who else would find this funny?

I couldn't have been more wrong!

Alpha Waves, meet Infogrames

I understood that when I presented this code to Infogrames. At the time, this was still a pretty small company occupying a single floor of a building in Villeurbanne. I don't know how large it was, but I would guess about 20-30 people. Still, this new building was already a giant step up compared to the office I had visited one year earlier, during my first interaction with them. And I need to explain that the first interaction was the reason I was getting back to Infogrames.

The first time, I had been looking for a student job, and they were looking for someone to translate some book about expert systems. Don't ask me why. I think that Bruno Bonnell thought at the time it was a good idea to diversify the company into "serious stuff" like artificial intelligence and some kind of expert system software for mom and pop. No kidding! These were wild times...

In any case, I did the required job, but when came time to be paid... they had already figured out that expert systems were a totally crazy idea and changed their mind. So they did not need my work any more, and in that case, why pay for it? Guess what, when you are aged less than 20, you are pretty naive, you tend to trust folks. In short, there was no written contract, just a gentlemen's agreement that they all too happily broke. I did not get a dime.

So one year or so later, when I returned to them, it was primarily with the intent to make up for that loss by working as an intern for one month, doing little and learning a lot from them. Why did I think this was a good idea? I don't know. I just wanted them to pay me something I guess.

Hey! This is a game!

Anyway, to convince them to hire me during the summer months, I had prepared a sort of career portfolio with various tiny programs. These were a number of half-baked experiments with various technologies like 2D scrolling, sound, text display, and so on. Not a single of these programs was a real game, but my point was more to show that I could write code.

The piece of code I thought would impress them the most was some sort of small clone of Time Bandit, with a few additional features like proportional text being displayed on screen, that was looking so much nicer than the typical fixed font of the time... There was not much of a plot, only a few worlds, but I thought this demonstrated I knew enough about game coding for a summer intern job. Well, when I showed that code, Infograme's technical director essentially yawned. I was seeing the chance of getting my money back escape...

Disappointed, I took the last floppy in my pile. This was the one containing the "Cube" demo. But if my marvelous Time Bandit clone had failed to impress them, this would would definitely be a total flop as well. Anyway, I started it up, gave the joystick to the technical director... and one hour later, he was still holding it, bouncing left and right like crazy! In my memory, he looked every bit like the guy on the picture, fascinated by this new and strange kind of game...

When he finally left the room, the technical director quickly came back with a contract that essentially read: Christophe de Dinechin will be paid 5000F (less than $1000) for a two months intern job working on Infograme's "Project Cube". Well, fool me once, shame on you, fool me twice... My answer was quick: no way, that game is not an Infograme project, it's almost finished (something I had realized only minutes earlier), if you want it, this will be a royalties-based contract. He replied, "This is a standard contract, just sign it, we will adjust it later." Fortunately, I had previous experience with this kind of "contract", so I steadfastly refused to sign anything.

Frederick Raynal

After that, things moved relatively fast. Negotiating royalties was a real pain for me, and according to him, a pleasure for Bruno Bonnell. He commented something along the lines of "all these guys tell me that they don't need much... Well, that's what they get!". I fought for a royalties rate that I thought was decent. In the end, I was very disappointed when I left the room with, if my memory serves me right, something like 17%. I shared my disappointment with the engineers around. I remember a silence. And then, I was told that this was actually the best rate Infogrames had ever conceded to an independent author.

I do not recall how Frederick Raynal got involved exactly, but what I do recall is that he looked at the code, and told his management he felt this code could be ported to the PC. This was against Infogrames' policy at the time, which was to never port an assembly language game to a different CPU. Frederick argued that my code contained comments all over the place that made it very clear what was happening. And so he ported it to the PC. He actually did more than port it. The PC version included, for example, a very nice tutorial showing how to use the game which did not exist in my original version. The only thing he failed to do is accounting for different CPU speeds, and so Alpha Waves is practically unplayable on today's machines without slowing it down quite a bit. Update: I had him read this blog, since I'm talking about him, and he commented that it was the last time he made this mistake :-)

More than anything, Frederick is a really nice guy, and we still exchange email every other year. As history would record, he would go on creating Alone in the Dark, a game that was extraordinarily successful, and then many other very successful games. Alone in the Dark used 3D graphics for characters, a first in the industry. Frederick has said that this use of 3D was a consequence of his earlier work on Alpha Waves.

Aftermath

The rest of the story is, unfortunately, consistent with Infogrames earlier behavior regarding payments. I had every trouble in the world getting them to pay the royalties as scheduled in the contract. For a short while, I considered reusing my game engine for the Smurf-style adventure game. But after several late payment notices, I got fed up of Infogrames and gave up gaming for good. Apparently, Frederick Raynal had similar issues after the success of Alone in the Dark.

This is my personal experience of the early days of the gaming industry, and the very beginning of 3D in videogames. It was wild, it was fun!. Thanks to Alpha Waves and my urge to beat Starglider, I got to meet a few people who are living legends today, and to see the early days of the company that later bough american icon Atari.

If you have any stories about this period, I'd love to hear them. Please leave them in the comments area.
1Update: Well, it turns out I did not know much. Actually, the MS-DOS port of Elite also had flat-shaded graphics, unlike the hidden-line graphics of earlier versions. Like Starglider 2, however, the 3D experience was lacking.

Update: I also discovered that the id Software web site claims that Hovertank was the first 3D game on the PC. Obviously, they are wrong: Alpha Waves predates it by one year, and it offered a better 3D experience.

Je suis jeune, il est vrai ; mais aux âmes bien nées
La valeur n'attend point le nombre des années.

Pierre Corneille, Le Cid

25 comments:

Sarah said...

I remember Alpha Waves on the PC, at the time I had an aged Atari ST and a lot of Microprose games, it totally blew me away.

Funny thing, every so often I find myself humming the intro tune from the PC version... in fact hunting around google for it is what brought me here :)

SafeTinspector said...

I played this game on the PC in the US as "Continuum", and it was distributed hereabouts by "Data East", a Japanese software company.
I absolutely loved the music, which really put the Ad-Lib FM synth chip to work. Could you talk about the music a little?
This game was so great, but I can't play it now.. I run Linux, don't have an Ad-Lib card, and run far too quickly.

Great memories though.
I sence your game's presence in more contemporary fare like Kula World, but I'll always have a soft spot for your program.

ramzahn said...

I encountered this game on the Amiga. It was a very enjoyable ride. The audio was superior to the PC-version.

About one thing i wonder though:
Wasn't there a PC-Version where the speaker would play actual 'alpha-wave' frequencies? I always thought that was the original intention of the game.

Could you please illuminate?

Christophe de Dinechin said...

Sarah, SafeTinspector, ramzahn,


Thanks for the comments. All three of you commented about the music. It's true that I should have talked about it, sorry for forgetting that. The truth is that this is the part of the game where I had the smallest impact.

The music was composed by a guy named Frederic Mentzen. I was simply asked if I liked the music, which I did, so they added it to the PC version of the game. The Atari version did not have enough cycles to play it during the game, so instead, we had a sampled version that played during the intro.

I don't know what happened with Frederic Mentzen. Google tells me that a guy with the same name played for a short while in a group called "Le Voyage de Noz" in France, that might be the same person or not (See http://nozmail1.free.fr/historique.html). I cannot tell that I recognize any face on the picture on that page...

What I an tell is that, like the three of you, I occasionally hum the tune of Alpha Waves. I also have an old Phillips cassette with the tune. I think it would be a service to the community to convert that to MP3. We'll see if I get a pack of rabid lawyers on my back for doing that ;-) I think it is all the more precious in that it is not the music of the game itself, if I recall correctly, but the original composition on synthesizer.

Stay tuned ;-)

Anonymous said...

hi grenouille,

any chances to get the dos port c sourc code of the game?

will you ever release an pure linux or windows version of the game?

ciao llm

Christophe de Dinechin said...

Well, at one point, I started a Linux port. You can find it there: http://alpha-waves.sourceforge.net, and you can browse the source code here: http://alpha-waves.cvs.sourceforge.net/viewvc/alpha-waves. It's not finished, and probably never will be, because I now think it should be done in OpenGL / GLUT.

Anonymous said...

and the "original" dos source code?

im interested in doing an SDL based "vanilla" port

Christophe de Dinechin said...

The original assembly source code is at http://cc3d.free.fr/cube.s. The DOS port is owned by Infogrames, so you'd have to ask them.

Anonymous said...

I had an original DOS copy of Alpha Waves and I absolutely loved it.

Christophe de Dinechin said...

If you want to hear the original music and sounds, there's now a YouTube video.

Anonymous said...

This is one of those few games (and music) I have an emotional attachment to from when I was a kid. Probably the most frustrating yet addicting game I ever played ! I ran it again about a year ago but still could never come close to beating it all

Peter said...

I too came across this article looking for Continuum / Alpha Waves music files to play on a OPL2/OPL3 emulator (just AdPlug in WinAmp), searching for "Frederic Mentzen". I also hum the theme song from time-to-time, and I liked the music so much, that about a decade ago, I plugged the output of the soundcard into a tape recorder and recorded a tape of Continuum music! I look forward to viewing the YouTube video. Thank you so much for coding this game! I love bouncing around the rooms, and have always found the experience so magical, from when I originally played it on a 286 (still was super smooth!) with Hercules to later, enjoying the VGA graphics on more modern equipment. Interestingly enough, it was the PC Speaker beeps and boops version of the song I originally fell in love with, and when I finally heard the AdLib version, I was blown away!

P*ter Funk said...

This is Peter of the previous comment. I have just recorded some of the Continuum / Alpha Waves music to DRO files using DOSBox. Now we can easily listen to the great music again! Just play them in WinAmp using the AdPlug plugin. More info and the files at my blog:

http://onosendaicyberspace7.blogspot.com

Peter

Glutn Free Brooklyn said...

Great stuff from you, man. Ive read your stuff before and youre just too awesome. I love what youve got here, love what youre saying and the way you say it. You make it entertaining and you still manage to keep it smart. I cant wait to read more from you. This is really a great blog.

Pomax said...

Out of curiosity, have you ever heard of Processing/Processing.js? This would be a great game to port using its opengl/webgl capabilities =)

Online Shopping said...

It’s simply awesome to visit it. The content in the blog is highly interesting and entertaining to read out. Keep up the good work!!!

Online Shopping

Wholesale Gold Jewellery said...

This is for the very first time, I am visiting the webpage and I felt overjoyed after reading it out. I really thank you for making me feel so delighted after reading it out.
Wholesale Gold Jewelry

Owen said...

I loved Continuum and got pretty good at it, but I never got close to finishing the game. It was too easy to hit the save button just as I was falling off an important pad rather than the "reload" button. Also as I upgraded my computer the countdown clock started moving ridiculously fast. (Oh and the enemies were too tough :))

I would love to play it again, preferably with the option of a god-mode so I could just fly around and finally see *all* the rooms.

Christophe de Dinechin said...

Hi Owen,

If you have any programming skills, there's a reconstruction of the game that I started years ago on SourceForge, it's here: http://alpha-waves.sourceforge.net/. I don't remember exactly in what state it is, I think the basics work but half of the enemies are not functional.

Regards
Christophe

ggn said...

Hello,

Late to the party I know, but I tried assembling the source on Devpac just to see if I could make it run on machines like the Atari TT or Falcon and saw that the source relies on some external source files (ST\SYSMACRO.S, \PROJET.CUB\SNDTBL.S and ST\FILL.S). Any chance you could upload these somewhere too, or should I extract them from the prg?

(in any case I should extract all the binary files INCBINed from the prg, just thought it'd be nice to have the code at its original state)

Christophe de Dinechin said...

@ggn

Wow! If you succeed, that will be something. I no longer have a DEVPAC or anything like it. Regarding the other files, I'm afraid I lost them. More precisely, they are on a floppy disk or a hard disk in my attic that I no longer can read. I'll see if I can figure out something.

Thank you for your interest

Christophe de Dinechin said...

Hi ggn,


Good news: I found the rest of the source code. Here it is: http://cc3d.free.fr/Alpha-Waves.zip.


Let me know if you manage to rebuild everything.
Christophe

ggn said...

Hi Christophe,

I'm not sure if you got my e-mail, but I got the source - thanks! I already assembled it and have it running on my TT (only the polyfiller needs fixing from what I can see).

We've been trying to find the soundtrack (we even bought an original disk from ebay for that purpose) but it's not there (on side B), plus people I've talked to can't remember hearing any soundtrack. Is it possible that you have that somewhere? Or maybe the ST/E version didn't have any soundtrack at all?

Regards,
ggn

Nicolás Casaballe said...

Hi. Someone uploaded the intro/select music to youtube:

https://www.youtube.com/watch?v=MHh3MktBqq4

I used to have a SoundBlaster, but now I'm curious to know how it spund in a AdLib.

John Dudley said...
This comment has been removed by a blog administrator.