Hello, Hacker News. You found a post I wrote in 2018 that in hindsight has some issues. Please don’t judge me too harshly. Instead, check out my free online whiteboard Browserboard or read some of my newer posts, such as Let’s generate some imaginary guitar pedals.

Roguelikes are games that, among other things, have a lot of procedurally generated content. To generate content, we need random numbers. And to get random numbers, we need a pseudo-random number generator.

Not only do we want random numbers, but we want predictable random numbers! We want players to be able to share seeds and see who does better in the same situation, while also giving people a completely fresh experience every time they play.

We can’t just create a PRNG with a seed and be done. If we use the same PRNG for both level generation and combat, for example, then our second level might change based on how many times the player got into a fight!

So we need to be clever about how we create and store our PRNGs, to ensure that the procedurally generated maps are not affected by anything that happens during gameplay.

If we use the PCG family of PRNGs, our job is a lot easier. There are many variants of PCG, but in this post I’ll be referring only to PCG32, the one that generates 32-bit unsigned integers and keeps its state as two 64-bit unsigned integers.

(By the way, I used PCG in Dr. Hallervorden, my 7DRL entry for 2018.)

What makes PCG unique?

PCG has a lot going for it, and the web site does a good job of explaining the advantages, but for roguelike developers, it all comes down to the API.

A PCG instance is created with not one, but two values: the seed, and the stream. The seed matches the traditional idea of a PRNG seed, but the stream is something new: it lets you pick from multiple streams of random numbers generated by the same seed!

for seed: UInt64 in [12345, 67890] {
  print("Seed:", seed)
  for seq: UInt64 in [0, 1, 2] {

    // two numbers: seed and seq
    let rng = PCG32Generator(seed: seed, seq: seq)

    let values = [0,1,2,3,4,5,6,7,8,9].map({_ in "\(rng.get(upperBound: 100))" })
    print("Stream \(seq):", values.joined(separator: ", "))
  }
  print()
}

Seed: 12345
Stream 0: 9, 26, 14, 74, 3, 82, 86, 75, 82, 92
Stream 1: 24, 4, 3, 76, 54, 90, 40, 98, 15, 34
Stream 2: 60, 17, 46, 15, 6, 30, 0, 68, 29, 91

Seed: 67890
Stream 0: 54, 68, 74, 56, 1, 63, 43, 47, 21, 96
Stream 1: 36, 16, 80, 58, 36, 31, 5, 14, 29, 73
Stream 2: 89, 61, 71, 58, 85, 14, 70, 6, 59, 31

This means you can start your game with one seed, and then lazily create individual PCG instances for each level at the time you need them, without worrying that your PRNG state has been messed up just by playing the game. (There are other ways of making that guarantee that aren’t difficult, but this one is particularly convenient.)

Once we’ve created a PCG instance, we only need to store two unsigned integers! Serialization’s a snap.

So, to sum up:

• You can have multiple, uncorrelated streams of data from the same seed
• You only need to store 16 bytes per instance

A fun trick with strings

Imagine you have a branching level structure. You’ve got normal-dungeon-1 through normal-dungeon-30, and you might branch off into dwarvish-mines-1 somewhere between level 5 and 15.

Rather than deciding exactly how to branch when the game starts and generating all the level seeds in advance, you can create an object that lazily creates PCG32 instances based on the hash value if your level ID string!

public class PRNGStore: Codable {
  public let seed: UInt64

  private var rngCache = [UInt64: PCG32Generator]()
  private var collisionChecks = [UInt64: String]()

  public init(seed: UInt64) {
    self.seed = seed
  }

  /// Lazily create a PRNG instance based on the given stream
  public func get(stream: UInt64) -> PCG32Generator {
    if let rng = rngCache[stream] { return rng }
    let rng = PCG32Generator(seed: seed, seq: stream)
    rngCache[stream] = rng
    return rng
  }

  /// Lazily create a PRNG based on the given string by getting its hash value
  /// and handling hash collisions
  public func get(id: String) -> PCG32Generator {
    var seq = UInt64(bitPattern: Int64(id.hashValue))
    while collisionChecks[seq] != nil && collisionChecks[seq] != id {
      print("Collision between", id, "and", collisionChecks[seq] ?? "nil")
      seq += 1
    }
    if collisionChecks[seq] == nil {
      collisionChecks[seq] = id
    }
    return self.get(stream: seq)
  }

  public func get(stream: UInt64) -> PCG32Generator {
    if let rng = rngCache[stream] { return rng }
    let rng = PCG32Generator(seed: seed, seq: stream)
    rngCache[stream] = rng
    return rng
  }
}

Once you have a class like this, you never again need to think about when and how to generate PRNG instances, because it all just happens by magic. Using the example at the beginning of this section, you can now generate any dungeon using the PRNG instance at prngStore[levelId], e.g. prngStore["dwarvish-mines-1"].

Language support

PCG32 is very easy to implement, so it has broad language support, even though the algorithm was only introduced in 2014. I wrote two implementations myself: Python and Swift. You should be able to find a good implementation for your favorite language just by searching the web. And if you can’t find one, it really isn’t too hard to do! It’s just a handful of bitwise operations.