Genetic Programming and Limb Physics

Note: I realise my blog update schedule hasn’t exactly been regular recently. Truth is, I’ve been at a bit of a loss for things to write about. I could use some ideas. (The fact that I’ve been posting loads of potential blog material over on the forums instead of here probably doesn’t help).

I’ll try to get back to a every-Tuesday posting schedule in coming weeks, assuming I can think of something worthwhile to write about. In the meantime, here’s some disjointed thoughts.

* * * * * * * * * *

Species is a Genetic Algorithm, but it is not Genetic Programming.

Genetic Algorithms use mutation and selection to find the optimal solution to a problem. The problem to which Species looks for a solution is simply “survival”, in the context of the games environment, which adds some complexity and depth to the “problem” side of things, but the “solution” isn’t actually hugely complicated.

Creature Genetics in Species are simply a bunch of one dimensional numbers. There are exceptions, but most of the genetic values in Species can be represented as a simple slider. So the evolution in the game is simply pushing these sliders up and down on their axes. The interactions and dynamics between the ecosytem and the statistics add quite a bit of depth but ultimately it’s not a particularly deep solution.

The concepts of genetic programming are quite a bit deeper. Genetic Programs use a noded ‘tree’ structure: rather than pushing numbers up and down, mutations in a genetic program add and move branches of the tree around. These branches might refer to packets of code, if()then conditionals, or loops. Or, if we take the analogy a bit more literally, they might refer to branches.

This is actually closer to the way real-life evolution works, and I would quite like to implement some of these concepts into Species. GP concepts are much, much better at producing unexpectedly novel structures and behaviors.

Unfortionately, GP structures don’t evolve very fast, and Species is about *seeing* evolution in action. That video above encompasses 7 hours of evolution. This was exactly the problem I had with the original behavioral system, which used some similar idea’s: it was too complex and didn’t evolve fast enough to be relevant to the simulation. When I replaced it with the simpler aggression and social sliders, it became much more responsive to selection pressures.

But like I said, though I don’t have GP, I want it. I want it a lot.

* * * * * * * * * *

I am jealous right now, as I often am when looking at other evolution sims.

I cannot *begin* to describe how much I would *love* to build something like this into Species.

Unfortionately the only way to achieve that is to work out a way to fake it: physics like this is deadly to the framerate when you’re simulating more than one creature. Simulating 1500 is well and truly too much.

So… faking limb physics. My initial thoughts are that there are two ways to do this: top-down, or bottom-up.

The former involves Inverse Kinematics. The genes give us an indeterminate limb-shape, and at birth an IK algorithm takes that limb shape and makes it walk as best it can, similar to the way creatures in Spore could walk no matter the shape of the legs. We then reverse-engineer stamina and speed stats from the step motion.

The disadvantage to this is that even though the legs might look different, they will all be animated the same way. There won’t be any novelty to the motion. On the bright side, that motion will probably be (relatively) crisp and clean: the feet will reach the ground and will provide a good appearance of ‘pushing’ walking creatures along.

The second method is bottom-up: we give every joint in a creatures leg a ‘motor’ to run it, a few paramters to determine step size and speed, and we try to somehow analyse the result to give us a constant speed, or even better, a variable one. This is a painfully difficult method: it will cost a lot in terms of performance, and the physics probably won’t look great, but if it works it could have a lot of potential. The trick is in working out exactly how to *make* it work.

One possiblity is that ‘step size’ could be limited to fractions of a particular value. So step sizes could be 1.0, 0.5, 0.25, 0.2, 0.1… but not 0.8 or 0.3 or 0.15.

This would make the limb-movement cyclical, and we could simulate a single cycle of motion at birth to determine how fast the creature can move. This is an expensive operation, however, and might result in noticable lag-spikes during births if poorly implemented. It also has a limitation: if the creature moves forward in jerks and bounds, a constant movement speed would not register that and the creature would look like it was gliding (although there might be ways around that, maybe, I hope).

Don’t get your hopes up just yet, though. This is all very much long-term stuff, which I probably shouldn’t even be discussing publically, but hey: I had to post something. And this is the sort of stuff I consider for Species. 🙂

Cheers,
Qu

Advertisements
  1. #1 by Adam Benton on August 31, 2012 - 8:19 pm

    Wait, the blog has a schedule? Well you wouldn’t know it.

  2. #2 by Icefire2314 on September 3, 2012 - 12:15 pm

    Noticing the blog has been updated and the wave of relief that the project hasn’t been abandoned, giving the forums are fairly dead.. lol

  3. #3 by ququasar on September 3, 2012 - 12:44 pm

    The forums aren’t dead, just sleeping. It’s been pretty hectic and I haven’t had much time to contribute to them recently, and there aren’t enough people there yet to keep things active without me continually commenting, but rest assured I’m working on 0.5.0 (I can now confirm it will have 3d trees!), and also on something big to get loads more people interested in the game by the end of September. (Cryptic comment is cryptic)

  4. #4 by Anonymous on May 26, 2013 - 7:27 am

    I see that species is still a very unstable game!How about some limits for the engine so that it doesn’t make things beyond its limits and crash?

  5. #5 by Anonymous on May 26, 2013 - 7:30 am

    Oh,and by limits,I don’t mean the ones that crash the game if exceeded,but I mean limits where the game can’t make anything beyond that limit or the game is forced to delete the entity.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: