I have been working on objective planning for longer than I would like to admit. It’s been an interesting problem to get my head around and an even trickier one to actually solve. I’ve gotten my algorithm to the point that it produces graphs that are logically sound, but no player would want to play them. This is not ideal.
I’ve been using the same seed for this process of discovery so I can actually tell what things have changed based on things I’ve adjusted in the algorithm. Once I got it to where I was looking at a logically sound graph, I stopped and studied it a bit and discovered that the only open path from the start node was to the fire boss. No where to practice getting better, no where to get supplies to be more powerful, just a boss right away. An unlocked door is logically traversable, but you definitely wouldn’t enjoy the experience of being shoved face first into a boss fight with no preparation.
This obviously revealed that I have a problem with how I was doing things.
Here is a brief summary of how I was objective planning:
- Find a reachable node (from the start node, through unlockable edges).
- Select a random lock and use it to create an edge leaving that node.
- Search for a dangling edge I can reach.
- If I find one, select a random key and create the destination node.
- If I don’t find one, create a new unlockable edge and the destination node.
- Repeat from #1 until I’m out of keys to place.
- Make any dangling edges point back to random nodes.
I’m leaving out some details there, but the gist is that the keys are in a list of keys that haven’t been placed yet. Selecting one for placement removes it from that list and is random. The locks have logic that helps to determine if they are unlockable, and are selected from a weighted list that controls the odds of each kind. Using one doesn’t remove it from the list, so each one can be placed any number of times.
This makes that dreaded graph logic all delightfully consistent, but can produce worlds that would absolutely suck to play. After a big think about it, I’ve realized that a weighted set of locks simply can’t get me to the right answer. No matter how many ways I goof around with the weights. It’s pretty obvious now after thinking about it, but for a game to have progression, there has to be progression. In other words, the game should probably be a bit harder later in the game.
Progression can take a few different forms and a well designed algorithm should probably take them all into consideration. The game should get harder as you move farther away from where you started. It should also make things trickier as more supplies are available to the player. This doesn’t mean the player will actually get all of the things, but it can be assumed they will get bunch of them and could definitely have gotten all of them. Some things the player will need to move forward, like high jump to reach a higher ledge. Other things are just nice to have, like another handful of missiles or an energy capsule. Those things should have values too. Something to help the game decide that a boss is a reasonable thing to have at this point.
This has resulted in a system that uses a lot of the existing framework, but has additional information available to make informed decisions about what should be next. There is still randomness involved, but intelligence had to be added. You want the random worlds to be random, but you also want them to be fun. Imagine showing up to a convention to show of your game and players encounter a boss as the only thing they can do? More people are going to leave your booth annoyed than excited. That’s not ideal.