On Infinite Multi-User Dungeons

tl,dr: I present an algorithm for generating an infinite dynamic dungeon for a blockchain-connected multi-user Roguelike game.

I’m wouldn’t be surprised if someone else has done this before, but from a quick look I didn’t see anything obvious. In this piece I’ll highlight what I’ve done so far and then outline what I’ve been thinking about. I cover both game design and algorithm design.

SubRogue: Previous work

I have a working PoC now that takes block hashes from the Kusama network to populate the dungeon, but the hash are pulled passively rather than actively (this has known problems, see here).

Tweet: first public images of SubRogue

Current Algorithm

I haven’t written a blog yet about what I’ve coded so far because I hit a tricky problem that I didn’t know how to solve in Python. I want players to send a transaction that commits them to a given hash. I understand that there should be a way, by wrapping the current Substrate JS code in Python.

Here is an outline of the current generation algorithm

  1. Place the first room at a random x and y within the bounds of the map. The randomness comes from a block_hash.
  2. Assign the room a random height and width.
  3. Select another random x and y which are for the second room. Assign a random height and width.
  4. Check that the new room doesn’t overlap with a previously generated room. Otherwise re-do step three.
  5. Stop once the algorithm hits the maximum number of allows rooms.
This the current algorithm with a max of 10 rooms and grid of 160 x 100.

Current algorithm doesn’t scale

What do I want to do?

Here is a rough outline of the desired design:

  • Unbounded size — there is always more content to find in a psuedo-infinite dungeon. Naturally, the dungeon by what’s computationally feasible so not infinite in practice.
  • Dynamic and unseen rooms — dynamic content provides both feeling of exploration but it also provides an anti-bot mechanism. It should be risky to enter a new area.
  • Players can start anywhere — after some time players will have discovered all content near the starting area (I’m assuming some persistence should exist). This reduces the feeling of discovery for new players. Dynamic content is part of the solution, but if such content is only on the extremities then it will be slow to get to which will decrease fun.
  • Irregular grid — perhaps the hardest part is the desire not to force the dungeon just to be a regular grid of square rooms.

Finding a solution is reasonably easy if you ignore at least one of the other design requirements. Creating an “infinite” and dynamic dungeon is easy if all players start from the exact same room.

For example: generating the dungeon from the genesis hash forces all players to calculate their copy of the dungeon from first room. This doesn’t scale well and won’t provide some properties which are necessary to make the game fun.

Finding an algorithm for a scalable dungeon that allows all design ideas is tough.

A solution

A regular grid

An illustration of a regular grid. Each square is a region of dungeon.

Dynamic regions

Once explored, a region is recorded on-chain as “discovered” and is associated with a given block hash. This provides a notion of persistence. New NPCs can always be populated in old regions to provide new risks for new players, but the layout will be known ahead of time.

Each region (square) would look similar to what the current algorithm generates, as shown in previous section.

Dynamic regions within a regular grid

Simply connected

line_hash = H(block_hash|H(line_start_x|H(line_start_y)))

Each region must connect to its four neighbours, this means no region is cut-off from the global dungeon and that players can’t become stuck.

Topologically, the map is ‘simply connected’ at the region scale.

Each region is connected to all other regions

Start anywhere

In addition, determinism at the region level means there is no requirement to iteratively compute all rooms starting from the first room. Removing this level of determinism while also avoiding iterative computation (without isolated regions) was the biggest problem to figure out.

Using a regular grid allows for the calculation of connecting tunnels when needed. It isn’t necessary to store positions ahead of time. Now the game state grows as players discover new regions of the dungeon.

Each of the light coloured spots represents a unique starting spot

Feeling of exploration

Alternative Solution

When the new area is added the player’s local coordinates are transformed to global coordinates. Removing the regularity provided by the grid is great and this method ensures that all players are eventually connected to the global dungeon.

My fear is that this algorithm is messier as it has many coordinate transforms. Entirely new regions can still be added by allowing players to iterate outwards away from the regions already discovered.

Wrap Up

Procedural generation in this manner is not limited to dungeon crawling games, but can be used across a multitude of genres.

If I ever launch this game I probably won’t have an unbounded dungeon, but creating a scalable algorithm is important. Perhaps an “unbounded dungeon” can be a mode of play for those who want it. The natural alternative is periodic boundary conditions (dungeon wraps around on itself), but those are easy to add!

Acknowledgements

Andy and Daniel (from Xaya), and Ronan who is building Ethernal World which is also going to be a Roguelike with an “infinite” dungeon. Check it out. It is currently in (pre-)alpha at the moment.

About me

One of the main projects of the foundation is the Polkadot network. A next generation blockchain platform. To read more about the innovation that Polkadot is bringing to the blockchain industry I invite you to read the following blog post: link.

Questions / Comments?

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store