Archive for October, 2011

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.

There’s little doubt that gaming is moving towards the mobile and social platforms, and every day there is a new piece of analysis or opinion re-iterating this and suggesting bad times ahead for the console development houses and publishers.

There’s a very detailed presentation here from Digi-Capital which provides a good review of the state of play and who’s investing where.  In summary, there are four main ways to get revenue from consumers:

  1. Massively Multiplayer Online games, like World of Warcraft, where people pay a subscription of £10 a month and generally play for 15 hours a week on a PC.
  2. Classic computer games, usually bought on a CD / DVD in a shop for about £40, although moving towards download services which opens it up to independent game developers.  Played on XBox, Sony, Nintendo, PC.
  3. Mobile games, sold for about $1 – $10 on iPhone, Android, BB etc.  Usually much smaller experiences, can be built very quickly, and use features of the phone to create new fun games.
  4. Social games, which are usually websites, most often built in flash and available free to the customer and supported by advertising.  Now transitioning into the social networks where more casual gamers use the game as a way to interact with friends.

It should be noted that while there are a lot of people declaring the end of the console, in actual fact this sector has a lot of loyal gamers, and while they may decide to buy one less game a year due to having less pocket money (or having spent it on a few Angry Birds mobile games), console games remain a multi billion dollar industry still larger than the film industry.

However it cannot be denied that the mobile and social gaming markets are growing incredibly fast, from small independent studios through to the larger publishers translating existing game characters to the new platforms weekly.  While growth is good, there may be a note of caution attached to looking at the current top players.

Zynga are the hottest company in social gaming with ridiculous growth and early signup stats, yet players seem to be moving on, and not often coming back, causing problems for Zynga’s intended IPO this Christmas.  This may be a factor of the simplistic nature of the current crop of social games, certainly there are high expectations of more sophisticated social games such as Civilisation, which may usher in a wave of traditional games to be ‘socialised’ and push the boundaries of what’s possible with friends.

Another high profile company is Rovio, makers of Angry Birds, who have made many other games yet are concentrating on building up the Angry Birds property through as many merchandising deals as possible.  One reading from this is they feel that it will be hard to replicate their initial success with another game franchise, even with their own advertising network of 400 million users.  The obvious alternative is that now they have established characters with a whole generation of casual gamers, they’d be crazy not to cash in with the merchandising, and don’t need to rush out anything which won’t be at least as successful as their last hit.

Either way, both companies are providing entertainment and inspiration for developers and investors alike, the mobile and social platforms are becoming firmly entrenched as respectable gaming environments, and together this should ultimately breathe new life into the gaming industry and open it’s doors to a new generation of players.

Jetpack Joyride

I’ve been a game player for many years, although these days don’t have the time to sit down for hours at end in front of an XBox or PC, so now my gaming is limited to game ‘snacks’ generally on my iPhone.  This is a trend is causing a fair amount of turmoil in the games industry, as the large development houses who employ hundreds of designers, programmers and testers to build large games are finding that gamers are moving to mobile and social games and taking their revenue with them.

Mobile and social games are competing in a crowded marketplace, and have to reduce development costs to a minimum in order to survive.  A hugely successful way of doing this is to make use of PCG to develop game infinite game content, another is to get the players to generate their own content for friends (more on this another day).

A great example of PCG in games is Halfbrick Studios Jetpack Joyride, available on the Apple App Store.

The player has managed to steal a jetpack from a secret development facility, and needs to find a way out.  In this case there are a number of hazards including rockets, zappers and laser beams, however rather than these being placed by a human designer in increasing difficulty, the game itself decides when and where to introduce the dangers based upon a number of rulesets.  While this could become repetitive, the game developers have made use of fast pacing, a quick restart, a variety of powerups, varying challenges and in game currency to keep players interested.

As independent game studios are on the increase I’m sure we’ll see a lot more of PCG content on mobile and social gaming platforms.

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.

Route Planning: A*

The first week of the Stanford AI Class focused on route planning.  This is a pretty standard problem in computer science, with a number of well known solutions, including depth first and breadth first tree searching (it either means something to you or you really shouldn’t care).  Both of these have the drawback of taking a while to focus on the best route, so by simply applying a heuristic (a guess) to the remaining distance from each tested location, the algorithm should focus on the best path faster.

This slideshow requires JavaScript.

Here’s a few screenshots of the A* at work – blue is the starting point, pink the finish, yellow the tiles tested, and white the optimum path.

In this case there is a bug which means something is out of whack.  Unfortunately Processing (the language I’ve been using as a demo tool) doesn’t have much in the way of debugging, so I’m going to have to move to C++ or Java in XCode or Visual Studio.  It’ll take a while to transition this code, so I may as well head down the C++ route (in my opinion more useful as it allows me to easily port code to the iOS devices).

As an example of how procedural content generation (PCG) works, I’ve created a little demo.

In this case the level genotype is a random number, which the unpacking algorithm uses to mine out a level map.  Entering the same number as a seed creates exactly the same level, however the simple algorithm provides millions of variations on the level.  Granted, at this stage there is not much to tell one level from another other than geometry, but it should be easy to see how the geometry could be varied over time, and of course there is nothing restricting the technique to a grid pattern.

This second video has a minor modification, the algorithm back fills any areas it finds that are almost completely surrounded by space, which allows the map to look a little more natural.

Perlin Noise

Perlin noise is an algorithm for generating gradients in 1, 2 or 3 dimensions, largely by overlaying ‘octaves’ of noise over itself at varying frequencies.  The end result is that we can use this for creating seemingly random but realistic looking textures and fractal landscapes very easily.

The first video is a generic 3 octave Perlin noise gradient.

We can easily turn this into a 3d model, the following shows how this works by using frequency cutoffs to create terrain lines.

AI Test Environment

A test bed is needed to try out various AI virtual world generation techniques.  To this end I’ve put together a little system that consists of:

  • A server, which generates a map (very simple right now) and manages a number of simple AI’s (currently looking like Medusa)
  • A dispatcher, which passes messages between the server and clients
  • A client, which allows any number of players to join in on the fun from different locations.

The system has been built so that an AI can join in as a player, we can then run more complex AI’s from the same or other servers.

At the moment this uses images from a computer game I enjoyed many years ago, these will be updated shortly as the rest of the game develops.

With 2 players:

Source code to follow once I’ve got the right images in there.

Software agents are as much a creature of their environments as all creatures on earth are. We have been created by constant evolution brought about by surviving our environment, competing with other entities and succeeding to procreate new generations.

In order to create and evaluate software agents we need to create environments to test them in.

  • International Aerial Robotics Challenge – there have been six challenges set to date of increasing complexity, it’s absolutely amazing what the state of the art in robotics can achieve. The last solved challenge asked teams to build a completely autonomous drone which, without prior knowledge of the environment, flew into an unmanned nuclear facility, identified and located the control room, and sent pictures of the control instrumentation out to a second unmanned drone.  The next challenge is to enter an unknown territory and locate a USB key holding sensitive data:
  • The DARPA Grand Challenge – creating a driverless car which will traverse across unknown terrain, which has been successfully with a variety of different technologies, all of which worthy of further research.  The current challenge is set in an urban environment with other motor vehicles to be successfully negotiated.
  • The NASA Centennial Challenge – to find and retrieve samples of scientific interest in an unknown environment
  • The RoboCup challenge, which requires teams made up of autonomous robots to win a league against other robots.  The organizers are attempting to lead the way for a robotic team to beat the last winners of the World Cup by 2050.  They’ve got a long way to go:

Of more immediate interest are virtual challenges as these are more accessible for direct testing.

  • The Google AI Challenge – this is the third challenge that asks entrants to submit AI bots to compete with each other in virtual worlds, and the first I have entered.  The first year (Winter 2010) was inspired by Tron, competitors needed to take control of a light cycle and cause the other players to crash.  The second was based upon the game PlanetWars, developed by Galcon, competitors needed to take over planets given a number of spaceships.  This years is based upon ants, and competitors need to develop a hive mind which will grab the most food at the same time as destroying other ant hives, all of which takes up valuable resources.  Entrants build AI bots in pretty much any language they like, then submit them to the competitions central servers to be pitted against other agents.
  • Core Wars – A game that could only be thought up by a computer scientist.  Build a set of instructions which are let loose in a simulated computer memory stack, which then compete against other instruction sets to take over the whole memory.  Sounds very geeky but some ingenious entrants.
  • Mario AI Challenge – using an adapted version of Super Mario 3 for the Nintendo, build a software bot that can complete any level thrown at it.  As interesting as the entrants are, the game environment (Super Mario Infinite) is an excellent example of Procedurally Generated Content (more on this later).
  • The StarCraft AI Challenge – StarCraft is a real time strategy game that is celebrated as one of the most hectic and evenly balanced computer games of all time.  In Asia, specifically Korea, this is an international sport.  Most video games can be seen as challenges for AI, with a bot taking over the role of the human player.  All that is needed is an API so that the AI can understand what is happening in the game and relay instructions back to the game (although in some cases a lack of API can be overcome by screenscraping, and this in itself is an area of research as in some real world cases it may be easier to translate a video output than retrofit an API).  The interestig thing about StarCraft is the wealth of information that needs to be processed, the number of available strategies (pretty much infinite) and the real time nature of the game – this is far more complex than chess, although with the luxury of being able to ponder the next move for half an hour.  Here’s a video of a software AI playing (and beating) one of the top ranking players worldwide.
  • Many games open up API’s to allow AI builders to modify or completely recreate AI’s that play against the human player – one very sophisticated and challenging example is Civilization IV, and develop fans have taken to building an open source version called FreeCiv, which allows whole worlds to be built with independent AI’s for those with the time.

Pretty much every video game genre from poker through space and trading simulations, role playing games to first person shooters and platform games, can be used as a test bed for developing and evaluating AI techniques.

Computer games represent a vast number of artificial intelligence routines, and many people are attracted to the video games industry as the ultimate creative and technical software challenge.  While the computer game industry is very competitive and as such most of the technical development experience doesn’t make it into the public domain, occasionally people like to give something back to help out others.

There are a number of online resources for this, including GamaSutra (the art of making games), AIGameDev (run by Alex, a very chilled and wise guy), AI Wisdom and others, the games industry does have a regular magazine called, obviously, Game Developer.

In order to get a picture of the state of the art in Game Development, a quick review of the last few years Game Developer magazines, looking for articles relating to Procedurally Generated Content or Virtual Agents.

  • December 2004, page 40, optimizing pathfinding at low levels
  • June 2006, page 30, blob physics
  • December 2007, page 16, Multi User Dungeons & MMO’s
  • Feb 2008, page 16, creating waves in game
  • March 2008, page 32 – MapZone, creating procedural textures
  • April 2008, Page 36, Intelligent Mistakes, AI
  • September 2008, page 48, Game economies
  • March 2009, page 14 – Using particle systems for terrain modeling.  Basic concept is like comets hitting the earth
  • June/July 2009, page 14 – Procedurally Generated Content in space games
  • August 2009, Page 40 – Procedurally Generated flowers
  • September 2009, page 7, building worlds with voxels (3d pixels)
  •  Feb 2010, Page 40, Procedurally Generated Content
  •  Feb 2010, page 48, Procedurally Generated plants, trees and models
  •  August 2010, Page 8, how to build social games
  •  January 2011, Page 48, techniques for better AI
  •  Feb 2011, page 24, interview about Minecraft, a breathtaking use of procedurally created worlds
  •  April 2011, page 21 – Procedurally Generated Content with Minecraft and perlin noise
  •  Career Guide Fall 2011, page 12 – Useful path finding techniques
  •  August 2011, page 6 – random generation of structures

Apologies for not putting in any more context, however if you’re interested then you’ll know where to go to find out more…