Genetic Programming Applied to Interactive Art:

Interactive Evolution of Reactive Graphics

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)

Summary

This report describes the use of genetic programming to synthesize abstract, interactive "artwork". Similar to Karl Sims' SIGGRAPH 1991 work, the artwork, or phenotype, derived from each genotype is a 2D image, however unlike Sims' static images, these images respond interactively to input from the mouse.

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.


Introduction, Motivation, and Background

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.


Approach

As with other artificially evolved art, the selection of mutated genetic sequences is done interactively by the user, rather than by an offline algorithm. This is because (1) evaluation of art is subjective, (2) the tastes and goals of the user may change from one session to another and would be difficult to capture algorithmically, and (3) in participating directly in the evolutionary process, the user can accidentally discover forms they had not imagined and pursue their evolution further by selecting them.

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.


Implementation

The prototype was implemented in C++ using standard POSIX routines, STL, OpenGL, and GLUT on linux, and would port trivially to MS Windows. Various pieces of code were re-used from previous projects by the author for generating random numbers, storing and manipulating images, and drawing with OpenGL in 2D. The main class written for this project was a Genotype class, which stores the genetic sequence of an individual, and has methods for

Genetic Instruction Set and Virtual Machine

In designing the language of the genetic code and the virtual machine for interpreting it, inspiration was taken from assembly languages and their use of low level instructions, an instruction pointer, and registers for storing data.

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_n
Arguments 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 literal1
stores 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 variable3
and 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.

Mutation and Crossover

Mutations are performed on a single genetic sequence to produce offspring. The set of potential mutations should, at the very least, make it possible to reach any other valid genetic sequence, given sufficient patience on the part of the user and an appropriate sequence of selections. The mutations implemented in the prototype actually exceed this criterion, and, following Sims' example [16], allow for a variety of mutations to occur, each controllable by programmatically tuning its rate of occurrence.

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.


User Interface

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

The number of rows, columns, and image size are adjustable at runtime, and update if the window is resized.

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).


Early Results

Due to time constraints, I spent much more time writing the code for the prototype than evolving entities with it. I present here only output produced after very few generations (i.e. after 1-20 generations or so). Many parameters in the prototype could be tuned, and much exploration should still be done of the space.

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.
Increasing the mutation rate to too high a value causes the length of the mutated children to grow very large and bog down the system. This is because one of the potential mutations chooses a random block of random length to duplicate, and repeating this mutation causes the overall sequence length to grow exponentially.

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

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
and then mutated over 2 generations yielding many interesting variations (Figure 6).

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.

Lessons, Speculations and Implications

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.


Potential Enhancements and Future Directions

Some ideas for extending this work:

References

  1. Csuri: Computer Artist. http://www.siggraph.org/artdesign/profile/csuri/ See also http://www.csuri.com
  2. Joshua Davis. http://www.joshuadavis.com/
  3. Richard Dawkins. The Blind Watchmaker. 1986. Related website: http://www.world-of-dawkins.com/Dawkins/Work/Software/software.shtml
  4. Sam Kaufman. An evolutionary-art generator. http://individual.utoronto.ca/sam/evo/evo.html
  5. Golan Levin et al. The Alphabet Synthesis Machine. http://alphabet.tmema.org/
  6. Jörn Loviscach. Qbist. http://www.heise.de/ct/Redaktion/jl/projects.html
  7. Problem sets by John Maeda, and solutions by his students, for the MIT Media Lab course MAS 964 (Fall 1996): Principles of Visual Interface Design. http://acg.media.mit.edu/courses/mas964/
  8. John Maeda. Design By Numbers. MIT Press, 1999. 256 pages.
  9. John Maeda. Maeda @ Media. Rizzoli, 2000. 480 pages.
  10. maedastudio. http://maedastudio.com/
  11. Malcolm McCullough. Abstracting Craft. MIT Press, 1998. 336 pages.
  12. Michael J. McGuffin. (A collection of experimental graphic design work implemented as Java applets.) http://www.dgp.utoronto.ca/~mjmcguff/portfolio/experiments/
  13. John Mount et al. Genetic Art IV. http://mzlabs.com/gart/g4.html
  14. Yugo Nakamura. http://surface.yugop.com/
  15. Rhizome. http://rhizome.org/
  16. Karl Sims. Artificial evolution for computer graphics. Proceedings of ACM SIGGRAPH 1991. pp. 319--328 http://doi.acm.org/10.1145/122718.122752 Related website: http://www.genarts.com/karl/genetic-images.html
  17. Karl Sims. Evolving virtual creatures. Proceedings of ACM SIGGRAPH 1994. pp. 15--22. http://doi.acm.org/10.1145/192161.192167
  18. Soulbath. http://www.soulbath.com
  19. Stephen Todd and William Latham. Evolutionary Art and Computers. 1992. Related website: http://www.scit.wlv.ac.uk/events/latham.html
  20. Anson Vogt. http://phong.com