Countdown 2 (Extinction!). Genetic Algorithms!

In the last post we saw how how we could encode solutions to the Countdown numbers game as strings, and write Sniff code to both generate potential solutions and evaluate them. Using brute force we could generate thousands of solutions, and test them until we found a good one.

It actually worked pretty well but it required a lot of trials to find solutions for trickier problems.  In comparison we can be pretty sure that a human player could only check perhaps at most 50 solutions in the 30 seconds available to play the game? There's obviously a better solution, but what?

The computer generates a guess, tests it and if it doesn't work throws it away. By comparison, a human would also make guess and test it. Leaving aside that the humans "guess" probably isn't entirely random, when a human gets a "close" guess they don't throw it away for not being perfect - they try and "fix" it. If I need to make 804 and I gave 50 4 4 and 1, my first try might be 50x4x4 to get 800. That's pretty good. Rather than starting over I'd realise I can tweak the solution to give (50x4+1)x4=804.

Of course humans use all sorts of "skill and judgement" to arrive at good solutions, but the basic idea of taking a good solution and tweaking it to see if we can find a better one is the basis of "Genetic Algorithms".

A GA operates by generating a whole load of random solutions (we've done that already), and then testing them against a "fitness function" - how good a solution are they? Bad solutions are thrown away, and good ones get to produce offspring - solutions which are similar, but not exactly the same as the known good solution. The hope is that the offspring will keep the best bits of their parents, and maybe even improve, producing new, better solutions.

There are two main ways of generating new potential offspring from a known good solution. The first is mutation - just go through and randomly change some of the characters. For example if we want 101, and we have a promising solution of 4x25-1=99, then it might mutate next time of "4x25+1=101.

The other option is "crossover" where you take two good solutions, and pick the best bits from each. For example to make 125 we could have tried 5x5+50+10+10=95 and 50-5-5+10x10=140. They're both ok-ish solutions so but if we take the first part of the first one, and the second half of the second we get 5x5+10x10.

As we already have our solutions encoded as strings we can mutate them pretty easily:

when mutateCandidate
.make index number
.make newCandidate string
.make l string
.make r number
.set newCandidate to ""
.repeat length of candidate using index
..set l to letter index of candidate
..if pick random 1 to length of candidate=1
...if value of l = 0
....set r to pick random 1 to 9
....if r < 4
.....set l to "*"
....else
.....if r <7
......set l to "*"
.....else
......if r <9
.......set l to "-"
......else
.......set l to "/"
..set newCandidate to join newCandidate l
.set candidate to newCandidate

Mutating the card numbers would be tricky, so to keep things simple we just mutate the operations - that way we're sure that the new rule is valid. If we were to start changing the numbers we'd need to make sure we didn't use the same one twice, and swapping numbers of operators would upset the "balance".

Similarly crossover is a bit tricky, but there's a simpler way to handle it, which in many ways resembles a human approach - if we want 803, then we would start with 100x8=800, then start tagging things on the end to get a better solution. If they don't work we go back to 8x100 and try different things. With a but of tweaking we can modify our random solution generator to be a random solution comption script (making a new solution is just completing the empty string).

.repeat 10
..broadcast makeCandidate and wait
..add candidate to population

Now we can start by making 10 potential solutions and adding them to a population list.

.repeat until evalCount>1000000
..set index to 1
..repeat until index> length of population
...set candidate to item index of population
...broadcast evalCandidate and wait
...
...set offspring to 10
...if  abs of (eval - target) < bestErr
....set bestErr to abs of (eval - target)
....broadcast prettyPrintCandidate and wait
....say candidate
....say pretty
....say join "="[eval]
....if bestErr=0
.....say join "Evaluations:" [evalCount]
.....stop script
...if abs of (eval - target) > 10 * bestErr
....delete item index of population
....set offspring to 0
...else
....change index by 1

We then go through the population evaluating them. We keep track of the best one we've found, and if a solution is 10 times worse than the best we throw it away.

...
...set parent to candidate
...repeat offspring
....set candidate to parent
....broadcast truncateCandidate and wait
....broadcast mutateCandidate and wait
....#say join join parent "=>" candidate
....if not (population contains candidate)
.....add candidate to population

Then for each good solution we generate some new ones by truncating (and completing) the good one, mutating it and adding it into the new populations.

Lets test this.

Target:979

Numbers:75 8 6 4 2 9

Using brute force we find the solution:((8+((75*(9+4))-6))+2) after trying 56779 potential solutions. Our GA tries only 6296. However it didn't always work so well.

Given 803, and the numbers 100, 75, 10, 2, 2 ,8 the obvious solution is to start by multiplying 8x100 to get 800, and then mess around with 10, 2, 2 and 75 to get the remaining three. I suspect I'd end up with 802, or 804. It turns out there is an "easy" exact solution: (9+2)+(75-2)=803. The reason we miss it is that we're stuck in a "local minima". We've found a "good" solution, and we think we can tweak it to get a perfect one, when in fact the perfect solution looks nothing like the "good" one. The random generator will eventually find the perfect solution, but our smarter GA gets stuck trying to tweak the good one.

Of course a human would eventually give up. In fact our truncation stategey will occasionally throw out a rule completly and generate an entirely new candidate, but it still wastes a lot of trials. Looking at some  of the really bad results for the GA (When it did much worse than random), we saw that often is was the result of a divide. The better the solution we have, the more likely we are to throw out other solutions: if our solution is 5 away, then anything that is within 50 gets to play the next round. However we occasionally say results where we were 0.3 away, so almost all other solutions were discarded. Adding some code to block non-integer divides improves perfornance further, and we find our solution to 979 in only 729 trials! That's almost 100 times faster than brute force!!!

That gain however isn't representative: Over 1000 test puzzles, brute force averaged 60,597 attempts before getting the solution, while the GA averages 33,255. That's still a 50% improvement. The GA did better than random on a slightly disappointing 623 of the 1000 tests, but that's not really the whole story - subjectively brute did better on very easy and very hard puzzles. Sometimes brute force got lucky and found the solution to easy puzzles in under 1000 trials. For such easy puzzles, just guessing was likely to find and answer more quickly than trying  to work it out. For some the harder puzzles the GA got locked into local minima. However when GA did work (as in the 979 test) it showed some really good results.

The code for all this will be in the next Sniff release. There's lots more you could do with this - at least try changing the initial population size, number of offspring, and criterea for killing candidates. More complex mutation and crossover strategies would also be worth investigation, or try applying the approach to different number puzzles.

Countdown to extinction is of course also the title of a Megadeth album, and not one but three Transformers episodes!

Countdown (dada dada dada-dada, dum)

Countdown is a TV show that frustrates me as a maths/engineering person... The numbers game is great but I have to sit through four rounds of anagrams to get one maths puzzle (consider what that says about how society values technical skills vs literary skills...). Fortunately here I make the rules, so we're just doing the numbers game!

Pick up to four "big" numbers (but usually 1, sometimes 2  rarely more), then make that up up 6 selections using small numbers. Then a random number between 100 and 999 is generated. Now in 30 seconds use your mental arithmetic skills to derive the big number from the small number.

It turns out this has some real merit as a game: As this Real Maths analysis shows provided you pick 1 big number the statistics fall in a sweet spot that the solution is almost always possible, but only rarely obvious.

I fancied writing a program to solve Countdown puzzles in Sniff, so here's my first go at it.

make N list of numbers
make target number

make sourceN list of numberswhen pickNumbers
.make index number
.delete all of N
.delete all of sourceN
.
.add 25 to sourceN
.add 50 to sourceN
.add 75 to sourceN
.add 100 to sourceN
.
.set index to pick random 1 to 4
.add item index of sourceN to N
.delete item index of sourceN
.if pick random 1 to 5 = 1
..set index to pick random 1 to 3
..add item index of sourceN to N
..delete item index of sourceN
.
.delete all of sourceN
.repeat 10 using index
..add index to sourceN
..add index to sourceN
.
.repeat until length of N = 6
..set index to pick random 1 to length of sourceN
..add item index of sourceN to N
..delete item index of sourceN

To start with we need to generate a random puzzle to solve: a target number (Easy), and a set of numbers to make it from (not so easy). To generate a typical set of cards, we create a list sourceN which initially we fill with the big cards. 1 time in 5 we take two of those, otherwise we take 1. We then fill sourceN with 2 of each of the numbers 1 to 10, and fill up N with randomly selected cards (remembering to delete them from sournceN when they're picked).

We're going to need to generate solutions  and check it to see if they work. Which raises the critical  question of what does a solution look like?

The solution is obviously an equation. For example to make  796 from 50 3 4 3 7 10 we can do

(50+7+4)*(3+10)+3. Thats a pretty neat solution (if you know what 61*13 is!), but the problem is that regular maths notation is just too messy. For a start we need to remember that we * before we +, and when we don't want to do that we have to put brackets in to make sure everything works properly. Writing code to understand that is pretty hard. We can make things a bit easier if we always put brackets in:(((50+(7+4))*(3+10))+3). Now we don't have to worry about what order to do things in, but its still tricky.

Regular maths notation is great for representing equations, but not great for helping you do calculations. What we want is a notation that actually gives us a set of instructions for doing the maths. The way we generally do that is using "Reverse Polish" notation :RPN (that's as in the country, not the cleaning product). Instead of writing 1+2 we write 1 2 +. To evaluate an expression you just work from left to right. When you see a number you append it to the end of a list of numbers called the "stack". When you see an operator (+) you use the last two numbers in the list, remove them from that list and put the result back at the end of the list. So here we "push" 1 and 2 onto the stack, the perform a "+" which removes those, adds them, and puts the resulting 3 onto the stack.

If we want to evaluate 1+2*3 we could write in in RPN as 1 2 3 * +. Push 1, push 2, push 3 now multiply the top two (2 and 3) so that leaves 1 and 6 on the stack. Now add, to leave 7.

If we actually wanted (1+2)*3 we would write it as 1 2 + 3 *. Push 1 and 2, add them to leave 3. push another 3, multiply them to get 9.

Doing maths like rearranging equations on paper in RPN would be strange and tricky, but here we want to do calculations, so its exactly what we need. If we can generate equations in RNM then we can write some code to evaluate them pretty easily:

make stack list of numbers
make eval number
when evalCandidate
.make val number
.make index number
.make l string
.delete all of stack
.repeat length of candidate using index
..set l to letter index of candidate
..if l = "+"
...set val to item last of stack
...delete item last of stack
...set val to val + item last of stack
...delete item last of stack
...add val to stack
..if l = "*"
...set val to item last of stack
...delete item last of stack
...set val to val * item last of stack
...delete item last of stack
...add val to stack
..if l = "/"
...set val to item last of stack
...delete item last of stack
...set val to val / item last of stack
...delete item last of stack
...add val to stack
..if l = "-"
...set val to item last of stack
...delete item last of stack
...set val to val - item last of stack
...delete item last of stack
...add val to stack
..if not value of l = 0
...set val to value of l
...add item val of N to stack
.set eval to item 1 of stack

To evaluate a candidate string we simply go through one letter at a time and "follow the instructions". When we see an operator we perform the operation. When we see a number we treat it as a card number, get that card from the deck, and put it on the stack. As there are only six cards, we'll use the numbers 1 to 6 to represent the 6 cards, so we know that 25 means card 2 then card 5, rather than having the potential to confuse 2, 5 and 25. So our rules are going to look something like: 34*2+56++ (Card 3 *Card 4)+Card2+Card5+Card6.

Now we can evaluate a candidate, we can set about making some:

when makeCandidate
.make index number
.make balance number
.make r number
.delete all of sourceN
.repeat 6 using index
..add index to sourceN
.
.set balance to 0
.set candidate to ""
.repeat until balance=1 and length of candidate>5
..set r to pick random 1 to 2
..if length of sourceN>0 and (balance<2 or (balance<4 and r=1))
...set index to pick random 1 to length of sourceN
...set candidate to join candidate  [item index of sourceN]
...delete item index of sourceN
...change balance by 1
..else
...set r to pick random 1 to 9
...if r < 4
....set candidate to join candidate "*"
...else
....if r <7
.....set candidate to join candidate "+"
....else
.....if r <9
......set candidate to join candidate "-"
.....else
......set candidate to join candidate "/"

...change balance by -1

We put the numbers 1 to 6 to represent the 6 cards into sourceN and we remove them as we use them to that we don't use each card more than once.

We then generate a string one l letter at a time - each letter being either a card number or an operator. Nominally we pick a random number and choose each equally, but there are restrictions. We can't pick a number if there are no cards left. We can't pick an operator if there are no numbers on the stack to use. We keep track of how many numbers are on the stack using "balance". Initially it starts of as 0. When we add a card it increases by 1. When we add an operator it decreases by 1. If balance <2 then we can't perform any operators. If balance becomes large we probably shouldn't add any more numbers. We keep going until we have a string longer than 5 characters with a balance 1 (the answer we hope!).

Most solutions use * and + a lot, - a occasionally, and / almost never, so if we choose to select an operator then we bias the selection towards the more common operators. It would be interesting to see if in fact there are large numbers of solutions that could use division but simply don't because its "less obvious". However the danger is that division takes us out of the Natural numbers. We strictly shouldn't use fractions or negative numbers, but I've allowed them because they'd complicate the code, and I think that almost any solution which uses them would have an obviously equivalent solution that uses just Natural numbers.

Now we can generate a random puzzle, a random solution and see how good that solution is:

when start
.set target to pick random 101 to 999
.say join "Target:"[target]
.
.broadcast pickNumbers and wait
.say join "Numbers:" [ N ]
.broadcast makeCandidate and wait
.say candidate
..broadcast evalCandidate and wait
.say join "=" [eval]
.say join "err:" [abs of (eval - target)]

So to find a good solution we can just do that thousands of times and pick the best:

when start
.ask "ready?" and wait
.set target to pick random 101 to 999
.say join "Target:"[target]
.set bestErr to target
.
.broadcast pickNumbers and wait
.say join "Numbers:" [ N ]
.repeat 10000
..broadcast makeCandidate and wait
..broadcast evalCandidate and wait
..if  abs of (eval - target) < bestErr
...set best to candidate
...set bestEval to eval
...set bestErr to abs of (eval - target)
.
.say ""
.say best
.say [bestEval]
.set candidate to best
.broadcast prettyPrintCandidate and wait
.say pretty

As a final trick, I wrote another script "prettyPrintCandidate". This operates pretty much the same as evaluateCandidate, but instead of calculating the result of the calculation it calculates the regular string representation of the expression so 12+ becomes (1+2).

The code works supprisingly well, and actually performs similarly to a human player - with 10,000 tests it gets most smaller targets, and does pretty well on targer targets, sometimes getting them, and often being 1 or 2 off. One quirk, because we don't disallow fractions is that it produces non-integer "close" answers - occasionally being off by 2/3's.

The brute force solution runs in only a fraction of a second, so its pretty effective. However the next question is can we do better? I think we can, but I'll save that for another post...

Sniff Games (part 2): Catch the Flowers

A few years ago Blackberry had a promotion for developers to try and get them to support their Playbook tablet - write an App, and submit it to their App store and they'd send you a free Playbook. At the time the Playbook was decent hardware and was pretty cheap, so I bought one wrote a simple game, give it away on the app store, and got a second playbook free. I planned use them for more serious dev work and port some of my other code to them.

The app I wrote to get a free Playbook was a fun little game called "Catch The Flowers". My daughter was off school feeling unwell (she was probably in year R or maybe year 1), and to pass the time we designed the game, and she drew the artwork on the side of an old cardboard box. I just photographed it and used it with the minimum of editing and tidying. This is a great approach, as the hand-drawn images capture the fun of the game far better than digitaly produced images could.

As we've been developing a sprite system for Sniff it seemed like a good idea to revisit the game and port (i.e. rewrite) it to run in Sniff on something other than an old unsupported tablet.

The aim of the game is to collect flowers - petals fall from the sky, and you catch them one at a time. When you catch 5 they make a flower which appears in the bottom left. The problem is that each flower needs to be a single colour. There are 4 colours of petals and once you start catching one type you need to complete the flower in that colour - mixing the colours costs you a life (and the petals in the current flower). White are the most common flower, and Pink the rarest, so collecting a whole flower of Pink is much harder, and scores accordingly. When you collect a whole flower an extra  falling petal is added to the game - you might think this makes it easier but when the number of petals increase it gets harder to avoid the wrong colours.

Most of the code to write this is similar to the previous game examples where we make a sprite device, and move it around based on the keys that are pressed. We set up the Princess and Background sprites, just we have previously. However the petals, completed flowers and the lives remaining need a bit more attention.

We use a miniPrincess sprite to indicate lives remaining. This is has a smaller version of the princess artwork as a costume and is normally hidden:

make miniPrincess sprite device 

.set fileData to "Images/PrincessS.bmp"

.tell miniPrincess to "load costume"

.tell miniPrincess to "set unhittable"

..set spriteX to 30

..set spriteY to 440

..tell miniPrincess to "move to"

..tell miniPrincess to "show"

..repeat lives

...tell miniPrincess to "draw"

...set spriteX to 60

...set spriteY to 0

...tell miniPrincess to "move by"

..tell miniPrincess to "hide"

After we've drawn the main sprite list we call "draw" on the sprite ourselves to stamp the  required number of princesses to indicate the number of remaining lives. We use a similar approach to drawing the completed flowers, and the flower that's being collected.

The real interesting aspect of the game however is the main falling petals. So far we've created sprites when we write the code by making a sprite device. However sometimes we can't do that - we don't know how many petals are going to be falling, as the number increases as you progress through the game. Technically we need to "dynamically allocate" sprites - make them when we run the game, rather than fixing them into the code.

Fortunately if you've followed so far (and written some games using static sprites) then this is a pretty small step... Every sprite has an id: you can perform any operation you would normally perform on a sprite using "tell" by asking the spriteManager to do it for you:

.tell mySprite to "draw"

is the same as:

.tell mySprite to "get id"

.say [spriteID]

.tell spriteManager to "draw"

Every sprite has an ID, which you can get by telling to to "get id". We can then perform operations using the spriteID and the spriteManager rather than the sprite itself. This might seem like a waste of time, but it has a couple of advantages.

make petals list of numbers

when makePetal

.tell spriteManager to "make sprite"

.add spriteID to petals

.

.set fileData to "Images/LeafW.bmp"

.tell spriteManager to "load costume"

.set fileData to "Images/LeafY.bmp"

.tell spriteManager to "load costume"

.set fileData to "Images/LeafR.bmp"

.tell spriteManager to "load costume"

.set fileData to "Images/LeafP.bmp"

.tell spriteManager to "load costume"

Now we can use "make sprite" on the spriteManager to get a new sprite that doesn't have a name like a regular sprite. It just has a number. We can make as many of these as we need, whenever we need them. Though conceptually its a bit trickier (get up to speed with regular static sprites first!), we can do some neat things which make some stuff a lot easier:

when animatePetals

.make counter number

.forever

..repeat length of petals using counter

...set spriteID to item counter of petals

...set spriteX to 0

...set spriteY to -10

...tell spriteManager to "move by"

We've got all the spriteID's in a list called petals, so we can tell them all to move down 10 pixels. We use the same mechanism to check the petal to see if its hit the princess (only the princesss is "hittable"). The main game mechanic happens when we find that a petal has hit the princess:

...tell spriteManager to "check touching"

...if spriteHit

....set spriteID to item counter of petals 

....tell spriteManager to "get costume"

....if petalsCollected=0

.....set collectedColor to spriteValue

....if spriteValue=collectedColor

.....change petalsCollected by 1

.....if petalsCollected=5

......add collectedColor to levelColors

......set petalsCollected to 0

......broadcast makePetal and wait

....else

.....change lives by -1

.....if lives=0

......tell princess to "hide"

......tell princess to "set unhittable"

.....set petalsCollected to 0

....set petalIndex to counter

....broadcast resetPetal and wait

We check the petals colour (by getting its costume). If its the first petal in the flower then we use that colour. If not, we check that its the right colour. If it is then we record we've got one more. If we've collected 5, then we record we've completed a flower. If we've collected the wrong colour petal, then reset the flower, and subtract a life.

This whole block of code is quite dense, but it does fairly clearly sumarise the game logic!

As I got up to speed with what passed for the Playbook "Native Dev Kit", it was pretty clear that the Playbook SDK really wasn't ready for serious work. Blackberry didn't provide any code for displaying UI elements. They did however promise that Blackberry OS 10 was coming in a few months which would fix all of that.... So I waited, in pretty good faith, until 18 months later they announced that they couldn't be bothered to support the hardware we'd bought or the claims they'd made when we bought it...

Catch The Flowers was the only think I ever wrote for Playbook. It was a big hit with the family who loved the drawings (and sound effects!), so I'm really pleased to bring it back to a wider audience:

Catch The Flowers

Artwork and concepts by Anya (age 5)

Sound Design by Alex (Age 3)

Coding by Ian (Age withheld by request)

[slight aside: you might notice that in this post "tell" commands look a little different: Perviously we've used camelCase - whichIsWhereYouUseCapsToSeperateWords rather than spaces. You can still do that if you want to, but as of the next release (R20), we'll support the more kid friendly all lower case with spaces, so we've used that here]

The Beep test

One of the important ideas behind Sniff and the way we develop and promote it is that computing is pretty limited if it just lives in the computing classroom. That's why we've covered examples which use Sniff in Maths, Physics, Biology, English, Geography, and just about any other subject we can think of.

Today we add PE to that list!

The "Beep" test (also known as the shuttle test) is an exercise designed to measure aerobic fitness. First we make two lines 20m apart that you're going to run between. You start at the first line, and when you hear the beep you run to the second line. If you get there before the next beep, then congratulations you get a bit of a rest, till the next beep, when you run back. Every minute you'll hear a triple beep, which means that the beeps are going to get a little closer together. Eventually it will speed up to the point that you don't make the line. That's OK - the first time it happens just turn around and start running back. However if you miss a second beep you're out.

The fine print/technical details are that initially you need to run at 8kph. At the first triple beep that increases to 9kph, and it increase a further 0.5kph on each subsequent triple beep. Each level consists of the minimum number of shuttles to last over 1 minute. (though there are variations on this). Technically there are 21 levels, but professional athletes start dropping out as early as level 13. Note because you're running to exhaustion, this isn't recommended of for unfit adults - however kids generally don't have to worry about heart attacks, so its considered pretty good for them!

The traditional way to do this is to use a prerecorded audio track, but now we know the rules we can make our own beep test machine, using an arduino.

when start

.set level to 1

.set speedkph to 8.0

.set distance to 20

Lets start, initialising some variables. We stricty don't need a distance variable, as its always 20, but it will make our code look nicer to use the name rather than hard coding the value.

.broadcast beep

.

.repeat 21

..set speedmps to speedkph*1000/3600

..set interval to distance/speedmps

So make a beep (we'll figure that out later!), and then repeat for the 21 levels of the test. The rules tell us the speed in kph but that doeesn't really help. Problem solving 101: convert to SI units.  Multiply by 1000 to get meters per hour, then divide by 3600 to get meters per second.

Now we have the speed in a useful form, we can find the time interval between the beeps as distance/speed.

..set nextLevelTime to timer + 60

..repeat until timer > nextLevelTime

...wait interval secs

...broadcast beep

..broadcast tripleBeep

Now we know the interval, we calculate the time 1 minute in the future. We're going to keep going on this level until we've done more than a minute. So then wait for 1 time interval (everyone runs!), then beep. Everyone should have got to the end, and start running back. Then back round the loop to check if they've been running for more than 1 minute.

When we have got more than a minute, we sound a triple beep.

Finally we bump the level and the speed, ready to go around again.

..change level by 1

..if level=2

...change speedkph by 1

..else

...change speedkph by 0.5

All we need to add are the variable declarations (which we'll ignore for brevity), and the scripts to play the beeps:

when beep

.set buzzer to low

.wait 0.2 secs

.set buzzer to high

when tripleBeep

.repeat 3

..broadcast beep and wait

..wait 0.2 secs

One of the great things about Sniff is that these run at the same time as the main script, so don't affect the timing. You might also note that triple beep will start while beep is still running. That's OK, as it just restarts beep, and it sounds exactly as it should.

All would be great, and this "should"  work but there's a nasty edge case. If you check the timing chart you'll notice something fishy about level 8... At that level you should be running at 12kph, which gives an interval of exactly 6 seconds. So how many shuttles should you do? Well 10 shuttles would take 60 seconds, but look at the fine print... you need run each level for more than a minute, and so the official chart says you need 11 shuttles. Technically level 20 is similar, but that's not going to be an issue for pretty much anyone.

So how will our code behave? It looks like it should work, but are you sure? We're asking the computer to measure multiple 6 second intervals, and compare them to one 60 second interval. They should be the same, but that's not going to happen. We can be pretty sure that the code will actually take longer than 6 seconds to go around the loop, as it needs to do the tests and go back to the start of the loop as well as wait the 6 seconds. There's a pretty good chance it could take longer than a minute to measure 10, six second intervals - perhaps just a 10,000th of a second longer, but that would be enough to give us the wrong answer.

So how many shuttles should there be on each level:

..set shuttles to round (60/interval+0.5)

We divide 60 seconds by interval to tell us how many intervals would make exactly one minute, and then we round it to a whole number. However first we add 0.5 so that it always rounds UP. 60/6 is 10, but 10+0.5=10.5, which rounds UP to 11 - the correct answer.

..say join "Level:" [level]

..say join "Speed:" [speedkph]

..say join "Interval:"  [interval]

..say join "Shuttles:"  [shuttles]

Best of all we can easily check that this works by removing the delays, and adding some "say"s. Without the delays and edgy timing we can run the code in a second, and compare it to the chart, rather than have to wait 25 minutes to check its working.

Once we know shuttles is right for each level, we can replace our previous loop with:

..repeat shuttles

...wait interval secs

...broadcast beep

..broadcast tripleBeep

I ran the code on an Arduino with a multi shield attached, which has a buzzer build in. It also has 7 segment display, so you can make a really nice device. If you want to build something really cool you can get 7 segment displays over 15cm tall, and build a beep test machine for your school gym!

Playing Rock/Paper/Scissors with Sniff and the Leap Motion

This is the 100th post to the Sniff blog, and its a really fun one. The Leap Motion controller is like a Kinect for your hands (though the way it works is very different). It tracks your hands as you wave them around, and when it works its really amazing. In principle it can recognise the position of each joint of each finger and track it to milimeter accuracy. In practise it does that sometimes, then freaks out for a while, but its still super fun to play with.

The first thing I set out to do with it was teach it to recognise rock/paper/scissors - they're pretty distinct hand gestures, so we should be able to tell them apart. Assuming that you've already got the tracking software installed (you don't need the leap SDK), the next thing we do is set up a leap motion device in Sniff:

make leap leapmotion device
make handName string
make fingerNum number
make leapFound boolean
make leapPosX number
make leapPosY number
make leapPosZ number
make leapDirX number
make leapDirY number
make leapDirZ number
make leapVelX number
make leapVelY number
make leapVelZ number

That's a lot of variables - because the Leap produces a lot of data! However we're not going to be using the direction or the velocity in this example - just the positions.

when start

.forever

..set handName to ""

..set fingerNum to 0

..tell leap to "getPosition"
..

..if leapFound

...say join "Hand:" handName

...say join "X:" [leapPosX]

...say join "Y:" [leapPosY]

...say join "Z:" [leapPosZ]

..wait 0.5 secs

To get started here's the basic code to track a hand. We don't know which hand (yet), so we set the handName to "", and we're not interested in a specific finger, so we set fingerNum to 0. Then we ask the leap to do its thing!

If it finds a hand, then it tells is which it found, and fills in all the other variables, so we can print the hands position. EASY! You could take the XY positions and use that to move a sprite round the screen in a game!

We can use fingerNum to track specific fingers, so we're pretty much ready to go and build R/P/S. The easiest way to do this is figure the distance that each finger tip is away from the centre of the hand - big number means extended, small number means closed in.

make centerX number

make centerY number

make centerZ number

make indexDist number

make middleDist number

make ringDist number

make pinkyDist number

when start

.forever

..set handName to ""

..set fingerNum to 0

..tell leap to "getPosition"

..if leapFound

...set centerX to leapPosX

...set centerY to leapPosY

...set centerZ to leapPosZ

...

...set fingerNum to 2

...tell leap to "getPosition"

...set indexDist to sqrt of ((leapPosX-centerX)*(leapPosX-centerX)+(leapPosY-centerY)*(leapPosY-centerY)+(leapPosZ-centerZ)*(leapPosZ-centerZ))

...

...set fingerNum to 3

...tell leap to "getPosition"

...set middleDist to sqrt of ((leapPosX-centerX)*(leapPosX-centerX)+(leapPosY-centerY)*(leapPosY-centerY)+(leapPosZ-centerZ)*(leapPosZ-centerZ))

...

...set fingerNum to 4

...tell leap to "getPosition"

...set ringDist to sqrt of ((leapPosX-centerX)*(leapPosX-centerX)+(leapPosY-centerY)*(leapPosY-centerY)+(leapPosZ-centerZ)*(leapPosZ-centerZ))

...

...set fingerNum to 5

...tell leap to "getPosition"

...set pinkyDist to sqrt of ((leapPosX-centerX)*(leapPosX-centerX)+(leapPosY-centerY)*(leapPosY-centerY)+(leapPosZ-centerZ)*(leapPosZ-centerZ))

We start by getting a hand. We then go through and get the position for each finger, and use pythagoras to work out the distance from the hand to the finger tip. Note that asking for the hand position will set a handName, which means that when we ask for fingers (2-5 - we ignore the thumb) we're using the hand we've already found.

Finally we just need to parse those distances to check for each of the hand gestures:

...set threshold to 70

...

...if indexDist<threshold and middleDist<threshold and ringDist<threshold and pinkyDist<threshold

....say "Rock!"

...

...if indexDist>threshold and middleDist>threshold and ringDist>threshold and pinkyDist>threshold

....say "Paper!"

...

...if indexDist>threshold and middleDist>threshold and ringDist<threshold and pinkyDist<threshold

....say "Scissors!"

...

...wait 1 secs

Distances are in mm, and for my (large-ish!) hands I found 70m worked well as a cut of point between fingers being "in" or extended - adjust based on personal physique! If all the fingers are less than threshold then its "Rock!". If index and middle are the only two extended its "Scissors!", and if all are extended its "Paper!".

The results are surprisingly successful! It occasionally does loose track but its still pretty impressive (it can be helpful to just view the gestures in the Leap "visualizer" tool - if your gestures aren't clear in the visualiser then your own sw isn't going to stand a chance!). We've cut down the Leap API to produce something that's really easy to program, but still keeps most of the potential. The code for this is included in the current Sniff release. We've tested on a Mac, but it should work on other platforms - our older Windows and Linux build boxes are too slow to run the leap motion tracker, so let us know how you get on!

Playing Rock Paper Scissors with a computer is REALLY fun!

Sniff for the Web

Sniff is implemented by converting the Sniff code to C, which means that we can make it run on pretty much anything that has a C compiler. So we got pretty excited when we discovered Emscripten. Emscripten is a C compiler that outputs Javascript, which means you can write code in C and run it in a web page... which means you can now compile Sniff to run in a web page.

The first step is to install Emscripten, and update to the latest version of Sniff. With that done, you can write your Sniff program pretty much as normal, and compile it with the command "jsniff". This will produce a version of your code which you can then use online! That's basically all there is to it, though there are couple of minor things you need to watch for.

In addition to the actually js output file, we also generate an html file, so you can run your program by just opening the html file. However most modern web browsers won't let a web page start loading up file from your local hard disk. You need to place the files on a web server to access them (or use Firefox which still lets you do this!).

Similarly if you want to access any files - for example images to use in your game, you need to bundle them into the code. To make that easy, just add the names of any files or folders you want to include in the bundle after the .sniff filename on the command line. For example:

jsniff asteroids.sniff *.bmp

jsniff adventure.sniff objects rooms

Provided you bundle the files in at compile time, you can read files just as normal. You can also write files, but they get thrown away when your program finishes - thats just the web way!

We've mainly used this for games so far, and the window and sprite devices work really great online. Unofrtunatly Javascript can't use regular sockets, so minecraft, and leap motion don't work just yet.

The only other weirdness is that "ask" will pop up a modal dialog box, pausing your whole program. It works fine, but you can't run other scripts while the "ask" box is on screen.

Appart from that it just works. If you're running some kind of workshop you can write code to run on the local machine, and when you're done just put it on a website so everyone can see it!

Sprites in Sniff (Pt 1)

Everyone loves games, and Scratch makes it really easy to build simple games. However when we built Sniff we wanted it to be more like a "real" programming language, that could be used to solve all sorts of problems - not just sprite based games.

But of course that doesn't mean that writing sprite based games isn't fun! As we're rounding out the support for Sniff, we've now added support for Sprites, so you can write Scratch like games. However Sprites aren't part of the language as they are in Scratch - they're devices. While this means the two systems aren't exactly alike, it makes the implementation a lot cleaner, and makes it possible to do things that would be very difficult in Scratch.

We'll be developing the documentation for this over the next few weeks, but here's a brief introduction (and you can check the examples in SNIFF/examples/Hosted/sprite).

make nativeFile device
make fileData string

make display window device

make spriteManager device
make spriteX number
make spriteY number
make spriteHit boolean

make spriteID boolean

make spriteValue boolean

when start

..tell spriteManager to "drawAll"

..wait 0.1 secs

We start by making a whole bunch of devices and variables. The SpriteManager is going to look after all of our sprites. We'll use it more in part 2 of this tutorial, but its most important user facing task at this stage is to handle the drawing. You can ask individual sprites to draw, but for simple games, we're just going to task the spriteManager to "drawAll". We can put this in a separate script and just let it run.

The sprite manager uses the display device (which currently has to be a window, but we hope to support other display types in the future), which in turn uses a nativeFile device.

Now lets make some sprites:

make background sprite device

make donut sprite device

make player sprite device

when start

.set fileData to "sea.bmp"

.tell background to "loadCostume"

.

.set fileData to "turtle.bmp"

.tell player to "loadCostume"

.

.set fileData to "donut.bmp"

.tell donut to "loadCostume"

We make three sprite devices, starting with the background - by default they get drawn in the order they're created, so background has to go first. We then load up some images to set the appearance of each sprite. Here we've only loaded up one costume per sprite, but you can add up to 8, just by calling loadCostume again. "setCostume" and "nextCostume" let you cycle through the different appearances.

.set spriteValue to 2

.tell player to "setCostume"

Sniff windows are fixed at 640x480, so we move the background image to the centre of the screen:

.set spriteX to 320

.set spriteY to 240

.tell background to "moveTo"

To move things around, we can use XY coordinates to set (moveTo) or adjust (moveBy) the players position). We can also find the players position using "getPosition".

Alternativly we can turtle style graphics, with "turnBy", "turnTo", "getRotation": and moveForward:

.set spriteValue to 90

.tell player to "turnBy"

.set spriteValue to 100

.tell player to "moveForward"

We can combine that with code to read from the keyboard to move our character around:

when start

.forever

..set specialKeypress to ""

..tell display to "getEvent"

..if specialKeypress = "left"

...set spriteValue to -10

...tell player to "turnBy

..if specialKeypress = "right"

...set spriteValue to 10

...tell player to "turnBy

..if specialKeypress = "up"

...set spriteValue to 10

...tell player to "moveForward

..wait 0.1 secs

Now we need to configure the collision detection:

.tell background to "setUnhittable"

.tell player to "setUnhittable"

.tell donut to "setHittable"

The background takes no real part in the game, so we set it to be unhittable. Similarly we're interested in the player hitting the donut, rather than the donut hitting the player, so we set the donut as hittable, and the player as unhittable.

.forever

..tell player to "checkTouching"

..if spriteHit

...change score by 1

...set spriteX to pick random 30 to 600

...set spriteY to pick random 30 to 440

...tell donut to "moveTo"

..wait 0.1 secs

We call "checkTouching" on a sprite to discover it its hit something hittable. If it has (in this case) it must be the donut, in which case we increase the score by 1, and move the donut to a new random location.

Using these basic sprite functions its possible to write the standard chase the target, Scratch type games in Sniff. In addition Sniff has a much more powerful way of dynamically creating sprites through the SpriteManager, so you can spawn new sprites as your game is running, rather than having to code them all at compile time. The two approaches play nice together, so you can migrate to the advanced API when you're ready, but we'll leave that till next time.