Category Archives: algorithms

An interesting application of genetic algorithms

I recently watched an interesting BBC documentary called “The secret life of chaos”. It did a good job of explaining how interesting patterns could arise from very simple rules and how these could be further shaped by evolution to create the sort of complexity we see in the living world. It is well worth watching in full.

I have been interested in genetic algorithms for some time and use a genetic algorithm to optimise seating plans in my own PerfectTablePlan software. So I was particularly interested in a segment towards the end, where they showed how naturalmotion.com have used bio-mechanical modelling and genetic algorithms to create virtual humans that can respond realistically to various (unpleasant) physical stimuli, e.g. being shot, being hit or falling off things. The details are sketchy in the TV program, but it appears that they have evolved genetic algorithms that mimic aspects of the human nervous system. For example a human will instinctively put their hands out to cushion a fall or put a hand to an area that has been hit. They then combine this nervous system modelling with physics and a realistic a bio-mechanical modelling of the human anatomy. The results are impressive. You can see them about 2 minutes into the video below.

They claim they can use these models to generate realistic movements for synthetic characters in real time. Their Euphoria software is already being used in computer games, such as Grand Theft Auto IV.

More videos by naturalmotion.com

A mathematical digression (revisited)

I received two working programs that attempted to solve my ellipse problem. Both were creditable attempts, but neither of them were quite accurate enough for my requirements. One had small (but visible) gaps between the first and last circle and the other didn’t work well for small or large n. However they made me think that a heuristic approach might be workable.

I made a couple of attempts to work out the quartic equations I would have to solve to find the solution analytically. But my brain started to bleed.

After much thinking about it I coded a heuristic approach myself in a day (till 3am!). It works from n=1 to n=100 for variable a/b without noticeable gaps or overlaps for n>7. There is some slight overlapping at n=7 and a/b=1.5. But I can fudge that by changing a/b to 1.6!

The approach is:

  1. use Ramunajan’s formula to work back to a reasonable starting value for b (semi-minor axis)
  2. lay out the n circles
  3. work out the gap/overlap between the first and last circle
  4. if gap/overlap error acceptable, stop, otherwise go to 2

There is also a bit of extra fudging for small n.

I used the secant method to interpolate the values for steps 1,2 and 4. As the functions were all smooth and well-behaved this converged on accurate answers very rapidly (typically 5 or 6 iterations per calculation).

Despite the fact that it is doing 2 levels of iterative calculation, it is surprisingly fast. Even going for high accuracy it takes <1ms for n=50 and <2ms for n=100 on my Windows box. About double that on my old Mac mini. And I can easily cache results in memory for more speed.

You can download and play with the test harness binaries here, if you are so inclined:

Windows binaries (Windows XP or Vista)

Mac binaries (MacOSX 10.3.9 or later)

Both Windows and Mac versions are created from a single set of C++ using the Qt cross-platform toolkit. Note that the timer resolution is 1ms, so times <1ms show as 0ms.

So the next version of my table planner software will have oval tables. As always, there was something I hadn’t though of. I had to do a bit of extra work to calculate the normal to the ellipse circumference (which isn’t the same as the line that joins the ellipse centre and the circumference – as I had initially assumed).

Without calculating normals.

With calculated normals

The commercial value of this feature probably isn’t worth the time I have spent on it. But it will make some of my customers very happy and it was an interesting problem. Part of the reason I set up as a microISV was to do things that I find interesting.

Many thanks to everyone that contributed code or suggestions to the original post.