Genesis

Duke Nukem 3D is not one codebase but two :

• Build engine: Providing rendition, network, filesystem and caching services.
• Game Module: Using Build's services in order to generate a gaming experience.

Why such a division? Because back in 1993, when development started, very few people had the skills and dedication to produce a good 3D engine. When 3D Realms decided to write a game that would challenge Doom, they had to find the technology that would power it. That is where Ken Silverman enters the picture.

According to his well-documented website and interview, Ken Silverman (18 years old at the time) wrote a 3D engine at home and sent a demo for evaluation to 3D Realms. They found his skills promising and worked out a deal:



Silverman would write a new engine for 3D Realms but he would keep the source code. He would only deliver a binary static library (Engine.OBJ) with an Engine.h header file. The 3D Realms team on their side would take care of developing the Game module (Game.OBJ) and would also release the final executable DUKE3D.EXE.

Unfortunately both part of the game were not open sourced simultaneously:

• The Engine module source code was released by Ken Silverman on June 20, 2000 .
• The Game module source code was released by 3D Realms on April 1, 2003.

As a result the full source code was available 7 years after the game was released.

Trivia : The name of the engine "Build" was chosen by Ken Silverman when creating the directory for the new engine: He used a thesaurus to search for a synonyms of "Construction".

First contact

Since the original code released rotted a long time ago (It was targeted to Watcom C/C++ compiler and DOS systems) I tried to find something like Chocolate doom: A port that accurately reproduces the experience of Duke Nukem 3D as it was played in the 90s and would flawlessly compile on modern systems.

It turned out the Duke Nukem open source community is not very active anymore: Most ports have rotted again, some have MacOS 9 PowerPC targets and the only one still maintained (EDuke32) has evolved too far from the original code. I ended up working with xDuke even though it did not compile on Linux or Mac OS X (which ruled out XCode: An outstanding IDE when it comes to reading code and profiling).

xDuke's Visual Studio Solution is fidele to the original workflow. It features two projects: Engine and Game: The "Engine" project compiles to a static library (Engine.lib) and the "Game" project (featuring the main method) links against it in order to generate a duke3D.exe.

Upon opening VS, the engine source felt unwelcoming with difficult filenames (a.c, cache1d.c). Opening those files reveals something hostile to the eyes and the mind. An example among many others from Engine.c (line 693):

 
 
  if ((globalorientation&0x10) > 0) globalx1 = -globalx1, globaly1 = -globaly1, globalxpanning = -globalxpanning;
  if ((globalorientation&0x20) > 0) globalx2 = -globalx2, globaly2 = -globaly2, globalypanning = -globalypanning;
  globalx1 <<= globalxshift; globaly1 <<= globalxshift;
  globalx2 <<= globalyshift;  globaly2 <<= globalyshift;
  globalxpanning <<= globalxshift; globalypanning <<= globalyshift;
  globalxpanning += (((long)sec->ceilingxpanning)<<24);
  globalypanning += (((long)sec->ceilingypanning)<<24);
  globaly1 = (-globalx1-globaly1)*halfxdimen;
  globalx2 = (globalx2-globaly2)*halfxdimen;
 
 
 

Note : xDuke port uses SDL but the cross-platform API advantage is lost to WIN32 timers (QueryPerformanceFrequency). It seems the SDL Timer used to be too innacurate in order to emulate DOS 120Hz tick rate.

Building

After setting up SDL and DirectX header/lib location the code will build in one click: That is very pleasant. The only last part is to get a DUKE3D.GRP asset file and the game runs....well kinda :/.... SDL seems to have some palette issues with Vista/Windows 7:



Running in Windowed Mode (or better, use Windows 8) seems to fix the issue:

Immersion

Now the game is running. Within the first seconds Build shines with, in order:

• Sloped floors.
• Realistic environments.
• Free fall.
• Feeling of true 3D.

The last point is probably what struck players the most in 1996. The level of immersion experienced was unprecedented. Even when the technology reached its limit because of 2D maps, Todd Replogle and Allen Blum implemented "sector effectors" allowing to teleport the player and improve the feeling of evolving in a three dimensional world. This feature is used in the legendary "L.A Meltdown" map:

When the player jumps in the ventilation shaft:

A sector effectors triggers and teleports the player at a totally different location on the map just before "landing" :

Trivia : Ever since, 3D engines have tried to improve immersion with better graphics. Things may take a new direction with the release of the Virtual Reality device "The Oculus Rift".

Great games age nicely and Duke Nukem is no exception: Twenty years later the game is still incredibly fun to play. Except now we can start digging in the source!

Engine Library Overview

The engine code is in one file of 8503 lines with 10 master functions (Engine.c) and two auxiliary files:

• cache1.c: Contains the virtual filesystem (sic) and the cache system routines.
• a.c: A C reverse-engineered implementation of what used to be highly optimized x86 assembly. It works but is a monstruous pain in the ass to read :( !

Three translation units and few functions makes the high level architecture hard to comprehend. Unfortunately this is not the only difficulties a reader will face.

As full page is dedicated to the engine: Build Engine Internals.

Game Module Overview

The game module is built completely on top of the Engine module, the way an operating system's system calls are used by a process: Anything the game does is done thought Build (drawing, loading assets, filesystem, caching system, ...). The only exception is the sounds/music system which Game completely owns.

Since I was mostly interested in the engine I did not read it in depth. But it shows more experience and organization: 15 files divide the source into clear modules. It even features a types.h (precursor of stdint.h) in order to improve portability.

A few interesting things :

• game.c is a beast featuring 11,026 lines of code.
• menu.c" features a 3000 lines "switch case".
• Most methods have "void" parameters and return "void". Everything goes via global variables.
• Methods naming does not use camelCase or NAMESPACE prefix.
• Features a neat parser/lexer even though token values are passed via decimal values instead of #define.

Overall this part code is easy to read and understand.

Source code legacy

Looking at the innumerable ports that spawned Doom/Quake, I was always puzzled to see so few ports of Duke Nukem 3D. The same question arose when the engine was ported to OpenGL only when Ken Silverman decided to do it himself.

Now that I have looked at the code I can risk an explanation in a dedicated page: The legacy of Duke Nukem 3D source code.

Chocolate Duke Nukem 3D

Admiring the engine and loving the game so much, I could not let things this way: I started Chocolate Duke Nukem 3D, a port of the Vanilla source code with two goals in mind:

• Education: Easy to read/understand and very portable.
• Fidelity: The gaming experience should be similar to what ran in 1996 on our 486s.

I hope this inntiative will help the code to find a new legacy. The key modifications are described in Chocolate Duke Nukem 3D page.

Recommended readings

None. Go rock climbing: It is awesome !

Add a comment

Name		Homepage
E-mail (Will not appear online)
Comment

Comments (50)

#1 - Justin Meiners - 02/15/2013 - 00:19

Awesome Thank You!

#2 - Gustavo - 02/15/2013 - 00:44

Check out archive.org for the forum: http://web.archive.org/web/20080222020457/http://www.jonof.id.au/forum

#3 - Lucas - 02/15/2013 - 00:49

Unless I'm mistaken, JonoF's forum is backed up in the web archive here: http://web.archive.org/web/20120619233705/http://www.jonof.id.au/forum

#4 - Jan Zwiener - 02/15/2013 - 02:03

Another very interesting article, thank you Fabien!

#5 - Ben. - 02/15/2013 - 03:08

Thanks for this. I really appreciate people having a closer look on something and sharing their insights.

It's a pitty that they could not just refurbish the graphics, add some new maps and release a new Duke. What they released was a "let's get things done" game and called it "Duke Nukem Forever".

Maybe there will be a "Duke Nukem Community Edition" with all the cool gameplay...

Thanks for your work!

#6 - Pierre Riteau - 02/15/2013 - 04:07

Direct link to Ken's posts on the forum: http://web.archive.org/web/20120318021908/http://www.jonof.id.au/forum/index.php?action=profile;u=12;sa=showPosts

#7 - allanaes - 02/15/2013 - 05:18

"...SDL seems to have some palette issues with Vista/Windows 7..."
same problem when running Starcraft or Diablo II, the easiest solution is to kill explorer.exe before run the game (use taskmanager or create a batch command :)

#8 - Jan Michalowsky - 02/15/2013 - 05:23

Thanks for the very good review

#9 - Pedantic Panda - 02/15/2013 - 05:25

"Slopped floors" sounds like an interesting technical challenge... I assume you mean sloped.

#10 - niyaro - 02/15/2013 - 07:52

That's gonna be awesome read, thank you! Coinsidently just couple days ago I've downloaded duke3d atomic edition and finished first episode :)

May I ask you to write an in depth article on how you actually *read* code? Where do you start, how much notes you make, maybe you document the code you read, and so on. In my experience, reading code is an essential skill for any programmer, but there seem to be absolutely no resources explaining how to do it properly. I've tried reading quake3 code (three times) and tried reading eAthena code (open-source server engine for MMORPG Ragnarok Online) but after couple days I've got lost in detailes and in the end had no clue about how thing works. You are on the other hand extremely skilful at the task and your insights are very valuable for an open community.

#11 - Matt - 02/15/2013 - 07:54

These reviews are very interesting and well done. thanks.

#12 - Gustavo De Micheli - 02/15/2013 - 09:27

Great reading as always Fabien. Why would Silverman put all code in one monolith file?
I laugh about your note about variables/files with numbers, I totally agree with you. I always remaind my coworkers of that (after some year developing seriously and reading books like Clean Code made ponder the value of good names).

So, what's the next step? do you have any engine you want to review next?
It's a shame that any of the Unreal games doesn't release their source codes.

#13 - Ohcmonakismet - 02/15/2013 - 10:03

Can you please not use JavaScript for images?

I can't read the article via Instapaper app, and the page is otherwise unreadable on mobile (and I don't have time to read at my desk)

#14 - Luc Trudeau - 02/15/2013 - 10:40

Wow, what a great review! Very educational.

I've always wondered, what software do you use to make your diagrams?

#15 - Hugo - 02/15/2013 - 10:42

Very nice work Hail to the King Baby !

#16 - Arthur Langereis - 02/15/2013 - 11:37

Your Mac OS X binary uses @rpath relative paths (such as @rpath/SDL.framework/Versions/A/SDL) that do not resolve to the frameworks inside the App Bundle (at least for me, OS X 10.8.3pre). I'm assuming you have SDL in another Library/Frameworks dir somewhere, but for people who don't it will not work right now, use otool to change the install name in the bin to use @executable_path/../Frameworks/SDL.framework/… for both.

Excellent post btw, nice deep analysis of the source and render mechanics. I remember looking at ENGINE.C when it was first released and indeed did not feel encouraged to continue investigating :) But I respect that he got a post-DOOM engine working smoothly on such feeble hardware. It took some sacrifices, especially then. Compilers now can turn a ton of types, lambdas and whatnot into a tight loop but back then you really had to write high-level assembly to get stuff fast. Props to Ken and you!

#17 - Daniel Platz - 02/15/2013 - 12:21

Hi Fabien,
As always a great read!
Once I saw it over at HackerNews while at work, I knew I had to make a short day :-)
One thing: Could you elaborate on why using cross products makes a difference to using a dot product if you have fixed-point/integer math?
Also, two small typos in the related source code snippet:
* If I am not color-blind, the one vector is blue and not green. ;-)
* The return-statement should compare against the 2D zero-vector not a scalar, right?

Cheers,
Daniel

#18 - John O'Grady - 02/15/2013 - 13:07

A Valentines day well spent. Very interesting read about a game I loved.

#19 - Ken Causey - 02/15/2013 - 13:54

s/fidele/faithful/ (I think)

#20 - Will Lam - 02/15/2013 - 18:11

So many awesome memories of this game - really appreciate your code review as it allows to to try to appreciate the game in a different way.

#21 - Allen - 02/16/2013 - 06:33

Hi, thanks for the interesting read. But one thing struck me as *very* annoying on reading - your blog loads graphics only when the user scrolls to the part where they are embedded. So upon scrolling it takes 1-2s before I can see the actual image and have to stare at a white space instead. Please think about removing that 'feature'. Thank you!

#22 - Hugh O'Brien - 02/16/2013 - 16:20

Seems the Internet Archive has you covered for those lost forum posts;

http://web.archive.org/web/*/http://www.jonof.id.au/forum/

#23 - Woody - 02/17/2013 - 05:54

Super interesting. Thank you very much!

But why the hell would you use quicktime videos... :D

#24 - Steve - 02/17/2013 - 12:20

cannot read the videos
Chrome give me an alrt that is due to a plugin named : quick time

use html video tag or flash for video other solution are lame !

#25 - Javier Villa - 02/18/2013 - 16:46

I really enjoy these reviews, glad to see Duke Nukem starring here, after all the awesome Dooms and Quakes it makes the coverage of the clasic FPSs pretty comprehensive.

Thanks!

#26 - David Bundgaard - 02/19/2013 - 04:19

Hello Fabien,

I wonder what tools you use to make your diagrams.


I appreciate to read your comments and notes on different games, its very nice of you to take the time and read and share it with all of us.


Have a good life


//David

#27 - Kam - 02/19/2013 - 11:50

Is there any chance you could alter this page so that it doesn't require Javascript to load the images, please?

Thanks.

#28 - Stephen - 02/19/2013 - 13:22

Great read about those legacy gaming engines.

I also enjoyed, very much, your article's page presentation.
Nicely done and pleasant to view.
I had no problem viewing any of the images or QT videos.

#29 - Arkitekt - 02/19/2013 - 13:44

Sweet. Uber good work sir.

#30 - Dexter - 02/19/2013 - 14:21

Awesome reading, thank you for your great review!

#31 - Evan B - 02/19/2013 - 15:09

I wonder if archive.org has it in the wayback machine?

#32 - Jonathan Bayer - 02/19/2013 - 16:32

Thanks for a great article. I tried installing the Mac binary, but it requires OSX 10.7, I have 10.6.8 (snow leopard)

#33 - pleegwat - 02/19/2013 - 16:33

You remark that functions are very badly commented, but you don't mention an obvious reason: Terminal size.

Depending on the editor, you have at most 24 lines of 80 columns on a VGA screen. The inside function you mention is 20 lines long - pretty close to that limit. The desire to keep logic sections within the size of the screen is much more important than comments for other people years down the line to enjoy.


Also, regarding globals: While I'm not sure about 486 specifically (I'm too young), a global array of a primitive type (1, 2, or 4 bytes per element) is very fast to access. I believe the address of the element could be calculated as part of the memory fetch instruction.
An array of structs, whether as a global or on the stack, would probably require 2 instructions to calculate the memory address, and a third for the actual fetch.
Aditionally, the size of the stack would have been tightly constrained.

#34 - Tym - 02/19/2013 - 17:40

If you liked duke nukem 3d, check out Shadow Warrior... Lo Wang come for you, snake coward! Loved that game, it was also developed on top of the 'Build' engine

#35 - Taamalus - 02/19/2013 - 17:41

This was a great read.
Any plans to mention the active Source Port EDuke32?
http://www.eduke32.com/
OpenGL is very much improved, there is now true Room over Room capabilties and much more.
The team has an very active forum
http://forums.duke4.net/
Best
Taamalus

#36 - Mark - 02/19/2013 - 18:22

I don't agree that it's hard to understand, but I also used to write 3D renderers back in those days so it makes sense to me.

* Putting as much code into a single file as possible was a good way to help the primitive compilers do some optimisations & inlining
* Arrays of scalars instead of structs are simply much faster to iterate through given limited CPU caches
* The example math method is straightforward bitmask operations on the sign bits
* Ahh, hand-coded assembly. I'll admit it takes the right kind of masochist to read it :)
* Nothing magic about those numbers! Just bitmasks.
* IDEs have no excuse to be slow these days. DJGPP etc handled huge files just fine back then!

I think you mean 120Hz, not 120 ticks per frame (that would be far too much IRQ overhead). But the PIT native frequency was 1193180Hz. You set a divisor value from 0-65535 which determines the frequency of IRQ0. You can't get 120Hz exactly (more like 120.002Hz) so it's unusual to quantize rendering / physics to this as you get graphics "tearing". What did they use this timer for?

#37 - Adam Baxter - 02/19/2013 - 19:32

http://web.archive.org/web/20120509103449/http://www.jonof.id.au/forum seems to work.

#38 - mbidule - 02/20/2013 - 11:06

Amazing work. I really enjoyed reading it !

Thanks for sharing all this knowledge.

#39 - kd - 02/20/2013 - 11:39

quicktime lol. why not just embed a youtube video. i havent seen a quicktime video for like 10 years

#40 - Ivo - 02/20/2013 - 12:41

I am guessing the binary was complied for 64 bit windows?

I get C:\Duke3D\ChocolateDuke3D.exe is not a valid Win32 application when tying to start.

When a get a bit more time I will try and get this complied locally, both on Win XP and Linux(Raspberry Pi)

#41 - Enze - 02/21/2013 - 06:52

#22, #23:
The Videos are in the folder fd.fabiensanglard.net/duke3d/movies/
the 3 *.m4v-files
VLC plays them just fine

#42 - Edgar Acosta - 02/21/2013 - 10:29

I want to learn how to program VideoGames, how can i start?. i am a software engineer but with experience in embedded and client server systems, data bases. How can i move to Video Games>? also i don't have experience in computer graphics...How to start? any Suggestion? what books do i have to read?.

#43 - Daniel "MontyOnTheRun" Monteiro - 02/21/2013 - 11:53

I really enjoy your articles! Keep on going!

Maybe, if you're running out of code bases to review, you should turn to Aleph One. Its kind of "Chocolate Marathon" ( http://en.wikipedia.org/wiki/Marathon_2:_Durandal ).

Its surprising that most of my pet game engines of the past have similar algorithms (in fact, the "current sector" tracking is exactly the same) to Build.

Greetings from Rio ;-)

#44 - Daniel "MontyOnTheRun" Monteiro - 02/22/2013 - 22:15

One more comment (possibly worth asking Ken) is:

"The renderer does not rely on recursive function (the way Doom did when walking the BSP). Instead a stack and a loop is used (for sector flooding)" (from your raw notes)

There is no recursion based on machine stack, but rather on software stack. Maybe this is because (if my memory serves me well) Ken prototyped the engine in QuickBASIC and (from my faded memory again) it didn't have recursion until 4.0;

Or perhaps not...maybe was stack size thing from those old dark (and very fun) days?

QuickBasic was a fine "IDE" for some quick hacking. I grew making lousy 3D games in it myself. My biggest inspiration at the time was Ken, but I wasn't aware he used the very same tool I was;

#45 - Tigrou - 02/27/2013 - 12:01

Hi Fabien,

Very interesting review as usual. I already took a look at code some years ago and discover most inner workings but some things remains mysterious, your review cleared them out.

I expected to see an explanation on how mirrors works (why they require an additional empty room with special texture). Still unclear to me.

One interesting trivia : the way updatesector() works caused some well know glitch/cheat during the game, that was used a lot in multiplayer (warp glitch) : if you make player run very fast in a place were sectors are very small (eg : stairs), updatesector get lost and start scanning all sectors. If there is two (or more) overlapping sectors where player is, game sometimes choose the wrong sector (depending their order), and it will teleport player there.
see video : http://www.youtube.com/watch?v=VUOhZIdCSiI

#46 - Fei Yuan - 03/03/2013 - 07:43

This might sound stupid, but after downloading the mac osx release of Chocolate Duke Nukem 3D, where do I place my DUKE3D.GRP file???

#47 - fabien sanglard - 03/03/2013 - 17:07

In the same directory as the Bundle :P !

#48 - Bruce - 03/14/2013 - 18:07

Very interesting to see what's behind this engine.
Ken was a true whiz kid - imagine a threesome, hopefully limited to engine concerns, between Carmack, Abrash and Silverman in the 90ies... the arch software rasterizer could have been born ^^

Thanks for your excellent review and bringing the code to life in classic fashion!

#49 - Fei Yuan - 03/22/2013 - 12:22

Why is there no support for Duke Nukem 3D v1.4?

I want to play the Atomic Edition but I can't patch to 1.5, please make Chocolate Duke Nukem 3D work for v1.4!

#50 - FistMarine - 03/23/2013 - 03:31

When I try to start a game by selecting any episode, the game crashes/freezes. Any solutions?
Note that the intro demos work fine.

 

@2013