[MUD-Dev2] [TECH] Randomly-generated Faction Names

[Johnicholas Hines]

Cruise said:
> Randomly generating character names is nothing new - but has anyone
> attempted generating names of in-game factions?

I have been working on a random string generator. The idea is that
people write a grammar for the strings that they want to randomly
generate.

For example, here is a grammar for organization names:
         Note: "colon colon equals" might be pronounced "can be"
organization ::= beginning middle end .
beginning ::= Some .
beginning ::= The .
middle ::= Light
middle ::= Dark .
end ::= Knights .
end ::= Rogues .
end ::= Avengers .

This generates 2*2*3=12 (dumb) organization names like "Some Dark
Knights", at the cost of only 1+2+2+3=8 lines of content. It's a dumb
example, of course, but multiplication trumps addition pretty quickly.

>From a user's point of view, there is not a big difference between a
system that allows only finite sets and a system that also allows
infinite sets. Adding one production to the above like this changes it
to an infinite set of names.
middle ::= Very middle .
Now you can have "Some Very Very Dark Knights", and "Some Very Very
Very Dark Knights". What fun.

>From an implementor's point of view, the infinite language is
considerably trickier, because you can't just say "pick one at random
from a uniform distribution". You need to favor small sentences over
big sentences.

However, it might add a little convenience for the user to allow
infinite sets, so I implemented it.

A tricky part is allowing weights, so that the user can say some words
are common and some words are rare. There is a straightforward
implementation, where you start with a sentence containing the start
symbol, and at each step, you take the leftmost non-terminal and
choose a production at random from that non-terminal's productions.
This straightforward implementation has a bug.

S ::= terminal . %probability 0.1
S ::= S S . %probability 0.9

If you apply the straightforward implementation, the number of S's
increases more often than it decreases. You have no guarantee that the
generation process even terminates. With only a slightly different
grammar, you can make the number of S's increase even faster.

You might think that those inflationary circles never come up in real
procedural content generation, but in my experience, avoiding them is
annoying.

I have a way of avoiding that problem. To generate random strings, I
basically build a bijection between the set of all parses of sentences
in the grammar and the natural numbers - then I can count up 0,1,2...
to generate exhaustively, or generate random numbers in [1000,10000]
or whatever, to generate random sentences of a certain size. (shorter
strings come before longer strings in the enumeration).

I don't have weights implemented inside the system yet, because
they're easy to do by hand. If you duplicate a production a certain
number of times, you introduce an ambiguity into the language. Because
the bijection is with _parses_ rather than with _sentences_, that
sentence comes up more often in the output.

In order to generate, for example, "blueish" jewelry descriptions (for
a water-magic-enchanted item), I would use the same generator as
jewelry generally, but with different weights; basically turning off
all the "colorish" productions other than "blueish". I'm sure you can
see how to apply the same principle to generate aligned faction names.

Johnicholas