How to go about making an on-line artifical life game

May 4, 2006 5:34 PM

I've been reading about evolutionary computing and artificial life and suchlike. As an exercise, I would like to make a multi-player online game where players can design creatures, which would then compete for survival.

I rigged something up in PHP/MySQL (because it's the only language I know) - outputting plain-text HTML, and using meta-refresh, which is pretty clearly not the best solution.

So, how should I go about it? I'm happy to learn any language so long as I can pick it up fairly quickly, while I'm building the program. Processing looks fun, but I'm not sure how suitable it is for this project. I worry that java would be too much effort to learn for a spare-time kinda deal. Flash, perhaps, though I don't know if it is really up to the task. Or would it be concievable to hack it together with AJAX, as I'm planning to learn AJAX anyway?

I'm open to any kind of suggestion, with the goal of getting it made as quickly and easily as possible, though learning an otherwise useful language would also be nice. I would eventually like to play around with all sorts of evolutionary computation ideas, if that is relevant.

I'd also be interested in links to existing or historical implementations of the idea, or something like it. Creatures, and this BBC experiment are the sort of thing I'm thinking of.

posted by MetaMonkey to computers & internet (18 answers total)

like Spore?
posted by dness2 at 5:42 PM on May 4, 2006

Wil Wright is making a game called spore you might want to investigate. It's all about evolutionary processes and competition between species and such. Maybe you've heard of it, given your interests. But if not, I bet you'll be entranced by the video I linked.
posted by chudmonkey at 5:42 PM on May 4, 2006

If you're pretty happy with what you've got together with PHP/SQL AJAX will really make it seem more responsive and professional and will also presumably save you bandwidth since you can send a bit of raw data instead of the whole page every N seconds.

If you really want to do some tricky AI stuff Java lends itself brilliantly to that kind of thing. Not as well as Lisp, but it's easier to pick up and it's got better out of the box net functionality. Unless you're thinking of moving towards a really thick client with this though I think AJAX is a pretty reasonable avenue to pursue.

AJAX isn't the gigantic new paradigm of wow you might think from its reputation though, and I imagine you'll pick it up and implement it really quickly if you have decent familiarity with javascript and/or XML.

Flash's thing really still is graphics, although I guess ActionScript is pretty robust. If you're planning to make it pretty it's an option but I wouldn't bother if your core interest is in the algorithms.
posted by moift at 5:45 PM on May 4, 2006

I think for game programming, you would want to use a true typed programming language rather than a scripting language for the web. But you could go that way if you really want to. The thing is, there are a lot of EC frameworks already built for Java and C++. And you could eventually link them up with OpenGL if you wanted to drop things into a 3d environment. Anyway, I suggest learning Java. It's really not that hard, and an object oriented language would lend itself easily to competing entities with different statistics and operations.

Here's a good example of a simple Genetic Algorithm implemented in Java. You can control environment variables through the menus, and you can look at the source code through a link at the bottom of the page. Also, this guy has written a great introductory book to Java which he has put online. It got me through some 400 level programming courses when I didn't know the language. Enjoy, and let me know what you come up with, regardless of what you decide to do...
posted by Roger Dodger at 5:52 PM on May 4, 2006

Microsoft also did something like that.
posted by Steven C. Den Beste at 5:57 PM on May 4, 2006

That reminds me, too. I've been meaning to look more closely at JOgre. It's a multiplayer gaming environment which takes care of all of the online overhead. You just have to implement the game. I don't really know that much about it, but thought I'd throw it out there.
posted by Roger Dodger at 6:00 PM on May 4, 2006

There's flow (flash), which enthralled me for hours. It's pretty simply, but engaging, nonetheless. You might want to check it out to see what other people are doing...

Also, you might be interested in Polyworld by Larry Yaeger (who used to be at Apple, now at Indiana University). The source code is available, so it might be something to build from. My advisor has worked with Larry on evolving neural net controllers for polyworld critters, so it doesn't seem like a huge jump to having individuals brew their own...
posted by logicpunk at 6:01 PM on May 4, 2006

I have a few comments:

You want to run your genetic algorithm server-side for a maximal number of generations. If you go through post-back loop (meta refresh) then you will only get a few generations per minute.

You can think of evolution as a search algorithm. It creates a bunch of random "potential" (usually based on the previous generation of good performers) and then tests which ones are best suited to the world.

But computer worlds are very simple, so the "search space" is small, and thus the set of possible creatures is very small. So computer-world evolution usually results in little gadgets that gain very small capabilities, although they are always novel. And also for the same reason, there is little "bio"-diversity in the community. Its always a great victory in simulacrum when you get a simple ecosystem going (predator-prey, etc).

So a goal is to have a rich, dynamic world for them to live in (so that there is competing strategies, etc). But increasing the world size means it takes exponentially more time to chew through each generation. Slowing down your generation cycle time means it takes much longer to get to something interesting.

These goals are all incompatible with scripting languages in general. Perhaps look into FPGA evolution. Having a web-page hooked into an FPGA which is running evolved code would be pretty cool. Have two, one running the evolution process, and another running the latest generation for public consumption. Maybe have visitor's "votes" act as the fitness indicator, and have the FPGA generate a bitmap. People would quickly push it in interesting directions.
posted by clord at 6:49 PM on May 4, 2006

This is what Mathematica was designed for.
posted by Mr. Gunn at 6:57 PM on May 4, 2006

But it sure isn't cheap!
posted by Roger Dodger at 7:14 PM on May 4, 2006

From the historical implementations dept: Back in the early days of the Web, there was a game called Technosphere, which was very similar to your idea. It wasn't real-time viewable, though - you would design a creature and it would live in a server-side world, e-mailing you reports about its having children, eating things, dying, and so on. The Technosphere site is long-dead, but there's some information and screenshots at the author's site.
posted by pocams at 8:04 PM on May 4, 2006

Muse Software's RobotWar (by Silas Warner) was a very early implementation of this. Instead of being online, everyone brought their floppy disk containing robot code over to someone's house, you loaded all 6 robots onto the Apple ][+, and then - glorious destruction!
posted by ikkyu2 at 8:08 PM on May 4, 2006

have you seen karl sim's blockies?

how about framsticks?

flesh out the design first, then the choice of tool will follow.
posted by paradroid at 10:03 PM on May 4, 2006

Wow, the FPGA idea is out there. Cool, but maybe a bit too involved for a guy looking for a cool program to write in his spare time? :)

You could definately do this in PHP/MySQL or even AJAX, but if you interest lies in the algorithms, then you'd be better using a more traditional game programming language like C++ or Java (I'd go C++, but it's all preference). As a few others have said, PHP is great, but it is really just a web scripting language. Also, I imagine you wouldn't have too much difficulty with C++ if you already know PHP (at least, I was able to pick up PHP based on my C++ knowledge).

Having said that, if your intention is to eventually learn more about EC, you might want to consider a language like the aforementioned Mathematica or, my favourite, Matlab. While Matlab isn't much different than C++ (and in some ways inferior) it does have the big advantage of having a very mature set of artificial intelligence and genetic algorithm tools.

Let me know how you go with this (e-mail in profile), I'd really like to hear about the results!
posted by ranglin at 10:10 PM on May 4, 2006

In the thinking I've done concerning a similar kind of project, I believe I can say with some certainty that the most difficult obstacle to doing something like this well is making the variety of possible creature great enough so that the game isn't a matter of maxing out one or two obvious statistics or sterile in some other way, while keeping a handle on the complexity so that you don't go crazy implementing too much than you can handle.
posted by JHarris at 10:36 PM on May 4, 2006

Some thoughts:

Your question is a touch confusing because you start by talking about evolutionary computing, and then go on to describe a system where human-designed creatures compete, with no mention of evolution. That doesn't matter too much, as an automated process can upload creatures into the environment just as easily as a human. (That is, the environment and the creation of creatures are two completely separate processes and should be treated as such).

Have you explored CoreWars? It's the grandaddy of a lot of this stuff. It was one of the inspirations for TS Ray's Tierra. CoreWars has been pretty thoroughly explored, and it's now clear that there's a scissors>paper>rock thing going on there, and creativity has long been focused on writing better scissors, papers and rocks.

JHarris is right - planet earth is a big, complex place with lots of variation and evolutionary niches to exploit. By comparison the environment you create will be as sterile as a petri dish. The best approach for open-ended evolution seems to be to have the programs be each other's environment - this is why Tierra was so successful. Rather than evolving towards a fixed target, each program was evolving to best survive in the current population, and so the current population was a moving target.

I'd say there are three basic approaches you can take.

The first is to use your genotype as your phenotype - this is how CoreWars and Tierra work. They just lay the programs that are being run directly in shared memory, and this memory is their environment. Another example might be programs living inside a 2d cellular automata (creating a 2d machine language is left as an exercise for the reader).

The second is to have a fixed phenotype, into which genotypes are loaded. An example would be AT-Robots, where programs are loaded into identical robots bodies, fitted out with guns, scanners, etc., and the best strategy wins.

The third is to have a genotype encode for a phenotype. This is closest to evolution as we think of it, and some of the people competing in sodarace are evolving XML genotypes that describe sodaplay phenotypes.
posted by Leon at 3:25 AM on May 5, 2006

Hardcore-programmers will scoff at this suggestion, but you might try Flash (Actionscript). The problem will be speed. AS is way slow compared to languages like C++. I don't know whether or not you need computational speed. This will depent on how many creatures live in your world, how complex they are, etc.

The advantages of Flash/Actionscript?

--It has a drawing program built into it, so making the "sprites" will be easy.

--AS is easy to learn if you know PHP. They are both scripting languages. You'd have a MUCH bigger learning curve with C++ or Java.

--AS 2.0 (the current version -- 3.0 is in beta) is pretty advanced for a scripting language. It's strongly typed, has true OOP classes, etc.

--Most people have the Flash plugin for their browser.

--If you want, you can still use your PHP and use Flash as a front-end for display.

--Flash is relatively inexpensive.

If you're interested in doing just this one project, Flash might be the way to go. On the other hand, if you'd like this to become a stepping stone into a world of hard-core programming, you'd probably be better off learning C++ or Java.
posted by grumblebee at 7:54 AM on May 5, 2006

Huge thanks to all for the great answers, so much useful, thought-provoking information! I am refraining from marking best-answers, as almost all of them are great, so it would make the thread less readable. Unfortunately, ya'll have made me question my initial assumptions/model such that I now have more questions/ideas than I had when I asked the original question. Answering these questions is of course half the fun.

In case anyone is curious about where this is going, I'm currently torn in two major directions -

1. Make a persistent world with 'creatures' which evolve in both structure and intelligence. Allow users to seed the world with new creatures, operations, and so on.

2. Make a generalized framework for interactive arty evolution, where people vote according to their likes to determine 'fitness', and contribute arty seeds/genes. The idea would be to then apply this system first to pictures, then music/sound, and finally video.

(I suspect there is some ingenious way to marry the two concepts, which thus far eludes me).

My plan is to keep working out initial ideas/models until I've settled on something interesting, with potential for fun and eventual complexity. Once I've picked a direction, I will pick the language/approach which suits it best.

I clearly have a lot to learn, so I would appreciate any suggestions for directions to take the project, useful initial conditions and so forth; any further advice or ideas of any kind would be much appreciated. Feel free to post here or to my email (in profile). I may even start a web-page or blog or whatnot, in order to solicit further interesting thoughts.

Roger Dodger & ranglin, rest assured if anything comes of this you will be the first to know (though if my previous big-idea projects are anything to judge by, I wouldn't hold my breath).
posted by MetaMonkey at 10:26 AM on May 6, 2006