New generators: designed from scratch for use in procedural content

By /

We introduced generators the first time in Extensions 1.2. Those early generators, while useful at times, were quite inflexible and too specific.

In the latest version of Extensions (which came out yesterday!), we introduced the completely redesigned generators. A generator, if you don’t know the concept as we use it, is simply a class that has a Next method that always gives you an object of a certain type. They work a bit like random generators, except the elements may or may not be random. They support various LINQ-like methods, and so also resemble sequences (although generators are always infinite).

There are a few “primitive” generators that you can construct directly with the various static methods in the Generator class. These include:

  • Constant: a generator that always generates the same element.
  • Count: a generator generates the sequence 0, 1, 2, 3, …, n, 0, 1, 2, forever.
  • Repeat: generator that generates the elements of a given list repeatedly in sequence.
  • Iterate: a generator that applies a given function to the last k elements to generate the next one.
  • Various random number and bool generators (uniform, arbitrary distribution, Markov chains)

By themselves these generators are not very interesting. But there are several methods that manipulate and combine them to make more interesting generators. Some of the most important are these:

  • Where: generates only elements from a source generator that satisfy a predicate
  • Select: transforms the elements of a source generator and generates the transformed copies
  • Choose: a generator that uses an integer generator to select from a list of objects
  • Group: groups elements of a source generator, and generates the groups.
  • Combine: uses several source generators to generate parameters for a function
  • RepeatEach: uses a source generator, and repeats each generated element several times.

For a full list on all the generators and methods that can manipulate them, see the Extensions API documentation.

Here are some simple examples:

var generator = Generator
   .RamdomUniformInt(500)
   .Select(x => 2*x); //Generates random even numbers between 0 and 998

var generator = Generator
   .RandomUniformInt(1000)
   .Where(n => n % 2 == 0); //Same as above

var generator = Generator
    .Iterate(0, 0, (m, n) => m + n); //Fibonacci numbers

var generator = Generator
   .RandomUniformInt(2)
   .Select(n => 2*n - 1)
   .Aggregate((m, n) => m + n); //Random walk using steps of 1 or -1 one randomly

var generator = Generator
   .Iterate(0, Generator.RandomUniformInt(4), (m, n) => m + n - 1)
   .Where(n >= 0); //A random sequence that increases on average

In each case, elements are only being produced each time you call the Next method or one of its variants. Most calculations are done lazily, so the bulk of the processing is spread over getting the elements and most generators don’t required much memory.

Generators are useful in creating procedural content, or alter properties of game entities (such as their strength) procedurally. A place where you want to use randomness is the ideal candidate, especially when you want to inject some order to make the playable experience more interesting or coherent.

In our own games, we have used generators that generate sky colors that change over time, scene decoration next to an infinite road, for obstacle patterns, for implementing AI that looks like they move with purpose, for controlling the current difficulty of the game, for making random interesting paths, and for generating letters that have a good chance to make words.

One of the programmers in our studio asked me to give him some exercises to help him practice thinking in terms of generators; they may be helpful to you too, so here they are below. They are roughly in increasing difficulty order; beware the last ones may be very difficult!

Write a generator that will produce:

  1. the even numbers (0, 2, 4, …)
  2. k! (1, 2, 6, 24, …)
  3. an item from either of two generators, randomly selected.
  4. an item from either of two generators, randomly selected, but advances both generators.
  5. noise added to a float generator.
  6. a read-only dictionary that counts the number of items generated so far by another generator.
  7. random integers below 10 with no two successive numbers equal.
  8. pairs of floats between 0 and 1 with negative correlation (of -0.5).
  9. random integers below 10 with no two successive numbers a difference larger than 4.
  10. 0s and 1s, where the distance between consecutive 1s is determined by another generator.
  11. 0s and 1s where the probability of successive values being equal is given by another generator.
  12. a sine wave sampled 10 times per revolution.
  13. items from a number generator with each for elements in sorted order (if the original sequence is 7, 4, 9, 2, 5, 8, 2, 0, 4, 4, 7, 3, … the new sequence will be 2, 4, 7, 9, 0, 2, 5, 8, 3, 4, 4, 7, …
  14. a function summing 10 sine waves with a random frequency and amplitude each.
  15. a function made of sine waves, where the amplitude is a new random number each revolution, sampled at 10 times per revolution.
  16. a function summing 10 generators of the previous type.
  17. a random smooth curve in 3D (a 3D “scribble”) where the curve is composed of pieces of circles, and the curve has no sharp bends.
  18. Vector2s around a circle sampled 10 times per revolution.
  19. Vector3s in an upwards spiral sampled 10 times per revolution.
  20. a random 3D walk.
  21. random vectors on a unit sphere. (Steps are equal distance).
  22. a random walk on a sphere. (Steps are equal distance).
  23. random floating point numbers normally distributed.
  24. 1D Perlin noise.
  25. the convolution of a number generator with a list of numbers.
  26. all the permutations of 3 from a list of 5 (and repeat). (0, 0, 0, 0, 0, 1, 0, 0, 2, 0, 0, 3, … After 0, 0, 4, the sequence continues 0, 1, 0, 0, 1, 1, 0, 1, 2)
  27. all the combinations of 3 from a list of 5 (and repeat). (0, 0, 0, 0, 0, 1, 0, 0, 2, 0, 0, 3, … After 0, 0, 4, the sequence continues 0, 1, 1, 0, 1, 2, 0, 1, 3)
  28. cubic interpolation for a generator of Vector3 (sampled at 10 times per original interval).
  29. Bezier interpolation for a generator of Vector3 (sampled at 10 times per original interval).
  30. the Fibonacci numbers (1, 1, 2, 3, 5, …)
  31. the tribonacci numbers (1, 1, 1, 3, 5, 9, 17, …)
  32. the prime numbers (2, 3, 5, 7, …)
  33. GridPoint2s that traverse a rectangle diagonally ((0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2), (3, 0), …)
  34. 1 element from a generator, restart the generator, generate two elements from the generator, restart the generator, generates 3 elements from the generator, and so on. If the base generator generates 1, 2, 3, this generator must generate 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, …
  35. GridPoint2s in a spiral on a rect grid.
  36. GridPoint2s in a spiral on a hex grid.
  37. GridPoint2s in a Hilbert curve on a rect grid.
  38. GridPoint2s in a Gosper curve on a hex grid.
  39. GridPoint2s in a 3D Hilbert curve.
  40. Write a generator that will Zip another generator.
Scroll to Top