Category: PCG


Procedural Textures

Generating textures for games and virtual worlds is a time consuming task, to give you an example any big budget film or game may have well over 50% of the development budget assigned to creating 3d models and the images which cover them to make them realistic.

I’ve talked about procedural content generation before, but to give you an idea of it’s capabilities is a picture generated by the Graphic Designer Toolbox.

Looks pretty creepy, but the interesting thing is that it is created by a few blocks of mathematical algorithms rather than designed by hand.  Simply swapping in different algorithms can create entirely different effects, from clouds, to cities, mountains, deserts, and many other instantly recognisable features.  The effort required to generate a tool box of features may be large, but once you have the toolbox and can begin chaining effects, a single skilled designer can outperform a team very quickly. Modern films such as Avatar used this along with other PCG techniques to generate a whole alien worlds fauna and flora – without such methods it simply would not have been possible.

SketchaWorld

The current generation of games and virtual world applications require vast amounts of content to be considered believable, all of which takes designers, graphics artists and 3d modellers to put in place.

As the expectations of consumers rise, the cost of creating this content increases exponentially.  This is one reason that Procedurally Content Generation is of high value to the next generation of games and virtual world applications, whereby programmers design algorithms that create infinite worlds of all shapes and sizes.

One major issue with PCG is that sometimes the results can be ugly, boring, or unplayable.  Another is that it is can be difficult to direct the creation of a world without an underlying knowledge of how the abstract code works, which can be difficult for a designer to manipulate.

Ruben Smelik from the Delft University of Technology has just successfully defended his PhD in a Declarative Approach to Procedural Generation of Virtual Worlds, which makes very good reading for those interested in the subject.

Ruben has also built an application which immediately shows the simplicity and potential for successful PCG – SketchaWorld.

I am intending to apply the NEAT algorithm to this approach of building worlds, either a a direct (using HyperNEAT) or indirectly via softawre agents under the control of evolved neural networks.

In 2002 Ken Stanley and Risto Miikkulainen presented an evolutionary method for developing solutions using Neural Networks – NeuroEvolution of Augmenting Topologies, or NEAT. This technique, while relatively new, takes inspiration from natural evolution and has been used in a number of very interesting applications from agent control through to creation of new music and art forms.

It’s an area of research that is highly relevant to my work, and to better understand the topic I’m putting together an implementation in Objective C, the preferred language for Mac and iOS devices.  As an introduction to the topic and for other students I’ve put together a brief presentation on the subject.

Presentation on NEAT

Since then Ken has moved on to the Evolutionary Complexity Research Group (EPLEX) at the University of Central Florida and extended the research in a number of ways, the most interesting to me being in the search for novelty.  Ken has a website that shows some of the directions and algorithms, and to get an idea of where it is heading I’d recommend his Keynote speech from the 2010 SPLASH conference.

Subversion RIP

It’s a great shame to hear that Introversion Software, a London based indie game developer, have decided to put on hold Subversion, a game of great interest to anyone involved in PCG.  The company has decided to take some of the technology they built for the project and focus on another game called Prison Architect, which should be good news as they’ll undoubtedly be making sensible commercial decisions.

There is a full interview here, and has many topics worth considering for an indie developer, or anyone involved in PCG.

  1. Worlds and Levels created by PCG techniques are, more often than not, really boring to play.  This is a biggie – you can make a computer generate the most beautiful landscapes, plants and water features, but this stuff has a tendency to repeat itself to infinity, which is no fun at all.  Even the makers (well publishers) of Elite limited the number of galaxies from the possible 256 million to only 8, on the basis that the player would lose all interest in the ridiculous scale.  Successful PCG games like Minecraft ensure that the players can design their own unique architecture over the world of mathematics, this generates interest for other players.
  2. Making something more realistic does not make it more fun.  Everyone knows that the KISS (keep it simple stupid) mantra is the most important in UI, UX, product, game, or pretty much any other design, however it’s very difficult for an artist to follow this simple rule, even more so when there is an elegance to making the environment fully integrated to the point otherwise designed laws naturally emerge.  I’ve been following Introversion for a long time and I can see the quandary they would have been in: as proponents of PCG as a necessity to make up for lack of human level designers, it became more tempting to generate everything well past the position of utility.
  3. It’s a highly complex (possible unsolvable) problem to simulate architecture that would otherwsie been created by a human (or even animal) builder.  The most immediate uses of PCG may be as a tool to generate ideas that human (or crowd of) designers then curates by selecting and modifying into something useful.

The direction of my research is in creating software agents that can assist human designers (or crowds of them) generate more interesting levels, either by evaluating the raw creations of PCG, or perhaps by simulating human behavior in shaping their environment, or even learning how designers create content and replicating these fuzzy techniques.  Introversion software have been pioneering these techniques for many years, and so I wish them the best in commercial success with Prison Architect so they have more time to play with creating virtual worlds.

Plant Growth

Generating plants and fauna has been one of the primary successes of computer graphics over the last few decades, most people would be surprised at how often the plants in a film or advert are virtual copies of the real thing.

A simple way to create plants is using Lindenmayer Systems, which take a starting string and over a number of steps re-write the original string based upon simple rules.

So for example we could start with the character A and every time we iterate we replace the letter A with AB, and if we find a B we replace it with letter A. This gives us a series that looks like:

A
AB
ABA
ABAAB
ABAABABA
ABAABABAABAAB

and so on.  Visually we could change the characters to directions for an image drawer (things like turn left, turn right, draw forwards) and instantly we’ve produced some nice little snowflakes.

We can generate all sorts of interesting shapes by making tiny additions to those initial rules, such as adding the ability to jump spaces without drawing, changing colour, all in all a very simple way to make some familiar looking patterns.

Where things get more dynamic is if we allow the algorithms to maintain a stack of visited matrices, which means to branch, a bit like trees.

Move into the realm of 3D and we begin to get some very lifelike trees.  Of course trees are not made up of identical sticks from root to branch, so we need to add in a little stochastic sampling (randomness in the growth) as well as the idea that the tree will grow seasonally, and a trunk will grow differently to a branch, a leaf or a flower, however all of this can be managed with some imagination.

To get an idea of how far this has come, check out the virtual arboretum managed by SpeedTree, a company which specializes in dreaming up virtual fauna.  To get some more details of how the magic happens, I’d recommend The Algorithmic Beauty of Plants by Przemyslaw Prusinkiewicz and Aristid Lindenmayer.

 

Genetic Algorithms

Genetic Algorithms provide computers with the solve all manner of problems by following the simple principles of natural evolution, largely by breeding virtual programs, allowing them to compete at solving a problem, then selecting the best to reproduce and create a new generation of possible solutions.

I first came across this concept while reading The Blind Watchmaker by Richard Dawkins, a book I cannot recommend highly enough – while it focuses on the evolution of life, it provides insight on all manner of subjects.  In the book Richard Dawkins introduces Biomorphs, a computer program he wrote that would take a simple genotype (a coded sequence similar to a DNA string) use it as a seed for a development algorithm which would result in a phenotype (in this case images which bore striking resemblances to insects or plants).  A few examples from his book:

Without going into the technical details, genetic algorithms such as have the potential to solve all sorts of problems faster than random searches or even human design.  Some applications include:

  • Acoustics, in the design of amongst other things opera houses and high fidelity speaker cone enclosures  for optimum sound reproduction
  • Engineering, for example car and wind turbine shapes for aerodynamics
  • Astronomy, in the identification of undiscovered star systems
  • Electrical Engineering, in all manner of chip design optimisations
  • Financial Markets, in many cases outperforming traders predicting market changes
  • Playing games such as Chequers, to the level that within a relatively small number of generations can beat any but the most expert players.
  • Military and other logistical planning, both areas where it is used to aid human decisions in summarizing a near infinity of variables.
  • Data mining or search, particularly in areas where the data sets are so vast that patterns simply cannot be put forward or tested by simpler techniques (including skilled humans) with any hope of success.
  • Recognition of patterns and objects in images.
  • Developing agent and team behavior, used in many computer games and real world competitions such as RoboCup.

My interest in the field is as an underpinning to the main subjects of my research, right now focusing on the use of agent intelligence and procedural content generation to create digital content such as environments, worlds, graphics, music and virtual characters and agents.

These require slightly different use of Genetic Algorithms than in the above examples – generally GA’s are able to find a solution to a given problem when this can be expressed formally (such as a mathematical sum) however in general are not optimised for finding a solution that is based upon taste, fashion or other qualities that are difficult to quantify. They do, however, provide a mechanism to help a human designer create and evaluate such content, an area which traditional procedural content generation techniques have been criticized for being unable to do.  An early example of this happening comes courtesy of Karl Sims from a contribution to the SIGGRAPH 5 years after the Blind Watchmaker was published.

This slideshow requires JavaScript.

To get an idea of the state of the art have another look at Avatar, pretty much 90% of what you see on screen was created using GA graphic techniques.

Inventing the Future of Gaming

The University of California recently held a public talk regarding the use of Procedural Content Generation (PCG) in games.

This highlights the growth of interest in PCG within the gaming development sector, which will inevitably overflow into other media as the cost of creating interesting content increases.  There has been a long held skepticism that PCG cannot create truly engaging content, however with a renewed focus on machine learning techniques and the use of PCG to aid a human designer (either singular or through group collaboration) this problem is being overcome.

Jim Whitehead, Professor of Computer Science and founder of the game design degree at UCSC, took up that thread when he talked about Infinite Games: Procedural Content in Game Design. He noted that computers can generate amazing shapes and patterns, and can be creative by themselves or with people. Procedural content generation can use the computer to augment a designer’s insights. In fact, the Augmented Design Laboratory at UCSC has several projects underway with procedural content generation. Tanagra is a 2D platformer design tool that works with a human to generate levels. Further on, what if a player is providing input to a procedural content generator, rather than a designer? Levels could be generated automatically based on the player’s actions. In other words, infinite content.

The full article can be found here.

Follow

Get every new post delivered to your Inbox.