On Infinite Multi-User Dungeons

SubRogue: Previous work

In a previou blog I discussed my plans for building a Roguelike blockchain game that I dubbed SubRogue. Initially, suggested as a single player game with procedurally generated dungeons but the hope has always been to make it multiplayer.

Tweet: first public images of SubRogue

Current Algorithm

The current generation algorithm is iterative starting from the first room, which prevents easily starting anywhere and forces a lot of computation.

  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

In step 1 I note that the map is bounded. This is because of the algorithm needs range within which a random number is generated. That was the first thing I struggled with. This algorithm also populates the dungeon in an iterative manner. That won’t scale well for areas far from the starting point.

What do I want to do?

I want to create a game where the dungeon can be generated dynamically and so new content can always be found even for new players. The feeling of exploration in an entirely new MMO is one of excitement, but that feeling is lost once the game has been around for a while. I’m not sure if an psuedo-infinite dungeon will solve that problem, but it has been an interesting problem to think about and having a scalable algorithm is useful.

  • 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.

A solution

I was stuck figuring out how to scale up the current generation algorithm that I couldn’t find a good solution. Fortunately some discussion helped. Daniel Kraft (from Xaya) made a suggestion that broke my creative block. His solution is different from what I propose here, but I outline his idea at the end.

A regular grid

First, we have to accept some regularity and adopt a grid structure at a particular scale. The map will be divided into regular sized regions (e.g. 100 x 100), but each region can have dynamic room generation such that the layout will not be known ahead of time.

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

Dynamic regions

Dynamically generation of each region can be done by following the current algorithm (see previous section). The boundaries are known and finite (e.g. 100 x 100).

Dynamic regions within a regular grid

Simply connected

Regularity at the region level is acceptable trade-off. The tunnels that cross the boundaries of each region will be positioned deterministically based on the genesis hash. Although that hash needs to be mixed for each specific line, e.g. something like:

line_hash = H(block_hash|H(line_start_x|H(line_start_y)))
Each region is connected to all other regions

Start anywhere

Having determinism at the region level allows players to start in any region. There is no fear of them becoming stuck as all regions are connected. Players have complete safety that they are joining the global dungeon: i.e. they can find their friends and group up.

Each of the light coloured spots represents a unique starting spot

Feeling of exploration

New players can start out in an entirely new and unexplored region. A new block hash can be pulled to generate that region. Also, not allowing the computation of the whole dungeon ahead of time prevents bots gaining an easy edge over human players.

Alternative Solution

One promising variation that removes grid regularity has players create their own region of the dungeon. It isn’t initially connected to the global dungeon but rather there is a random chance of joining one player’s dungeon to another. Potentially simplify that to just having a random chance of a player’s dungeon joining the global dungeon.

Wrap Up

Implicit in all this is that any user can fairly check the actions of any other user (via distributed and replicated state machines). Out-of-protocol cheating is prevented: i.e. everyone agrees upon the game state and game rules, at all times, in a decentralised manner.

Acknowledgements

I’d like to give thanks to the following people from feedback on my previous blog or for engaging in discussion about random number generation.

About me

Currently, I work at the Web3 Foundation (mainly running the grants program). This blog is of a personal nature. It just so happens that my hobby aligns with work.

Questions / Comments?

You can create a reply to me here on Medium, or reach out to me on Twitter: @EAThomson.

--

--

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