Michael J. MCGuffin
University of Toronto
submitted May 2004 (slightly edited following submission)
A course project completed for CSC 2521: Artificial Life (Prof. Demetri Terzopoulos)
The phenotypes of the system are instances of what John Maeda has called reactive graphics -- a kind of minimalist interactive art that might be defined as interactive graphical entities that respond in simple, direct, and visual ways to input such as that from a mouse.
Each genotype in the system is interpreted as a sequence of executable statements. This "genetic program", written in a toy language, takes the last few mouse positions as input, and renders output onto a bitmap image. As the mouse is dragged over the image, its genotype is re-executed for each mouse motion event. Selection of mutated genotypes is user-driven and interactive.
Computers are distinct from other artistic media not only in that they are interactive, but also in that they are "the only medium where the material and the process for shaping the material coexist" [8]. As Alan Kay put in it 1984 (quoted in [11]),
The protean nature of the computer is such that it can act like a machine or like a language to be shaped and exploited. It is a medium that can dynamically simulate the details of any other medium, including media that cannot exist physically. It is not a tool, although it can act like many tools. It is the first metamedium, and as such it has degrees of freedom for representation and expression never before encountered and as yet barely investigated.
Although visual artists have been investigating the possibilities afforded by computers for decades (e.g. Charles A. Csuri as early as the 1960s [1]), there has been a more recent surge in computer art from graphic designers who use tools like Macromedia Flash to create forms that are abstract, interactive, and web-oriented [e.g. 2,7,10,12,14,15,18,20].
John Maeda is a computer scientist and graphic designer who is often seen as a pioneering influence in this recent vein. Maeda coined the term reactive graphics [8,9] to describe a kind of minimalist interactive art, of which he and his students have produced many examples. In his words, "For many years I have been fascinated with the design of what I call reactive graphics, which are programmed to respond directly to actions of the user. These are reactions that are concise [...] In this basic area of visual inquiry, I have focused primarily on the mouse" as the input device [8]. "The purpose of reactive graphics has always been to engage the human sensory system at the instinctual level, rather than the communicative level, as in interactive graphics. The mutation of form in a direct and immediate manner leaves little to be guessed beyond what has occurred." [9].
Examples of reactive graphics include cursor "trails" or glyphs that follow a mouse cursor; geometric patterns that translate, scale, rotate, or change in other simple ways in response to cursor motion; glyphs that change shape or colour in response to the speed, direction, or position of the cursor; and visual metaphors such as elastic bands or graphical objects that bounce, fall, collide, stick, or spin in response to input (Figure 1).
|
| Figure 1. Examples of Reactive Graphics. Left: screenshot of concentrics by John Maeda [10], in which discs follow the cursor with a delayed reaction, and are drawn in an XOR-fashion. Right: screenshot of February 10, 2000 piece by Joshua Davis, featured in praystation [2]. Colours have been adjusted to increase contrast. |
The aspects of fun, play, and surprise are often important elements in the design and experience of reactive graphics, however there is also a more serious side to experimentation with these abstract interactive forms: they can reveal some of the basic elements of interaction, and different, sometimes novel, ways of combining these elements. Reactive graphics can help liberate a designer's mind from common interface metaphors (see the syllabus at [7]) and even inspire new visual metaphors and/or interaction widgets.
Reactive graphics are almost always hand-crafted by a programmer, however their apparent visual simplicity makes it tempting to think we might automate, to some degree, their creation. Artificially synthesized reactive graphics might provide inspiration to both artists and user interface designers, by generating combinations of elements perhaps not thought of before.
Genetic algorithms, or artificial evolution, has been successfully applied in many domains to generate successful solutions to problems and also generate output that can appear "creative". Examples of an artistic flavour include genetically evolved imagery [16,4,6,13]; "creatures" with genetically evolved morphology in 2D (such as biomorphs [3]) and 3D [19], and even with evolved morphology and behaviour [17]; and genetically evolved "alphabets" [5]. Much of the existing work in artificially evolved art has focused on the generation of static artifacts in 2D or 3D, and in some cases behaviours for these artifacts (such as creature behaviour). Although I have not performed a thorough survey, I am not aware of any efforts to evolve interactive artwork.
This paper describes the application of genetic programming to evolving reactive graphics. The implementation of a prototype is described at a high level, the strategy for representing and mutating genotypes is given, and sample output is presented.
Many potential genetic encoding schemes could be designed for describing reactive graphics. To keep the implementation of the prototype simple, the genetic encoding that was chosen is based on an imperative programming language. A genetic sequence is interpreted as an executable sequence of instructions, or genetic program. Instructions can fetch input data, perform mathematical operations, and draw simple rendering primitives on the output image.
When the genetic program is executed, an array of the most recent mouse positions is passed in as input, which the program is free to use however it likes. The array of most recent mouse positions makes it possible to render graphical "tails" or other sequences of shapes that follow the mouse cursor, perhaps lagging behind by a few positions. Mouse position information may also be used in a more abstract manner, such as to drive the colour of a shape that is rendered by the program.
Interaction occurs when the user drags the mouse over an image. Each new drag event causes the array of mouse positions to be updated, the genetic program to be re-executed, and the new output image to be displayed.
Each genetic sequence is a program that consists of a sequence of statements. Each statement is a single command followed by zero or more arguments, and has the form
command argument_1 argument_2 ... argument_nArguments may be literals (i.e. constant values), or, more usually, variables (analogous to registers in an assembly language). Literals and variables are all of type signed integer. (Note that every program is prefixed with the number of variables it uses. For example, the prefix "5" implies that the program uses 5 variables, all of type signed integer, and named 0, 1, 2, 3, 4.)
The LOAD command, with the form
LOAD variable1 literal1stores the value literal1 in the variable variable1. For example, "LOAD 3 14" would store the value 14 in variable 3. Currently, the LOAD command is the only command that has any literal parameters. All other commands take only variables as arguments.
As an example of how variables may be used, the ADD command has the form
ADD variable1 variable2 variable3and stores the sum of the values of variable2 and variable3 in variable1.
Following is the current instruction set of the language. Hash marks '#' denote comments, and can be used with a program's source code -- they are stripped out when the program is read in by the system.
LOAD v1 l1 # v1 = l1, l1 a literal COPY v1 v2 # v1 = v2 copy NEG v1 v2 # v1 = -v2 negate ANEG v1 # v1 = -v1 auto-negate AINC v1 # v1 = v1 + 1 auto-increment ADEC v1 # v1 = v1 - 1 auto-decrement ADD v1 v2 v3 # v1 = v2 + v3 add SUB v1 v2 v3 # v1 = v2 - v3 subtract MULT v1 v2 v3 # v1 = v2 * v3 multiply DIV v1 v2 v3 # v1 = v2 / v3 divide (unless v3 is zero, then v1=v2) MOD v1 v2 v3 # v1 = v2 % v3 modulo (unless v3 is zero, then v1=v2) SQRT v1 v2 # v1 = sqrt(abs(v2)) square root # These retrieve the (v2)th most recent mouse coordinates, v2 >= 0 MOUX v1 v2 # v1 = mouse_x(v2) MOUY v1 v2 # v1 = mouse_y(v2) # conditional jump: jumps forward v1 statements (where v1 may be negative) # if v2 < v3 and v1 is non-zero. # Otherwise the instruction pointer moves forward one statement, as usual. JMP v1 v2 v3 # Early exit. Terminates program. END # draws line from (v1,v2) to (v3,v4) with colour (v5,v6,v7) LINE v1 v2 v3 v4 v5 v6 v7 # Draws line from last plot point to (v1,v2) with colour (v3,v4,v5). # The plot point is initially the most recent mouse position. PLOT v1 v2 v3 v4 v5 # draws rectangle from (v1,v2) to (v3,v4) with colour (v5,v6,v7) RECT v1 v2 v3 v4 v5 v6 v7 # draws filled box from (v1,v2) to (v3,v4) with colour (v5,v6,v7) BOX v1 v2 v3 v4 v5 v6 v7
Input is retrieved through the MOUX and MOUY commands, and output is rendered using the LINE, PLOT, RECT, and BOX commands.
The JMP command is general enough that if / else clauses, for-loops with a fixed number of iterations, and while-loops with a variable number of iterations can all be implemented in the language. Thus, ignoring memory limitations, the language appears to be Turing complete.
The virtual machine is designed to be forgiving enough that any program written in the language can be interpreted without error, and also tries to help programs produce interesting output. For example, x and y coordinates and RGB values passed to the LINE and other output commands are wrapped to fall within the valid range for the output image, so that the commands produce visible output. Also, the index passed as the 2nd argument to the MOUX and MOUY commands is wrapped to fall within the array of mouse positions.
To prevent infinite loops from causing the virtual machine to spin endlessly, the virtual machine stops executing instructions after a maximum number of instructions, as set by the user, have been executed.
Following is an example program, hand-written, than draws a polyline through the sequence of most recent mouse positions (Figure 2).
8 # variables: x, y, r, g, b, n, delta, max # indices: 0, 1, 2, 3, 4, 5, 6, 7 LOAD 2 100 # r = 100 LOAD 3 100 # g = 100 LOAD 4 100 # b = 100 LOAD 6 -4 # delta = -4 LOAD 7 5 # max = 5 LOAD 5 0 # n = 0 MOUX 0 5 # x = mouse_x(n) MOUY 1 5 # y = mouse_y(n) PLOT 0 1 2 3 4 # plot(x,y,r,g,b) AINC 5 # ++n JMP 6 5 7 # jump delta if n < max
|
| Figure 2. Output from the sample program. |
Again heeding Sims' advice [16], mutations that simplify or shorten the genetic program were made slightly more probably than lengthening mutations, to discourage sequences that are unnecessarily inefficient.
The mutations implemented are
Whenever a mutation involves a choice -- such as choosing which statement or argument to operate on, or the length of a block or place to insert something -- a uniform pseudorandom number generator is used to make the choice. Multiple mutations can be performed within a single generation by increasing the mutation rate, a user-controlled parameter. A high mutation rate can be useful if the user starts with an empty genetic sequence and wants to evolve something interesting from "nothing".
The mutations and virtual machine were carefully implemented so that an invalid program would never be generated, nor would executing a program ever cause an error to occur. However, genetic programs can be generated that contain infinite loops, dead code, code that has no effect on the output, or that generate output that is not a function of the mouse input.
Successive mutation and selection allows the user to explore the space of all genetic sequences by "probing" along a path, changing the direction of the probe at each generation. Increasing the mutation rate allows the user to travel farther with each generation, but also makes it easier for the user to overshoot into uninteresting regions of the space. Sims [16] and others have suggested imitating sexual reproduction by allowing for genotypes to be combined in various ways, allowing the user to "jump" from two probes to locations in the space that may combine characteristics of both original parents.
In the prototype, a very simple kind of sexual combination was implemented. The user may select two individuals and invoke a crossover feature, which generates offspring by taking a random contiguous block of statements from one parent, and inserting it at a random position in the genetic sequence of the other parent.
The prototype systems opens a single window divided into a left and right pane. Each pane contains a table of images arranged in rows and columns, showing the phenotypes of the current population. The upper-left-most image in each pane corresponds to the parent for that pane. Commands available to the user include
|
| Figure 3. The user interface. The program for Figure 2 is the parent in the upper left corner of the left pane (parents have a red border). It was mutated, producing other individuals in the left pane. One of these offspring was then made the parent of the right pane and itself mutated. |
Because the phenotypes are interactive, it is not obvious how to best display their output in a manner that affords rapid browsing, evaluation, and selection. Sims [16] discusses the evolution of animations, and points out they would take longer to "display and select" than static images. However, whereas animations are images that are a function of only time, the interactive images in the current system are functions of the x and y coordinates of each of the most recent mouse positions, and hence have a much higher dimensionality.
Since the images are intended to be interacted with through a mouse, the prototype allows the user to simply drag over any image to see it respond. Furthermore, to allow the user to browse multiple images simultaneously, the user may hold down the Ctrl key and drag, in which case all of the images in the pane respond simultaneously to the mouse positions relative to whatever image the cursor is within. During this Ctrl-dragging, the system may slow down if the genetic programs each require a significant amount of time to execute, however in practice Ctrl-dragging has proven very useful for quickly identifying the most interesting images, which can then be dragged over individually for faster interaction.
Below each image, two statistics are displayed: the number of statements executed to produce the current output, and the total number of statements in the genetic sequence. If the former number is larger than the latter, at least one JMP statement was executed, possibly in a loop. If the former is much smaller than the latter, the genetic program may contain many dead or unreachable statements. These statistics help the user identify highly inefficient candidates, or candidates that likely contain infinite loops (the latter would have execution counts equal to the maximum number of statements that can be executed by the virtual machine, i.e. 10000 in the case of Figure 3).
Starting with an empty sequence
One interesting test is to try and evolve something from "nothing", i.e. from an empty genetic sequence. When attempting this, it is convenient to increase the mutation rate to something very high, to obtain interactive forms in just one generation, which can then be further mutated at a much lower rate in successive generations. Setting the mutation rate to a maximum of 175 mutations per generation produced the output in Figure 4 in just 1 generation, starting from empty parent sequences. Some of the images in Figure 4 indeed change in response to mouse input. Unfortunately, they tend to be highly inefficient, and probably contain much code that is either dead or has little to no effect on the output. Note the high statement counts in the more interesting images.
|
| Figure 4. Evolving entities from nothing. |
Starting with the program for Figure 2
If a hand-written program is used as a starting point, a very small number of mutations can lead to interesting variations. The program for Figure 2 was used as an initial parent, from which many interesting descendants were evolved. Figure 5 shows screen shots of some of the interesting ones found in very little time.
  
|
  
|
  
|
  
|
  
|
  
|
  
|
  
|
  
|
| Figure 5. Descendants of the program for Figure 2. To give a sense of the interactive behaviour of these entities, each row contains 3 shots of the entity for different mouse input. |
The genotypes of all the entities in Figure 5 were saved into files and can be later reloaded and mutated. For example, the genetic program for the last row of Figure 5 is
8 # number of variables # 25 statements in total AINC 7 LOAD 6 100 LOAD 3 100 COPY 4 1 LOAD 6 -4 LOAD 7 5 LOAD 5 -249 MOUX 0 5 LINE 4 5 7 7 2 6 4 RECT 6 1 5 4 1 2 5 MOUY 1 5 PLOT 0 3 1 2 4 AINC 5 LOAD 3 100 COPY 4 1 LOAD 6 -4 LOAD 7 5 LOAD 5 -249 MOUX 0 5 LINE 4 5 7 7 2 6 4 RECT 6 1 1 4 1 2 5 MOUY 1 5 PLOT 0 3 1 2 4 AINC 5 JMP 6 5 7
Starting with a different program
As another test, the following program was hand-crafted
and then mutated over 2 generations yielding many interesting variations (Figure 6).14 # variables: x, y, g, g2, n2, n, delta, max, x2, y2, radius, g_delta, one, two # indices: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 LOAD 12 1 # one = 1 LOAD 13 2 # two = 2 LOAD 2 0 # g = 0 LOAD 3 255 # g2 = 255 LOAD 5 0 # n = 0 LOAD 7 8 # max = 8 LOAD 11 32 # g_delta = 32, or 256 / max MULT 10 7 13 # radius = max*two LOAD 6 -16 # delta = -16 SUB 4 7 5 # n2 = max - n ADEC 4 # --n2 MOUX 0 4 # x = mouse_x(n2) MOUY 1 4 # y = mouse_y(n2) COPY 8 0 # x2 = x COPY 9 1 # y2 = y SUB 0 0 10 # x = x - radius SUB 1 1 10 # y = y - radius ADD 8 8 10 # x2 = x2 + radius ADD 9 9 10 # y2 = y2 + radius BOX 0 1 8 9 2 2 2 # box(x,y,x2,y2,g ,g ,g ) RECT 0 1 8 9 3 3 3 # rect(x,y,x2,y2,g2,g2,g2) ADD 2 2 11 # g = g + g_delta SUB 3 3 11 # g2 = g2 - g_delta SUB 10 10 12 # radius = radius - one AINC 5 # ++n JMP 6 5 7 # jump delta if n < max
|
| Figure 6. Descendants of a different program. The program just given in the text is the parent in the upper left corner of the left pane. It was mutated, producing other individuals in the left pane. One of these offspring was then made the parent of the right pane and itself mutated. |
Crossover
This is the least tested feature of the prototype, but appears to work acceptably. Below, Figure 7 shows the result of combining the program for Figure 2 and a descendant in Figure 6.
|
| Figure 7. Crossover. The genotypes of the two parents are combined to produce offspring that exhibit properties of both parents. |
Before completing the prototype, I was concerned that the genetic programs would be perhaps too fragile and break down during mutation into uninteresting, dead programs. To my surprise, mutations regularly produced entities responsive to mouse input and quite different from their ancestor of 1 or 2 generations ago.
I had also expected the code resulting from many generations of evolution to be very different from the kind of source code a human would write (e.g. convoluted, difficult to understand or reverse engineer, and inefficient). Although I have not yet explored any deep evolutionary paths with the system, nor analyzed many of the evolved genotypes, I see no reason to doubt this expectation.
On the other hand, it had not occurred to me that the phenotypes would also be so unlike something a human artist would design. Although I expected some randomness in the phenotypes, after using the prototype a bit, it seems that the evolved entities tend to be rather "messy" and visually noisy or busy. I was somewhat disappointed by this. It seems to me that, although some of the entities evolved with the system might be considered beautiful (e.g. involving pleasant colour shading, or "sparkling" colour/motion effects), none of them are elegant, and only in very simple cases can the user fully grasp what the genetic program is doing by watching how the phenotype reacts to mouse motion. In this sense, it seems that the entities fail at being true reactive graphics, which (when designed by a human) often exhibit a cleverness that may surprise at first, but that can be understood if the user interacts with the graphic for long enough. Although the artificially evolved forms could be used as part of a true artistic process, and/or serve as inspiration, I feel nevertheless that, by themselves, they don't amount to very interesting art.
Finally, I had hoped that, by providing an array of mouse positions as input to the programs, and the ability to implement loops within the language, I might be able to evolve entities that draw different kinds of "tails" trailing behind the cursor, like different kinds of strings following a kite, involving sequences of shapes and/or colours etc. This seems to have largely failed. After very few mutations away from the program for Figure 2, for example, there is no visible trace left of any coherent, continuous effect of the sequence of mouse positions fed into the programs. Although multiple mouse positions may be indeed used by a program, it could be in a convoluted, inelegant way, such as: the x coordinate of the first position controls part of the colour for drawing something, and the y coordinate of the next point determines by how many statements a JMP statement will jump, etc. I suspect that new commands or control structures could be introduced into the language that would encourage the kind of cursor-trail-drawing behaviour I had hoped for, by making it easier to implement the behaviour, and by making this behaviour more robust across mutations. However, building in such behaviour would feel like cheating in a way, and would also limit the system and constrain it against discovering other, perhaps more interesting or more original, behaviours.