It's all in your head, Part 5

The only place you'll ever hear the truth
User avatar
Chris
Introversion Staff
Introversion Staff
Posts: 1172
Joined: Sat Nov 25, 2000 7:28 pm
Location: Cambridge, UK
Contact:

It's all in your head, Part 5

Postby Chris » Sat Apr 14, 2007 1:47 pm

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.

Image

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.

Image

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.

Image

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.

Image

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 2:10 pm, edited 1 time in total.
User avatar
shinygerbil
level5
level5
Posts: 4667
Joined: Wed Dec 22, 2004 10:14 pm
Location: Out, finding my own food. Also, doing the shinyBonsai Manoeuvre(tm)
Contact:

Postby shinygerbil » Sat Apr 14, 2007 2:06 pm

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
Here is my signature. Make of it what you will.
Image
Rkiver
level5
level5
Posts: 6405
Joined: Tue Oct 01, 2002 10:39 am
Location: Dublin, Ireland

Postby Rkiver » Sat Apr 14, 2007 2:13 pm

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.
Uplink help: Read the FAQ
User avatar
Cooper42
level4
level4
Posts: 810
Joined: Tue Mar 13, 2007 3:04 pm

Postby Cooper42 » Sat Apr 14, 2007 2:41 pm

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...
Whoever you vote for, the government wins.
elDiablo
level5
level5
Posts: 3111
Joined: Thu Mar 14, 2002 12:23 pm
Location: London, UK

Postby elDiablo » Sat Apr 14, 2007 2:41 pm

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.
We dont stop playing cos we get old... We get old cos we stop playing.
User avatar
xander
level5
level5
Posts: 16869
Joined: Thu Oct 21, 2004 11:41 pm
Location: Highland, CA, USA
Contact:

Postby xander » Sat Apr 14, 2007 3:50 pm

*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
User avatar
Xocrates
level5
level5
Posts: 5262
Joined: Wed Dec 13, 2006 11:34 pm

Postby Xocrates » Sat Apr 14, 2007 4:16 pm

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 :D

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
User avatar
shinygerbil
level5
level5
Posts: 4667
Joined: Wed Dec 22, 2004 10:14 pm
Location: Out, finding my own food. Also, doing the shinyBonsai Manoeuvre(tm)
Contact:

Postby shinygerbil » Sat Apr 14, 2007 4:32 pm

Having never played Halo is a good thing. ;P
Here is my signature. Make of it what you will.

Image
User avatar
BrianBlessed
level4
level4
Posts: 867
Joined: Sat Dec 24, 2005 9:33 pm

Postby BrianBlessed » Sat Apr 14, 2007 5:08 pm

I played Halo once; no amount of showers made me feel clean after that.
User avatar
xander
level5
level5
Posts: 16869
Joined: Thu Oct 21, 2004 11:41 pm
Location: Highland, CA, USA
Contact:

Postby xander » Sat Apr 14, 2007 5:48 pm

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
User avatar
shinygerbil
level5
level5
Posts: 4667
Joined: Wed Dec 22, 2004 10:14 pm
Location: Out, finding my own food. Also, doing the shinyBonsai Manoeuvre(tm)
Contact:

Postby shinygerbil » Sat Apr 14, 2007 6:13 pm

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

xander


Fix'd. :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!)
User avatar
Leonaken
level3
level3
Posts: 285
Joined: Thu Mar 23, 2006 7:36 am
Location: Palo Alto, CA, USA

Postby Leonaken » Sat Apr 14, 2007 6:23 pm

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
level1
level1
Posts: 16
Joined: Fri Jan 21, 2005 9:03 pm
Location: Leicester
Contact:

Postby koorb » Sat Apr 14, 2007 6:27 pm

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.
User avatar
Leonaken
level3
level3
Posts: 285
Joined: Thu Mar 23, 2006 7:36 am
Location: Palo Alto, CA, USA

Postby Leonaken » Sat Apr 14, 2007 8:14 pm

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
User avatar
NeoThermic
Introversion Staff
Introversion Staff
Posts: 6254
Joined: Sat Mar 02, 2002 10:55 am
Location: ::1
Contact:

Postby NeoThermic » Sun Apr 15, 2007 12:06 am

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 :P

NeoThermic

Return to “Introversion Blog”

Who is online

Users browsing this forum: No registered users and 3 guests