Thursday 31 January 2008

7 Day Roguelike Challenge dates are set

Temple of the Roguelike has the details.

Who's thinking about entering this year? I've got a little caught up with the new job, so I'm not so sure at this stage. I'm trying to organise a little extra publicity, and will be running some relevant polls closer to the date, as well as cheering from the sidelines and providing support if I don't end up competing.

I'm open to suggestions about articles to write to help would be developers out as well.

Results for 'Which character generation method do you prefer?'; new poll

This poll may have been a little over the top in terms of choices. 75 of you took the time to answer though. The only real conclusion I can draw from the answers is people prefer to make less complicated choices to more complicated ones.

The results were:

Character completely anonymous
9 (12%)
Pre-generated amnesiac e.g. Planescape: Torment
6 (8%)
Pre-generated archetype e.g. Half-Life
6 (8%)
Pre-generated character e.g. Metal Gear Solid
7 (9%)
Choose from several pre-generated characters
5 (6%)
Choose name
33 (44%)
Choose appearance
29 (38%)
Choose background or plot arcs
19 (25%)
Randomly generate background or plot arcs e.g. Traveller
22 (29%)
Choose career, class and/or race at start
31 (41%)
Choose skills, abilities and/or powers at start
22 (29%)
Spend money on equipment at start
17 (22%)
Choose which skills/career to advance
25 (33%)
Don't make choices at the start; but have decision points early in the game
19 (25%)
Don't make choices at the start; but have decision points later in the game
15 (20%)
No explicit stats
9 (12%)
No stat variation
9 (12%)
Pre-generated stats
4 (5%)
Point assigned stats
24 (32%)
Random stats
16 (21%)
Answer questions to decide stats
12 (16%)
Generate one main character + group with pre-generated characters
11 (14%)
Generate multiple characters to form a group
11 (14%)
Other
4 (5%)

The next poll is one of my semi-regular 'Tell me what you think of my writing' type polls. The links to the articles are accessible below the poll.

Wednesday 30 January 2008

Temple of the Bamlike

Temple of the Roguelike, who in a previous statement of brotherly love referred to Ascii Dreams as 'our sister site', has changed it's name. This follows revelations on gamesquarter and publicised by TIGSource that there is a roguelike that pre-dates Rogue: Beneath Apple Manor.

While I applaud Slash's integrity in making this decision, I feel that he's premature in assigning Beneath Apple Manor primacy in inspiring the genre of games we develop.

Henceforth, Ascii Dreams will be renamed Blocky Dreams, and will be found at ponglikedeveloper.blogspot.com. Blocky Dreams will be centred on discussion of the ponglike genre, and the critical relevance of ponglikes to the games community at large.

In other news, development of JADE, Thomas Biskup's follow-up to ADOM has begun. You can read his development blog for further details.

Monday 28 January 2008

The Death of the Level Designer: Procedural Content Generation in Games (Part Six)

(You'll want to read parts one, two , three, four and five first)

The human brain has a powerful set of tools for detecting and matching useful patterns in otherwise chaotic data. This set of tools can be conditioned to override normal behaviour patterns in the presence of sufficiently powerful and randomly provided incentives: so-called operant conditioning. You will have probably seen the term 'Skinner box' associated with certain types of game-play: in particular with MMORPGs and slot machines, where people become addicted to randomly provided rewards for repetitive activity.

But the same set of pattern matching tools are useful for the designer of procedural content generation systems. The semi-randomised output of PCG systems will be picked over by the player's brain, and the underlying systems hopefully understood and enjoyed. This reinforcement of play through randomisation is hopefully a more 'nutritious' game environment that simply statistical delivery of reward and one I would expect Johnathan Blow to commend rather than criticise.

The greatest challenge of procedural content generation will be to augment or replace human intelligence in the creation of meaningful narratives in computer games. But even in a single player game, there is a powerful creative intelligence involved in the decision process, and that is the player themselves. A procedural content generation system may be able to leverage this human intelligence in creating meaning and narrative: in part through relying in part on serendipity, happenstance and superstition. In juxtaposing two disparate game elements, the human mind will attempt to find a meaningful relationship between them, and provided that the game does not mix every game element into a brown stochastic blend, the player will build up a narrative of moderate complexity from very simple components. Such a narrative may be no more complicated than 'first I did this, then I did this, and then I did this', but it will have meaning.

It is possible to go too far in procedural content generation techniques: too far being when no two games have any elements in common. This may still be an interesting game - Minesweeper being a good example - but a less interesting movie. Even Minesweeper has a beginning, a middle, some tough choices where a guess might be required, and an end. Most games will have more complex choices that could be formed into a player-centric narrative. Angband for instance encourages the player to stay within a certain distance of the surface until certain resistances are acquired - encountering monsters deeper in the dungeon without these resistances would likely result in game over. A more sophisticated example of these player-centric narratives is the 'Day in the Life' posts that many games encourage - these can either be mundane or dramatic retelling of in-game events from the perspective of the player controlled avatar.

These player-centric narratives, while interesting, are probably not what you envisioned when you hear 'procedural content generation of narrative'. And while the emergent narratives of Dwarf Fortress are a sophisticated example of what is possible with a sufficiently deep game system, as mentioned, not every game developer has the time, resources and fortune to develop this type of game.

What would an explicit, as opposed to emergent, PCG narrative system look like? One way of implementing this is little more than a sophisticated puzzle generation system - essentially a string of escalating Fed Ex quests, and randomly selected Blankety Blank sentences. This is still developer expensive, and at the same time not particularly rewarding for the player, as the systems underlying the puzzle generation is no more sophisticated than the statistical generation of reward probabilities in Skinner Boxes.

By increasing the complexity of the systems underlying the puzzle generation, there is a greater sense of involvement from the player, who must decode these underlying systems in order to maximise their rewards from successful puzzle solving (or questing, or whatever game equivalent process is). And the easiest way to increase this complexity is to have a behind the scenes meta-game, that the player has no direct involvement in.

Consider the plight of an individual person living in the world of a game of Civilisation IV. They may be pivotal to the outcome of a single battle, if they are in the position of being a spy, or help advance the civilisation, if they are a Great Person. Each civilisation is run by a leader, whose particular traits inspire the civilisation to work better in certain areas. But no individual (except the 'hand of God' player who is playing the civilisation behind the scenes) is responsible for the actual decisions taken from turn to turn, how the civilisation advances and how the game of Civilisation IV is played.

Now, replace all the human players playing a game of Civilisation IV with computer players. And instead put the human players in the roles of individuals living in the game world. Civilisation IV has suddenly become the meta-game. Individuals will perceive the actions of the AIs controlling the game only through their indirect effects: cities will be built, technologies gained, enemies routed and civilisations fall. But no player in the game will directly be able to control these effects - their influence will instead be felt only as warriors or spies, or great people or perhaps civilisation leaders.

The actions of the AIs in controlling the meta-game should appear to the individuals in the game to be a consistent narrative. An AI's decision to amass armies on the border to invade a neighbour will have profound in-game consequences. Whether the invasion is successful or not could be decided by one individual: a spy whose vital information enables the encirclement of enemy forces, a leader who can inspire his troops to break through the enclosure, a peasant who correctly shoed the horse of a general so he wasn't thrown from it's back. But the fact that the attack occurred, and the consequences of it, should form a consistent narrative from the player's point of view because it follows a consistent set of meta-game rules, which the player may be able to decode over the course of the game. With sufficient understanding of these rules, the player may be able to predict which side to take, when to rally his troops, when to flee the scene.

And Civilisation and other 4X games are well understood problems, with sophisticated AI, that can provide a narrative backdrop to a lower level game involving player control at an individual or a squad level. There are already examples of blended RTS/FPS games such as Natural Selection and Savage: The Battle for Newerth that have proven successful using this kind of idea. The weakness of these games, and the reason that the Valve elected not to have a commander class in Team Fortress 2, is that the success of the game depends heavily on the competence of the battlefield commander player. Replacing the battlefield commander with an AI levels the playing field in this regard.

And hopefully makes the story behind the play.

Further Reading:

The articles and links sections on the Procedural Content Generation wiki.
Proceduralism: The follow up article series.

Interzone rejection

I've just received a thoughtful rejection from Interzone for the short story I submitted to them in November. I made it down to the final 30 out of 404 stories (apparently adding up to some 1931100 words). The feedback was great - basically keep writing and try submitting it elsewhere, which is always nice to hear, but ran to 10 paragraphs, which I think is a good sign. I just want to say publicly thanks to Jetse de Vries to take the time out to provide such great feedback to an aspiring writer (as well as critically reading through nearly two million words in less than two months).

I've picked Strange Horizons next, over the Magazine of Fantasy & Science Fiction, simply because they have an electronic submission process. They also have stricter word limits, so I cut the story down to 8,024 words. Given that Paul J. McAuley's "Gene Wars" covers much of the same territory in a much smaller word count, I don't think I'm being too aggressive in the cuts.

Friday 25 January 2008

I, for one, welcome our Metafilter overlords

A big hi to everyone coming from Metafilter. While you're stopping by, feel free to have a cup of tea, answer the poll, read a few articles, maybe download a game.

(Oh, and John - finish typing up that interview).

Thursday 24 January 2008

Seven Day Roguelike 2008: Call For Dates

Jeff Lait has just issued the call for dates for the 4th annual 7 Day Roguelike Challenge. This involves deciding which of three weeks the 7DRL challenge will be run on. See the announcement post for the suggested dates and reply to indicate your availability.

For more details on the history of Seven Day Roguelikes, check the article on 7 day roguelikes on RogueBasin. You can also read my brief teaser reviews of 6 of the best from previous challenges.

The seven day roguelike challenge is a great programming exercise to test your ability to design and code with the best. For anyone out there who thinks they have what it takes on the game design front, you're more than welcome to enter. You have 168 hours...

(The medal above is from the 2006 7DRL challenge and was issued to the people who completed the challenge. The 7DRL 2006 Contest Medal was designed by Paula Agudelo.)

Wednesday 23 January 2008

Results for 'Choose a class'; new poll

As I mentioned previously, I conceded defeat on this poll. 222 of you decided just to vote for it instead. The results were:

Soldier
32 (14%)
Spy
28 (12%)
Scientist
24 (10%)
Tinker
30 (13%)
Tailor
12 (5%)
Sailor
17 (7%)
Beggar
21 (9%)
Wizard
42 (18%)
Thief
36 (16%)
Mesmerist
18 (8%)
Paraphysicist
18 (8%)
Politician
13 (5%)
Roboticist
30 (13%)
Press ? for help
54 (24%)
Other
14 (6%)

I haven't had much in the way of response as to why you chose the class you did. Feel free to provide feedback in the comments.

The next poll: 'Which character generation method do you prefer?'. I think I'll have to provide concrete examples for this one to help explain what I mean by each choice.

Hopefully I've accommodated everything around character generation.

Sunday 20 January 2008

The kiwi bird hits you -more-

I've previously mentioned a Finnish roguelike connection and wondered on the origins of it. But there is also a strong connection between roguelikes and New Zealand, which predates the obvious Lord of the Rings link. There's this discussion of a surf beach in the North Island, and how it relates to a randomly generated Angband artifact. There's the dreaded kiwi bird in POWDER. The maintainers of two separate variants are from NZ (Myself and Antoine).

Then there's Caverns of Underkeep (warning: link crashes Firefox 3 Beta 2), which is a Java-based roguelike I discovered via the Indie Games weblog. Joshua Smyth runs his own development blog but is also in Auckland Game Works, which is how I figured out the New Zealand connection.

Saturday 19 January 2008

John Harris on Angband

Ah, the @ Play column everyone has been requesting.

I've been outclassed

Okay you guys - you've won. Through mass voting for a poll question 'Choose a class' you've driven me to concede. I mean, it's threatening to become the most popular poll ever.

My original plan was to explain how the question 'Choose a class' at the start of the game essentially is meaningless to a player, and that by asking it, you're asking them to play a mini-game called 'look at gamefaqs.com and ask around on the forums', which takes place outside of your control as a game-designer. I mean, I've already made it clear I'm no big fan of classes.

To this end, I designed the choose a class poll game, which featured some hidden information about the poll including how to score points. I'll leave that for you to figure out for the rest of the week, if you're still interested. This would have created a set of haves, and have nots, and hopefully some gaming of the poll questions to show that the actual choices you were making were less important than the underlying game rules.

It did get some of you to pick 'tailor' though...

So why did you pick your class choice?

And will you complain if I nerf roboticist?

(A big thanks to everyone who made the effort to play)

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

(You'll want to read parts one, two , three and four first)

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

Depth is similar to what I think Dwarf Fortress does for it's random world generation - 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 combination of height, vegetation, temperature etc result in plains, swamps 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. 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 as the combination of moves grows so quickly, so deep solutions such as having a 'book' of moves are required.

Dwarf Fortress achieves the depth problem probably better than anyone else. But I can't think of anyone coming up with complex solutions for procedural content generation. For instance, 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 the lower level rules in 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, particularly 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'.

Most responses to earlier parts of this article have focused on procedural content generation being equivalent to randomly generating game levels or game worlds. I agree that this is an important area to focus on, and something that we'll see increasingly used in commercial games. But I also would argue that these techniques are mostly 'solved' and are therefore 'uninteresting'. In particular, most games which procedurally generate '3D' maps are really just generating a 2d surface e.g. a height field, and those that are 3d are mostly done through fractal subdivision, which while an interesting field of study, has been used extensively.

The one area that random map generation is missing complex 3d topology generation: and no game is currently doing this. Dwarf Fortress doesn't generate the fortresses for you - it still relies on human intelligence to go through the process of placing tunnels and building bridges and towers. When a game is capable of procedurally generating maps of the complexity of Half-Life 2, S.T.A.L.K.E.R., Minerva or any other modern FPS, then PCG for random map generation will be completely 'solved'.

And the reason that this hasn't been done is that complex 3d topology is a complex problem as opposed to a deep problem. 3d space with gravity is immediately an ordered space, and therefore requires that map connectivity be checked as a part of the generation process. Since connectivity cannot be guaranteed, the map generation may have to throw away randomly generated maps and you immediately move into the bounds of the halting problem - you can no longer prove the PCG algorithm will ever complete, for whichever algorithm you choose. (To clarify: the issue is not proving an individual map is disconnected, it's ensuring that you don't generate an infinite number of disconnected maps in succession).

In addition, complex 3d topology highlights some significant human perceptual issues - particularly the fact that we are biased against looking up. I suspect that any PCG which generates complex 3d topology will have to include an expert system that constrains the types of maps created. Constraints will include techniques to encourage the player to look up in the instance where there is a vertical element in the map, ensuring that gaps in the map that the player has to traverse are jumpable, tunnels are at least the player unit size and so on.

The expert system may act as a 'generator' rather than a 'constrainer' - these are analogous to 'wall-adder' vs. 'passage carvers' in maze generation, in the sense that the 'generator' may add features to the map that are consistent of a set of rules such as lily pads on a lake surface that the player can jump across.

It may well be that it is not ever possible to create a complex 3d topology procedural content generator that is good enough to be acceptable. I believe it will require extensive use of user mediated content techniques to get right, particularly for multi-player maps. Tools such as heat maps, as demonstrated in Valve's Half-Life: Episode 2 and Bungie's Halo 3, are already used for high-level analysis, and could be adapted for analysis with AI techniques such as neural networks and genetic algorithms. Similar AI techniques could potentially analyze every 3d map ever made and try to come up with a rule set of common features. These are not straightforward suggestions.

If we are stuck with hand made 3d maps, this only excludes 2 out of the 7 procedural content generation techniques I outlined previously. Again, S.T.A.L.K.E.R. is a great example of this - particularly in it's use of dynamic AI to ensure that the game-play within the maps keeps randomly changing. Even in Halo, where the AI is completely deterministic (after earlier experiments with random AI behaviour), there is still enough randomness from the player actions to ensure that the AI behaves differently every time encountered.

But I believe the real strength of procedural content generation will be seen in procedural generation of plot and narrative content. I'll discuss this in greater detail in part six.

Friday 18 January 2008

At least two people have realised I'm not (completely) insane...

Casey has a high score of 98, having chosen paraphysicist.

I am trying to make a point or series of points with 'the choose a class poll game'. One of which is that having the high score is not necessarily how to win the game.

All will be revealed when the poll closes. In the mean time, at least make an effort and try to figure out how to play...

The Watery Pachinko Machine of Doom

This strange-sounding object is a six-word summary is part of what I've been trying to suggest with my recent article on procedural content generation. My only problem is someone else came up with the analogy. Have a read of Project Horseshoe's Thoughts on Story, over at Gamasutra.

Thursday 17 January 2008

Press ? for help

Your class determines a number of important factors in the game.

The length of your class name determines your in-game magic factor, which can be used immediately to cast spells or retained as an accumulating psychic multiplier.

The number of letters between the first and last vowel in your class name determines your starting gold, but inversely for your personality factorisation. For the purposes of this rule and rule 7, y is counted as a vowel on odd-numbered days.

Soldiers have a special vulnerability to blue imps that can be countered by multi-classing with politicians.

Picking the other class can boost your initial score early in the game, but is not recommended as a long term strategy.

In a three or more larger player group, the scientist class can accumulate both buffs and de-buffs for a diurnal period.

Here's how help works:

Every day I'll check how many people have voted for 'Press ? for help'. If I see that it's more than 10, I'll provide a help file. But you only get a score of 0 voting for this voting option, so it's not an optimal voting choice - unless you want to help other people playing the game.

DeathClam has the current highscore

DeathClam has a high score of 68, having voted for tailor.

BTW: You can always change your vote, but I'll only accept new high scores for different voting combinations from the same person.

Freedom to Fail

I had mentioned previously that I was planning on writing an article about failure in games. It turns out that most of the article is getting written by other people instead: Only A Game features a great piece on the Freedom to Fail.

At this rate, I'll just end up with one paragraph with a collection of links. Much like the one you're reading.

X-Com remakes

Someone hurry up with a roguelike X-com remake already. X-Com is another one of those roguelike-likes I've been talking about. Random terrain, destructible scenery. It seems custom designed for an ASCII make-over.

In the mean time, you can read about this Quake II based remake featured on Rock, Paper, Shotgun.

TIGSource: The Independent Gaming Source

A fair few gaming sites and blogs now exist for discussing Independent Gaming. I'm sure to do a review of them at some point as how well they relate to Amateur Gaming. Probably the most relevant of the sites that I subscribe to for the rougelike community point of view is TIGSource. At the moment they're featuring a link to an interview by Geek Nights, of Tarn Adams. For those of you who don't know, Tarn is one half of the Dwarf Fortress development team.

This is highly recommended listening.

Sixteen Colors ANSI Art and ASCII Art Archive

Enough people end up at this site searching for ascii art assets that it's worthwhile me putting up a side bar featuring links to sites that actually have ascii art. Sixteen colours is one site that features both Ascii and ANSI art that you may want to look at.

Do you have any other suggestions that I could recommend?

The Amateur: WYSIWYG Game Design

My latest column for GameSetWatch is up featuring WYSIWYG Game Design. It's not as strong as the other columns I've written for them - but still has some interesting ideas that I wanted to explore. It may have some strange relevance for other activities occurring on this site at the moment.

With 54 votes so far

The maximum possible score is 53. No one has successfully registered a score yet, except me.

It's worth pointing out that it's a very stubborn '?' button - it might need a few more people to vote for it press it before it clicks.

Wednesday 16 January 2008

With 5 votes so far

With 5 votes so far, the maximum possible score is 42. Don't forget, you have to correctly register your score in order to have a chance to get the high score.

Choose a class

I'll point out now that you should seriously reflect on the choice you make for the latest poll. This will direct affect your enjoyment of the 'Choose a class' poll game that will be run all week. Once you've voted, you should check back regularly for updates and to assess your final score.

Results for 'What features must a game have to be a roguelike?'; new poll

Of all the polls I've run, this has probably been the most interesting in terms of results. 136 people voted with the following choices.

80x24 screen
6 (4%)
Ascii instead of graphics
32 (23%)
Character advancement
68 (50%)
Character generation system
40 (29%)
Classes or skills
40 (29%)
Fantasy setting
8 (5%)
Hit points
30 (22%)
Keyboard based
44 (32%)
Line of sight
37 (27%)
Lots of enemies
45 (33%)
Lots of items
47 (34%)
Overhead view
53 (38%)
Permadeath
77 (56%)
Randomly generated levels
102 (75%)
Shopping
14 (10%)
Single @ to control
41 (30%)
Single dungeon with multiple floors
5 (3%)
Single player
38 (27%)
Turn based combat
77 (56%)
Unknown items / identify system
48 (35%)
Using items in unusual ways
42 (30%)
Other
15 (11%)

Now I don't think any of the above 'must' exist in a game for it to be a roguelike - I'm a big believer in prototype theory. But there's definitive clusters of essential (randomly generated levels), nearly essential (turn based combat, permadeath), and relatively important features that make interesting reading.

Let's focus on the 'character generation system' for the next two polls. Surprisingly, this is not a critical feature for roguelikes.

First the fun question: 'Choose a class'

Mysterious article

John Harris, who writes the excellent @ Play series on roguelikes, also does another of my favourite columns: Game Design Essentials at Gamasutra. The latest Game Design Essentials column is up at the moment - it features 20 'mysterious' games and is replete with discussion about secret rooms in Gauntlet II and the undocumented and unknown mysteries of ADOM.

The thing is - about half the pages of the column are missing - returning a 'page not found', including the front page of the article. While it could just be a web server problem, the fact there are pages mysteriously missing is itself quite a coincidental conundrum. I wonder if the readers of ASCII Dreams can figure it out?

[Edit: Apparently it was just a bug. Shame really.]

Dwarf Fortress isometric graphics

Dwarf Fortress finally has isometric graphics!

In a great mock-up.

Thanks SpriteAttack.

(Thanks also to RockPaperShotgun for the link).

Tuesday 15 January 2008

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

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

It's January 2013. The Christmas games embargo that the Clinton administration put in place to ensure you saw friends and family over the holiday season has been lifted, and you excitedly unwrap the plastic from your lastest purchase: Dream Park 2.0. You've already heard about the great mods created by international players working on behalf of Gamers Now United (Stallman's reorganisation of the former Open Source movement once he finally succumbed to playing World of Warcraft), and you download a pre-recommended pack from your Facebook game reputation system.

The game fires up, and you click through the menus making a few choices and letting the RNG choose the rest. Medieval. Clockpunk instead of magic. Moderate size continent. You see a few of the random choices flash in front of you: the game has generated four civilisations, distinguished by Ionic, Doric, Corithinian and Tuscan architecture, and the first mod kicks in. FastGen reduces the elabourate character generation options down to the choice of three key phrases: you choose Rugged, Handsome and Prankster on a whim, and end up with a boyishly good looking peasant standing at the edge of a mud-hovelled village amidst a crowd of on-lookers.

The king of the Ionic civilisaton (Hrepathous) is visiting the local barony and come down to the village to demonstrate his gift of healing and attend to the villagers' ailments. As you grow bored of the Baron's speeches and begin to look elsewhere, your lover whispers 'the pigsty' in your ear and with a shy smile slips out of your grasp and towards the romantic rendevous. You follow at a short distance, but come up abruptly against the squat figure of her father.

'Where are you going?' he asks threatening. You stammer something and are forced to divert your course to around the back of the building the king sits in.

In the shadows, stand two assassins, in Doric dress, cradling weapons you have never seen before. They've cut a hole in the adobe and are preparing to slip through.

One sees you, and raises his weapon. Just then your lover runs out, between you and your attacker. She is cut down in a hail of projectiles, and your heart beats and time seems to slow.

Do you run or fight? Your decision is made for you, as the screams of the villagers signal that more armed men have appeared in the fields around you. You run.

The hectic pursuit, between huts and over fences, watching your fellow villagers gunned down and slaughtered, comes to a climax. Trapped in a dead end, amidst the rutting pigs where you had intended an altogether different purpose, you are caught by your pursuers. One, cruel looking and with a milky blindness in one eye, and a clockwork hand, steps forward. He raises his mechanical arm and laughs at you. It is the last thing you see.

The You Only Live Once mod kicks in, working in conjunction with the AI plot director. Instead of restarting from an earlier checkpoint, you awaken again, this time as a Corinthian merchant in a larger town. Rumours of war between the civilisations are spreading...

(You'll want to read part five next).

Small signs

For those worried about new warning signs, the search for a nanohazard sign is up to 54 pages long...

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.

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

(You probably want to start with part one of this article).

4. Instancing of in-game entities

Most games hide the enemies faces. This is a natural consequence of the fact that humans naturally look at faces to distinguish individuals, and designing or video capturing a new face for each potential enemy in a game can be a long and exhausting process. Consider a game engine that is automatically capable of generating a large number of faces based on a set number of parameters. This possibility is used to great effect in various MMORPGs such as Eve Online, where it is important to distinguish players from each other. Procedural content generation would be the next logical step - where each enemies face is randomly assembled by picking a random value from the allowed range. You'd end up with good looking and ugly individuals - mostly ugly if the random face selector in Oblivion is indicative of the results.

But this is not just limited to individual faces. The Massive program used by Weta in Lord of the Rings does the same for whole orcs, elves and other races. Again, individuals are selected from a base design template that is then varied from one to the next. When will we see this technology in-game? Well if Project Offset is anything to go by, soon. The first sneak peek video released showed a large number of instanced goblinoids of various shapes and sizes getting shot by a crossbow and turned to ice within real time in the game engine (The fact this video is now no longer available on their site does not bode well for this feature).

Any why stop at goblins? Borderlands has instanced guns - apparently close to 500,000 different types of them, as well as other equipment types. By combining instanced guns and enemies, you ensure a virtually unique stream of opponents for the player to encounter. This can also be used to cut down on the total art assets required for the game. If you have different in-game statistics for small, medium and large individuals, you can increase the number of potential encounter types - much like World of Warcraft does with it's cookie cutter but with different paint mobs.

5. User mediated content

You can go one step further than SpeedTree, and instance all the game vegetation, so you'll never run into the same tree twice. This particular example is useful for two reasons: firstly, it's often used in first year comp sci courses to demonstrate fractals and procedural techniques, but also because Stanford are now offering a user guided procedural content generation system called Dryad to assist people in exploring the possibilities of virtual worlds. Dryad allows you not just to create trees, but it serves as a template for all possible trees, and guides you towards 'high-quality' trees within that space, based on other user choices.

This mechanic is very similar in concept to that used in Spore. Rather than directly exploring the procedural content options by using random selections, both Dryad and Spore provide the same procedural frameworks of a PCG to allow user generated content to be rapidly created without deep technical know how. The face composite selection mentioned earlier that MMORPGs use is a similar mechanic. These rely on the user's perception of beauty or interest to guide procedural selections.

This process is extremely powerful. Google uses the ESP Game to label images for search using this kind of distributed intelligence. The concept of "Games with A Purpose" is the ongoing academic project based on the ideas of Louis Van Ahn, who noticed that games can be a great motivating force for otherwise repetitive and uninteresting activities. The concept of user generated content when combined with PCG allows the created content to be tuned by intelligent feedback, compensating for the main weakness of PCG in that human intelligence is only indirectly in control of what is produced. The players in effect become the censors of what are appropriate and inappropriate choices (The issue of censorship and procedurally generated content vis-a-vis a procedural hot coffee is another great topic - one I've briefly touched on before).

6. Dynamic systems

S.T.A.L.K.E.R.: Shadow of Chernobyl provides the best modern example of the variety that a dynamic AI system can provide in a static game environment. It's A-life system procedurally creates enemies in previously vacated areas, and ensures that no two encounters, even after a reload of a saved game, will ever proceed in quite the same fashion. Oblivion promised a similar revolution with it's Radiant AI system, but the majority of the dynamism was scaled back to prevent a rapid depopulation of Cyrodiil - a problem that suited the atmosphere of S.T.A.L.K.E.R. more than a fantasy world.

To call dynamic AI a procedural content generation system may feel slightly revisionist - but the elements of unpredictability through a range of possible options fit the scope of what procedural content generation delivers. More importantly, it imparts the same benefits and problems. A dynamic AI system allows the developer to cut down on time required to develop step by step AI scripting and allows them to focus more on the high level goals. But at the same time the system must be robust enough to cope with the game-space and handle the same contingencies that plague PCG based systems. A S.T.A.L.K.E.R. developer's diary highlights the issues they experienced tuning the A life system.

Other dynamic systems in game, such as weather and music are also being explored. Brian Eno is producing procedurally generated in-game music for Spore, and other games have used dynamic changes in music based on the player circumstances to great effect. Dynamic weather and a day/night cycle are starting to feature in games, such as Crysis, which again perturb the possible in-game states by providing a significant unpredictability to any encounter.

Facade is an experimental game which provides another dynamic system which is procedurally controlled - that of conversation. The individual snippets of conversation are not procedurally generated, but the ordering and topic transitions are controlled; and human language is flexible and context dependent enough that listeners will often fill in additional meaning to randomly adjacent phrases, particularly when cued by previous attitudes. Facade occurs within a limited space, and an emotionally charged scene, to try to emphasize these cues, and has yet to see a wider adoption of the same processes.

Speech synthesis and natural language generation are nearing levels of sophistication to be used in computer games. Note that natural language comprehension is more difficult - the best that can be delivered at the moment are heavily context dependent deciphering, or as contextual cues. But a game is a controlled enough a domain where both of these techniques may be useful.

7. Procedural puzzles and plot-generation

Many game plots are little more than dependency graphs, which a sequence of actions must be performed in a particular order. At the simplest level, procedural content generation can be used to change the door codes and other individual puzzle elements to prevent a user from getting the information off of a game FAQ website or other source of information. And as Raph Koster points out in a article delicately titled "You Are All Cheaters", the use of these out of game information repositories are game-breaking in that they stop the game being played in the way it was intended. Similarly, puzzles can be extended by making multiple parts of the dependency graph randomly placed (e.g. moving the key that opens the door to a random accessible location).

But procedural generation can do more than just make puzzles harder to solve. It can potentially give an infinite number of ways of solving a puzzle. This is an important point. In one way, failure within a game can be construed as consuming a certain amount of game content (A point I'll discuss in more detail in another article). Procedural generation of content ensures that there is an infinite amount of content to be consumed. In most games, "if at first you don't succeed, you fail", as GlaDoS puts it succinctly. But games like Rogue, which have the harshest penalty for failure - restarting the game - the fact that no two games play the same way makes the real cost for failure virtually zero. If you die in Rogue, you don't have to repeat the identical game elements in the way that you would if you fell off of a platform near the end of a level in Mario, or just before a check point in Halo.

This is even more important for games that have a fixed narrative. Narrative is consumed in a game much the same way as content. Having different multiple endings is a way of extending the narrative so that it is worthwhile playing at least twice. But why have multiple endings? Why not have multiple beginnings? Why not make every single plot point significantly different from game to game? Procedural generation of plots is a way of extending the life-time of a game significantly beyond that of a single play through. [Edit: It sounds like this complexity of plot branching features in Mass Effect, but in a non-procedural manner].

By making plots dynamic, choices will take on real significance. Suddenly no individual (except the player) is indispensable. Conversation trees will take on real meaning, where it is truly possible to offend or impress anyone. The threat of death will hang over any NPC - and the necessity of resetting the game in certain non-failure states will hopefully be lessened (although the negative reviews of Fire Emblem suggest otherwise. Maybe it is a natural human need to not want to lose anything of value you have invested time in). The dynamic AI director in Left4Dead suggests that pacing, another important game element, is amenable to procedural techniques.

In part three, I'll look at what ways I suspect PCG will be used in the future.

A request for Google Reader developers

I've just read the new #xkcd signal-to-noise ratio proposal to sort out their problems with a large community size in IRC.

I have a similar problem with a signal-to-noise ratio in Google Reader (which I highly recommend you should be using to read this blog). Lets have a look at my reader stats:

From your 161 subscriptions, over the last 30 days you read 9,368 items, starred 10 items, shared 0 items, and emailed 0 items.
Ugh. That means I'm reading approximately 300 items per day, of which 0.3 of per day which I find worthwhile enough to keep for later and at a guess 30 of which per day were actually worthwhile reading.

Now, I'd like to label some reader items as noise. The quickest way I can think of doing it is by link inspection. If a reader item has a link in it that points to the same link as another reader item, label one of them as noise - say the newest one. Then hide all noisy items by default (not just list view - hide them completely).

If I star an item, show me a list of all items that were 'noisy' which share common links - under the starred item in the starred item view only.

That should cut down on the massive duplication of posts which seem to cloud the blogsphere. Yes it's great that Darth Vader and Yoda are appearing in Soul Caliber IV. But I only need to know about that once - if I'm really interested, I'll star it.

I'm sure there'll be some tuning required for old reader items - but that'll be a good performance saving. Let's say 7 days is old enough. Or 30. Or some dynamic value based on how many items I end up getting.

Anyone else using an RSS reader with a feature like this?

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

(This article is in six parts: parts one, two , three, four, five and six, along with a follow up article series Proceduralism; and is also available as a PDF)

Procedural content generation is yet to set the game industry on fire. It has featured in one of the greatest games of all time, Diablo and it's successor, who directly trace their roots to roguelike games such as Angband. But the recent implementation of random level generation in Hellgate: London did little to inspire people that this method works well for game level design. But bubbling under the surface of the industry, and very much evident in future games like Spore is a methodology that like most technologies has been underwhelming in the short term but in the long term will have profound consequences for how games are designed.

An announcement late last year should have set the hearts of anyone working in the games industry a tremor. No, it wasn't Activision merging with Vivendi. Gearbox Software previewing use of procedural content generation in Borderlands was met with moderate skepticism, but was generally well received. It enabled me to remind at least one other person of the greatness of the line 'Guns. We need lots of fucking guns.', predating Neo's similar but censored sentence by seven years (The movie in question was Split Second). But more importantly, it points the way forward to a time where the current role of the level designer will be as obsolete as punch cards for programming computer games.

This article will survey the current scope of procedural content generation in order to highlight where PCG is making inroads into the traditional level designer roles, and how various enabling technologies are making procedural content easier to build and deploy within other game technologies. The survey will point in a number of directions, not necessarily positive, that I anticipate procedural content generation taking game play, and conclude with some suggestions what the next five years will bring, and a few options for anyone interested in taking the ideas herein further.

Procedural content generation (PCG) is the programmatic generation of game content using a random or pseudo-random process that results in an unpredictable range of possible game play spaces. I prefer the term procedural content generation to procedural generation: the wikipedia definition of procedural generation includes using dynamic as opposed to precomputed light maps, and procedurally generated textures, which while procedural in scope, do not affect game play in a meaningful way. The concept of randomness is also key: PCG should ensure that from a few parameters, a large number of possible types of content can be generated.

Procedural content generation can exist in games in a number of ways.

1. Runtime random level generation

This is the 'prototypical' example of procedural content generation, which is what most of you would have thought of when you starting reading this article. The classic example is of Rogue's random placement of rooms linked by corridors, which makes the game infinitely replayable and softens the penalty of permadeath. I would suggest that dynamic random level generation in two dimensions is still an interesting area of research: I've written extensively about it elsewhere, but there are still algorithms to be discovered and techniques to be used. The problem is however mostly solved in the sense that there is a robust variety of interesting algorithms from maze generators to room placers to choose from and considerable literature covering the implementation methods.

In contrast, procedural content generation in 3 dimensions is still a relatively undeveloped field. Hellgate: London is an example of how not to do three-dimensional design - the cost of generating sufficiently interesting 3d objects and textures ensures that there is a great deal of repetition in the resulting random levels. It is possible to extend many of the two dimensional concepts into the 3rd dimension: maze generation is mostly extend able depending on which algorithm you choose, and the recent releases of Dwarf Fortress shows that it is possible to extend the classic roguelike design into three dimensions.

Procedural generation of height fields in 3d is the only other area that has had considerable effort devoted to it. Probably the best in-game example is Tribal Trouble which uses a simulation of erosion in order to create a play field resulting an infinite number of multi player maps. There are a large number of fractal-based world generators which use similar techniques to create vast and elaborate world spaces, which to a greater or lesser degree use simulation of geological and meteorological processes to design the map height-fields and populate them with content.

What is missing is any serious attempt to create fully three dimensional world spaces, including bridges, archways, towers and other highly interconnected topologies. This is in a big part due to one of the key constraints of dynamic level generation which is to ensure complete connectivity between all parts of the map. Even in a two dimensional map, this can be a complex problem. In 3d, any game which simulates gravity must ensure that units that fall into lower parts have a way of accessing back to the higher parts unless deliberate disconnections form a part of the game play. In addition, constraints on slope steepness, minimum unit size and so on can complicate level connectedness considerably.

Tribal Trouble side steps these issues somewhat by generating enough maps and checking their connectedness, and then using a statistical proof to show that a sufficiently large percentage of maps will be playable. Other random level generators may use a verification method, which discards and restarts any maps that may prove unsuitable for play. Sufficient tests have to be made for degenerate cases, and fall backs to avoid infinite loops or sufficiently long delays in level generation, which even with a two dimensional maps can be a considerable complication, often due to the computational cost of random number generation. Dwarf Fortress maps, even prior to the introduction of a 3rd dimension, could take 15 minutes or more to run on a modern processor.

2. Design of level content

If the problems of random map generation may seem insoluble, then this does not stop them from being used. What frequently happens is that level content, particularly height fields, is generated in the level design tool, as opposed to the final game engine. The level designer is then responsible for verifying the correctness of the level or modifying it to ensure it is correct. Procedural content generation then becomes a mechanism for minimising the cost of content creation.

Darwinia by Introversion Software is a great example of using procedurally generated levels supplemented with hand editing to leverage a small developer base. The Darwinia levels were original built using a procedural 3d height field generator as it would have been unfeasible to places all the map vertexes manually. Introversion is using the same technique for their next in-development game Subversion: Chris Delay releases frequent development updates on the in house blog that are well worth reading. The Subversion city generator looks robust enough to be used as a dynamic random level generator at this stage but without knowing the final game play it is impossible to be sure.

The MegaTexture technology that John Carmack developed initially for Enemy Territory: Quake Wars lends itself well to importing a procedurally generated bitmap for a map level. The technology itself uses Wikipedean 'procedural generation' to convert this bitmap into a three dimensional playing space, but the original bit map could be created using standard PCG height field algorithms and 2 dimensional PCG techniques.

At a lower level, there are already well accepted techniques for infilling level detail using 'procedural generation' and procedural content generation techniques. Chief amongst these is SpeedTree, a middle ware product that enables level designers not to have to worry about the placement of every in-game tree and shrub. SpeedTree is used in Oblivion to great effect from what was originally a piece of software developed to enhance computer game golf courses.

Similar techniques can be used to automate the placement of textures and decals so level designers don't have to worry about texture alignment and can instead focus on higher level design elements. This is in addition to procedural textures, which are again an example of 'procedural generation' that may incorporate random noise to lessen visible artefacts.

3. Dynamic world generation

This is one of the earliest procedural content generation techniques, where the in-game map exceeds the ability of the computer to store it either in memory or on-disk (depending on performance requirements). While storage has grown massively since the days of Elite, it is still not unlimited and the same techniques can be put to great use, for instance, displaying all the objects in an typical size asteroid belt or planetary ring.

The technique is to use a seed number (42 is a popular choice) which remains constant, and then grow the playing field iteratively using this seed number permutated by pseudo-random number techniques. Usually growth is from a top-down subdivision, which lends itself well to fractal generation techniques, as well as matching typical level of detail (LOD) implementations. The map is never held in memory except as a temporary structure to display, and is discarded as soon as components of it are no longer required: nothing procedurally generated is ever written back out to disk.

The best example of this in development is Infinity: The Quest for Earth. I can only urge you to watch this video (wait for the second half if you are impatient) and then read the developer's blog, in order to see the power of this technique.

It does have significant drawbacks. In particular, certain structures, typically long thing ones like roads and rivers are very hard or completely impossible to implement this way because of the subdivision technique (roads are merely hard, rivers impossible because of the dependency of having to know the height of an adjacent subdivision in order to compute the river path). And currently the process is very CPU intensive, with increasing levels of detail usually depending on a high O-notation algorithm of some kind.

Changing the algorithm will also change all of the map, as the map structures themselves are highly dependent on the algorithm and therefore the software cannot be upgraded easily without resetting the game. The procedural content generated must be verified as consistent as a part of the run-time implementation: which limits what checks can be made to ensure that the content makes sense and therefore requires robust generation procedures. Finally, any change to the map must be stored as a delta. Reloading map deltas will ultimately overwhelm the strengths of the technique, so the majority of implementations will prevent, minimise or ignore any player or designer made changes to the map structure.

What instead happens is that the map lends itself well to exploration: essentially you are moving through a set of possibility spaces. The game designer is as much in the thrall of the procedural content generation algorithm as the players. He can manipulate the algorithm to try to generate different types of spaces - but the whole world depends on the algorithm, and therefore he may equally destroy something else that has been created. In fact one DOS-based game has made this exploration a central element of the game: features discovered and named by the players become a part of each further release.

I hope you've enjoyed reading this far. More to come in part two.

Further Reading:

The articles and links sections on the Procedural Content Generation wiki.