Elite, Making Galaxies and the Fibonacci Sequence

As the Elite: Dangerous Kickstarter draws to (hopefully) a successful launch, it reminded me of an anecdote from the original game’s development. David Braben and Ian Bell are probably two of the UK’s most famous “bedroom coders”, who teamed up to create the classic BBC Micro game Elite when they arrived at Cambridge University in 1982. During the development they hit a problem which ended up with them seeing the following pattern:

34 55 89 144 233 377 610 987

You might recognise that sequence as it’s part of the Fibonacci sequence which describes an integer pattern where each new number is the sum of the previous two, it starts 0,1,1,2,3,5 and so on.

It’s a very useful pattern and it can be modified if you supply the two starting numbers which is exactly what Ian Bell and David Braben did when they were writing Elite. They used this pattern to provide an efficient way to create a structure on which they could automatically generate huge numbers of galaxies for their game – in the end, they artificially limited the number so as no to make it too sparse.

What’s interesting about this is that it goes right to the heart of why teaching programming brings wider benefits, particularly in the way we approach and think about problems. Ian and David only had around 22k of memory in which to write their game (for comparison, 22k is about the size of a small thumbnail image on a website) and they quickly realised that building a galaxy by hand would quickly eat away at small amount of memory so they needed a plan b and saw a ‘pattern’ that could be filled by a self-generating sequence.

Programming is often thought of as a very cold mathematical pursuit but it’s also about looking for/recognising patterns, alternative routes and is very often about working within constraints, e.g. too little time, memory, etc Both of these aspects teach you skills that reach beyond computers and technology. Interestingly, one of the main comments from Nicola Scholfied who’s teaching programming in St Morden’s primary school, is that it teaches independence and a ‘try, fail, repeat’ mentality.

Here’s a little snippet from the recent book by Francis Spufford “Backroom Boys” which described their approach, it’s re-printed here in this Grauniad article

They could encode all the information on a particular solar system in a relatively short row of digits. That number, it occurred to them, wouldn’t have to be stored if it were an iteration in a Fibonacci sequence – or a Fibonacci-like sequence, anyway. All you would need would be a starting point, a rule for doing the iterations, and a mechanism for extracting the information from the number.

Some digits controlled the physical specs of the system: the size, the location, the number of planets. Some determined local politics. Others grew into brief flourishes of verbal description – which always read a little weirdly, put together as they were from stray adjectives and nouns. Since the adjective list contained “carnivorous” and the noun list contained “arts graduates”, it was possible to land on a planet where all the inhabitants were, yes, carnivorous arts graduates: a little swipe maybe at Cambridge – not random but pseudo-random. As the player entered the star system, then, it swelled into existence as if it had always been there.