Building pyramids with code composition

The Al Jazari 2 bots currently have six basic actions – move forward/backwards, turn 90 degrees left or right, pick up the block underneath them or drop the block to the space they are currently sitting on. Given these instructions, how do we procedurally build pyramids (of any given size) like this in their minecraft-esque world?

The Pyramids of Guimar, Canary Islands, Spain
The Pyramids of Guimar, Canary Islands, Spain

1. A pyramid can be built as a series of plateaus layered on top of each other, the plateaus can be built from material mined from nearby:

ajplat

2. A single plateau can be built as a series of single block wide ridges next to each other, mined from a series of trenches. This is an example ridge/trench of size 3:

ridgetrench

3. We need a gap between the ridge and the trench in order to place the plateau in the correct place in the pyramid (also the bots can only climb a single block at a time, otherwise they get stuck).

So in order to build a complete pyramid, we write the code to build a ridge/trench of any size and figure out the steps in-between to get the robot into the right position for the next one. The simplest ridge/trench is a single block long, so lets try writing some code to do that:

aj2single

The lambda, and bot-sequence etc are scheme code required to get the bot language working, we’re just interested in the contents of the “seq”. After running these instructions we’re in the right place for the next block. Note that the majority of the actions are involved with positioning the bot after doing it’s work. To place the next cube we copy the code and add some more ‘forward’s (as we have to travel a bit further going back and forth):

aj2double

This is already getting pretty long – we could do with a way to do repetition, so I’ve added a ‘repeat’ form to the language which takes a count, a name bound to the current iteration number (like a ‘for’ loop) and a list of instructions. This is the complete ridge/trench definition for any size, including gaps of any size:

aj2ridgetrench

The majority of the code is the maths to get the bot picking up and placing blocks further and further apart including the gap parameter. When collapsed into a function and run we get this:

aj2ridgetrench-fn

With the bot ending up in the same place as it started. In order to create a square plateau we call this function, move sideways and repeat, and then move back to where we started again when we’re done:

aj2plateau

Going from a plateau function to a pyramid is even shorter, and involves moving inwards diagonally and building smaller plateaus each time. Of course it also mines out a negative pyramid at the same time:

aj2pyramid

Here is a time lapse of a massive 8×8 pyramid being built, the code ‘compiles’ to 3224 low level instructions:

So this is a kind of programming that encourages solving problems through composition of abstractions – from the low level instructions, simple loops, primitive building constructs, up to complete structures. I’m not sure why in educational languages such as Scratch this is somehow sidelined (interestingly it’s not in Logo, it’s predecessor). Whether this is due to the ubiquity of imperative programming that leads to a focus on manipulation of state, or this kind of programming being considered as too advanced – but for me it’s fundamental, and I’m pretty sure it wouldn’t be that challenging for the kids in the CodeClub I’m running either.

Android Camera Problems

The DORIS marine mapping platform is taking shape. For this project, touch screens are not great for people wearing gloves in small fishing boats – so one of the things the android app needs to do is make use of physical keys. In order to do that for taking pictures, I’ve had to write my own camera android activity.

It seems that there are differences in underlying camera behaviour across devices – specifically the Acer E330 model we have to take out on the boats. It seemed that nearly every time takePicture() is called the supplied callback functions fail fire. I’ve tested callbacks for the shutter, raw and jpeg and error events and also tried turning off the preview callback beforehand as suggested elsewhere, no luck on the Acer, while it always works fine on HTC.

The only solution I have so far is to close and reopen the camera just before takePicture() is called which seems to work as intended. As it takes some seconds to complete, it’s also important (as this is bound to a key up event) to prevent the camera starting to take pictures before it’s finished processing the previous one as that causes further callback confusion.

import android.view.SurfaceHolder;
import android.view.SurfaceView;
import android.hardware.Camera;
import android.hardware.Camera.CameraInfo;
import android.hardware.Camera.PictureCallback;
import android.util.Log;

class PictureTaker 
{
    private Camera mCam;
    private Boolean mTakingPicture;

    public PictureTaker() {
        mTakingPicture=false;
    }

    public void Startup(SurfaceView view) {
        mTakingPicture=false;
        OpenCamera(view);
    }

    private void OpenCamera(SurfaceView view) {
        try {
            mCam = Camera.open();
            if (mCam == null) {
                Log.i("DORIS","Camera is null!");
                return;
            }
            mCam.setPreviewDisplay(view.getHolder());
            mCam.startPreview();
        }
        catch (Exception e) {
            Log.i("DORIS","Problem opening camera! " + e);
            return;
        }
    }

    private void CloseCamera() {
        mCam.stopPreview();
        mCam.release();
        mCam = null;
    }

    public void TakePicture(SurfaceView view, PictureCallback picture)
    {
        if (!mTakingPicture) {
            mTakingPicture=true;
            CloseCamera();
            OpenCamera(view);
            
            try {
                mCam.takePicture(null, null, picture);
            }
            catch (Exception e) {
                Log.i("DORIS","Problem taking picture: " + e);
            }
        }
        else {
            Log.i("DORIS","Picture already being taken");
        }   
    }
}

Users > “drivers” of software

I’ve finally had a chance to sit down and comment on John Naughton’s article in the Guardian and it’s manifesto addressed to the education secretary The Rt Hon Michael Gove MP on computer education in the UK. This joins an avalanche of recognition that programming – or “coding” – is suddenly a Good Thing for People To Know.

It is wonderful to read a major media publication pouring scorn on the old idea that “computers are like cars”, “users are drivers” which has dogged perceptions of computers for years. There is a new philosophy here focusing on hacking, in the original sense – an algorithmic literacy of processes which now mediate every aspect of our lives. This is seen as good as a general life skill, and of course good for the economy for encouraging the kind of independent thinking needed for successful startup companies.

This avalanche has to be credited to some extent to game designer David Braben and his Raspberry Pi project, and an extensive PR campaign tweaking people’s memories (including an increasing number of politicians in their 30’s and 40’s) who remember school computers like the BBC micro, and their later influence on what these same politicians like to call the “creative industries”. This of course all seems instinctively good sense for those of us who have been closely watching the boom in popularity of arduino, processing and free software methodologies in hacklabs and fablabs.

However, an approach organised on this scale is unlikely to support such generalist and creative philosophies we are used to. A few days prior to this article we had an announcement of £575m for kitting out schools with computing infrastructure from familiar public sector contractors including Serco and Capita, and a bit more detail on Staffordshire county council who are spending £28m on “Apple products under the iOS lot including iMacs, Mac Books, iPods, iPads, Mac Minis and Lion Server.”

The problem here is that a rejection of “users as drivers” is a rejection of iOS (and to a lesser extent Android) and the app store philosophy. App stores are extremely successful at promoting the idea of phones as appliances (never computers in their own right) and software as small digestible “apps” encapsulated in locked down environments generally marketed as a kind of protection for users. If these models of computing are to grow as expected – they are completely at odds with an accessible understanding we need for this change in education approach, and the creative literacy of algorithms which would follow.

When I’ve interviewed graduates for creative programming jobs the thing which is really most valuable (much more so than knowing the relevant programming language) is exactly the thing that having an “edit source code” button on every app would encourage (as included on OLPC’s sugar, another older example of an education targeted effort). What is needed is a creative lack of respect for software, a cheerful abandonment of the fear that “breaking something” will be your fault rather than that of the system.

Germination X in HTML5 canvas

I’ve spent a couple of days on an experimental not-quite-working-yet port of Germination X to HTML5. Port is probably a slightly misleading word, as it’s actually running exactly the same HaXE code, it’s just compiled to Javascript rather than swf with a load of extra Javascript filling in the stuff needed to replace Flash. The game engine that Germination X is built on is now officially cross platform! It’s great to finally have a non-proprietary browser option for the game, and HTML5 is much faster now than when I first tried it, but it’s still got a long way to go. Problems I’ve noticed so far:

It’s still slow. I’m aware of the limitations and background to browser tech, but it’s depressing that it’s somehow problematic drawing a few hundreds of sprites in 2012 while my ancient Gameboy DS can manage quite fine thankyouverymuch :)

Tinting images is quite a basic thing to do in order to efficiently use images and save bandwidth and memory. Why do I have to loop through pixels in javascript to do this? This is the main cause of slowness in the HTML5 version of the game ATM, hopefully a simple bitmap cache will fix this. There are also some neat ways to do it with offscreen bitmaps and blendmode tricks, but they seem even slower.

Having to write your own mouse event detection for sprite down/up/over/out. I guess this is one of the biggest reasons for the explosion of HTML5 game engines. It’s quite non-trivial and un-fun to set up properly. Actually getting the real mouse coordinates is also quite hard to do.

On the plus side, it’s a breath of fresh air to get back the control of immediate mode – it seems historically that this tends to be the optimal approach, give us the render loop!

Now you’ve got this far – here is some accidental art which happened this morning, and which I’m particularly proud of:

Shaving yaks on android

fluxus installed on the emulator

Mostly my android experience has been good so far, it’s been very quick to get things running and be fairly productive. It doesn’t come without it’s share of yak shaving though. I’ve spent quite a lot of time trying to get remote debugging of native code working with my phone (a HTC desire) with little success. This seems to be a fairly well documented problem, the symptoms are messages like this when running ndk-gdb:

ERROR: Could not setup network redirection to gdbserver?
Maybe using –port=
to use a different TCP port might help?

When run with –verbose it seems something a little different is wrong:

run-as: Package ‘am.fo.nebogeo.fluxus’ has corrupt installation

Which looks like some result of having a rooted phone (which I do) as ndk-debug is a possible attack vector for doing nasty things and is therefore very critical of the permissions of the directories on the system. In order to fix this I installed ROM Manager from the market which contains a script to fix permissions. This didn’t work at first by pressing the button in the app so after some poking around I found the shell script in: /data/data/com.koushikdutta.rommanager/files/fix_permissions

It turned out that this script depended on an interesting utility called busybox, which provides tiny versions of GNU programs for phones. The easiest way to install this was to install TitaniumBackup and click on it’s “Problems” button which would download it, then copy it from /data/data/com.keramidas.TitaniumBackup/files into /system/bin/ and run busybox –install -s /system/bin/

Then the script could run, and additionally I needed to run chmod 774 /data/data/* to get make sure everything was in the correct state, but still no luck with gdb. At this point I decided my time would be better spent on making a linux version of the android app for debugging purposes and get it running in the software emulator. More on this soon.

I’m also documenting bits and pieces of my android development notes on FoAM’s wiki here.