SubRogue: a simple game with tough problems

Something I put together quicker than you can read this! :-)

SubRogue — what did I propose?

Roguelike games are typically 2D, RPG styled games with procedurally generated dungeons. Gameplay is turn-based, grid-based and single character focused. While the original Rogue was set in a fantasy world, the style can be applied to other story settings.

Game Summary

Here is a summary of what I proposed:

  • Rogue-like that connects to a Substrate blockchain.
  • Uses on-chain randomness for procedural generation of maps and spawning of items.
  • Simple mechanics, but complex enough to be an entertaining challenge.
  • Multiple players and games on one chain.
  • Public and verifiable account history that is protected.
  • Provably fair gameplay (prevents cheating).
  • Trade accounts or items with the guarantee of true ownership.

What are the problems with SubRogue (and how to fix them)?

Problem: passive random values can be ignored

If the player passively obtains random values from the chain, then a player could ignore all hash numbers that generate a bad dungeon and lead to a bad outcome. Some block hashes will likely generate a nicer dungeon than others.

Problem: Entire map is revealed at the start

In the simplest design you take a single random value and generate the entire dungeon from it. For a human, the map is hidden on the screen and must be revealed as you traverse the dungeon. However, once the dungeon is revealed a player could try to ‘exit’ via a timeout (or whatever) if the dungeon looks hard. Part of the fun of these games is to explore the dungeon and experience the “fog of war”.

Mock up to help visualise: seeing the whole dungeon means you can plot the safest path ahead of time.

Problem: Random Number Generation

Generating public random values, either on-chain or off, is hard. There are many ways in which a player can collude with the nodes producing the random values in order to bias the outcome. Block withholding is one such problem, but brute forcing is also potentially a problem here. If the player can guess lots of possible paths then there could be ways they can use that to bias random number generation.

Problem: Generate random numbers at high speed

Now do the random number generation at high speed.

Problem: brute-force many possible paths with passive randomness

When I was first thinking about how to make a Roguelike game “on the blockchain”, I was trying to avoid transactions as I figured they are generally expensive. I was hoping that it might be possible to generate the dungeons passively using (e.g.) block hashes. However, as we can see above that gives all the power to player to generate the dungeon.

Left: small segments require fast block times. Right: large segments need brute-force protection.
F = H(random_seed|H(player_location|H(block_hash|H(step_number))))
  • Random_seed — this comes from the network and forces this new dungeon segment to be unique. If a player has actively signed a transaction for this number then we can have some faith that the dungeon generation can not be heavily manipulated by the player.
  • Block_hash — this comes from the chain and I figured it forces the calculation to be unique in time, but this may be redundant with the random seed actually (this was probably more useful before when I was still considering passive random numbers).
  • Player_location — is the coordinates of the player when generating the next dungeon segment. This will have multiple possible inputs and will depend upon the path taken, plus how the current dungeon segment was generated (which in turn relies upon the previous segment). While the number of locations is fairly limited, and can be partially predicted ahead of time, I hope that the nesting of parameters within the hash function make it harder to parallise this calculation.
  • Step_number — is a simple count of the number of steps of the player. I hope it adds extra difficulty since if you walk back on yourself you would affect the output of this function. This value will monotonically increase, it increases even if you visit the same square twice.

Final thought…

There are a number of technical challenges that are necessary in order to minimise cheating, but I think there are also game design issues that can make constrain the extent to which cheating has an impact.

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