Update 7/6/2012 - Quests!
So we've gotten a lot of questions about it, so we thought we'd re-print this old blog entry that explains how our procedural quest system works. Hopefully it helps people decide who are half-and-half about pledging (or pledging higher).
It's exciting because it involves Kevin Bacon! :-O
The project team have the distinct honor of listing actor Kevin Bacon in the ‘Special Thanks’ portion of our credits, but I doubt he has any idea that he’s in there. The fact is, he’s had a very large – albeit unknown – influence on the game’s development.
The game is Malevolence: The Sword of Ahkranox, which I have been
project lead on for over two years now, and its engine is quite
different to most games due to the fact that the entire game world is
procedurally generated, infinite and also persistent.
Being infinite AND persistent, the team’s main challenge was to keep the game interesting so long as the player kept playing (not an easy task). We, of course, took the path of procedural item/weapon creation, even going so far as to make the game procedurally generate the graphics for the weapons, to ensure plenty of new gear to find. That, however, can only last for so long, and procedurally generated countryside, dungeons and towns can only entertain a player for so long before they all start to look the same. So we put our heads together and came up with a solution. We all agreed that would couldn’t keep the players interested infinitely, but we can take steps to ensure they get maximum enjoyment and re-playability out of the game while they do play it.
What we came up with in the end was the quest and dialog system, and the way they interacted. Both were to be procedurally generated and intricate enough to ensure long-time interest from the player. But how does Kevin Bacon get involved with this? The answer lies in his namesake header file:
Some readers will be familiar with the Six Degrees of Kevin Bacon
game back in 1994. The basic concept was that you could take the name
of anyone involved in the Hollywood film industry, whether they be an
A-List actor or an isolated gaffer somewhere on an obscure film, and
within no more than 6 steps, be able to link them to Kevin Bacon. For
example, one of the voice cast in my game Malevolence, Karen Kahler, was
in the short film “The Magician” with actress Jackie Zane, who was in
the film “Burning Palms” with actor Nick Stahl who acted in the movie
“My One and Only” with Kevin bacon. Thus, her “Bacon Index” is 3 (and
through Karen, mine is 4!). Make sense?
Well, it’s that system (or a modification of it) which the NPCs in Malevolence work with.
Let’s say that the player enters a town and talks to an NPC. The game determines that this NPC will have a quest for them, and so the game spreads its feelers out and works out what is relatively close to the town, and how far away each location is. Since the game world is generated procedurally, it does this process dynamically:
First the game procedurally generates the quest. The engine first
selects what type of quest to generate and settles on an item centric
quest. It then generates an item, and an incident and comes up with a
backpack which was lost. Once this is done, the NPC tells the player
that they need help recovering their backpack from a dungeon that they
were exploring. Only the catch is, they fled the dungeon so quickly that
they don’t remember where it was.
While this is happening, the engine consults the memory map shown above and looks at the area around the town for a few kilometers, then chooses a dungeon that is close enough to not be too far away, and far enough away that the player will have to search for it. However, once it has found a dungeon, it doesn’t let the player know where it is like most games. It is now the player’s mission to search for it.
Now that you know that there is a dungeon out there somewhere with a backpack in it, you can ask around to get more info. The engine, however, is processing the dungeon’s “Kevin Bacon Index” in the background. The main difference, however, is that not everyone knows everyone else perfectly well, so if one person gives you information, they may not be 100% sure about the information. So when you get a map of people like this:
You can see the percentages between them all. That shows the familiarity of the characters between them. So, if you speak to NPC ‘A’ and ask them about nearby dungeons, they will tell you that they have no idea about that sort of thing, but their friends Steve and Kyle might. If you speak to Steve, he may refer you to Kyle or pass you on to Bob the Blacksmith, who he’s fairly sure knows a mapmaker and a woodsman, who would probably have a better idea about dungeons in the area. When you speak to Bob the Blacksmith, he’ll tell you about Keith the Woodsman, who is familiar with the local wilderness, but will more likely put you on to Kevin the Mapmaker, who knows Keith the Woodsman quite well and may be able to help you himself (with his maps). These NPCs may all be in the same town, or they may be spread between multiple towns. It’s all generated by the procedural engine, but it’s how the player FOLLOWS the path that defines how well the quest will work out.
If a player is clever and good at deduction, they may have an easy time of it – for example, if they followed the path ABDEF, while it may not be the most direct route to Keith, they will get some accurate maps out of it, and maybe even a new weapon to help clear out the dungeon to find the backpack. But if they don’t follow good advice, they may have a far less fortuitous way. And keep in mind that due to the lack of familiarity between certain NPCs, sometimes the player will get false information in their searching, which can slow them down quite a bit.
However, not all quests in the game will work like this. The quests are divided into two quest types. There are the multi-tiered quests, as mentioned above, and “b*tch quests” which are your standard “there’s a dungeon, clean it out” or “there are rats in my basement, kill them”. On top of that, even when a player is assigned a multi-tiered quest, sometimes they will have 3 steps to complete, sometimes they will have 20, it all depends on how the cookie crumbles in the procedural generation.
Making a game which is infinite AND persistent has provided countless challenges to us as a dev team, but the solutions to intricate problems are often the most unique. I hope you enjoyed reading about this little section of our game, and if you ever end up playing it and you see Kevin Bacon in the credits, you’ll now know why!