Most people got a bad feeling when they hear about procedural quests. Most will most likely think about the "deliver item X" or "kill X monsters" quests encountered too often in MMORPGs. I want to generate more complex quest, maybe even character specific quests. I've got some ideas and I want to develop a procedural quest system slowly step by step, beginning with a simple system and refining it with each iteration. My experiences and thoughts will be documented in this journal as a little series of entries.
Well, let's start. In my first entry I want to talk about a quest and level setup. First off, I can generate indoor levels and will incoperate this in my quest generation. My approach will most likely be applicably to "closed" levels not so likely to "open worlds".
Talking about levels, I define a level as a collection of sections which are connected by gates. Each section is an isolated island where the player is able to walk around and do something, but the only way to leave or enter a section is through a gate. Take a look at figure 1. Think about a survival horror game, you're coming from town and want to investigate the house of a mad scientist. To proceed in the story you have to find the secret research labour reached by a tunnel in the cellar. Cliche pure :-) As you can see, a section could be of different size. The kitches might be quite small, whereas the ghouse could be large.
The next step is to define a goal. We start with a simple but often encountered goal: find the exit and leave the area.
Now we need to introduce some rules, my first rule is: whatever happens, the player must be able to reach his goal. Sounds pretty standard.
We need some kind of critical path through the level which the player can follow to reach his goal. The level looks coincidentally like a graph and we use this to run a minimal spanning tree algorithm which lead to the result seen in figure 2. As you can see, there are two edges (or gates) which are not included in the spanning tree. These two gates will be closed for the start. In our example this could be a barrier, a fire, a jammed door whatever.
The next step is to find the unique path to our goal. A simple depth search will deliver the wished result.
To introduce a challenge we can lock one gate on the critical path and place the key somewhere in the level, preferable in a section which is not on the critical path. To find a proper placement of the key, start a conditional depth search at the entry point on the minimal spanning tree. Take the deepest section you encounter. But do not surpass the locked gate and prefer a node, which is not included in the critical path.
That's all for the first part. To sum it up:
- Devide your level into sections which are connected by gates.- Sections are isolated parts of your level which are only reachable through gates.- Determine the minimal spanning tree.- Block all gates which are not contained in the spanning tree.- Determine the critical path to the level exit.- Lock one gates on the critical path.- Do a conditianal depth search to find a proper placement of the key.All this is pretty basic graph theory I will start to implement some basic graph structures and algorithms. Next things to do are alternative routes, sub goals, sub quests, quest story generation etc. , so stay tuned !
