

Thursday, 24 April 2014

A Brighter BubbleSort

On of the great things about embedded computing is that it lets you measure all sorts of fun things. By taking programming out into the "real world" it becomes much more engaging, but then we bring it back home and display it on a screen and it all gets a bit dull again. What if we could display our results in a physical fashion?

I just got hold of 1m of SMRT Pixels from Embedded Adventures. These are basically the same as AdaFruit NeoPixels as they're both based on the WS2812B chip/led system. NeoPixels are tricolour LED's, but what makes them special is that they have a controller embedded on each one which allows you connect them together in a chain, and control any number with a single control pin. The colour of each of the 30 LED's in my 1m strip can be individually controlled!

The way these works makes them very tricky to program, as the timing has to be accurate to about a micro-second. This is hard on a 16Mhz Arduino, and even harder on a Pi as its got a whole load of other code running on it at the same time. Fortunatly AdaFruit have some good Arduino code, so I took that and wrapped it into a Sniff "neoPixel" device - currently Arduino only.

make neoPixel device 3
make neoShade list of number
make neoColor list of number

The string of pixels is connected to pin 3, and the colour of the pixels is controlled by two lists - neoColor and neoShade. These follow the Scratch pen colour model, that the newColor list sets the Hue, while the Shade controls brightness.

To turn the LED's on we just give them a colour:

when start
.set ledCount to 16
.set ledA to 0
.repeat ledCount
..add (ledA/ledCount)*120 to neoColor
..change ledA by 1
.tell neoPixel to "show"

We're not worried about brightness, so I've ignored the neoShade list - if you don't add entries to that list it assumes the default value of 50 (0 is black, 100 is white, 50 is a fully saturated colour). The neoColor list is filled in with values from 0 to 120, which is 1/3 of the way round the colour circle from Red to Green. 360 takes us all the way back through blue and back to red again (Scratch uses a value of 200 but 360 makes far more sense!).

Of course the obvious thing to do is produce lots of cool animated patterns - which of course I did, but there's plenty of other fun things you could do to visualise data using these: you could make a Pie Chart (or what ever a linear Pie chart is called?), you could move dots at specific speeds, you could make a giant thermometer. You can of course cut these into shorter strips, so you could make a digital abacus, or a clock face, or any number of cool things (I've got a totally insane project in mind for these, but thats for another day!).

I filled the strip with red to green rather than a full spectrum for a specific reason... because we're going to sort them, and red to green has a clear "order". Sorting is a classic computer science problem, and it usually involves lists of numbers. The SMRT/NeoPixel strip makes in physical! Rather than some abstract values, the colours actually mean something, and we need to "repair the rainbow!".

First we need to break the rainbow:

when swap
.set tmpVal to item ledA of neoColor
.replace item ledA of neoColor with (item ledB of neoColor)
.replace item ledB of neoColor with tmpVal

.repeat ledCount
..set ledA to pick random 1 to ledCount
..set ledB to pick random 1 to ledCount
..broadcast swap and wait

The best way to make a messed up list is to start with a good list, then pick random pairs and swap them over. If you think it would be better to just generate a list of random numbers, feel free to read up on low discrepancy sequences, then come back and do it my way... (actually its not really a big deal here, but something like a Halton Sequence is far better than random numbers for lots of applications - but I digress).

To help us see what going on we can create a showSwap script which flashes the pixels back and forth a couple of times, so we can see they're being swapped:

when showSwap
.repeat 3
..broadcast swap and wait
..tell neoPixel to "show"
..wait 0.01 secs

when showNoSwap
.repeat 2
..broadcast swap and wait
..tell neoPixel to "show"
..wait 0.01 secs

showNoSwap does the same, but leaves them back where they started, so we can show they were compared at but not swapped.  You probably want to adjust the timings to slow things down (unless you're trying to make the whole demo fit in a six second video).

.repeat ledCount
..set ledA to 0
..repeat ledCount-1
...set ledB to ledA+1
...if item ledA of neoColor > item ledB of neoColor
....broadcast showSwap and wait
....broadcast showNoSwap and wait
...change ledA by 1

And finally we're ready to sort the list, using a bubble sort. A bubble sort compares the first two items, and if they're in the wrong order its swaps them. It then compares the second and third, and so on until it reaches the end of the list. If you repeat that enough times, then the list ends up sorted (enough times being some unknown number less than or equal to the number of elements in the list).

I feel compelled to point out that bubble-sort is a TERRIBLE way to sort a list, and this isn't even a good bubble sort, but its probably the first sort everyone learns, and the point here is that we're visualising the sort,  not that we're doing a good job of sorting. You really should be using something better - a comb sort or shell sort is only a little more complex. A quick sort is generally best, but is a bit more tricky...

The code for this will of course go into the next Sniff release, but for now you can download and install the files yourself:Download

The code is tested on a standard 16Mhz Arduino, but should support a variety of AVR speeds, and the Due ARM board. If you try it on any other boards, then let me know how you get on.

No comments:

Post a Comment