Markov Chains and Names

I want my text adventure to be all procedurally generated, that includes names. I did not know much about this when I started, but I wouldn't let that stop me! I decided to ask chatGPT to make a random name generator for me, but it just made code to select names from a list, this is not what I wanted! I wanted the names themselves to be generated. I knew if I just used a string of random characters that it would produce gibberish! I asked chatGPT for methods on how to accomplish this and it told me about Markov chains.

So, what is a Markov chain? A Markov chain is a statistical model that predicts the next state based on the current state. They are named after Andrey Markov, a Russian mathematician who first studied them in the early 20th century. Markov originally applied his research to the study of stochastic processes in physics, but his work soon found applications in many other fields, including probability theory, statistics, economics, and computer science.

Markov chains are a powerful and versatile tool for modeling complex systems and predicting the probability of future events based on past events. In the context of text generation, a Markov chain can be used to predict the next character in a sequence based on the previous characters. For example, if the previous two characters are "th", the Markov chain can be used to predict the probability of the next character being "e", "a", "i", or some other letter, based on how often those letters follow "th" in the sample text.

By analyzing a large sample of text and building a Markov chain based on that analysis, we can create a model of how language works and use that model to generate new text that has a similar structure and style to the original. This makes Markov chains a popular tool for text generation, language modeling, and other natural language processing tasks.

Markov chains have been used for:

1. Natural Language Processing: In natural language processing, Markov chains are used to generate text, identify parts of speech, and perform language modeling.
2. Finance: In finance, Markov chains are used to model stock prices, interest rates, and credit ratings.
3. Genetics: In genetics, Markov chains are used to model DNA sequences and predict protein structures.
4. Image Processing: In image processing, Markov chains are used to perform image segmentation, object recognition, and texture analysis.
5. Game Theory: In game theory, Markov chains are used to model game states and predict optimal strategies.

Now that we know what they are, I will go over how to create a name generator in C# using Markov chains. In this tutorial, we will use a Markov chain to generate names by analyzing a set of sample names and predicting the probability of the next character based on the current two characters.

Coding the Name Generator

You will need the following libraries:

using System; 
using System.Collections.Generic; 
using System.Linq; 

The NameGenerator class is defined, which will be used to generate names using a Markov chain.

class NameGenerator     
{
      private readonly Dictionary<string, List<char>> _chain = new Dictionary<string, List<char>>();
...

The class includes a private field, _chain, which is a dictionary that will hold the Markov chain.

The NameGenerator class includes a constructor that takes in a list of strings as its parameter. This constructor calls the BuildChain method, which is responsible for building the Markov chain.

public NameGenerator(List<string> p_sample) 
{
     BuildChain(p_sample); 
} 

The BuildChain method builds the Markov chain based on the list of strings passed into the constructor. The Markov chain is a dictionary that maps two-character sequences to a list of characters that follow that sequence in the original names.

private void BuildChain(List<string> names) 
{
     foreach (var name in names)
     {
         for (int i = 0; i < name.Length - 1; i++)
         {
             if (i + 2 >= name.Length)
             {
                 break;
             }
             var key = name.Substring(i, 2);
             var nextChar = name[i + 2];
             if (!_chain.ContainsKey(key))
             {
                 _chain[key] = new List<char>();
             }
             _chain[key].Add(nextChar);
         }
     }
} 

This method iterates over each name in the list of names, and for each name it looks at each two-character sequence in the name (except for the last two characters). It uses each two-character sequence as a key in the dictionary, and adds the character that follows the key in the name to the list of values for that key in the dictionary. If the key is not yet in the dictionary, it adds the key to the dictionary with an empty list of values.

The GenerateName method generates a new name using the Markov chain that was built by the BuildChain method. This method takes a Random object as a parameter, which is used to randomly select keys and values from the Markov chain.

public string GenerateName(Random p_random) 
{
     var currentKey = _chain.Keys.ElementAt(p_random.Next(_chain.Keys.Count));
     var name = currentKey;
     while (true)
     {
         if (!_chain.TryGetValue(currentKey, out List<char> nextChars))
         {
             break;
         }
         var nextChar = nextChars[p_random.Next(nextChars.Count)];
         name += nextChar;
         if (name.Length >= 20)
         {
             break;
         }
         currentKey = name.Substring(name.Length - 2, 2);
     }
     return char.ToUpper(name[0]) + name.Substring(1); 
} 

This method starts by selecting a random key from the Markov chain, which will be used as the starting point for generating the name. It then enters a loop that will continue until the name is at least 20 characters long or there are no more keys in the Markov chain that match the current two-character sequence.

During each iteration of the loop, the generator checks if the current key is present in the Markov chain dictionary. If the key is not present, the loop is broken out of, and the name generation process is complete.

However, if the key is present, the generator randomly selects a next character from the list of characters associated with the current key. The selected character is added to the name being generated, and the loop continues to the next iteration.

The loop continues until the generated name has reached the maximum length of 20 characters or until a key is not present in the Markov chain dictionary.

Once the name generation process is complete, the first character of the generated name is capitalized, and the name is returned as a string.

To use this NameGenerator class in your game, you need to first create instances of it and provide it with a list of names to use as a sample for the Markov chain generation process. You can then call the GenerateName method of the NameGenerator instance to generate a new name.

Here's how I used it in Endless Prose, I set up different instances of NameGenerator class:

// Creating instances of the NameGenerator class 
var maleNames = new NameGenerator(new List<string>() 
{
      "William", "Henry", "Richard", "Thomas", "Edward", "Robert", "John",
      "Charles", "David", "James", "Geoffrey", "Peter", "Walter", "Simon",
      "Andrew", "Stephen", "Roger", "Ralph", "Oliver", "Nicholas"
});
var femaleNames = new NameGenerator(new List<string>()
{
      "Aelith", "Aurelia", "Bridgette", "Cecilia", "Daphne", "Eadgyth", "Eleanor",
      "Esme", "Gertrude", "Hazel", "Isolde", "Joan", "Juliana", "Lillian", "Margaret",
      "Matilda", "Millicent", "Nora", "Rosalind", "Ursula"
});  
var lastNames = new NameGenerator(new List<string>()
{
      "Blackwood", "Brown", "Curtis", "Day", "Edwards", "Flynn", "Green",
      "Hale", "Hunt", "Johnson", "Knight", "Lane", "Marks", "Nash", "Owen", 
      "Pierce", "Reed", "Simpson", "Thomas", "Wright"          
});
var cityNames = new NameGenerator(new List<string>()             
{
      "Avalon", "Camelot", "Castlewood", "Dover", "Glastonbury", "Harwich",   
      "Kingsbridge", "Leeds", "Norwich", "Oxford", "Plymouth", "Rochester",        
      "Shrewsbury", "Tunbridge", "Winchester", "Yorkshire", "Zennor",          
      "Arundel", "Bridport", "Canterbury"             
});

Then you can use it to generate names like this:

// Generating new names var random = new Random();  
var maleName = maleNames.GenerateName(random); 
var femaleName = femaleNames.GenerateName(random); 
var lastName = lastNames.GenerateName(random); 
var cityName = cityNames.GenerateName(random); 

I hope you found this tutorial helpful in creating a name generator using Markov chains for your text adventure game. Remember, feel free to experiment with different sample sets, adjust the length of the generated names, and tweak the code to suit your needs. And of course, if you have any questions or comments, please leave them below - I'd love to hear your thoughts and see what you come up with! Thanks for reading, and happy coding!