Evolving humanoid walking


In this post I will discuss a nice experiment with evolution of locomotion in humans that i did few years ago.
You can judge from Youtube quality how long ago that was =)

Let’s begin with a movie showing the current status that I achieved:

Very far from full walking, but a nice start 🙂

The goal:
Evolve a walking humanoid, without performing any “cheats”.
What do I consider a “cheat” ?

A spring holding the torso up is a cheat.
Starting from a base animation is a cheat.

The method:
After I’ve created a setup of ragdoll physics, using ODE physics engine, and after converting their rendering to pure OpenGL in order to make life easier for me later,
I used genetic algorithms to evolve this walking animation.

In order to “bring life” into the ragdoll, I’ve added angular motors on all joints.
The joint constrains are defined as max allowed velocities on the angular motors.
They are hardcoded as a very simplified model of a human being.
For example, a knee has only one degree of freedom, but a heel as more.
I insert an angular motor per ragdoll joint.

Now, a Brain class is defined, which may control all of the motors (“muscles”…)
I chose genetic algorithms, but the “Brain” class was created generic enough to allow to easily create and test a different machine-learning technique.

Ok, now, for a genetic algo we need to define how a “Gene” looks like.
The class CWave was created:

class CWave
CWave(UINT uiWaveType,float fBase,float fAmplitude,float fPhase,float fFreq);

static void GetWaveTypeName(unsigned int wave_type, char* pFillMe, unsigned int fill_me_size);

void SetParams(UINT uiWaveType,float fBase,float fAmplitude,float fPhase,float fFreq);
void SetParams(const CWave& other);

float ComputeSin(float fTime);
float ComputeTriangle(float time);
float ComputeSquare(float time);
float ComputeSawTooth(float time);
float ComputeInverseSawTooth(float time);
float ComputeNoise(float time);

float Compute(float fTime);

UINT  m_uiWaveType;
float m_fBase;
float m_fAmplitude;
float m_fPhase;
float m_fFreq;


Available wave types are:

#define WF_NONE            0
#define WF_SIN             1
#define WF_TRIANGLE        2
#define WF_SQUARE          3
#define WF_SAWTOOTH        4
#define WF_NOISE           6

It’s nearly identical to the wave definition in Quake3Arena OpenGL fixed-pipeline shaders code.

BTW – I’ve coded in the past a Quake3Arena clone with a nice twist (before the source was released! =P ), I will post it soon 🙂

A gene is simply a set of such waves.
Per angular motor per “allowed” axis.

Per physics “tick”, a new force (per axis) is calculated per joint, accumulating the results from the different layers, which will cause the engines in the joints to start “push”/”pull”.

Scoring/Evaluation Method
A scoring method was defined.
The goal was to advance on the X axis as far as possible before falling.
Falling was defined when torso becomes very close to the ground.

At first I evolved a “jump” animation, and then moved to crawling / walking.
The score was simply, inside a few seconds time window, what was the highest that the torso got.
I experimented with other scoring methods for jumping, such as max general height, which cause the humanoid to raise the hand to the sky while jumping and crashing dramatically 🙂

The nice part is that when a framework like this fully works, you can easily experiment with the scoring method, to get different behaviors.

Few videos of the evolution of the jump animation

Ballet anyone?

Next steps:

  1. This was just a framework setup plus relatively basic sanity check! The fun part starts now! 🙂
  2. Allow some moderate evolving of the humanoid body in parallel to the animation, in real evolution the body evolves as well.
  3. Use IK to allow low level control, and evolve the humanoid walking logic based on that.

Here’s the full source code – enjoy!

Note: I would appreciate credit if you used it/learned from it somehow !
Update me directly as well, I’ll be happy to know that my decision to go open-source is helping people come up with cool projects 🙂

Credits/Thank yous
I used ODE as the physics engine
For fast and relatively nice quality random numbers generations I used SFMT
As a base I started with the following tutorial (converted the python code to C++ and pure OpenGL)
IIRC – back when I started implementing  quake3clone CWave class, Mathias Heyer (a.k.a “Syknet”) assisted me quite a lot. Thanks man!

Posted in Uncategorized | 8 Comments