Particle Systems
Weapon projectiles in GAR are particle systems, which are commonly implemented in modern video games and movie graphics to represent fuzzy or non-solid objects. A set of complex mathematical "rules" controls each particle in a system. Coding the algorithms and tools to manipulate particle behavior to satisfy the developers (and ultimately the users) can be a complex and time-consuming aspect of game development. However, in GAR, the game itself creates the particle weapons, relieving developers of the effort entirely. Thus particle systems in GAR are a symbol for difficult-to-design content in general, which will someday be possible to evolve as well.
To automatically generate interesting particle weapons, there is a need for an efficient approach to both representing and evolving the rules of the particle system behind the weapons. The representation in GAR is called Compositional Pattern Producing Networks, or CPPNs.
Compositional Pattern Producing Networks
CPPNs are a special type of Artificial Neural Network (ANN) that have proven effective at encoding patterns, for example in evolutionary art and music. CPPN-controlled particle systems can potentially generate an infinite variety of particle behaviors. However, there is a need for an algorithm to evolve them to create effects that people will like. An effective method for evolving CPPNs is Neuro-Evolution of Augmenting Topologies (NEAT). Below is screenshot from NEAT Particles, a program created before GAR in which CPPN-controlled particle systems can evolve complex effects.
NEAT
The NEAT method evolves CPPNs by starting from minimal structure. As evolution progresses, CPPN topology may be augmented by either adding a neuron along an existing connection, or by adding a new connection between previously unconnected neurons. The picture below shows a generation of new particle systems evolved by NEAT Particles.
CPPN Weapon Evolution
As increasingly complex CPPNs are evolved by NEAT, increasingly sophisticated weapon behaviors are produced by the CPPN-controlled weapon systems. During the game, players periodically find new CPPN weapons. Because their ships have a limited number of storage slots, players will be forced to discard less favorable weapons and keep only what they consider the best.
New weapons are generated by the cgNEAT (content-generating NEAT) algorithm, a variant of the standard NEAT algorithm, based on the weapons currently in use by the player population. Thus, players will decide the course of weapon evolution in the game by using or discarding weapons. Thus the game implicitly encourages a collaborative form of Interactive Evolutionary Computation (IEC), even though players do not need to understand this evolutionary process to contribute to it.
Implications
The aim of GAR is to demonstrate that automated content generation can be viable in a main-stream type of game. Similar techniques could be employed to generate many other types of graphics and game content, such as 3-D models, textures, or programmable shader effects. Such an automated technique might be especially suited to Virtual World or Massively Multi-Player (MMOG) games in which large amounts of content are required and unique content is coveted by players.
Publications
The following links provide additional information about technologies used in GAR.
- IEEE CIG Journal Paper: Describes in detail cgNEAT and multiplayer procedural content generation in GAR.
- CIG Conference Paper: Reveals the inner workings of GAR, focusing on initial single player content generation results. Best Paper Award CIG 2009.
- AIIDE Demo Paper: A short 2-page description with some images for the GAR demo at AIIDE.
- SIGEVO Article: A feature on GAR in the quarterly newsletter of the ACM Special Interest Group on Genetic and Evolutionary Computation.
Evolving Particle Systems
The system of evolving particle systems in GAR is based on the techniques described in this paper.
Compositional Pattern-Producing Networks and Artificial Neural Networks
CPPNs, a form of ANN, power the weapons in the game.
- CPPNs on Wikipedia
- Picbreeder: evolve your own CPPN-encoded pictures online
- Research Paper on CPPNs
- CPPN Activation Functions
Interactive Evolutionary Computation
IEC is a process through which evolutionary or genetic algorithms are guided by human input rather than traditional fitness functions. Weapons in the game evolve by a form of collaborative IEC.
Neuroevolution of Augmenting Topologies
NEAT is a neuroevolution algorithm that evolves CPPNs and ANNs. The CPPNs that power the weapons in GAR are evolved by a special variant of NEAT called content-generating NEAT (cgNEAT)
Neuro-Evolving Robotic Operatives Game
NERO is another video game based on a variant of NEAT. NERO uses real-time NEAT (rtNEAT) to evolve the behaviors of robots in real-time. In NERO, players evolve robotic army AI by training them to complete objectives. Players can pit their trained armies against each other in a battle royale.
Particle Systems
Particle systems are the de-facto technology for creating effects such as fire, smoke, energy, explosions, and many other "fuzzy objects" in computer graphics and games. NEAT Particles is a predecessor to GAR that allows users to evolve particle systems through a simple interface.