Published Papers

Paper: SIG Evolution Article

Authors: Erin J. Hastings and Kenneth O. Stanley

Published in: Newsletter of the ACM Special Interest Group and Genetic and Evolutionary Computation (SIGEVO 2009 Volume 4)

Summary: A higher-level overview of Galactic Arms race, the cgNEAT algorithm, and the potential applications of evolving video game content.

Paper: Evolving Content in the Galactic Arms Race Video Game

Authors: Erin J. Hastings, Ratan K. Guha, and Kenneth O. Stanley

Published in: IEEE Transactions on Computational Intelligence and AI in Games 2009

Keywords: procedural content generation, Galactic Arms Race, cgNEAT, particle systems

Abstract: Simulation and game content includes the levels, models, textures, items, and other objects encountered and possessed by players during the game. In most modern video games and in simulation software, the set of content shipped with the product is static and unchanging, or at best, randomized within a narrow set of parameters. However, ideally, if game content could be constantly and automatically renewed, players would remain engaged longer. This paper introduces two novel technologies that take steps toward achieving this ambition: (1) A new algorithm called content-generating NeuroEvolution of Augmenting Topologies (cgNEAT) is introduced that automatically generates graphical and game content while the game is played, based on the past preferences of the players, and (2) Galactic Arms Race (GAR), a multiplayer video game, is constructed to demonstrate automatic content generation in a real online gaming platform. In GAR, which is available to the public and playable online, players pilot space ships and fight enemies to acquire unique particle system weapons that are automatically evolved by the cgNEAT algorithm. A study of the behavior and results from over 1,000 registered online players shows that cgNEAT indeed enables players to discover a wide variety of appealing content that is not only novel, but also based on and extended from previous content that they preferred in the past. Thus GAR is the first demonstration of evolutionary content generation in an online multiplayer game. The implication is that with cgNEAT it is now possible to create applications that generate their own content to satisfy users, potentially reducing the cost of content creation and increasing entertainment value from single player to massively multiplayer online games (MMOGs) with a constant stream of evolving content.

Paper: Evolving Content in the Galactic Arms Race Video Game

Authors: Erin J. Hastings, Ratan K. Guha, and Kenneth O. Stanley

Published in: Proceedings of the IEEE Symposium on Computational Intelligence in Games (CIG'09)

Keywords: procedural content generation, Galactic Arms Race, cgNEAT, particle systems

Abstract: Video game content includes the levels, models, items, weapons, and other objects encountered and wielded by players during the game. In most modern video games, the set of content shipped with the game is static and unchanging, or at best, randomized within a narrow set of parameters. However, ideally, if game content could be constantly renewed, players would remain engaged longer in the evolving stream of novel content. To realize this ambition, this paper introduces the content-generating NeuroEvolution of Augmenting Topologies (cgNEAT) algorithm, which automatically evolves game content based on player preferences, as the game is played. To demonstrate this approach, the Galactic Arms Race (GAR) video game is also introduced. In GAR, players pilot space ships and fight enemies to acquire unique particle system weapons that are evolved by the game. As shown in this paper, players can discover a wide variety of content that is not only novel, but also based on and extended from previous content that they preferred in the past. The implication is that it is now possible to create games that generate their own content to satisfy players, potentially significantly reducing the cost of content creation and increasing the replay value of games.

Paper: Demonstrating Automatic Content Generation in the Galactic Arms Race Video Game

Authors: Erin J. Hastings, Ratan K. Guha, and Kenneth O. Stanley

Published in: Proceedings of the Artificial Intelligence and Interactive Entertainment Conference Demonstration Program (AIIDE'09)

Keywords: procedural content generation, Galactic Arms Race, cgNEAT, particle systems

Abstract: In most modern video games, content (e.g. models, levels, weapons, etc.) shipped with the game is static and unchanging, or at best, randomized within a narrow set of parameters. However, if game content could be constantly renewed, players would remain engaged longer. To realize this ambition, the content-generating NeuroEvolution of Augmenting Topologies (cgNEAT) algorithm automatically evolves novel game content based on player preferences, as the game is played. To demonstrate this approach, the Galactic Arms Race (GAR) video game, which incorporates cgNEAT, will be presented. In GAR, players pilot space ships and fight enemies to acquire novel particle system weapons that are evolved by the game. The live demo will show how GAR players can discover a wide variety of weapons that are not only novel, but also based on and extended from previous content that they preferred in the past. The implication of cgNEAT is that it is now possible to create games that generate their own content, potentially significantly reducing the cost of content creation and increasing the replay value of games.

Paper: Interactive Evolution of Particle Systems for Computer Graphics and Animation

Authors: Erin J. Hastings, Ratan K. Guha, and Kenneth O. Stanley

Published in: IEEE Transactions on Evolutionary Computation 2009

Keywords: Interactive Evolutionary Computation, IEC, NeuroEvolution of Augmenting Topologies, NEAT, particle systems

Abstract: Interactive Evolutionary Computation (IEC) creates the intriguing possibility that a large variety of useful content can be produced quickly and easily for practical computer graphics and gaming applications. To show that IEC can produce such content, this paper applies IEC to particle system effects, which are the de facto method in computer graphics for generating fire, smoke, explosions, electricity, water, and many other special effects. While particle systems are capable of producing a broad array of effects, they require substantial mathematical and programming knowledge to produce. Therefore, efficient particle system generation tools are required for content developers to produce special effects in a timely manner. This paper details the design, representation, and animation of particle systems via two IEC tools called NEAT Particles and NEAT Projectiles. Both tools evolve artificial neural networks (ANN) with the NeuroEvolution of Augmenting Topologies (NEAT) method to control the behavior of particles. NEAT Particles evolves general-purpose particle effects, whereas NEAT Projectiles specializes in evolving particle weapon effects for video games. The primary advantage of this NEAT-based IEC approach is to decouple the creation of new effects from mathematics and programming, enabling content developers without programming knowledge to produce complex effects. Furthermore, it allows content designers to produce a broader range of effects than typical development tools. Finally, it acts as a concept generator, allowing content creators to interactively and efficiently explore the space of possible effects. Both NEAT Particles and NEAT Projectiles demonstrate how IEC can evolve useful content for graphical media and games, and are together a step toward the larger goal of automated content generation.

Paper: NEAT Particles: Design, Representation, and Animation of Particle System Effects

Authors: Erin Hastings, Ratan Guha, and Kenneth O. Stanley

Published in: IEEE Symposium on Computational Intelligence and Games (CIG'07)

Keywords: particle systems, IEC, NEAT

Abstract: Particle systems are a representation, computation, and rendering method for special effects such as fire, smoke, explosions, electricity, water, magic, and many other phenomena. This paper presents NEAT Particles, a new design, representation, and animation method for particle systems tailored to real-time effects in video games and simulations. In NEAT Particles, the NeuroEvolution of Augmenting Topologies (NEAT) method evolves artificial neural networks (ANN) that control the appearance and motion of particles. NEAT Particles affords three primary advantages over traditional particle effect development methods. First, it decouples the creation of new particle effects from mathematics and programming, enabling users with little knowledge of either to produce complex effects. Second, it allows content designers to evolve a broader range of effects than typical development tools through a form of Interactive Evolutionary Computation (IEC). And finally, it acts as a concept generator, allowing users to interactively explore the space of possible effects. In the future such a system may allow content to be evolved in the game itself, as it is played.

Paper: A Scalable Technique for Large Scale, Real-Time Range Monitoring of Heterogeneous Clients

Authors: Erin Hastings and Ratan Guha

Published in: Proceedings of the 3rd International Conference on Testbeds and Research Infrastructures for the Development of Networks and Communities (TridentCom'07)

Keywords: range monitoring, multi-level spatial hashing, mobile object database, continuous query

Abstract: Range monitoring is the continuous query on location data of mobile, real-world objects in real-time. Such real world objects are typically wireless, low capability clients. Therefore, tracking techniques must limit client computation and memory overhead, allow for client/server heterogeneity, and most importantly, minimize wireless transmissions. This paper presents a technique for range monitoring based on multi-level spatial hashing. The technique addresses: 1) real-time queries on mobile object locations, 2) real-time query on the proximity of mobile objects in relation to each other, 3) user defined special query areas, and 4) allows for variable levels of mobile client capability (heterogeneity). The spatial hashing-based method presented here provides a level of scalability similar to the best existing methods for client processing requirements, transmission size, and transmission frequency. Additionally, it provides the flexibility of multiple tracking modes, proximity queries, and support for multiple server base stations which other methods may not. The results of a simulation that computes total transmission overhead and data server requirements based on mobile object characteristics are presented.

Paper: Multi-Level SB Collide: Collision and Self-Collision in Soft Body Objects

Authors: Jaruwan Mesit, Erin Hastings, and Ratan Guha

Published in: Proceedings of the International Conference on Computer Games: AI, Animation, Mobile, Interactive Multimedia, Educational & Serious Games (CGAMES'06)

Keywords: soft body simulation, collision detection, animation

Abstract: In interactive 3D graphics collision detection of soft bodies in real time is a significant problem. It is time consuming because soft bodies are composed of possibly thousands of moving particles. Each time step all particles rearrange in new positions according to their behaviors and collision must be detected for each particle. To optimize collision detection in soft bodies, we introduce a solution called Multi-Level SB Collide. The method relies on the construction of subdivided bounding boxes, box hash functions, and contact surfaces. Multi-level SB collide applies multi-level subdivided bounding boxes (AABBs) into a box hash function and uses contact surface method to detect collision. This contact surface can be used to detect both collision with other objects and self-collision in soft bodies. Experimental results show that multi-level SB Collide is an accurate and efficient method for real-time collision detection in soft bodies.

Paper: Optimization of Rendering, Collision and AI Routines in Large-Scale, Real-Time Simulations by Spatial Hashing

Authors: Erin Hastings, Jaruwan Mesit, and Ratan Guha

Published in: Summer Computer Simulation (SCSC'05)

Keywords: spatial hashing, collision detection, frustum culling, picking, AI

Abstract: As simulations grow in scale, optimization techniques become equired to provide real-time response. In this paper we will discuss how spatial hashing can be utilized to optimize many aspects of large-scale simulations. Spatial hashing is a technique in which objects in a 2D or 3D domain space are projected into a 1D hash table allowing for very fast queries on objects in the domain space. Previous research has shown spatial hashing to be an effective optimization technique for collision detection. We propose several extensions of the technique in order to simultaneously optimize nearly all aspects of simulations including: 1) mobile object collision, 2) object-terrain collision, 3) object and terrain rendering, 4) object interaction, decision, or AI routines, and 5) picking. The results of a simulation are presented where visibility determination, collision and response, and an AI routine is calculated in real-time for over 30,000 mobile objects on a typical desktop PC.

Paper: T-Collide: A Temporal, Real-Time Collision Detection Technique for Bounded Objects

Authors: Erin Hastings, Jaruwan Mesit, and Ratan Guha

Published in: Proceedings of the International Conference on Computer Games: Artificial Intelligence, Design, and Education (CGAIDE'04)

Keywords: real-time collision detection, spatial hashing, uniform spatial subdivision, bounding volumes, simulations, games

Abstract: This paper presents T-Collide, a fast, low memory-overhead, low execution-cost, time-based collision detection scheme. It is intended for real-time systems such as games or simulations to optimize collision detection between large numbers of mobile objects. Nearly all aspects of T-Collide are fully customizable to application specifics or implementer preference. T-Collide is based upon Spatial Subdivision, Bounding Volumes, Spatial Hashing, Line Raster Algorithms, and Continuous, or Time-Based Collision.

Paper: Optimized Collision Detection For Flexible Objects

Authors: Jaruwan Mesit, Erin Hastings, and Ratan Guha

Published in:

Keywords: collision detection, multi-resolution method, hash grid function, location tracking, flexible body

Abstract: We present a scheme for collision detection of flexible models. This scheme relies on a multi-resolution technique of: 1) object location tracking to decrease time complexity, 2) the combination of bounding boxes (AABBs) and a hash grid function, and 3) computation of distance domain to determine collision with a contact surface. Experiments show that this approach can efficiently detect collisions in a large set of flexible objects.