From 1980’s Rogue to recent games like No Man’s Sky, randomly generated content has become an important part of game design. The techniques used for this are far more sophisticated than just coin flips, since the content they provide needs to satisfy an array of complex conditions. For example:
- A randomly generated puzzle needs to be solvable;
- A randomly generated level needs to be completable;
- Randomly generated terrain should not have features that trap the player.
When trying to ensure that these conditions are satisfied, we can easily run into computational problems that simply take too much time or computer memory to solve.
For example, suppose we wanted to make a puzzle game based on the traveling salesman problem. In this we would generate a map with a set of random cities, and challenge the player to find the shortest route that visits them all.
Finding such a route is well known to be a computationally intractable problem. As the number of cities increases, the computation effort required to find the correct solution increases exponentially. We can therefore easily generate puzzles for which we cannot calculate the best solution. And if we don’t know the best solution, we can’t tell the player how well they’ve done. It would not be a good game.
While trying to find a workaround for this problem, there are a few more conditions for our random generation that need to be taken into account:
- Each random sample should give a unique player experience;
- That experience should be fun!
These can be even trickier to satisfy, since here we run into the “10,000 bowls of oatmeal” problem.
I can easily generate 10,000 bowls of plain oatmeal, with each oat being in a different position and different orientation, and mathematically speaking they will all be completely unique. But the user will likely just see a lot of oatmeal.
- Kate Compton
This shows the danger of content that is too random. Though each sample is unique, it is unique in ways that humans don’t notice or care about.
We get a similar problem for content that is not random enough. Humans are adept at pattern recognition. If we simply remix the same few blocks of content in a simplistic way, player’s will soon see through the facade. The illusion of infinite content will be broken.
From the computing perspective, being ‘not random enough’ is a good thing. If generation of puzzles, levels or other content has some structure to it, analysis of the content can make use of that structure. This makes it easier to ensure that our puzzles are solvable, our levels are completable, and to compare our player’s solutions to the best that is possible. Unfortunately, the same is also true for the player: once they see the structure, things can become boring.
Balancing all of these conflicting requirements means that high quality random content generation can be a challenging task!
How quantum computers can help
Quantum computation is a new architecture for computing, allowing completely different approaches to be taken in designing and implementing algorithms. It has the power to solve problems that were previously intractable. Though hardware is currently still in the prototype stage, we already know exactly what the software will be able to do. This means we can start to look at how it might be applied to the problems of random content generation.
For example, let’s think again about our traveling salesman game. The complex optimization problem on which this is based can be done with a significant speedup when using quantum computing. So we can generate a map however we like and give it to the player. While they are working out their solution, we can use a quantum computer (via IBM’s cloud quantum computing services, for example) to determine the best solution possible. Then we can use this information to rate the player’s efforts.
The same is true of many other kinds of problems that are relevant for randomly generated content. By expanding on the kinds of puzzles and levels that can be analyzed, quantum computing will allow greater freedom in creating algorithms to generate this content.
Quantum computers can also help in the generation of random content itself. These devices can be thought of as extremely fancy random number generators, which can generate random distributions that no normal computer ever could.
For example, Shor’s algorithm takes an integer and computes its prime factors. At the heart of this is essentially a quantum process that takes an integer as a seed and then spits out random factors of that integer. Computing these factors would take exponential effort for a normal computer, and so it becomes practically impossible for large numbers. But quantum computers will be able to do it without breaking a sweat.
Shor’s algorithm shows that quantum computers will be able to produce random solutions to computationally hard problems. Generating good puzzles, levels or terrain for a game can also mean producing random solutions to computationally hard problems. The two are therefore well poised to work well together. So now we can start exploring how to do it.
Using quantum computation today!
In the rest of this article we will create a proof-of-principle. We’ll make some randomly generated but player-pleasing content that can be used within a game. We’ll show that it can be done in the current era of quantum computing, which means using simulators and prototype quantum hardware. And we’ll show that it can be done fast enough to fit in a loading screen.
With this we’ll show that the era of generating random content in a quantum way is here. Not coming soon. Not decades away. It’s something you can start doing now!
Admittedly, we won’t see anything that normal computers couldn’t do too. The aim instead is a proof-of-principle: to show that playable content can be quickly generated, and to serve as a starting point for others to start experimenting with what quantum could do for them.
Since this is going to involve some coding and the occasional bit of mathematical notation, we’ll move over to a Jupyter notebook. You’ll find it in the box below.
So there we have it: islands made with quantum computing. Available now for game designers everywhere.