Context Free Design Grammar is a cool language made up by Chris Coyne (see here) for generating pictures. I've been working on a tool to randomly mutate pictures described in this language so that pleasing images can quickly be evolved. The gallery link above goes to collection of images created using this tool. This page is brief description of how the tool works and how the images in the gallery were created. I assume you are already familiar with CFDG, see here if not.
The tool is simple to use, it is used on the command line like:
cfdg_mutate parent.cfdg child.cfdg <mutation rate> <random seed>
Where mutation rate is an integer from 1 to 100 determining the amount of mutation desired, and random seed is any number to seed the random number generator (if you use the same random seed on the same input file you will get the same output).
The things that the mutator may do to a cfdg file are:
- Add a new rule
- Remove an existing rule
- Add rule instanciations to existing rules
- Remove rule instanciations from existing rules
- Add a parameter to an existing rule instanciation
- Change the value of a parameter of an existing rule instanciation
- Change the start shape for the file
Note that cfdg_mutate does not yet understand the concept of having more than one definition of the same rule, this does not seem to have been particularly restrictive though.
Meta-Evolution
In order to allow meta-evolution, i.e. evolution of the way in which the mutation occurs, I implemented a header which is mandatory for cfdg files which you desire to use with cfdg_mutate. The header must be included at the top of the file, it should look something like:
/*VARS
ADD_PARAM_WEIGHT = 0.181194
REMOVE_PARAM_WEIGHT = 0.0425088
CHANGE_MULTIPLIER_WEIGHT = 1.02284
ADD_INVOCATION_WEIGHT = 0.164979
REMOVE_INVOCATION_WEIGHT = 0.0382294
ADD_RULE_WEIGHT = 0.0107277
REMOVE_RULE_WEIGHT = 0.00629287
CHANGE_START_SHAPE_WEIGHT = 0.103024
PARAM_VALUE_CHANGE_RATE = 8.33953e-07
MUTATE_MUTATE_RATES = -0.000817582
END_VARS
*/
It is marked as a comment so existing cfdg tools will ignore it. The header contains a list of variables, each one tells cfdg mutate how likely each type of mutation should be to occur. For example the following header:
/*VARS
ADD_PARAM_WEIGHT = 1
REMOVE_PARAM_WEIGHT = 0
CHANGE_MULTIPLIER_WEIGHT = 0
ADD_INVOCATION_WEIGHT = 0
REMOVE_INVOCATION_WEIGHT = 0
ADD_RULE_WEIGHT = 0
REMOVE_RULE_WEIGHT = 0
CHANGE_START_SHAPE_WEIGHT = 0
PARAM_VALUE_CHANGE_RATE = 0
MUTATE_MUTATE_RATES = 0
END_VARS
*/
Would cause cfdg_mutate to only add new rules and not do anything else. (This would not be very useful as although new rules would be created the existing rules would never start instanciating them as ADD_INVOCATION_WEIGHT is set to zero, and no effect would be seen).
The final variable in the list, MUTATE_MUTATE_RATES, describes how likely these variables themselves are to change. This allows the mutation rates to evolve to be big enough in value to create images of interest, but not so great that evolved images are too regularly completely destroyed by unwanted mutation.
The first example header included above, is taken from an actual file from my own evolution experiments, getting reasonable starting numbers for these variables was a tricky process so I would recommend any experimenters to use this file header as a starting point.
Automating evolution
While cfdg_mutate will allow you to mutate an individual file, producing interesting results requires dozens of generations, so aswell as the cfdg_mutate tool I have knocked together a simple python script, which uses cfdg_mutate to iterate through the following steps:
- Produce 6 mutated offspring from a parent file
- Run the command line cfdg tool to generate images from these files
- Open a image viewing program to display directory of results (I used gwenview)
- Wait for the user to enter the index of the favourite offspring
- Produce 6 mutated offspring from the chosen file, and 2 from each of 2 randomly chosen offsrping, so that there are 10 in total
- Go back to step 2
In step 5 notice that 2 lucky files will get to produce offspring despite not being chosen by the user. I found that this was necessary in order maintain genetic diversity. Otherwise you might find at times that although you picked a promising looking image, it has no potential to develop any further and without children from other parents you would be stuck. One situtation where this could happen is an image could mutate some interesting feature but at the same time its mutation rate could mutate to be too low to develop any further, obviously its now in a dead-end situation because its mutation rate is too low to change, and the mutation rate can't mutate higher again for the same reason. Having children from more than one parent lowers the chance of this occurring.
Starting point
As a starting point for the images shown gallery in the gallery I used a simple file containing only a single rule to draw a square:
/*VARS
ADD_PARAM_WEIGHT = 0.2
REMOVE_PARAM_WEIGHT = 0.1
CHANGE_MULTIPLIER_WEIGHT = 0.2
ADD_INVOCATION_WEIGHT = 0.1
REMOVE_INVOCATION_WEIGHT = 0.1
ADD_RULE_WEIGHT = 0.1
REMOVE_RULE_WEIGHT = 0.1
CHANGE_START_SHAPE_WEIGHT = 0.1
PARAM_VALUE_CHANGE_RATE = 1e-05
MUTATE_MUTATE_RATES = 1e-03
END_VARS
*/
startshape box
rule box {
SQUARE{ }
}
|
Download
cfdg_mutate_src.zip
This is the source for cfdg_mutate(under GPL license) and the python script. All feedback and suggestions welcome.
|
