Monday, 14 January 2008

The Death of the Level Designer: Procedural Content Generation in Games - Part Three

You'll want to read parts one and two first)

Every so often, someone rediscovers procedural content generation and for a moment sees it as the solution to their game development worries. The latest last crisis was in the increasing cost in delivering triple A games on console platforms, and procedural generation was going to magic this cost away by making content free. Googling for 'procedural content generation' is like looking through a slightly forlorn graveyard - it's sunny and the textured head stones look beautiful in the evening light, but ultimately it's not as full an after-life as you anticipated.

Why has PCG failed to deliver on the promised hype?

Firstly, procedural content generation algorithms are hard. Not hard as in you need to get a smarter programmer. Hard as in the travelling salesman ate my NP-complete halting state hard.

You are no longer looking at simple test cases in resolving issues with PCG. The problem domain becomes a complex web of interacting cases, so that you instead need to start coding automated players to explore it. And these automated players, because they are powered with less than human intelligence are good at finding crashes and infinite loops, but less than perfect at spotting anomalous events, such as water running up hill. And there are never any guarantees in this exploration that you cover the whole problem domain, because this domain is infinite in size. You are left evaluating statistically whether you have enough coverage before releasing the game.

Consider that dynamic AI is a sub-set of PCG, and the promises of AI are consistently five years away on delivering, if not longer. But dynamic AI is starting to become an acceptable part of game development, and even if crippled, starting to feature more in major game titles such as Oblivion.

But I have suggested in parts one and two that the pieces are falling into place, albeit slowly. Even random plot generation, although handled poorly in S.T.A.L.K.E.R. (see GearHead for a good example) is moving in the right direction. Outside of dynamic world generation, I don't believe anything I have shown you is a compelling argument for procedural content generation - as compared to the majority modern game titles. I'm not surprised if you disagree with my assessment that the level designer is under any kind of threat. But you're wrong.

Let me suggest where procedural content generation will move in the next five years and under what guises.

1. Traditional level design tools will adopt more and more procedural content generation functions. You will be able to paint a section of landscape and farm buildings, a village or town will pop up into existence. Similarly, more game engines will support dynamic lighting and weather, requiring less pre-rendering components.

2. Triple A titles will incorporate more PCG elements in controlled conditions (as will MMORPGs). You'll find much greater use of instancing to enhance visual appeal. Games that feature a central PCG mechanic will do much better in the marketplace - whereas Hellgate: London mostly missed the mark, Left4Dead and Borderlands will be more successful.

3. Spore will be released, possibly delayed again, and be a resounding success - cannibalizing the game playing audience much as World of Warcraft has done for PC games, but on a multi-platform basis. This will put EA 3-5 years ahead of the market, with only Sony, with LittleBigPlanet, being able to compete (Will Wright is arguably one of the world's best game designers, and he has ninjas working for him). As a result, a round of inferior Spore knock-offs will appear the following year and put back the cause of PCG by a year or two (Much like the current round of MMORPG cancellations).

4. PCG will continue to eat away at the bottom end, with various independent developers coming up with better game designs using these techniques. This will have the perverse effect of making independent development harder as the best indie games take the audience away from both other indies and 2nd tier developers.

5. At some point middle ware developers will get on board with PCG. This is already happening with dynamic AI, but I'd expect to see it with 3d level design systems and more generic 'game-in-a-box' systems. What timing this occurs around depends on whether they're able to achieve it ahead of or behind the Spore release fallout.

It's this last point that I want to expand on and suggest some ways of moving the state-of-the-art forward for procedural content generation. You may wish to stop reading at this point unless you're passionate about procedural content generation, or a venture capitalist.

Firstly, I think there's a great place in the market at the moment for a fast-moving company to deliver 3d arena like first person shooter levels using a subscription model. Call it Map of the Day or similar (that particular URL is cyber squatted, but it's the point I'm trying to make).

Users sign up for a subscription based on their favourite shooter and get a single player map every day generated by the company's random map generator. It's important that it's a single player map - multi-player maps would be a lot harder to balance and are re-usable, whereas no-one is catering well for single-player episodic gaming on a frequent enough a basis. It's not critical to start with that the map designs are exceptional - good enough is fine. Obviously you want to DRM lock the content if possible, but it's not strictly necessary. Maybe partner with Valve to deliver through Steam, although you're potentially competing with them at the same time.

Secondly is the 'game-in-a-box' middle ware model. This is targeted for companies looking to take their media intellectual property and turn it into a game, without having to pay either huge development costs or leave consumers with a badly designed game. The game in the box takes the minimum character and art assets required and uses PCG techniques to turn those elements into an entire game at a fraction of the cost of normal game development. While the game itself does not have to have PCG elements, for extensive re playability you may as well include them.

The consumers benefit because they get a well-designed game as opposed to the licensed rubbish that is often churned out at the moment. The 'game-in-a-box' company also becomes a well known brand in it's own right, so purchases would also be made on strength of the franchise in addition to the media property. The media company at least gets the moral satisfaction of having licensed a well-produced product, as opposed to having to bury it in a land-fill in the New Mexico desert.

An unlikely prospect? Well, as you've probably guessed, one company is already doing it. Chunsoft's Fushigi no Dungeon (Mysterious Dungeon) is heavily indebted to the procedural content generation techniques pioneered by Rogue, and has produced Mysterious Dungeon games under license for Pokemon, Dragon Quest and Mobile Suit Gundam as well as their own series of independently produced games.

A match made in procedural heaven. Oh, and there's a part four.


Nick said...

So triple AAA - isn't that AAAAAAAAA ?

Andrew Doull said...

Hahaha - fixed but it looks wrong now.

Mikolaj said...

You've really impressed me here. When you start hiring, count me in.

JohnH said...

I don't think procedural content need be so hard to implement, but to take developers who don't know anything but traditional game development and asking them to do something like this may not always work well.

I suggest that the key to developing a procedural content generator is to start simple and add in features. Start out with basic terrain, get that working. Then add in water levels and rivers. Then settlements. Then monster generation tables and locations. work on making each step able to function using arbitrary input.

Dwarf Fortress contains what is probably the most advanced world builder in the world right now. While it's closed-source, perhaps a budding young designer could glean some ideas from its semi-visible terrain creation process....

Andrew Doull said...

JohnH: There's two kinds of hard - I'll call them depth and complexity.

Depth is similar to what I think Dwarf Fortress does - it requires that you come up with e.g. a list of every possible type of mineral, multiple 'layers' of level generation such as height, moisture, temperature and combine these all. The building blocks however are relatively simple - some kind of fractal subdivision, working out which combinations of height, vegetation, temperature etc result in plains, savanah and so on.

Complexity includes problems however that there is no possible solution for, or the solution cost rapidly increases out of bounds. Things like the Travelling Salesman problem, placing rooms and corridors in some kind of ordering, etc. I think placing rivers falls in this scheme - you have to keep trying and abort if the river doesn't reach the sea in most naive implementation of rivers for instance.

To compare the two, most naive AI routines are complex rather than deep. For instance, in chess, it is complex to check for every possible move, so deep solutions such as having a 'book' of moves are required.

Dwarf Fortress achieves the depth problem probably better than anyone else. I don't see a huge amount of people coming up with complex solutions for procedural content generation. In AI, the 'complex' solutions are always 5 years away, as I mentioned, but they seem to be getting closer, and AI becoming a little smarter.

Listening to Tarn Adams' recent interview with Geek Nights, he's anticipating that plot like game behaviour will emerge from Dwarf Fortress. I suspect this will, because he has enough depth in the game to support it. But I also suspect that very few other people, particuarly commercial developers are going to want to spend the time coming up with as deep games. (S.T.A.L.K.E.R. is on the outer edges of 'deep' game behaviour, and it took six years to develop). So the 'short cut' is to come up with a procedural content generation system for game plots / game narrative to try to get replayability to another 'level'.

I'm probably going to write this up and expand on it in a part 5.

RSpalding said...

Looking back at this article 3+ years on, it's mostly relevant... but reading #3 made me cringe.

Andrew Doull said...

Yeah. Spore.

Ironic how Dark Spore was the one of the few games to pick up with the AI director model that Left4Dead pioneered.