Breeding NPCs – Genetic programming.

I’ve been doing some reading on ways to generate content for my games.  Mainly because I’m lazy, and don’t want to invest time in designing or tweaking a bunch of NPCs individually.  What if I could write some code to make my decisions for me?  That’s when I decided to check out this thing I’ve been hearing about – genetic algorithms.

So how is a Genetic algorithm used? Well, you can think of it like this, consider our galaxy a universe composed of millions of solar systems containing loads of planets (which it is).

In that universe there are planets that suit all your needs in terms of atmosphere, resources, and aesthetics.  There may also be some worlds that are similar to your ideal planet, perhaps in the same solar system, which would do almost as well if you had to make a compromise on some of your needs, i.e. if there is no natural atmosphere, then you’d settle for a life support system, especially if the resources are really worth staying for, or if you wanted to expand out from your ideal planet at some time in the future and didn’t want to stray from your solar system (any way I digress).

Trying to consider all possible permutations and then performing a search for that perfect planet is going to take a while and you may miss some interesting combinations. That’s where genetic algorithms can help.  They essentially search for an ideal candidate solution in amongst potentially millions of possibilities.

You can also think of them as good procedural content generators. Take NPCs in an RPG, for example, say you want to have a nice population of people who look like they should be there, or at least seem to descend from a common clan.  You can encode a series of attributes in arrays (I’ll be using Python from here on):

 npcdata = {
    'gender': ['m', 'f'],
    'class': ['dwarf', 'elf', 'barbarian', 'wizard'],
    'hair': ['no hair', 'short hair', 'long hair', 'pony tail'],
    'occupation': ['builder', 'peasant', 'scientist', 'warrior', 'cleric'],
    'body': ['small', 'regular', 'tall', 'fat'],
    'behaviour': ['generous', 'loner', 'helpful', 'evil', 'hostile', 'kind', 'sad', 'happy'],
}

So we could create a whole load of NPCs using just your regular random() function. However, I’d like them to share some traits, pass others on etc.  The other advantage to genetic algorithms over just selecting random attributes is that you can select the ones that fit your criteria by measuring their ‘fitness’.  In other words, if I had a preference (or fetish) for dwarfs, then of the NPCs generated I’d assign a higher fitness score to dwarfs.  That way there would be a higher probability that dwarfs would be selected from the population of genes (or classes).

Fitness is hard to define sometimes, which is why genetic algorithms can seem a bit tricky. In my case, I don’t know how to define what makes a good NPC (so my fitness function just returns a random score between 0 and 1).  If I wanted nice well behaved dwarfs, then I might grade their behaviour attribute and combine it with my preference for dwarfs.  Therefore, most of your time will be spent tweaking your representation of the attributes or parameters you want to evolve, and the fitness function, everything else is pretty straight forward as we’ll see.  Here is the code we’ll be discussing.

Kicking things off

So we have some data representing possible NPC attributes.  Next we set up our genetic algorithm with some parameters.

POP_SIZE = 30
CHROMO_LENGTH = 6
CROSSOVER_RATE = 0.5
MUTATION_RATE = 0.1

So here I’m going to create 30 individuals (POP_SIZE), their genetic make-up is composed of six attributes [gender, class, hair, occupation, body, behaviour] represented by CHROMO_LENGTH.  Next I’m going to set up how likely the NPC attributes will be swapped between their parents (CROSSOVER_RATE), or changed (MUTATION_RATE).  These values are the result of playing around until you see something that looks good in terms of diversity.

Encoding the Genome

So for each NPC we’ll create an object that stores it’s generation number, where 0 represents the original parent, it’s dna otherwise known as an array containing the six values representing the above NPC attributes, and it’s fitness score.  Here as mentioned, I’m going to just return a random number, so we’re not quite making the most of genetic algorithms here, but have a play around and think about what would be a good fitness function in the context of your projects.

class Genome(object):
    def __init__(self, generation):
        self.generation = generation
        self.dna_string = []
        self.fitness_score = 0.0

Now we’ll take a look at the main program that will handle everything else:

def Run(self):
    # Create a new population
    children = 0
    next_gen = []
    self.generation = 0
    self.startPopulation()

    # Main loop
    while children < self.population_size:

        N = 10

        # Select two parents
        self.mum = self.TournamentSelection(N)
        self.dad = self.TournamentSelection(N)

        self.baby1 = self.CreateGenomes()
        self.baby2 = self.CreateGenomes()

        self.CrossOver()

        self.baby1 = self.MutateIM(self.baby1)
        self.baby2 = self.MutateIM(self.baby2)

        # add to new population
        next_gen.append(self.baby1)
        next_gen.append(self.baby2)
        children += 2

        # copy babies back into starter population
        self.gene_pool = next_gen

        # increment the generation counter
        self.generation += 1

The first few lines are pretty self explanatory (set up a count for the number of children produced, an array to store them for later insertion in to the population, and set the starting generation number to 0).

Next we create two parents who will produce our 30 individuals through breeding (more string operations than breeding to be honest).  Here’s that function:

def startPopulation(self):
    chrome1 = self.CreateGenomes() # Mother
    chrome2 = self.CreateGenomes() # Father
    self.gene_pool.append(chrome1)
    self.gene_pool.append(chrome2)

First step, create the parent NPCs and add them to the gene pool or population if you like.

To create a genome we simply select some attributes from our data (which are stored in a Python dictionary as self.memory) and insert them in to the array representing the genome of our NPC object.

def CreateGenomes(self):
    genome = Genome(self.generation)
    for i in range(0, self.chromosome_length):
        # Get the current attribute
        attribute = self.FetchField(i)
        total_types = len(self.memory[attribute])
        # Pick a value of the attribute at random i.e. body = 'thin'
        dna = int(random()* total_types)
        genome.dna_string.append(dna)
    # Assign the initial fitness score
    genome.fitness_score = self.Fitness(genome)
    return genome

The FetchField function simply returns the .keys() of our Python dictionary based on the position in the chromosome (i.e. 0 = ‘gender’ attribute).

I’m well fit!

The fitness function is very basic, but you could come up with something better quite easily:

def Fitness(self, genome):
    return random()

Who’s the daddy?

We have some parents set up so now we can do some breeding. First we need to select candidate parents (initially there will only be two, but they’ll be replaced by the new offspring), to do this we use the TournamentSelection function:

def TournamentSelection(self, N):
    bestFitnessSoFar = 0
    chosenOne = 0
    # Select N members from the population at random testing against the best found so far
    for i in range(0, N):
        thisTry = choice(range(0, len(self.gene_pool)-1))
        if self.gene_pool[thisTry].fitness_score > bestFitnessSoFar:
            chosenOne = thisTry
            bestFitnessSoFar = self.gene_pool[thisTry].fitness_score
     # return the champion
     return self.gene_pool[chosenOne]

The function randomly searches the gene pool for individuals with the highest fitness score and returns them to be used as the parents of the next generation. Again, if our fitness function was doing something more interesting this function would come in to its own!

Lets cross over

The parents are used to augment the new children with their genes which is handled by the crossover function.  Here we swap sections of genes from the winning mother and father genomes with the children at a random point in their chromosomes:

def CrossOver(self):
    # define the likelihood of a crossover event
    if random() < self.crossover_rate:
        return
    # choose random point to split the chromosome and swap over genes between parents
    copy = int(random() * self.chromosome_length)

    # swap beginning section
    for i in range(0, copy):
        self.baby1.dna_string[i] = self.mum.dna_string[i]
        self.baby2.dna_string[i] = self.dad.dna_string[i]

    # swap end section
    for i in range(copy, len(self.mum.dna_string)):
        self.baby1.dna_string[i] = self.dad.dna_string[i]
        self.baby2.dna_string[i] = self.mum.dna_string[i]

Mutants!!

In order to keep the gene pool nice and diverse we need to mutate some genes, the amount of mutation was defined at the beginning.  There are a number of algorithms out there, I’ve selected Insertion Mutation (based on my reading this is supposed to be pretty good! See the reading list at the bottom of the page):

def MutateIM(self, genome):
    # return based upon mutation rate
    if random() > self.mutation_rate:
        return genome
    # choose a gene to move
    curPos = int(random() * self.chromosome_length-1)

    # keep a note of the genes value
    oldVal = genome.dna_string[curPos]

    # remove from the chromosome
    genome.dna_string[ :curPos - 1] + genome.dna_string[curPos + 1: ]

    # move the gene to the insertion location
    curPos = int(random() * self.chromosome_length - 1)

    # Check the swapped attribute exists within the range of possible values,
    # if not get a random one within the range
    attribute = self.FetchField(curPos)
    if oldVal > len(self.memory[attribute]) - 1:
        oldVal = int(random() * len(self.memory[attribute]) - 1)

    # rebuild the chromosome
    genome.dna_string = genome.dna_string[ :curPos] + [oldVal] + genome.dna_string[curPos + 1: ]

    # return the mutated chromosome
    return genome

And there you have it, that’s pretty much it, all we do is take the mutated genome and assign it back to one of our children, and then add the children to a temporary array. Once we’ve finished all the breeding, we assign our temporary array to the new gene pool, replacing the previous parents in the process, and we increase the generation count.

The result

And here is a sample of what we end up with

Parents:

[0] ['cleric', 'fat', 'generous', 'm', 'pony tail', 'dwarf']
[0] ['warrior', 'tall', 'sad', 'f', 'pony tail', 'barbarian']
------------------------------
Mutate:
[0] ['builder', 'fat', 'generous', 'm', 'pony tail', 'dwarf']
----------
Mutate:
[9] ['warrior', 'fat', 'generous', 'm', 'pony tail', 'elf']
----------

Final set of NPCs:
[0] ['builder', 'fat', 'generous', 'm', 'pony tail', 'dwarf']  - Mutated
[0] ['cleric', 'fat', 'generous', 'm', 'pony tail', 'dwarf']
[1] ['builder', 'fat', 'generous', 'm', 'pony tail', 'dwarf']
[1] ['builder', 'fat', 'generous', 'm', 'pony tail', 'dwarf']
[2] ['warrior', 'fat', 'sad', 'f', 'pony tail', 'barbarian']
[2] ['warrior', 'fat', 'generous', 'm', 'long hair', 'barbarian']
[3] ['warrior', 'fat', 'sad', 'f', 'pony tail', 'elf']
[3] ['cleric', 'small', 'kind', 'f', 'short hair', 'elf']
[4] ['warrior', 'fat', 'loner', 'f', 'no hair', 'barbarian']
[4] ['scientist', 'tall', 'kind', 'm', 'long hair', 'elf']
[5] ['scientist', 'tall', 'happy', 'm', 'long hair', 'dwarf']
[5] ['warrior', 'regular', 'kind', 'm', 'no hair', 'elf']
[6] ['warrior', 'fat', 'generous', 'm', 'long hair', 'barbarian']
[6] ['warrior', 'fat', 'generous', 'm', 'long hair', 'barbarian']
[7] ['peasant', 'regular', 'generous', 'm', 'pony tail', 'elf']
[7] ['scientist', 'tall', 'kind', 'f', 'short hair', 'dwarf']
[8] ['builder', 'tall', 'evil', 'm', 'pony tail', 'elf']
[8] ['warrior', 'regular', 'loner', 'f', 'short hair', 'dwarf']
[9] ['builder', 'tall', 'evil', 'm', 'long hair', 'barbarian']
[9] ['warrior', 'fat', 'generous', 'm', 'pony tail', 'elf'] - Mutated

As you can see we have a fair amount of diversity coupled with some common traits inherited from the parents (generation 0).

In closing…

I’m tired of writing now, and I’m sure you’re pretty bored too so let’s wrap things up.  This post has covered an application of genetic programming in game content generation.  I’m no expert and only just taking my first steps, but you can see that with a lot more thought and consideration the framework above can be used to generate some interesting results. for instance, what if we set the NPC attributes to something more interesting like skill, stamina, magic, etc. instead of appearance?

Imagine the diversity of characters you could create.  You could submit these NPCs to a few rounds of fighting to see who comes out on top, and then use these as parents to spawn even better versions.  This is how genetic programming can be used to create better opponents for human players. In addition, the behaviour attribute of our NPC chromosome could point to a function that would implement the specified behaviour. How cool would that be, eh?

The possibilities are quite exciting, though the hardest part as you see and will hear from others, is encoding your data in to chromosomes, and describing your ideal candidates or solutions through an appropriate fitness function.

Further and recommended reading

This blog and its code has been plagiarised or is simply a rip-off of the following articles and books (well not exactly, but they were a great source of inspiration or good starting point in terms of code):

A very interesting article on some applications of genetic algorithms and such to game content. Check out the bits on generating and evaluating the ‘fun’ or balance of tile-based game maps. This is where things get really cool!!

Chapter 3 discusses genetic algorithms providing C++ code, on which my code is based, and also a number of cool solutions and optimisations to problems such as finding the exit in a maze, travelling salesman problem, automatically controlling a lander, and providing weights for training a neural network. Well worth a read!!  This is where Insertion Mutation is covered.

Another good book, chapter 6 discusses AI and provides some nice simple examples. I based the NPC example, on the one in this chapter. Not many full code examples provided as the one above, but this book is great anyway.

Thanks for reading!!  If there are any inaccuracies or bugs, do let me know (in a nice way) 😉

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s