Dungeon Keeper: Remake

Link to the Github.

Description

Dungeon Keeper: Remake was my graduation project, the goal for me was to recreate the game as best as I could by myself. Since the original game isn't open source a lot of the behaviour has been guessed by playing the original game and inspecting how certain things react and behave.

Another important goal for me was to read in the original files, this makes it so it requires the original game to run (prevents me from distributing copyrighted assets) and I wanted to the build to only exist out of a single .exe, no DLL's or other files next to it, so that using my version of the game was as simple as dropping the .exe in the game folder.

The Challenges

Video Playback

I started out with every step you'd see when running the game, so when you launch it you'd see a splash screen, then the intro video, a loading screen and finally the main menu. So in order to really get that feel when you start the game I started of with recreating this.

The splash screen was quite easy, it's simply a texture that shows full-screen for a few seconds, The step after this however was the first challenge, I had never worked with video before (well.. other than in Unity), though I do know about video codecs and video encoding it wasn't much help with the actual implementation.
The video files that Dungeon Keeper uses are Smacker Video files, this is a proprietary format by RAD Game Tools (same as BINK), There's a single page describing how the format can be decoded but it's not official and I also couldn't spend a week trying to write a video&audio decoder from scratch.

So I ended up looking for video libraries that could decode Smacker files, I ended up trying LibAV but other than a very very basic h264 player there's no documentation on how to set up anything else (and well the docs are lacking as well), in the end I couldn't get the smacker codec to initialize no matter what I tried, others worked which means I wasn't doing something terribly wrong but well.. I ended up abandoning libAV.
I looked around and saw Libsmacker which was a very simple library consisting out a few C and .h files. I got it working very quickly but the library failed to properly decode the video file as it showed artifacts a few seconds in (at the first pallette swap) meaning it was incorrectly handling Smacker video, or at the least this specific file.

See left: Libsmacker (artifacted), right: proper version.

Eventually I discovered that ScummVM could play back Smacker video and that it was open-source, so with half a day of work I managed to separate the video module from it as it was quite tangled into the main engine code with lots of abstractions as well.

UI

Next up was another temporary full screen texture for the loading screen and the main menu, I wrote a simple UI button for this, but it turned out a bit more complex than I thought it would be as the buttons weren't a single texture or sprite but existed out of multiple parts, each of em animated and with different states.
After that was all done I ended up with a near exact copy of the original game's main menu (some buttons are slightly off the real position) but its very close!

The level select screen was simply background texture and a overlaid front texture, they're of different sizes and their movement speeds are carefully tweaked to give a parallax effect whilst not showing their edges. The flag is another UI button placed at the part of the world the level will play.

Game Rendering

While I was researching on how Dungeon Keeper was put together I noticed the actual levels were very voxel-like. Each tile exists out of 3x3x8 cubes, and the entire level consists out of 85 by 85 tiles.

So the first challenge was writing a voxel renderer which luckily due to the scale of a level and the nature of the ingame view didn't need to be super-optimized. I never measured the time it took to construct the whole voxel mesh, but the entire game tick runs in less than 1 ms with my i7 6700k, that includes all the creatures and their behaviour as well.

Fog of War

Whilst on the topic of rendering, once the creatures were in and behaving properly I needed to have them actually discover tiles as well, as the player doesnt start of with the entire map visible. I thought of several ways to do this including the generic "Fog of War" approach but I imagined this wouldn't feel like the original implementation as one can see ingame that the entire tile is covered by a blackness on a (sub)tile basis.

So in the end I added a boolean to each tile indicating whether it was visible or not, if it wasn't it would render a full black tile, otherwise it'd render the real tile.

Checking for visibility is done by keeping track of neighbouring tiles, once a tile is dug out, the tiles surrounding that (if they're not visible) would get added to a list, once a creature is in range of that tile they would raycast towards it, if it hits that tile it would be marked visible and the invisible tiles surrounding that one would get added, this prevents me from having to check a big amount of tiles each time and only the tiles that actually have a chance of being seen would be checked.

A quick debug version of the visibility checking can be seen below:

Creature Behaviour

For the creatures I wrote a task system that allows them to ask for tasks, depending on the availability this might either succeed or fail (in which case they will ask for a different one). Though the system is seperated into two parts, one for the imps, which are "Tasks" and one for the other creatures which are "Activities", This is due to how the creatures act. Tasks need to be kept track of and be made available again once an imp can't focus on it anymore (due to combat, being picked up or death). Activities are spontanious things that are only relevant to the creature itself, they don't need to be kept track of and can be freely forgotten about. Both systems are used similarly though.

There's lots more that went on during this project, like parsing and running level scripts, the reverse engineering of a lot of files, playing sounds, or how the actual level is built, textured and updated, and much more, but I don't want this page to result in several dozens of megabytes so if you're curious to know more, feel free to ask me or look at the source code which can be found by using the github link at the top of this page.