Asteroids on a Torus

One of the great things about meetups is their ability to generate weird idea exchanges. Late last year I demonstrated ThreeBody – another of my oddball, limited appeal physics apps. I was mentioning that it might be fun to see what happens to the three body problem in a spherical space – since this would solve the “ejection to infinity” issue by removing infinity. This led to a discussion about the topology of games like asteroids where the top/bottom and left/right are wrapped. This mapping creates a space that is a topological torus. This was the spark I needed to think more carefully about what motion on a real torus would be like.

I don’t need much of an excuse to think about an odd physics scenario.  My past includes time spent taking a break from the working world and doing a PhD involving curved spacetimes. One of the problems that comes up in such studies as a way of sharpening skills is the study of motion on curved 2D surfaces. It is a great place to learn to use the mathematical machinery and intuitive enough that the answers can be visualized.

This made me wonder how different a space shooter would be if the physics of a torus was made “technically correct” (the best kind of correct) . The result is a soon to be released game “Geodesic Asteroids” in which there is a dual view of the 3D motion and the 2D motion with the paths of objects moving in a “technically correct way”.

 The Torus

Torus1

Figure 1: Torus coordinates

First we need a mathematical description of the torus. It is a 2D surface so only two co-ordinates (\theta, \chi) are needed to describe a point. If we think of the typical donut representation sitting on the x, y plane then \theta is the angle around the z-axis (say from the line x=0) and \chi is the angle around the cross section of the torus at a given \theta. The radius of the center of the torus is a and the radius of the cross section is b.

In the mathematics for a torus, everything can be described in terms of these co-ordinates, including the equations of motion that define how an object moves when there is no force on it. We are accustomed to thinking of the torus as a three dimensional object but exactly which three dimensional shape results is partly due to the choice made when we embed the surface in 3D. There is really no reason we have to do this but it can help our intuition. [Digression: It an interesting mathematical question about exactly how may dimension are required to embed an N dimensional surface, we are accustomed to N+1 for e.g. spheres and torii but this is not the general rule!].

In our case we pick a customary embedding:

$$x = (a + b \cos{\chi}) \cos{\theta}$$

$$y = (a + b \cos{\chi}) \sin{\theta} $$

$$z = b \sin{\chi} $$

This allows us to map (\theta, \chi) into the x, y, z world co-ordinates the game will use and retain our intuitive picture of a torus.

What about a 2D map of this torus? Here I elected to just use (\theta, \chi) as pure 2D co-ordinates i.e. as if they were the displays “x and y”. I impose a slight twist that I’ll explain in a minute.

Motion on the torus

The embedding equation provides the world space position to show events on the torus. What equations should be used to calculate motion on the torus? The motion takes place on the torus so the description is in terms of  (\theta, \chi). Here there is a departure from the usual equations that govern games. In the flat 3D game world x, y and z are independent and there is no need to worry about where in the space we are. F=ma is the same at the origin as it is at any other point. On curved surfaces things are different. To make this clear lets consider a simpler 2D surface, the sphere, with longitude \phi and latitude \theta.

greatCircle

As you know from looking at maps of airplane flights, the lines between points take what seem to be curves on the map. This is because the force-free (or geodesic) path that connects two points is a great circle. This means if you are in New York and head directly west the geodesic path must be a diameter of the circle and will carry you into the southern hemisphere until you are at the antipodal point directly opposite New York through the center of the earth. [Fun fact: very few places on land have an antipodal point on land]. You started out with only a velocity in the \phi direction but ended up on a trajectory for which \theta also changed. This means that the equations of motion are coupled. The equation for the evolution of \theta depends on the velocity in the \phi direction. In the case of a sphere the equations for force free motion are:

$$a_{\theta} =v_{\phi} v_{\phi} \sin{\theta} \cos{\theta} ,  a_{\phi} = \frac{-2 v_{\theta} v_{\phi}}{\tan{\theta}} $$

For a torus the equations are:

$$a_{\theta} = \frac{2 \sin{\chi} v_{\chi} v_{\theta}}{b (a + b \cos{\chi})}, a_{\chi} = – \frac{2 \sin{\chi} v_{\theta}^2}{(a + b \cos{\chi})} $$

The good news is that on the torus the co-ordinates are well behaved. The expression are finite. (If you look at the equations for the sphere you’ll see it is possible for some values to be dividing by zero. Never a great idea. This is not a fundamental part of motion on a sphere, there is no special place where acceleration goes to infinity. It’s just a bad choice of co-ordinates and we need to choose a different origin in some case. It is quite usual to have to cover a surface with several co-ordinate patches. For the torus we are lucky that this is not needed.)

Where did those equations come from?

The equations for F = m a on a curved surface come from a branch of mathematics known as differential geometry. “Differential” since it studies the behaviour of surfaces that are smooth enough that you can do calculus, i.e. no sudden steps or cusps. One of the new ideas that enters with differential geometry is that while you can do calculus at each point, you cannot directly compare the results of these calculations at different points. This is because each point has its own tangent plane (more generally tangent space). As an object slides along the 2D surface the local co-ordinates of the object change relative to the surface co-ordinates. Returning to our sphere example, if you initially were heading west from New York when your great circle crosses the equator you are no longer facing west BUT you did not turn, you were just following your geodesic path. Exactly what the geodesic path is and how it turns as you go is something that can be calculated for a surface.

It’s not my goal to turn this post into a treatise on differential geometry. It is a very interesting subject and is the stage on which Einstein’s General Theory of Relativity takes place. All the introductory GR texts start with some background in differential geometry and I find their approach more geared to my interest than the way math books approach the subject. For those interested in a good introduction to the geodesics of the torus and an introduction to the basics of differential geometry, I recommend Jantzen’s paper. My favourite intro GR book is Schutz’s “A First Course in General Relativity”

Differences between 2D and 3D representations

A space game on a torus can be shown in 3D but it is also interesting to play the game on the 2D representation of the surface. Here the odd paths of the objects make the impact of the curved surface apparent. There are some compromises in mathematical purity that I have made in the interests of actually finishing the game. The primary one is that the size of objects in the 2D and 3D view cannot be fully reconciled (more below).

On the true mathematical surface the distance travelled as you walk around the outside diameter is different from the inside diameter. On the 2D map this means that the top edge of the map should not be as wide as the middle. Our choice of a 2D map is therefore vulnerable to the an effect similar to that occurring on a Mercator projection of the Earth (Greenland is shown as far too big).  I have chosen a simple scaling depending on the “latitude” \chi. To continue this accuracy it is necessary to change the horizontal size of the objects as they change latitude. I did put this in the game as an option – but the result is a bit odd looking. In normal play this mode is disabled – with the consequence that the objects on the screen are not exactly the correct size. The correct size is used for detecting bullet hits and in some cases an apparent hit on the map is not a “real” hit.

 

True scaling leads to some weird paths in the map view. If an object is moving quickly in \chi the shrinking due to the scale factor can exceed motion towards the edge making it look as if the object backs up a bit before continuing on.

Geodesic Asteroids is available on Blackberry, iOS and Android. It has been great fun to think about and use the geodesic math I learned long ago. It is also the first time I have written a more “video game” style game. Hope you’ll find it interesting.

[social4i size=”large” align=”float-right”]

Learn Physics With This One Trick

When I look at new physics books (which I do far too often) I get a “Flowers for Algernon” feeling. There was a time when I knew about this stuff. That knowledge has seeped away over the past  fifteen years leaving me with a sense of loss and nostalgia. However, there is a trick I used in undergrad when I decided that I wanted to have the option of going to graduate school, that applies here. I am using it to get my physics kung-fu back.

gravity

First, some background.

I “speak” math with some fluency. In high school it was easy to pick up. I do not speak much else. Efforts to learn French, Spanish and Mandarin at various points in my life have all been tedious and I have never managed to get very far.

Although I speak math, I was a lousy student. In first year I was so close to the bottom of the class, that I doubt anyone below me returned for the next semester. I did manage to squeak up to being 30th percentile – and I would have told you I was working hard. What I told myself (after getting in to a good school) was that I was on a different curve now and that this was the new “level”. In reality I was looking at the material, “grazing the text”, nodding to myself that it all made sense and doing only the assigned questions as best I could.

In the middle of third year I decided it was time to open the door to grad school and using my “trick” I achieved an 85% average and made in onto the Dean’s list.

The “trick” is: Do EVERY question until you can do it PERFECTLY.

I didn’t say it was an easy trick.

It almost killed me.

For the entire term I was either in class or at my desk. I did every question multiple times. I filled in every gap in the derivation in the text books. I went back and repeated start to finish questions I had not gotten right the first time, until I could take a blank sheet of paper and get it right.

I learned by doing, using the material in the book to solve problems.

I got into grad school.

Back to the present…

There is a new physics textbook “Gravity” by Eric Poisson and Clifford Will. This book is a tour-de-force, beginning with Newtonian gravity, detouring into shapes due self gravity and tidal forces, three body orbits and then heading into techniques to model general relativity and gravitational waves in situations where full blown general relativity cannot give direct answers.

I have decided that I refuse to feel nostalgia and loss about this topic. I need to learn it.

Back to the trick. It is NOT any easier. After a fifteen year break, I have spent more that a few hours reminding myself about div, grad, curl and lots of other forgotten math. The progress is slow, but not painful. Chapter 1, question 1 took me two weeks. I had to refresh my knowledge of vector calculus, derive some results in the text and figure out Stoke’s theorem. When I go back to the text with a specific problem in mind, I read far more carefully. As I feel knowledge seeping back I am excited to discover the connections and see where physics leads. There is a sheer joy from simply using my brain much like the feeling I get from a long bike ride or XC ski. My justification is precisely the same – it’s challenging and it’s providing exercise for part of my body.

The questions in chapter one have taken me a little over two months. Chapter two is going a bit better, since I now have some of my math skills back. I do not have as much time to focus on this as I would like, but the time I can put in is rewarding – and I can go off on detours to remind myself about Green’s theorem – or whatever it is I need to re-learn. Right now I am “stuck” on a line in Chapter three that starts “expanding in terms of r/R we get” and I need to go find out about Taylor series of vector functions.

This may take some time, but the trick is working again.

[social4i size=”large” align=”float-right”]

ThreeBody – Can Gravity “keep it all together”?

I have returned to N-body, my first mobile effort , with the goal of making it cross -platform and adding new ideas. Given all my recent positive experiences with the Unity game engine the idea is to port as much as possible and avoid “the rewrite”. (This has a very tempestuous history in software and is one of the things Joel Spolsky thinks you should never do.)

The good news for the small community who have enjoyed N-body is that moving it to Unity is going quite well, and I am FULL of cool ideas I want to add: gravitational fields for non-spherical objects, galactic potentials, dust accretion – it’s almost endless. The bad news is that I read a great Sci-Fi novel “The Three-Body Problem” by one of China’s top sci-fi writers, and this has caused me to set aside Nbody for awhile. “The Three Body Problem” reminded me of the non Sci-Fi book with the same title (you could see how that would happen). One of the things I made a note of when I read the more academic of these books was the static three body problem. The question is: can three bodies be placed in initial conditions with zero velocity such that they will stay in a bound configuration? Would you expect that since gravity is attractive they would “keep together”, perhaps with some cool triple orbits?

As I was reading the sci-fi 3BP I was feeling like I needed a break from NBody and figured I’d try a quick mock up of the static three body problem in Unity. As I get more kung-fu with Unity (and using the leap frog integrator I had ported for Nbody) this kind of side project becomes very do-able. I spent an afternoon doing the basics and found that there was a nice little physics “time waster” game here.

Shortly after, during my usual lunch time perusal of arxiv, I found a paper about using GPUs for N-body simulations which mentioned replacing the three bodies with three binaries. Another addition for the ThreeBody app.

This was all about a month ago and since then I have added the minimum of “gamification” so others can take a swing at this problem on their mobile devices. It is weirdly addictive and a good way to see how sensitive the problem is to initial conditions. Hope someone out there also finds it fun.

You can find ThreeBody for Android and Blackberry (coming soon to  Amazon and iOS). There is some further technical detail.

[social4i size=”large” align=”float-right”]

The Unity 4.6 UI – Some Tidbits

Unity 4.6 provides a fantastic new UI framework. I will never use the old OnGui() again! I have been using the new framework for the past several months while Unity 4.6 was in beta. During this time I have collected a few tidbits on working with the framework.

Getting Started

The tutorials  are very good and the information in the manual is getting better all the time. I found the tutorials on Canvas, RectTransform, Button and Event System a bare minimum to get the idea of the whole thing.

Adapting for Mobile Screen Sizes

This was one of my first “care-abouts”. There are two things that are important to know. The first is the anchor system for the layout of elements  (see the RectTransform tutorial) but that is only part of the solution. The crucial other element is adding a CanvasScaler to your root canvas.

Screen Shot 2014-11-29 at 12.45.51 PM

Once attached to a Canvas this can then be set to give a reference size and you’re good to go. As the device screen size change your UI element will scale appropriately.

UI interactions with Scripts

In the C# world the Unity elements can be created and modified as you would expect. You will want one or both of the following includes:

using UnityEngine.UI;
using UnityEngine.EventSystems;

ColorBlock: Changing Button Colors

The ThreeBody game I am creating makes use of collections of buttons as radio boxes. I set the disabled and highlighted colors to reflect the color I want for unselected and selected. When it is time to enable a button, then the normal color of the button is set to the value in the highlighted color. It would be reasonable to expect that:

button.colors.normalColor = Color.white; // DOES NOT WORK!

would work. It does not. Instead you need to make a temporary copy of the ColorBlock and then modify its elements and copy back the ColorBlock:

    // flip to highlighted color
    private void EnableButton(GameObject go) {
        Button b2 = go.GetComponent<Button>(); 
        ColorBlock cb2 = b2.colors;
        cb2.normalColor = cb2.highlightedColor;
        b2.colors = cb2;        
    }

Touch Events and Buttons

Button touch events will still fall through into code that handles touches so it becomes important to screen out those touches that are over top of buttons. A technique that works for both mouse and touch events is:

    private bool IsTouchOnButton() {
        GameObject go = EventSystem.current.currentSelectedGameObject
        if (go != null) {
            if ( go.GetComponent<Button>() != null) {
                return true;
            }
        }
        return false;        
    }

 Panel Fading and CanvasGroup

There is not a lot said about panels in the tutorials or online docs. These appear to be containers for holding a subset of the UI being developed. I found them useful for Settings Menus and High Score panes. In order to run a fade effect on these panels, you can add a CanvasGroup (which then has a field “alpha” that allows direct control over fading). An example of such a fade coroutine is:

    public GameObject menuPanel; 
    private const float FADE_TIME = 0.5f;
    private const float FADE_STEPS = 10f;
    private const float FADE_INCR = FADE_TIME/FADE_STEPS;
    
    private IEnumerator FadeMenuPanel(bool visible) {
        CanvasGroup cg = menuPanel.GetComponent<CanvasGroup>();
        if (!visible) {
            for (float i=FADE_STEPSi > 0i--) {
                cg.alpha = i/FADE_STEPS;
                yield return new WaitForSeconds(FADE_INCR);
            }
            cg.alpha = 0.0f;
            menuPanel.SetActive(false);
        } else {
            menuPanel.SetActive(true); 
            cg.alpha = 0f;
            for (float i = 0fi <= FADE_STEPSi++) {
                cg.alpha = i/FADE_STEPS;
                yield return new WaitForSeconds(FADE_INCR);
            }
            cg.alpha = 1.0f;            
        }
    }

Note that in my case I also change the panel active status. This needs to be done at the end of the fade out or the start of the fade in for the object to stay visible during the fade.

Off-Topic: Trail Renderers

This is not part of the new Unity UI theme but as part of getting ThreeBody ready I had to learn a bit about TrailRenders. I use these to leave paths behind the “stars” in ThreeBody so the orbital paths can be seen. I always had weird issues with setting materials and colors until I finally found some clear advice on the forums about the material choice. I need to choose a particle material and the trails look best with a mobile/particle/vertex-lit shader on that material. To get solid colors I have created a simple 128×128 solid color PNG, imported as a texture.

Another tidbit is how to recycle objects once you have used trail generation. To get rid of the trail I ended up setting the trail length to -1, then counting 5 update cycles before setting the object inactive and putting it back into my object pool. I played around with coroutines for this but they ended up creating more complications – and a simple synchronous design won out.

Hope some of these save you some time.

[social4i size=”large” align=”float-right”]

Thank You Apple For Rejecting My App

One way I cling to the notion that I still know something about physics is to create oddball mobile physics apps. Since this is a side-project my goal is to spend most of the time on physics and less on the time-intensive UI tuning. I have moved to Unity and while learning Unity I decided to try and make a mobile game inspired by a spinning magnet office toy I had had for years.

IMG_0886

When I look at something like this I wonder what might happen if I could change the number of arms, number of “propellers” and a game/simulation seems like a good way to explore these ideas.

In my initial enthusiasm for Spinor I decided that adding leaderboards would be a good idea. It would encourage people to share their love of my awesome game and take me on the road to self-sufficiency as an indie developer. This meant that I needed to add code to track login state and provide options on the level select screen and game over screen. I found a way to spooge it in. What I had was “workable” and I went ahead and started to submit Spinor for Android, BB10 and iOS.

Google will take pretty much anything. Within hours my app was up on Google Play.

Amazon approved it.

Blackberry approved it.

Apple rejected it.

They rejected it on the basis that the level select and game over screens were “too ugly”.

They were right.
IMG_0883
The level select screen was one of those things that is not the fun part of developing the app, and I had just plopped in some touchable tiles and some hacky strings using the Unity OnGUI() approach. It *was* ugly. I then decided this was a great time to search the Unity asset store. I quickly discovered the Mad Level Manager and decided to grab it when it went on sale. The end result is a cleaner looking game that is more presentable.

IMG_0885

The chaos of magnetically interacting systems *is* cool – and I enjoyed watching some of the odd interactions that result.

IMG_0823

Next time I’ll be submitting to Apple FIRST. They give the best feedback.

[social4i size=”large” align=”float-right”]

Potential

Potential is now available on BlackBerry World and Google Play.

The idea for the game came from watching my kids play with the BuckyBall magnet toys on a coffee table – taking turns placing them and trying to keep them apart. The interactions were sudden and dynamic. It seemed a great choice of the kind of app I like to write – lots of physics.

The result can be seen here:

This is my entry in an internal hackathon at work. The development did take some interesting turns that I may now have time to blog about.

iOS: A Three Year App Development Odyssey

I have spent three years of spare time to create a single App. Upon reflection this seems more than a little crazy until I remind myself that the goal was not so much to get the App out into the world but to teach myself about iOS game development from “soup to nuts”. It was very satisfying to be completely curiosity driven.  This was a complete departure from the ruthless pragmatism that informs the way I code in my day job.

The catalyst was the fact that in my day job I had taken on the role of leading R&D in a start-up. The dev team knew what they were doing and what the company really needed me to do was articulate our vision to customers and analysts. As a result I found I had traded in Eclipse for Powerpoint and Word. After a while I found that I really missed the kind of problem solving that comes with developing software. At the time iOS was really hot and a hobby project in this area seemed like a good idea (admittedly, not an original thought).

When I get a blank sheet of paper I generally do something relating to physics. I had the great fortune to evolve from an undergrad in engineering into graduate degrees in physics. I had nearly gone into physics instead of engineering as an undergrad but I was wisely counselled that engineering had a much better chance of paying the bills – unless I was sure I could be at the top of the class. Good advice – and apart from a sojourn in graduate school my software skills have been how I pay the bills. When Java first came out, during my PhD in general relativity, I created applets that showed orbits in a variety of different forces. It seemed natural to try and link iOS and gravity in some way.

The journey started with something not too different from the old Java code from long ago. I got some basic iPhone code running with Quartz graphics added a bit of touch interaction and simple gravity evolution. It was ok but seemed a bit uninspired. At the time there were people in the startup doing graphics stuff. They kept talking about shaders and GPU code and I was curious about their world. I also thought it would be cool to make the gravity simulation do proper 3D. At this point I probably had invested about five months in iOS to get the Quartz game going. I decided to press reset and start again in OpenGL.

Getting OpenGL up and running was a BIG deal and caused at least a six month hit. It takes a while to have the right mental model of what is really going on in the shaders and without a graphics debugger using only newbie knowledge I ended up doing a huge amount of experimenting. The resource I used at the time was a book iPhone 3D Programming. This was a good introduction to OpenGL ES and I went between it and the Blue Book. I was able to get some reasonable 3D stuff going. I did find the C++ cross-platform framework in the iPhone book a bit unsatisfying. After all I was also trying to get some chops in Objective-C. However, I had running code and started to work on the touch interface and game flow.

During this time, in my day job, I had realized I just did not have the temperament to pitch for a startup and wave the flag day after day. I found a senior software role in a mature company and started to wade through their code. It is hard to adequately convey how bad this code was. As a consequence I started to read about dealing with bad code and started to take Clean Code seriously. This had repercussions in N-body. Since I could not have clean code “at the office” I tried extra hard to keep N-body clean. This resulted in some significant refactoring in N-body.

Then iOS5 came out. It had GLKit routines for math and utility routines for texture loading at a time when I was just starting to realize the values of texture atlases. Again, I rushed towards the shinny new thing and refactored out all the C++ code making some structural improvements along the way. I found it very useful to revisit design patterns in the context of Objective-C. The structure of a language and it’s libraries often informs the style in which common problems get solved. I found Cocoa Design Patterns a big help in getting into the flow of Objective-C coding. Another big bonus was a colleague who had a long history in MacOS development and was generous with his time. I also used this opportunity to go all the way to the bottom in OpenGL. Since I had no strict self-imposed deadline I messed around with how vertices were generated, how the lighting in the shaders work, normal maps for texture simulation, how to map strings into textures into transparent objects, and on and on. (Once iOS6 came along the Xcode OpenGL debugging became much easier. That feature in Xcode is hugely powerful).

In parallel with this I was working through Solar System Dynamics and became entranced with the weird tadpole and horseshoe orbits that occur as bodies oscillate about Lagrange points. I really wanted to show these orbits in the co-rotating frame and find a way to interactively generate some intuition about how variations in starting conditions affect the orbit. This added more time to the development. Then I stumbled into the choreography orbits. These were amazing but didn’t quite hang in there with the integrator I had in my physics engine. This sent me on a detour to learn more about choreographies and change the physics engine to do fourth-order Runge-Kutta evolution.

Finally, it seemed like a good idea to have built-in autoplay for all the levels – so I could regress after making changes to the integrator. This took a further investment in time but one which on reflection was time well spent. I found a number of issues during these regression tests.

Then it was time to polish. This is a challenge for me. I have a half dozen other cool physics game ideas and a shelf of unread books. Somehow I managed to stay focused and get N-body done to a level that I felt I could stand behind. There are things I wish were better, levels I wished I had time to add but I forced myself to just record all the diversionary ideas and after two and half years stop wandering off and stop the feature creep.

Finally, I started beta testing (using TestFlightApp as recommended by a friend – it’s awesome). Bugs were found, discussion on the merits of what the app was and wasn’t were had. After some reworking and a bunch more polish I deemed it was ready to submit.

Okay, I think I get where the three years went.

Hunting Zebras in Outer Space

I once took a graduate course: ”Physiology of Excitable Cells I” run by an eccentric British professor who wanted to teach in a far-reaching classical sense. (In the first class on hearing my surname he commanded ”Next week you will tell the class the connection between your name and Sherlock Holmes”; perhaps a bit off-topic given the course title). One thing he said that has stayed with me is that common problems have common solutions. He was discussing how all the medical students he taught were quick to assume a patient had a rare condition, instead of something more mundane. The tag line they teach medical students is:

“When you hear the sound of hooves, think of horses not zebras”.

I use this phrase a lot when it comes to debugging issues in software. It’s far too easy to believe I am the victim of some fiendishly clever interaction in my system or (so help me) a compiler bug. The answer is (to first order) always that I have done something very dumb or just failed to see an edge case. After a long time writing code I am a lot less likely to get caught by this. However, it did happen to me with N-Body and I was so amazed at how dumb I had been I had to close the laptop and go for walk.

The issue related to the use of sprites for a collision. They seemed to work pretty well except on a level where I had a number of other masses moving around. The latent trap was that I felt guilty about the quick way I had pushed sprites into the code. I decided not to worry too much about optimizing them and allocated a sprite group on the fly. I know it’s better to pre-allocate a sprite pool and all that – but at the time I added them my main focus was elsewhere and I knew I would have to come back and clean them up.

So when I hit an issue where collisions on a busy level resulted in a serious pause in the game loop – I decided the time had come to finally put in sprite pools. That HAD to be the source of the issue. Off I went, with the added fun of feature creep in the refactoring. All in all I spent about ten hours. It made no difference.

The real issue showed itself when I was doing the feature creep part of the refactoring. The loop nesting was wrong and I was running the sprite evolution inside a loop that was running over each body in a level. When there were five masses, I evolved the sprites five times per clock tick and things got really slow. Instead of looking hard for a simple error I had jumped to the conclusion that it must be due memory inefficiency and my use of on-the-fly allocations. Doh! I was amazed I had gone on such a long Zebra hunt.

I have used the Zebra hunting metaphor for such a long time that sometimes I now use it without setting the context properly. I was working with our very bright overseas team in India but thought that this time they were on the wrong track, chasing a theory that seemed too intricate. When my manager asked me how they were making out I responded ”Oh, I think they’re off Zebra hunting”. He replied ”Really?! Do they have a holiday or something?”. I then explained my metaphor as well as the fact that India does not have Zebras…

N-body Choreographies

You would think that after three hundred years the consequences of the law of gravity for “simple” systems would have been pretty well studied and nothing surprising would emerge. Amazingly there is such richness and complexity in the physics of three masses that new discoveries are still being made.

The opening of the door was the paper “Braids in Classical Gravity” by Christopher Moore 1. This did open the door but the paper seems to have missed its audience a bit since one of its results was rediscovered a few years later 2. What these papers discovered was new families of solutions to the gravitational N-body problem not just for N=3 but for much more complex systems. They involve a mathematical assumption that the N bodies follow the same path and were termed choreographies. The gem at the center of all these solutions is a stable figure-8 solution for three equal masses.

These solutions are hypnotizing and as soon as I learned of them I had to get them into the N-body app. The solutions have very special initial conditions and when I first put them in they did not evolve as expected. The version of N-body at the time had a very simple numerical integrator, known as Leapfrog with a fixed time step 3. The choreographies required a more careful approach. Even though N-body was close to being ready to go I could just not give up on these choreographies. So I put in a 4th order Hermite integrator with some adaptive time step capabilities. This was enough to get the simple chain choreographies running. (I then found some more cool choreographies on arXiv, in fact new classes of choreographies. These will need more integrator tuning but look for them in a future update to N-body. In addition the Java gallery by Vanderbei has some solutions I’d like to include in the next release).

I’d love to understand how these solutions are found, but I’m just not there yet. Scholarpedia N-Body Choreographies  is great place to start. A useful expository paper that also finds even more solutions (including some new non-choreography solutions) is Vanderbei’s New orbits for the N-body problem. His paper provides code to calculate choreographies in the specialized language AMPL. This makes the details of the search quite clear, even if you (like me) have never seen AMPL before.

Based on what I’ve absorbed thus far it seems the general idea involves using a path optimization approach using variational principles. This comes from an idea which is in the very core of physics, the notion of finding the path along which a specific quantity (the action) is an extreme value. I learned how to do this when I was in graduate school but I have always been a bit baffled by how the mathematical machinery is searching over paths. There are such a huge number of possible paths! The key mathematics here is the calculus of variations. I’ve gotten as far a buying a copy of the classic staring point Calculus of Variations (aka Gelfand and Fomin) but it is still mocking me quietly from the shelf…

 

Notes:

  1. Phys.Rev.Lett 70:3675-3679. This was in turn anticipated by M. H´enon (1976) “A family of periodic solutions to the planar threebody problem, and their stability.” Celestial Mechanics 13 267–285.
  2.  A. Chenciner and R. Montgomery (2001) “A remarkable periodic solution of the three body problem in the case of equal masses.” Annals of Mathematics 152 881–901.
  3. This is a good place to acknowledge the places I read about N-body evolution codes.  Firstly, Moving Stars Around which is written in a quirky Socratic-dialog style. As part of the learning arc some of the code shown has deliberate errors that are then explained, so be careful. Everything you ever wanted to know about the subject is in the comprehensive Gravitational N-Body Simulations: Tools and Algorithms (Cambridge Monographs on Mathematical Physics). For a more concise summary of N-body codes and their pros and cons the section in Galactic Dynamics: (Second Edition) (Princeton Series in Astrophysics) is very to the point. 

+1 Changes Everything

There are times in physics when what seems like a simple extension to a problem causes the floor to drop out. The motion of three bodies due to gravity is one of those cases. For the two-body solution there is a modest differential equation and a solution that describes the motion as an ellipse, parabola or hyperbola. Adding a third body seems like “no big deal”. You might think that the math gets a bit messier so maybe the solution will not be quite as clean as a simple ellipse – but there should still be some kind of sensible solution. This is one of those cases where our optimism/intuition fails.

Newton’s work was published in the 1680s. It took other great mathematicians to get further. Euler found an unstable 3-body solution in the early 1700s. Lagrange found another unstable solution as well as some stable solutions in special cases for the 3-body problem. His work was published in 1772 – almost a hundred years later. [Lagrange also fundamentally changed physics with his Mechanique Analytique. Today huge parts of modern physics is still rooted in “the Lagrangian”].

Lagrange found a few special cases where three bodies could stay in a stable solution by making simplifications that result in what is called the “restricted three body problem”. In this case one body is “heavy”, the other has moderate mass and the third has no mass. As a concrete example think of the Sun, Jupiter and an asteroid in the same orbit around the sun as Jupiter. As a further simplification, assume Jupiter moves in a perfectly circular orbit. It is then convenient to think in terms of the position of the third massless body in relation to Jupiter i.e. in a co-ordinate frame that rotates around the sun at exactly the same rate as Jupiter. Lagrange found there were five points at which the third body experienced zero net force and could stay fixed in relation to Jupiter in this rotating frame.

This in itself was an interesting result. However these five Lagrange Points would only be really interesting if the massless body actually stayed in this relation to Jupiter even if it was bumped away from this zero force location i.e. if the motion around a Lagrange point is stable. It turns out that two of the five Lagrange points are stable but there’s a catch. The catch is that the Lagrange points L4 and L5 are stable only if Jupiter is not “too heavy” compared to the sun. Exactly how heavy? L4/L5 are stable as long as Jupiter is not more than 3.85 percent the mass of the Sun.

These points are of more than academic interest. This solution motivated a search for asteroids near these locations in Jupiter’s orbit and as the technology of telescopes improved the first such asteroid, Achilles, was found in 1906. There are now thought to be as many of these “Trojan” asteroids as there are asteroids in the belt between Mars and Jupiter. Other planets have such asteroids as well. Recently, more asteroids were found at the L4 point of Mars (http://arxiv.org/pdf/1303.0124.pdf).

What if the test particle is not quite at the stable Lagrange points L4/L5 or does not have quite the right velocity? Then the resulting motion is very interesting. This leads to orbital paths relative to Jupiter that get names such as tadpole or horseshoe orbits, due to their shape – you can get a sense of why these names arise by playing the levels in the Lagrange group in N-body. The image below shows oscillations about the L5 point in the N-body iPad app.

Tadpole

Oscillations about Lagrange points also have real-world implications. For example, the detection of a dust ring around Uranus puzzled astronomers since location of the ring could not be stable. It was proposed that there were “sheparding satellites” 1. Subsequent discovery of two small moons, Ophelia and Cordillia by Voyager lend credence to this idea. 2

Amazingly (and a testament to just how opaque the physics becomes when N=3) another stable three body solution for equal masses was found in the 1990s more than two hundred years after Lagrange. It was a result of considering topologies of paths. We’ll look at this fascinating solution and some of it’s unstable cousins in the choreography group of N-body levels.

One aside: In general relativity the step of going from one to two makes the floor fall out. In the case of Einstein’s general theory of relativity (GR) finding a solution for ONE body is really hard. The spherically symmetric solution was found by Schwarzschild in 1916 about a year after GR was published. It took until the 1960s before the axially symmetric one-body solution was found. There are no two body solutions corresponding to a simple orbit that can be written in terms of modest mathematical functions. This is part because in GR the idea is that gravitational interactions do not operate via a force but by defining the shape of the space they are part of. As bodies move around each other there are ripples in space-time (waves) that need to be taken into account. This makes things very messy. Numerical modelling and simplifications can be employed and things can be learned – but there is not a tidy mathematical description.

Notes:

  1. Goldreich and Tremaine (1979) Nature 277 97-99
  2. See the discussion in 10.5.3 of Solar System Dynamics