Mister Muffin Blog

A very nice minimal code size implementation of the Mandelbrot algorithm by Ken Peril I found here

main(k){float i,j,r,x,y=-16;while(puts(""),y++<15)for(x
=0;x++<84;putchar(" .:-;!/>)|&IH%*#"[k&15]))for(i=k=r=0;
j=r*r-i*i-2+x/25,i=2*r*i+y/10,j*j+i*i<11&&k++<111;r=j);}

It is very interesting to see what techniques where applied to minimize the amount of source code bytes. When I tried out the code, not knowing what pattern it would output I was very find to see a Mandelbrot pattern printed to my terminal :)

The code translates to this which outputs the exact same bytes:

#include <stdio.h>

int main(int argc, char **argv)
{
    int k,x,y;
    float i,j,r;
    char *chars;
    chars = " .:-;!/>)|&IH%*#";
    for(y=-15;y<16;y++) {
        puts("");
        for(x=1;x<=84;x++) {
            i=0;
            r=0;
            for(k=0;k<112;k++) {
                j=r*r-i*i-2+x/25.0f;
                i=2*r*i+y/10.0f;
                if (j*j+i*i>=11) {
                    break;
                }
                r=j;
            }
            putchar(chars[k&15]);
        }
    }
    puts("");
    return 0;
}

y and x iterate over rows and colums on the terminal. They are scaled by 1/25 and 1/10 respectively. 112 is the maximum iteration number and only has the requirement of being divisible by 16 (the number of characters for the ascii art). A difference to the original algorithm is the -2 in calculating j but this is just to shift the x values to the right on output. Alternatively one could also just iterate x eg from -50 to 34 instead from 1 to 84 which would give a similar output. To compensate for the shift and to also draw points close to the border 11 was chosen as a good stopping criterion for beautiful output. Normally one would check for jj+ii being less than or equal to 4 but this would mean that for border points the algorithm would terminate in the 1st iteration, painting those points the same as the ones that do not lie in the Mandelbrot set.

For my touchbook i recently bought a Navilock USB GPS-Modul NL-302U SIRF III containing a SiRF III chip that are known for their excellent quality.

This is how the baby looks on the inside:

And this is how it looks when attaching it to my linux box:

[40538.052593] pl2303 2-1.2.1:1.0: pl2303 converter detected
[40538.054396] usb 2-1.2.1: pl2303 converter now attached to ttyUSB0

Bus 002 Device 009: ID 067b:2303 Prolific Technology, Inc. PL2303 Serial Port

Unfortunately instead of the widely understood ASCII based NMEA 0183 protocol those chips are using the proprietary, binary SiRF protocol. Luckily the gpsd guys are hosting a pdf documentation of that protocol. Reading that documentation one can also find out that it is possible to switch between NMEA and SiRF modes.

Reading and displaying data from a serial port is most convenient with:

apt-get install python-serial
/usr/share/doc/python-serial/examples/miniterm.py /dev/ttyUSB0 9600

And writing to serial is quickest with:

from serial import Serial
tty = Serial("/dev/ttyUSB0", 9600)
tty.write(message)

or

python -c "from serial import Serial; Serial("/dev/ttyUSB0", 9600).write(message)"

According to section 1.2.3 of the documentation the following message needs to be written to switch from NMEA to SiRF binary mode at 9600 baud:

message = "$PSRF100,0,9600,8,1,0*0C\r\n"

Switching from the default SiRF binary mode to NMEA is more involved but described in section 2.2.2.

Numbers are 7 bit and in big endian notation:

pack = lambda x: chr(x>>8)+chr(x&0xff)

Every message has a start and end sequence

start = "\xa0\xa2"
end = "\xb0\xb3"

The payload is assembled with help from the documentation (only GGA, GSA and GSV messages enabled, 9600 baud)

payload = "\x81\x02\x01\x01\x00\x01\x05\x01\x05\x01\x00\x01\x00\x01\x00\x01\x00\x01\x00\x01\x00\x01\x25\x80"

Calculate 15 bit checksum:

checksum = sum(map(ord, list(payload))) & 0x7fff

Calculate the length of the payload

length = len(payload)

Assemble message:

message = start + pack(length) + payload + pack(checksum) + end

And after sending it as explained above the device will gladly output NMEA data.

i'm finally back to extlinux...

installation was perfectly painless:

apt-get install extlinux
mkdir -p /boot/extlinux
extlinux --install /boot/extlinux
cat > /boot/extlinux/extlinux.conf << END
PROMPT 0
DEFAULT debian
LABEL debian
    kernel /vmlinuz
    append root=/dev/mapper/volumegroup-root ro quiet
    initrd /initrd
END
dd bs=440 conv=notrunc count=1 if=/usr/lib/syslinux/mbr.bin of=/dev/sda
apt-get remove --purge grub-pc grub-common

checking that the boot flag is set to the correct partition with fdisk and reboot :)

the path to vmlinuz and initrd should probably made relative - something like: ../vmlinuz but /vmlinuz works in my case as i have a separate /boot partition.

wheeee! colors!

I was especially in the need of colors for git-diff.

git config --global color.diff auto
git config --global color.status auto
git config --global color.branch auto
git config --global color.ui auto
git config --global color.interactive auto
git config --global color.grep auto

one can certainly overdo it but I love colored output on my terminal :)

As I own a Always Innovating Touchbook I wanted to make use of its touchscreen by having some physics simulation games on it. Unfortunately it's kinda hard to find such open source games as the really good ones, phun (now algodoo), zanydoodle and crayonphyiscs are proprietary. Noteable opensource games I found were numptyphysics and the powder toy

While phun and the powder toy come with their own simulation engine, the rest are using open source libraries. This got me to research a bit to what is available on open source 2D rigid body physics simulation libraries.

The one that numptyphysics and crayonphysics (and angrybirds!) rely upon is box2d. As it is also used by the torque 2d engine it is probably also used in amazing games like Insanely Twisted Shadow Planet. Starting of in 2007 it is the older library but doesnt seem to be further developed since 2010. It is implemented in C++, released under the zlib license, rendering agnostic and supports lot of features like hinges, motors, friction and springs. Its sort and prune based broadphase collision detection is supposed to work better with objects of varying size.

The newer and more fancy one is chipmunk which builds on parts of box2d, is implemented in C99 and is more high level than box2d. It is used by zany doodle and xmoto and released under MIT license. The spatial hash broad phase collision detection is supposed to make it faster for lots of objects of the same size. This is also one of the reasons why chipmunk seems to be much faster with fluids which are quite problematic for box2d because of the huge number of small circles used to simulate it.

Box2d is ported to many languages, chipmunk as many bindings. They are both cross platform, running on Windows, Mac OS, GNU/Linux, Android and Apple iOS. Chipmunk has a more modern and thought out API but that might just be because of my C++ dislike. In the end, forum posts suggest that each of them has it's strengths and weaknesses and (as usual) in the end one has to go with the one than one is more comfortable in using.

Unfortunately the most impressive engine seems to be integrated in the propriety game phun, or algodoo as it was renamed. But this might just be an impression by the immensely complex and function rich program that phun/algodoo is. Most noteably is probably its smooth handling of water including simulation of buoyancy but it also simulates specular reflection, fraction and dispersion of light. Its other features like hinges, motors, springs, friction and mass are also handled by chipmunk and box2d but there is an editor missing that is as powerful as the one of phun/algodoo.

Now the two open source games I was checking out were numptyphysics and the powder toy. I wanted to have both on my touchbook and be able to control them with the touchscreen only.

Now numptyphysics is packaged in debian but development seems to have stopped in 2008. Fortunately it's quite useable and even supports touchscreen only operation by two slide-out menus on the left and right. It took me ages to find those and i only found them by accidentally clicking on the 5 pixel border of the window which slides out the menu. With this one it can be fully controlled with the left mouse button and is hence ready for touchscreens. Unfortunately it needs some tweaks to be nicely useable. Those changes were, to increase the window size to 1024x600 (there is no way to do that without recompiling), change the selection and click tolerance to bigger values for touchscreen use (also needs recompilation), increase the area on both sides for the slide-out menus (again needs to be recompiled) and disable drawing of the rotating joint symbol as it doesnt get scaled.

You can find my changes here maybe some time I will make a better patch that also includes command line options to change all of that at runtime.

Then there is the powder toy. It comes with a fixed resolution as well which is mainly due to the fact that it builds on an online community that shares their creation and those are of fixed size. If one doesnt care about that, changing the resolution is very easy but also only possible at compile time. It involves just changing XRES, YRES, XCNTR and YCNTR in includes/defines.h. Since I wanted to run it on the armel architecture I added a new target to the makefile that built powder without sse. Also to make it run faster I didnt choose 1024x600 but 512x300 as the resolution and combined that with the scale:2 commandline parameter. Sadly scale can be only 1 or 2.

While numptyphysics is perfectly useable on the touchbook performance wise, the powder toy runs at a mere 9 fps with an empty screen. Maybe this will improve with armhf but i didnt check out how much the powder toy uses floating point arithmetics.

In the end here are some videos that are worth watching:

• algoobla
• phun
• torque2d+box2d
• Insanely Twisted Shadow Planet
• crayonphysics
• chipmunk
• numptyphysics