Introversion

[Chris]

Regular readers might remember the solid geometry stuff I was experimenting with in Part 4, trying to write a procedural generator for Office blocks. A big part of the problem I kept running into was that I was trying to solve two very difficult problems simultaneously – firstly designing a data structure that can effectively represent an office block without resorting to full 3d editing (which would make everything ten times harder), and secondly trying to write an algorithm to generate offices that fit into this data structure intelligently. How can you generate a building when you don’t have a working data format for buildings in general? The answer is you can’t (because each problem requires the other to be solved first), you just end up going around in circles, and it took me a while to figure that out.

So I spent a little while working only on the building data structures, and in the end knocked up a simple map editor for testing basic room and building layouts.

After playing around with some really simple wall layouts for a few days, it dawned on me that I could make a fairly major progress leap by importing some map data from somewhere else (for testing purposes of course - not as the actual game levels!). All of the test offices that I’d built in my simple editor were extremely basic, because I’m not going to waste time building complex maps when the format is changing all the time. But there are hundreds of games out there with similar map data structures, and thousands of levels that have been made before, sometimes in incredible detail. So I had a little think and came up with the obvious answer – Doom maps.

Doom maps come in WAD files, and they’re a pleasure to work with. After printing the unofficial doom map specs I wrote the tool you see above to import any level from episode 1 of Doom, and it took no more than three hours from start to finish. Despite being essentially two dimensional, some of the maps in Doom really are quite intricate, and obviously way more interesting to look at (and work with) than the test square rooms I’d been using previously. There’s also something really exciting about hacking through someone else’s data file and importing their data – generally you have a mess of nonsense on screen for a while, then you make some crucial fix – some intuitive leap about the data’s inner workings, and suddenly you’re looking at an incredible 3d model that some level designer has spent hours working on.

With my doom map importer finished and working, I then made the final connection by re-exporting the doom map in my own map file format, and then loaded that result up in Subversion’s simple map editor. Doom maps don’t really work in the same was as Subversion maps (our maps don't support arbitrary floor and ceiling heights yet), but if you look closely (and you know Doom reasonably well) you should be able to recognise the map from the game.

Part of the problem I have now is that the frame rate is extremely low with this many walls – I’m rendering every wall semi-transparently, which is a double whammy in terms of performance because it means every wall has to be depth sorted and then rendered in back to front order every frame, and it means I can’t use display lists to optimise things because the rendering order changes depending on the camera position. This problem only became apparent after loading the fairly complex doom maps into the editor, but I was aware it would bite us eventually. John Carmack faced a very similar problem over a decade ago, and his solution was to invent an entirely new way of rendering based around Binary Space Partition trees (bsp trees) – an incredibly intuitive leap that is still in common use in todays modern games.

Last edited by Chris on Sat Apr 14, 2007 1:10 pm; edited 1 time in total

[shinygerbil]

A Doom remake, hmm? *finds red herring picture*

Seriously, this is really fascinating to follow, and I love that you're doing this rather than keeping absolutely everything behind locked doors. I still can't wait to see where this is all going!

EDIT: Oh, and 'First Post', or something. ;P

[Rkiver]

Congratulations on cracking the map issues and generation Chris. Look forward to see what will be coming in the future, and where this will end up fitting into the overall scheme.

[Cooper42]

What with the pinkies in the Darwinia development - it's clear IV are producing a zombie from hell-mars taking over a major cities central business zones, in the form of RPG/RTS...

[elDiablo]

Sounds (and looks) good! Really am very interested to see what this game is about, and now you have Doom levels being imported?! Nice! Heh.

[xander]

*xander's head asplode.

I am looking forward to using hacking tools and cute AIs to launch thermonuclear weapons in order to destroy hell zombies from Mars in a modern corporate environment.

Also, would now be a terribly bad time for me to admit that I have never played Doom? I was a Mac person back in the day, as I still am. We had Marathon. While I know what Doom is, and I have seen screenshots, and even have some idea what it is about, I have never played the game.

xander

[Xocrates]

xander wrote:

I am looking forward to using hacking tools and cute AIs to launch thermonuclear weapons in order to destroy hell zombies from Mars in a modern corporate environment.

Me too

Even if that isn't Subversion, it would be an awesome game.

xander wrote:

Also, would now be a terribly bad time for me to admit that I have never played Doom?

No Dooms, no Duke Nukem 3D, no half life's, no Halos, no...

Err... I did play UT

[shinygerbil]

Having never played Halo is a good thing. ;P

[BrianBlessed]

I played Halo once; no amount of showers made me feel clean after that.

[xander]

Xocrates wrote:

xander wrote: Also, would now be a terribly bad time for me to admit that I have never played Doom? No Dooms, no Duke Nukem 3D, no half life's, no Halos, no... Err... I did play UT

I have never played any of the Doom games, or Duke Nukem, or Wolfenstein, or Half-Life. I refuse to play Halo -- it was announced at a MacWorld Expo, a year or so before Bungie was bought out by MS. The game should have been released first for the Mac, but it took almost two years. Instead, I still play Bungie's greatest game ever, Marathon. I also have never played UT, though I did play Counter Strike once. I sucked. A lot.

xander

[shinygerbil]

xander wrote:

...though I did play Counter Strike once. It sucked. A lot. xander

Fix'd.

Unreal Tournament still is one of the finest games I've ever played; it has such sheer energy, it's truly a joy to play.

(i've gotta stop fixin' posts. but dammit, it's addictive!)

[Leonaken]

Again, I like what I'm looking at, but if only I knew what I was looking at. Lay out a clue, you tease!

[koorb]

I don't see why you would be having performance issues. But when that happens it is almost always because you are doing something that you can avoid doing, either by not doing it, wasting some other resource like memory tackling the problem, optimising or by cheating.

[Leonaken]

koorb wrote:

I don't see why you would be having performance issues. But when that happens it is almost always because you are doing something that you can avoid doing, either by not doing it, wasting some other resource like memory tackling the problem, optimising or by cheating.

ORLY

[NeoThermic]

koorb wrote:

I don't see why you would be having performance issues. But when that happens it is almost always because you are doing something that you can avoid doing, either by not doing it, wasting some other resource like memory tackling the problem, optimising or by cheating.

*Sigh*. Ok, each wall is semi-transparent. This involves depth sorting. This involves physically altering the scene. This makes it impossible to use static storage types like display lists. This means Chris must either use immediate mode, or implement some form of BSP trees.

(Actually it arises because one can move about the scene. If you can keep the observer static, you can get away with a pre-computed depth buffer and thus use a static storage type, but alas if you want your work to actually be goddamn useful, you can't have the observer static!)

So in this case, he can either avoid making the walls semi-transparent, but that ruins the style, you can't burn memory faking it as that's fucking expensive in terms of bus talk, you can't cheat the effect and finally, the optimisation of what he needs to do is to re-implement the data in a way that allows the kind of effects done to it.

If any of the above isn't correct, then you're more than welcome to slap me for not paying attention in lectures

NeoThermic