How Socketeer's Level Design Evolved
Its been a long journey from inception to completion, where the game design twisted and mutated into something quite different from the original concept. Although, in terms of delivering what I laid out in the original game design document (which, to be fair, came a fair bit after I started the project) the final game is actually pretty close.
From a pure game design point of view, Socketeer was an interesting challenge. The most dramatic design revisions came from the level generation system. Originally the levels were preset shapes that were supposed to represent the inside of a spaceship. But because of the camera placement being so close, you could never really tell you were navigating inside the shape of a spaceship. Also, the levels were open and lacked any structure, making them boring to navigate.
After watching the excellent youtube series presented by Mark Brown on how Zelda's dungeon's worked, I started to try and unpick how these levels were constructed and pondered if there was a replicate the hand authored level designs in zelda with procedural generation. I started by studying Mark's dungeon graphs, which he would use to describe how interesting each level was, and why some dungeons were harder or more interesting.
As you can see from this sample graph above, every zelda dungeon has a route which branches off at various points, and at the end of each branch there was a reward, which was either a key, an item or something else. Some of these branches were also locked, sometimes by keys, sometimes by items and sometimes by puzzles.
The first problem with my current level generation system was that if it locked off a single route it couldn't guarantee that would block off all paths to the reward. What I needed was a maze generation algorithm. Using an excellent book on coding mazes, I adapted the random level generation system to use layouts created by the newly implemented maze algorithm. This meant, because the system generated the "perfect" maze, there was only one route to each dead-end. Exactly what I needed.
After I had written the maze generation system and after studying the graphs further (and watched more of Mark's excellent videos) I managed to come up with a simple graph-generating system. The way the system works is that it finds and stores every dead-end (being a single cell or maze square, that has only one connection to another cell) and junction point (being a cell with three or more connections) in the maze. The system then randomly assigned "rewards" at each dead-end and in turn blocks that reward at the nearest junction point it can find, locked using a key which then can be placed as a new reward at a another randomly selected dead-end. The system keeps looping through all dead-ends, assigning rewards, and then locking them off, until there are none left.
The new system gave the levels a much more interesting structure. Suddenly, you had to think about where you were in the level, remember locked doors and rewards you found previously so you could navigate to them once you had found the appropriate key. Also, the system sometimes wouldn't block the reward off, or generate multiple blocked routes, helping give each level a more individual feel.
On the whole I am happy with how the graph generating system came out. I also think I've only scratched the surface of what is possible, and want to explore the idea further, perhaps in a future update to Socketeer, or perhaps in a sequel. We shall see...