Darknet Puzzle Generation

[cross-posted from the Darknet dev blog]

The most important element in Darknet’s gameplay is the hacking puzzle. The puzzles aren’t the only obstacles you'll encounter (there’s a lot of strategy on the “network layer” of gameplay as well), but every time the player goes through a level, they’ll have to complete at least a couple of puzzles to win. That’s why it’s so critical to make the puzzles unique and challenging. To this end, every puzzle in Darknet is procedurally generated, with the ultimate goal of creating a challenge for which not even the designer knows the answer. I’ve written a lot about the puzzle mechanics as they’ve evolved, but here’s a short video if you want to quickly get an idea of how they work:

The puzzle generation algorithm takes place in two stages. First, I create the “skeleton” of the puzzle, and then I populate it with antivirus programs and other obstacles. The skeleton starts out as a simple rectangle, with the dimensions determined by the size of the node:

That’s not a very interesting shape, visually or strategically, so the next step is to spice it up. I have two methods of doing this. First, I can carve out sections of the puzzle based on premade images, so that this...

... turns into this:

I usually cut out some sort of border, and I cut out one or two shapes from the interior as well in the hope of adding some interesting strategic twists.

There’s another, more organic technique for changing the image’s shape, though. Some of the time, I’ll use a classic “cave generation” algorithm, similar to those used in games like Minecraft. Essentially, this technique starts by randomly removing sections of the skeleton, then adjusting it over and over again to clump the empty spots together into recognizable “caves”. After much tweaking, I ended up with an algorithm that produced some pretty interesting randomized shapes:

That provides a good level of variety on the macro scale, but there are still a lot of boring open spaces. To spice it up more, I then cut out a bunch of spaces in the interior of the skeleton in an attempt to add some more interesting strategic texture:

At this point, I remove any disconnected “islands” and the skeleton is left in pretty good shape. Sometimes this process cuts too much away, and there’s almost nothing left, but in that case, I just rerun the algorithm until the puzzle skeleton is acceptable.

The next major stage of puzzle generation is to add the antivirus programs. These are the basic obstacles in the puzzle. However, they’re also a critical resource for the player, since they also serve as the only locations where the player can inject viruses. If there were no antiviruses at all, the puzzle would be impossible to beat.

In the end, there are three important variables that I change to control the difficulty of the puzzle. First, I adjust the density of the antiviruses (more dense = more difficult). Second, I adjust the minimum distance of an antivirus from the center (closer = easier). Lastly, I adjust the number of “unhackable” antivirus programs that surround the core (fewer = easier), which probably has the biggest effect on the difficulty. The end result looks something like this:

When the player has gained more skill and has started to take on greater challenges, there are a few more twists that I introduce. They aren’t given official names in-game, but in the code I refer to them as “death mines” and “circuits”. These special elements add some extra twists to the gameplay. Like the antiviruses, they double as obstacles and resources for the player, though most of the time the resulting puzzle is more difficult:

This algorithm works well in practice, and its greatest feature is that it can scale up to create puzzles of enormous size and complexity:

My only worry about the puzzles is that, although they work well, they might monopolize the player’s time and pull focus away from the other interesting parts of the game. I see the puzzles as one of three main layers of gameplay, but if you spend 90% of your time solving them, the game as a whole might get boring before you can enjoy the rest.

Still, in the end, I’m quite proud of the puzzles. I’ve been solving them for a long time, and I still find it to be an interesting challenge. Hopefully, new players will have the same feeling, and the puzzles will serve as a strong foundation for the experience as a whole.

- @E_McNeill