Grammar-Based Generation

To me, this is a new form of procedural generation. You declare specific rules for your desired content, and then a generator runs accordingly. I’ve only seen it used for text, but I’m sure the same technique works for anything. The simplest example is picking a random item from a list, and a slightly more complex version shows the power of defining a grammar:

grammar = {
  "first name": "Anna", "Belle", "John"
  "last name": "Brown", "Jameson", "Williams"
  "full name": "{first name} {last name}"
}

G(grammar, "full name") -- ex: Anna Williams

The syntax above is pseudocode for a generator I am working on. I plan to allow the use of a custom seed along with the generator so that you can do things like have uniquely generated people for a population, where only a lookup number needs to be stored (if you wish to remember a specific person).

It gets even more powerful when you make it possible to define multiple versions of the same grammar and use different ones depending on an object’s properties, and allow inline code within the grammars. Here’s an incomplete example based on my continuing efforts to build space games:

{
  "system name": {
    {
      props: { pulsar: true }
      "PSR {random(1000)}"
    }
    {
      props: { pulsar: false }
      "{Greek letter} {Latin name}"
      "{random(100)} {Latin genitive}"
      "{modern constellation} G{random(1000,9999)}.{random(1000,9999)}"
    }
  }
}

For this example, pulsars would get their traditional “PSR ###” names, while non-pulsars would get names based on differing classification methods.

I’m currently thinking about a game based on Aurora, but massively simplified and playable in-browser. Grammar-based content generation would play a very important role in this, from generating system names (as above) to NPC ship design.

References

Resources that helped me recognize the potential of grammars:


(Normally I would like to publish working code along with these posts, or some other form of useful data, but today we’re looking at a work-in-progress idea without even that much concrete form.)

Trying to Understand Noise

Perlin noise and simplex noise are the topics I keep coming back to, because I know they form the basis of a lot of procedurally generated content. All I knew about them to start with was give this function a value for 1 to 4 dimensions, and it will return a “random” value that is constant based on the input.

There is a somewhat ambiguous warning about passing integers “might” lead to a constant result. No, it will always be the same value at any integer. Turns out this is fundamental to how noise functions work:

One explanation I’ve read says that Perlin noise is essentially mixing dot products from 4 vectors from neighboring integers to the exact point you’ve chosen and 4 copies of a constant vector present at each of those “corners.” This is represented by the arrows in the above image.

A consequence of the constant vector at every integer value is that any integer will return the exact same value.

Another explanation describes a noise function as mixed sine functions of differing amplitudes and frequencies. Looking at an output from 1-dimensional noise definitely can make it appear to be that simple, but it isn’t. I mention this idea for three reasons:

  1. It looks similar. This can help trying to visualize it.
  2. It is periodic, you do not have an infinite domain of values to choose from without repetition.
  3. Some terminology can still apply, such as adjusting the frequency or amplitude of noise, and depending on implementation, the range can be the same (or something easy like LÖVE‘s 0 to 1).

Noise Usage

I have been trying to use noise for quite a while, with a lot of failure, mainly around not understanding the domain and range of the noise function. As of now, these are the things I’ve learned:

  • Period / Domain: There is a sample of (usually) 256 values used for the constant vectors, this defines the period before the noise function starts repeating. Keep this in mind combined with other adjustments to hide or avoid this repetition. (This is how I discovered the period of LÖVE’s implementation.)
  • Frequency: A higher frequency can be achieved by stretching the input, leading to quicker, more dramatic transitions.
  • Amplitude: This one feels kind of obvious, but with LÖVE, the output is 0 to 1, so that needs to be mapped to whatever range is desired.

Sources (aside from those linked in-article):

My apologies, but any other relevant sources at this time have been lost to the ages, with the possible exception of the source code to a demake of No Man’s Sky I have put some work into. I will revisit that at a later date.