One of the steps involved in procedurally generating a world is to figure out the order the player will actually be finding things. This doesn’t mean where they will end up in the world, at least not yet. This is called this objective planning and it’s required so the world has some hope of making sense when I get around to that. I described a bit of this in Keys and Locks but I didn’t go into some of the trickier bits of how the data is stored and used.
My first approach was to create a sort of tree structure that expanded downward from a starting node. Upgrade items were scattered through the tree (keys) and to move around the tree requires collecting and using them (locks). As I was working on it I had a bit of a think about what I was doing and the repercussions of this approach. It has the potential to make amusing worlds just by the nature of pseudorandom numbers bumping into cool stuff, but it seemed to me that it wasn’t going to succeed most of the time.
Example Tree
[Start]
/ \
(Narrow (Unlocked)
Passage) \
/ \
[Missle] [CatForm]
\
(MissleDoor)
\
[And so on...]A tree structure full of keys and locks that has no sense of direction and doesn’t easily support cycles has several limitations. First, no sense of direction implies free movement through unlocked edges in both directions. This makes if difficult or impossible to support 1-way movement through the world and having different requirements for backtracking doesn’t really work either.
This can result in a world that is overly simplified. Imagine a door that drops you into a room from the ceiling. From the top, it’s likely there are no required items to drop in, but from below it could be impossible to get back to that door without the items that allow it. This would be impossible to design if I can’t tell the difference between the directions you’re moving through the graph. This implies the graph must support an understanding of direction between nodes.
Second, a tree structure that doesn’t have a sane way to support cycles causes a lot of trouble. What happens if some later node in the tree allows traversal to a node that is closer to the start node? This means that while processing the graph, I could wander down to that node and then follow the cycle edge back to an earlier part of the graph, and then wander down to that same node again, and go back over and over without end. There are ways to guard against spinning around through the graph forever, but I would have to carefully manage it every time the graph is used. This seems to me to have huge potential for logic bugs. Without cycles, it would be very difficult to make alternate pathways through the world.
Think about to almost any metroidvania you’ve ever played. I’d be willing to bet there are several ways to get around through the world. Some shorter but trickier, others longer but easier perhaps. Sometimes, just ways to move around faster or with a different set of items. Without the ability to allow movement through multiple paths, the world will feel like it’s on rails and that can be boring. If we imagine a world that is simply a one to one copy of the objective graph with these limitations, it becomes fairly obvious that what we have ended up with is something resembling a simple series of hallways with doors to other hallways. Some of those hallways will have useful things in them, some won’t, but by brute force exploring all of them, eventually you’ll pop out the other side and you’ll find a lot of dead ends in the process. Instead of dealing with these limitations and the worlds they force us into, it seems like it would be better to redesign the structure of the graph.
Let’s switch from a nested tree structure a list of nodes and a list of edges. These are always just lists, so cycles are now much less dangerous. We can just process the whole list, and when we’re done, we’re done. It becomes impossible to get trapped in a cycle forever. A list of nodes where each of them knows nothing about the others, each containing only the information needed to function is a good start. Next, the edges can be modified. They used to exist as part of a node, and contain nodes themselves. If we make them have a reference to the node list for the source and destination nodes instead of simply connecting nodes, there is now a sense of direction. That means I can do 1-way entries and different connections depending on direction. If my nodes also keep track of edges that leave them, I now have a structure that can be moved through easily too.
I haven’t invented anything new here. A graph with a sense of direction is just called a digraph (short for directed graph). What I have done is identify a list of problems and made an effort to try to dodge them. It’s been an interesting problem to solve for sure, but I have to admit I’m getting a little tired of being slowed down by things like this.