Inspiration
Back in 1994 Karl Sims developed his Evolved Virtual Creatures. More info here and here.
I have always found these sort of simulations fascinating, using the principals of genetics to evolve better solutions to a problem. For years I have wanted to try writing my own evolved creatures, but coding a physics engine to handle the movements and joints was beyond me so it was yet another entry on my to do list (until now).
2D Physics
For my virtual creatures I decided to start with 2D. I needed a general physics engine that takes care of all the individual world parts interacting and moving. Erin Catto’s Box2D has all the physics simulation features that I need to finally start experimenting with a 2D environment. Box2D is great. You only need some relatively simple coding to get the physics setup and then Box2D handles all the collisions etc for you.
Random Creatures
The creatures I am using are the simplest structures I could come up with that hopefully lead to some interesting movements. Creatures consist of three segments (rectangles) joined together by rotating (revolute joints in Box2D) joints. The size of the rectangle segments and joint rotation speeds are picked at random. Once the random creature is created it is set free into a virtual world to see what it does.
Many of them crunch up and go nowhere,
but some setups result in jumping and crawling creatures.
In only a few minutes thousands of random creatures can be setup and simulated. From these thousands the creatures that perform well are saved.
Performance Criteria
Once thousands of random virtual creatures have been created you need a way to pick the best ones. For these creatures I used three different criteria;
1. Distance traveled. The maximum X distance the creature travels in 5,000 time steps.
2. Distance crawled. The maximum X distance the creature travels in 5,000 time steps, but with a height restriction to weed out creatures that jump too high.
3. Height reached. The maximum Y height the creature reaches in 5,000 time steps.
The best picks become a set of creatures in the saved “gene pool”. If you have a large enough random set of creatures (say 10,000) and only take the top 10 performers then you do tend to get a set of creatures that perform the task well.
Mutations
Mutation takes a current “good creature” that passed criteria searching and scales segment length, segment width, joint rotation torque and joint rotation speed by a random percentage. The mutated creature is then run through 5,000 time steps and checked if it performs better than the original. If so, it is saved over the original and mutations continue. This process can be left to churn away for hours hands free and when the mutations are stopped you have a new set of best creatures.
For the creatures described here the features I randomly change are the segment widths and heights, the joint motor torques and the joint motor speeds (for 10 total attributes that can be tweaked by mutation). The user specifies a max mutation percentage and then each of the creature values are changed by
changepercentage:=maxmutationpercentage/100*random;
amount:=(MaxSegmentWidth-MinSegmentWidth)*changepercentage;
if random(2)=0 then amount:=-amount;
segmentwidth:=segmentwidth+amount;
The new attribute is clamped to a min and max value so as not to suddenly grow extremely long segments or super fast motors. You can also randomly mutate only 1 of the attributes rather than all 10 each mutation.
Choosing the right mutation amount can be tricky. Too high a random percentage and you may as well be randomly picking creatures. Too low a percentage and you will get very few mutations that beat the current creature. After some experimenting I am now using a mutation rate of 15% and mutating 3 of the attributes (ie a segment length, a motor’s torque, etc) each mutation.
Running on an i7-6800K CPU my current code can churn through up to 21 mutation tests per second. This screen shot shows 9 copies of Visions of Chaos running, each looking for mutations of different creature types, ie 3 segment distance, 4 segment height reached, etc etc.
A mutation test requires the new mutated creature to be run for 5000 time steps and then comparing against its “parent” to see if it is better in the required fitness criteria (distance traveled, distance crawled or height reached).
Mutation Results
After mutating the best randomly found creatures for a while, this movie shows the best creature for distance traveled, distance crawled and height reached.
I will have to run the mutation searches overnight or for a few days to see if even better results are evolved.
4 Segment Creatures
Here are some results from evolving (mutating) 4 segment creatures. Same criteria of distance, crawl distance and height for best creatures. Note how only the white “arms” collide with each other. The grey “body” segments are set to pass through each other.
5 Segment Creatures
And finally, using 5 segments per creature. Only the 2 end arms collide with each other (otherwise the creatures always bunched up in a virtual knot and moved nowhere).
Availability
These Virtual Creatures are now included in the latest version of Visions of Chaos. I have also included the Box2D test bed to show some of the extra potential that I can use Box2D for in future creatures.
To Do
This is only the beginning. I have plenty of ideas for future improvements and expansions;
1. Using more than just mutations when evolving creatures. With more complex creatures crossover breeding could be experimented with.
2. Use more of the features of Box2D to create more complex creature setups. Arms and legs that “wave” back and forth like a fish tail rather than just spinning around.
3. 3D creatures and environments. I will need to find another physics engine supporting 3D hopefully as easily as Box2D supports 2D.
Jason.
