The Game AI Page: Artificial Life and Flocking

Game AI Resources: A-Life & Flocking

Artificial Life (A-Life) technologies are, to my mind, probably the single most interesting aspect of artificial intelligence work in general and Game AI in particular. These technologies seem to me to offer the greatest promise of providing truly immersive, believeable environments for the player.

This page is focused on A-Life and Flocking links and resources of various kinds. It is by no means exhaustive, so if you know of a page or two I should add please email me.

The US Air Force has plans to make use of flocking technology to help control their next generation of satellites. In a November 5, 1999 announcement on the Air Force Research Laboratory Public Affairs web page is an interesting article discussing the Air Force's planned new "microsat" constellation. Air Force researchers have noticed that birds flying in formation are very "fuel efficient" in a biological sense, and they feel they can use similar techniques to help manage satellite formations more efficiently.

Fascinating where things like flocking can pop up, isn't it?

Jeff Whitledge has written an interesting thesis paper on an A-Life experiment with some little critters he calls Animats.

Animats are a kind of autonomous agent that use simple state machines coupled with a sensory-based stimulation-response interface. These Animats exist in a world called Pandamat, where they try to find "food" by moving around in their environment and learning the lay of the land. Naturally there are various obstacles to be avoided.

Source code is available with the term paper, as well as a compiled demo that runs under MSDOS. Interesting stuff, especially for those looking to build systems that use several sense to explore and learn their environment.

Demonstrating Emergent Behavior with Schools of Fish -- An excellent version of a "flocking with teeth" implementation, the author (Darryl Gates) has put together an excellent demonstration that's both practical and fun to watch. There is code of course and some excellent documentation and links on the site itself. Well worth a gander.

Dragonfly trick makesmissiles harder to dodge -- This is only partially AI-related but it's a good example of ALife learning things from Real Life (tm). Turns out that scientists have discovered that a trick dragonflies use to make prey think they're stationary (called motion camouflage) can be used to make anti-aircraft missiles harder to dodge by target aircraft.

Of interest from an AI point of view is that the complex trajectoreis needed for an anti-aircraft missile to pull this off aren't all that difficult to figure out. A simple neural network can do it, based purely on the movement of the target as seen from the missile. Very slick, very neat.

More stuff in the news article. I'd love to see a good game or two take advantage of this little trick....

Framsticks -- Yet another cool "roll your own" experiement in A-life, Framsticks is an oddly named project that bills itself as a "3D artificial life simulation project". Participators in the project can download the softwaer and then build their own Framsticks, using just about any kind of AI technology they wish-- evolutionary computation, neural networks, etc. Kinda similar in some respects to the various roll your own AI games, but with (what appears to be) a somewhat larger userbase. The general focus does seem to be a bit on the more academic theory side as well, which is a bit refreshing. Nifty.

Alastair Channon has done some extensive work in the area of emergent behavior and A-Life. His web site is filled with some well-written papers on the subject, as well as his own "lab toy" for experimenting with the field named Geb. You can find executables and source for nearly every platform out there, and it's a pretty good little tool for exploring the field.

To learn more, hit the site.

Tom Grub, who did a nifty Delphi implementation of the A* Algorithm referenced on another page of this site, was semi-inspired by the first Game Programming Gems 1 book and decided to put together his own flocking app. It's pretty nifty, written entirely in Delphi, and of course he's made source code available to anybody who's interested. The demo lets you do a few things mine in that book didn't--you can run or step through the sim, change the number of flocks, toggle a given flocking rule on/off, and influence the strength of the effect a given flocking rule has on the flock in question (this last is rather interesting). Nifty stuff.

If you'd like to learn more (and if my flocking demo in Game Programming Gems 1 wasn't enough), hop over to Tom's download site.

Tom Grub kindly provided an update of his excellent flocking app which now implements formations. The formations provided aren't very complicated but they don't need to be; the point of the demo is to show how relatively easy it is to be "meta-constraints" on the basic "Rules of Flocking" to obtain all kinds of fascinating and useful game behavior. (Neophytes to the game industry would be amazed just how many variations there are on the basic flocking techniques being used in all kinds of games.) Tom's done a great job of documenting his code (it's Delphi) and the demo really is impressive. This software is well worth checking out if you're considering adding formations to your next project...

Laboratory of Life -- A kinda fun implementation of the classic "Conway's Game of Life" (showing how very simple rules can lead to very complex behaviors). This is basically a very straightforward tool (freeware) that lets you play with these rules a bit and see how well you do. There are even random events in the form of lightning and dead spots...pretty nifty, really.

Probably more fun than actually useful to most developers here, but it's neat and the price is right.

Karl Meissner, who did the AI for Civilization: Call to Power, has put together a number of neat little apps and tools. One of them is a nifty little flocking app which I think you 'll quite like. It uses fish to get the idea across, which is fairly natural I think (I wish I'd used them for Game Programming Gems 1!). A nice demo and the code (if you can call it that) is all in Dynamic HTML. You can find it either here or here....as of this writing their main server was hosed, so it's hard to say which will work when you try it.

Primordial Life -- Basically, you've got these little A-Life biots that move around the map and search out food. Often that's each other. Where the genetic algorithms come in is in the adaptation of each life form to its environment...neat stuff, and well done.

One rather unique thing about this software is that you can hop on the Internet and connect to other users of the software, allowing your biots to travel across the Internet and battle for survival in other worlds. Neat stuff.

This is just plain fun to watch, by the way. Highly recommended.

The folks at Machester University (in Britain) were inspired by some of what they'd read on flocking on the Web and in various resources to put together their own study on how it might be applied to unmanned aircraft. The result is a proposed flight control system for fleets of recon or armed and unmanned attack aircraft, together with a cool VRML demo of how it might all work together.

Not sure what's happened with all this since the initial research (which was in late 2001) but given world events recently I wouldn't be at all surprised to see this get applied. Find out more at their site (where you can also view the demo). Note that this has many similarities to what the US AirForce is thinking about doing with their next generation of satellites...

Sugarscape is an A-Life project being run at the Brookings Institute. Researchers Joshua M. Epstein and Robert Axtell have taken the basic A-Life rules and concepts demonstrated in the classic game Life and developed a more rigorous simulation of social interactions.

Sugarscape takes place in a two-dimensional world containing deposits rich in resources called sugar and spice. Independent agents roam this world, seeking sugar or spice and reproducing if they find enough. What makes this different from the normal Life-variant, however, are the inclusion of a number of social interaction rules. Agents can 'trade' sugar for spice, as needed, inherit stockpiles of either from their "parents", etc.

One ends up with what the researchers call a simple form of a hunter-gatherer society. The social interactions, however, lead to forms of behavior which strongly mimic the distribution of wealth in human societies--where a few individuals often hold the majority of the resources in the society.

The Sugarscape work was so promising that has been used for a wide variety of studies, including one attempting to determine what happened to the Anasazi Indians:
You can find more information about Sugarscape all around the Internet, though an excellent place to start would be over at the Science News web site.

The developers haven't been idle, of course, and they're now using their basic tools to study all kinds of neat things, from the Anasazi to segregation to honest government agents. You can read all about it in a very long article over at The Atlantic Monthly ...cool stuff! My hat is off to the University of Arizona researchers George Gumerman and Jeffrey Dean for their fascinating work! (I've always been a sucker for archaeology.)

Tierra is a fascinating project which has been around on the Web since at least 1994 and has had several papers written about it. (They've even gone so far as to add a link to the main page entitled "Media Coverage about Tierra" ...and there's a lot of stuff there.) In short, they were A-Life before A-Life was cool.

Tierra's stated purpose is "...to use evolution by natural selection in the medium of the digital computer to generate complex and intelligent software...." They do this by using a genetic-algorithm based approach to create little mini-programs that "live" on the host machine and compete for CPU time. Those which successfully use more CPU time are "winners" and get to reproduce. Random mutation of code instructions helps keep the gene mix ever-changing (and how they're keeping a mutation from being instantly CPU-fatal is beyond me.)

The page contains several interesting screen shots of a Tierra gene pool in evolution, featuring hosts, parasites, and antibodies that have evolved over time. You can also download a copy of Tierra for your own experimention, which is really neat to play with.

Tierra does a great job of presenting an easy-to-play-with A-Life implementation in an easy-to-understand fashion. The code is freely available for perusal, and the evolutionary process is fascinating to watch.

Highly recommended for anybody interested in pursuing A-Life techniques and technology.

CNET has an interesting article on a Japanese gaming genre that's fairly strange by American standards--the "virtual girlfriend" simulator.

Similar in many respects to Creatures and The Sims, but generally much simpler, the Japanese "virtual girlfriend" simulators basically--well, simulate girls. Many are aimed at girls (usually "school simulators" of one kind or another), but a big chunk are aimed squarely at the "shy guy" market. The idea is that these dating simulations let you experience all of the fun and excitement of real dating without the humiliation of being shot down in front of all your friends.

There's a lot more, but no need for me to repeat it here. Check out the CNET article....it's an interesting aspect of A-Life that we generally overlook in the American game market.

A-Life Database -- Ariel Dolan continues his exploration of the world of AI with his new online resource, the A-Life Database. Billed as a "searchable database for A-Life resources on the web", Ariel has basically adapted the technologies of the big Internet search engines to hunt down and index A-Life sites on the web. Definitely a valuable resource, and a much better bet than trusting what Lycos might come up with.

John Eikenberry's AI Projects Page -- John Eikenberry has done some interesting work with A-Life, agents, and 'bots. He's made some A-Life projects available on his web page, and has put together a nice reference of other AI pages, AI definitions, etc.

Throughout much of 1997, and then again in early 2000, I conducted a great deal of research on various flocking algorithms. There are a ton of resources on the subject; here are a few of the better ones:
Craig Reynolds is the "Father of Flocking", having presented a paper on it in the late '80s at Siggraph. His "boids" have become famous, and are described in detail on an excellent series of pages found at http://www.red3d.com/cwr/boids/. Craig has a number of different flocking demos (all done in Java) available to watch and control directly from your web browser.

Craig has also done some great flocking-related work in a related field he calls steering behaviors. Hop over to his page on the subject and see what he's up to now.

If you only visit one set of pages on flocking, visit these!

The Mathematics Department of UMIST has an interesting A-Life project underway to assist their studies of honeybees. Their intent is to use computer simulations, together with A-Life and flocking technologies, to study how the simple behaviors of an individual bee can lead to the "group" behavior seen in the hive as a whole. Interesting stuff for anybody interested in either technology, plus the design documents and rationale behind the simulation's architecture are well worth a read for anybody new to the field.

Enthusiast Mattias Fagerlund has written a great little Windows-95 app named MatFa's Boids that demonstrates flocking extremely nicely. It runs very quickly, has a mechanism for observing which flocking rules are taking precedence at any one time for a given boid, and has a number of parameters that you can tweak interactively. Very, very nice bit of work.

Take a look at Mattias' work by clicking here

Yet another page features a different variant of flocking called schooling. Hop over here to peruse that variation.

Ariel Dolan has a couple of flocking implementations he's done for some critters he calls Floys. An unusual feature of his Floys is the ability to introduce a "stranger" into a flock, which will then turn upon and kill it (making it the only decidedly blood-thirsty flocking app I've seen to date). Ariel has several versions of Floys, one implemented in Tcl/Tk and one which uses genetic algorithms to evolve their behavior rules over time. It's all at his place.

I did a simple flocking application for the book Game Programming Gems 1 which many might find useful. Source code and a detailed description are all included. The application is fairly straightforward, though it does recognize multiple (enemy) flocks that try to avoid one another. I later followed up on it with a "predators and prey" modification of that app for Game Programming Gems 2, which was also pretty neat.

I can't post either here since I did them for the books, regrettably, but you can of course buy them if you've a mind to.

Jonathan Gabbai has built a great little Flash-enabled flocking app that he calls "Flocking Dodos". What's neat about this app is that it has various environmental effects (such as wind) that you can toggle on and off at your leisure. Definitely worth a look.

Live Artificial Life -- Never mind the apparent redudancy in the page's name, it's a good page for anybody doing A-Life research. It focuses on some of the more "artistic" aspects of A-Life...very interesting stuff.

The A-Life Page -- Here is a great page dealing with nothing but A-Life in all its glory. Run out of Italy, the links appear to be quite thorough and cover all kinds of A-Life projects, publications, newletters, software, etc. A goldmine for researchers in this area.

Evolutionary Computing and Artificial Life -- An excellent collection of information on evolutionary computing and a great source of links to other AI locales on the Web.

Terrarium -- Probably the one bit of software I've been pinged about recently by more people than anything else. It's certainly got a lot of fans.

Those of you who are already experimenting with Microsoft's .Net know what Terrarium is all about. It's basically a multiplayer "world" of sorts in which user can create their own creatures with their own AIs and set them loose in the environment. The object is to build a creature that out-survives all the others.

The support group available is extensive, as are the creatures other developers have created that you can download and experiment with. Plus this one certainly looks much nicer than many. This is a great way to play around with A-Life in general and the .Net framework in particular. Very nifty....