BBCode Python Module III

May 31st, 2007

I had a little spare time to do some work on postmarkup.py, my BBCode module. It now handles Unicode correctly, which was a big omission, considering its intended use. I also added a few other features. The tag parameter string can now be specified in 3(!) different ways. For example, the following 3 lines are equivalent.

[link=http://www.willmcgugan.com]My homepage[/link]

[link="http://www.willmcgugan.com"]My homepage[/link]

[link http://www.willmcgugan.com]My homepage[/link]

Another addition, is an [img] tag.

[img]http://www.willmcgugan.com/wp-content/uploads/ant.png[/img]

There is also support for lists (ordered and un-ordered), with the phpbb syntax. For example:

[list]

[*]Apples

[*]Oranges

[*]Pears

[/list]

This produces an un-ordered list.

  • Apples
  • Oranges
  • Pears

I didn't implement the [size] and [color] tags, because for my purposes I don't want users creating annoying text! If you need them, take a look at the code - new tags are fairly easy to implement. For more information, please see the other posts regarding bbcode on my blog, or contact me.

Download postmarkup.py

I plan on putting postmarkup and some of my other open source code on google code when I have more spare time. Bare with me folks!

 

They should all be destroyed

May 24th, 2007

The Triops have started on solid food. They seemed un-interested in the food at first, but once the pellets swelled up with water the little darlings had a nibble. The instruction booklet says that after a week you can feed them tiny pieces of carrots and fish. I had some Australian Snapper fillets in the fridge for my dinner, so I snipped of a little piece and chopped it in to Triop sized morsels. Ive never tried snapper before, but it must be delicious - judging by the macabre feeding frenzy that ensued. Mental note: be careful about getting fingers in the water when they get a little bigger. Triops don't want to be fed, they want to hunt. Can't just suppress 65 million years of gut instinct!

Update: The snapper was indeed delicious.

 

Micro-optimizing Python code for 3D

May 22nd, 2007

I enjoy optimizing code. These days I don't get the opportunity to do it very often, since I prefer working in high level languages now. Which is why I have been particularly enthusiastic in optimizing the 3D math classes in Game Objects.

Whenever the subject of optimization comes up, someone inevitably regurgitates the quote "premature optimization is the root of all evil", which they take to mean that you should not do any optimization until you have a working application and are able to profile it. In general this is good advice - but if you know about the domain you are working in, occasionally early optimization is a good thing. 3D math for games is one of these situations. The code is a black box which doesn't need to be built upon. Speeding it up tends to have a direct impact on the user experience (i.e. a better frame-rate). There is also limited scope for algorithmic improvements (which should be considered first), so micro-optimization is justifiable in this case (IMHO).

When I started looking in to optimizing my Matrix class, I compared it against another matrix class in PyEuclid, which is a quite comprehensive set of classes for 2D and 3D euclidean geometry. When I looked at the Matrix3 implementation, I was surprised that it stored the values of the matrix as 16 attributes (self.a, self.b etc.), because attribute access can be a bottle-neck for serious number crunching code. So I suspected that the matrix multiplication in PyEuclid would be slower than the equivalent function in Game Objects, as I used a single list of 16 values, which should be faster. But when I timed it, I found that PyEuclid was fractionally faster. Naturally I had a look at the Matrix3.__imul__ method in PyEuclid, I noticed that It copied one of the matrices in to 16 local references, and that made it a little faster because the attribute access was done only once. So I tried doing the same thing for the self matrix, which turned out to speed it up my almost 20%, which made it faster than my version. I was happy to submit the optimization back to Alex Halkner, the author of PyEuclid, but naturally I was determined to speed up my version by at least the same amount! I used the updated Matrix__imul__ from PyEuclid (below) as my benchmark.

def __imul__(self, other):
        #assert isinstance(other, Matrix4)
        a = self.a
        b = self.b
        c = self.c
        d = self.d
        e = self.e
        f = self.f
        g = self.g
        h = self.h
        i = self.i
        j = self.j
        k = self.k
        l = self.l
        m = self.m
        n = self.n
        o = self.o
        p = self.p

        oa = other.a
        ob = other.b
        oc = other.c
        od = other.d
        oe = other.e
        of = other.f
        og = other.g
        oh = other.h
        oi = other.i
        oj = other.j
        ok = other.k
        ol = other.l
        om = other.m
        on = other.n
        oo = other.o
        op = other.p

        self.a = a * oa + b * oe + c * oi + d * om
        self.b = a * ob + b * of + c * oj + d * on
        self.c = a * oc + b * og + c * ok + d * oo
        self.d = a * od + b * oh + c * ol + d * op
        self.e = e * oa + f * oe + g * oi + h * om
        self.f = e * ob + f * of + g * oj + h * on
        self.g = e * oc + f * og + g * ok + h * oo
        self.h = e * od + f * oh + g * ol + h * op
        self.i = i * oa + j * oe + k * oi + l * om
        self.j = i * ob + j * of + k * oj + l * on
        self.k = i * oc + j * og + k * ok + l * oo
        self.l = i * od + j * oh + k * ol + l * op
        self.m = m * oa + n * oe + o * oi + p * om
        self.n = m * ob + n * of + o * oj + p * on
        self.o = m * oc + n * og + o * ok + p * oo
        self.p = m * od + n * oh + o * ol + p * op
        return self

It may appear that the 32 assignments would slow it down, but it was faster over all because they reduce the amount of attribute access in the function. Knowing that attribute access was the enemy, I tried the same trick with Matrix44.__imul__ in Game Objects. My 16 values of the matrix were stored in a list called self._m, and the individual values were accessed as self._m[0] thru self self.m[15]. Copying these in to local references turned out to be very easy, because I could use Python's list unpacking. Doing this for both matrices yielded the following code.

def __imul__(self, rhs):
        """Multiplies this Matrix44 by another, called by the *= operator."""

        m1_0, m1_1, m1_2, m1_3, m1_4, m1_5, m1_6, m1_7, m1_8,
            m1_9, m1_10, m1_11, m1_12, m1_13, m1_14, m1_15 = self._m
        m2_0, m2_1, m2_2, m2_3, m2_4, m2_5, m2_6, m2_7, m2_8,
            m2_9, m2_10, m2_11, m2_12, m2_13, m2_14, m2_15 = rhs._m

        self._m =    [ m2_0 * m1_0 + m2_1 * m1_4 + m2_2 * m1_8 + m2_3 * m1_12,
                       m2_0 * m1_1 + m2_1 * m1_5 + m2_2 * m1_9 + m2_3 * m1_13,
                       m2_0 * m1_2 + m2_1 * m1_6 + m2_2 * m1_10 + m2_3 * m1_14,
                       m2_0 * m1_3 + m2_1 * m1_7 + m2_2 * m1_11 + m2_3 * m1_15,

                       m2_4 * m1_0 + m2_5 * m1_4 + m2_6 * m1_8 + m2_7 * m1_12,
                       m2_4 * m1_1 + m2_5 * m1_5 + m2_6 * m1_9 + m2_7 * m1_13,
                       m2_4 * m1_2 + m2_5 * m1_6 + m2_6 * m1_10 + m2_7 * m1_14,
                       m2_4 * m1_3 + m2_5 * m1_7 + m2_6 * m1_11 + m2_7 * m1_15,

                       m2_8 * m1_0 + m2_9 * m1_4 + m2_10 * m1_8 + m2_11 * m1_12,
                       m2_8 * m1_1 + m2_9 * m1_5 + m2_10 * m1_9 + m2_11 * m1_13,
                       m2_8 * m1_2 + m2_9 * m1_6 + m2_10 * m1_10 + m2_11 * m1_14,
                       m2_8 * m1_3 + m2_9 * m1_7 + m2_10 * m1_11 + m2_11 * m1_15,

                       m2_12 * m1_0 + m2_13 * m1_4 + m2_14 * m1_8 + m2_15 * m1_12,
                       m2_12 * m1_1 + m2_13 * m1_5 + m2_14 * m1_9 + m2_15 * m1_13,
                       m2_12 * m1_2 + m2_13 * m1_6 + m2_14 * m1_10 + m2_15 * m1_14,
                       m2_12 * m1_3 + m2_13 * m1_7 + m2_14 * m1_11 + m2_15 * m1_15 ]

        return self

This optimized version removed all the list index operations from the function and reduced attribute access dramatically, making it considerably quicker; it could do 60,502 matrix multiplies per second, compared to PyEuclid's 47,594 per second. I think this must be the quickest way to do a full matrix multiply in straight Python. Other functions benefited from this to, transforming a Vector3 improved by about 20%, as did other operations. I also applied the same technique to the Vector3 class, which was worthwhile, but not quite as good an improvement as the matrix code.

These experiments have lead me to the following rules of thumb for micro-optimizing Python code, with the disclaimer that you should only micro-optimize if you know it will produce tangible benefits in the user experience!

  • Prefer lists of values, rather than attributes.
  • If you use an attribute more than once, copy it in to a local reference.

I'd like to point out that I'm not claiming that this is a good reason to use Game Objects over PyEuclid. They are intended for different things, Game Objects will eventually be a collection of general algorithms for games and other realtime apps. The speed advantage is not stellar, so you should use which ever interface you prefer - or even both!

 

Game Objects 3D math

May 20th, 2007

I've just uploaded a new version of Game Objects. The 3D maths classes (Vector2, Vector3 and Matrix44) are reasonably stable now. I'd like to invite Python coders to play around with them, and suggest any improvements. My intention was to make something that was very easy to use, but well optimized. Game Objects is public domain. Do what you want with the code - go crazy!

There is no documentation at the moment I'm afraid, but here are a few edited highlights.

Vector3 class

>>> from gameobjects.vector3 import *
>>> A = (-5, 2, -6 )
>>> B = (10, 2, 8)
>>> AB = Vector3.from_points(A, B)
>>> print AB
(15, 0, 14)
>>> AB.length
20.518284528683193
>>> AB.length = 1
>>> print AB
(0.731055, 0, 0.682318)
>>> AB *= 2
>>> print AB
(1.462111, 0, 1.364637)
>>> AB += (1, 2, 3)
>>> print AB
(2.462111, 2, 4.364637)

Matrix44 Class

>>> from gameobjects.matrix44 import *
>>> identity = Matrix44()
>>> print identity
[ 1 0 0 0 ]
[ 0 1 0 0 ]
[ 0 0 1 0 ]
[ 0 0 0 1 ]
>>> scale = Matrix44.scale(2.)
>>> print scale
[ 2 0 0 0 ]
[ 0 2 0 0 ]
[ 0 0 2 0 ]
[ 0 0 0 1 ]
>>> scale.transform( (1, 2, 3) )
(2.0, 4.0, 6.0)
>>> from math import radians
>>> rotate = Matrix44.x_rotation(radians(45))
>>> print rotate
[ 1         0         0         0 ]
[ 0         0.707107  0.707107  0 ]
[ 0         -0.707107 0.707107  0 ]
[ 0         0         0         1 ]
>>> p = (5, 10, 0)
>>> rotated_p = rotate.transform(p)
>>> print rotated_p
(5.0, 7.0710678118654755, 7.0710678118654746)
>>> inverse_rotate = rotate.get_inverse()
>>> inverse_rotate.transform(rotated_p)
(5.0, 10.0, 0.0)
>>> rotation.right
Traceback (most recent call last):
  File "<interactive>", line 1, in ?
NameError: name 'rotation' is not defined
>>> rotate.right
(1.0, 0.0, 0.0, 0.0)
>>> rotate.translate
(0.0, 0.0, 0.0, 1.0)
>>> rotate.translate = (10, 2, 5)
>>> print rotate
[ 1         0         0         0 ]
[ 0         0.707107  0.707107  0 ]
[ 0         -0.707107 0.707107  0 ]
[ 10        2         5         1 ]
</interactive>
 

Python unions? That's crazy talk!

May 19th, 2007

I don't often say this, but I miss something from C++ that I can't do in Python. What I miss is unions. I know they can be dangerous and aren't supported consistently across compilers, but damn it, they can occasionally be useful.

I'm working on a 4x4 matrix class (for 3D maths) as part of my Game Objects library. It's something I have done several times in C++, where I create a union of a two dimensional array and four Vector4 classes. That way the matrix is conceptually both a grid of numbers and four vectors, which allows for quite elegant code. For example if I have a CMatrix class that stores the transform for a spaceship and I want to move it forward 2 units, I might use code like this.

matSpaceship.vecTranslation += matSpaceship.vecHeading * 2.;

Which is nicely descriptive. I have something similar as part of my Python Matrix44 class; there are descriptive properties that return the appropriate row from the matrix as a tuple. So the equivalent spaceship code would be something like this.

spaceship_transform.translate += Vector3(spaceship_transform.heading) * 2

I find the extra step of having to create a new Vector3 object to be extra noise in the code, but it seems unavoidable. The reason I return an immutable object rather than a Vector3 is because changes to the vector wouldn't have any effect on the parent Matrix. But frankly, it would be nice if they did. I would like to write something like spaceship_transform.translate.y += 1 to move the spaceship along the y axis. I considered getting it working with a proxy object for the matrix rows that caught changes and modified the parent matrix - which I'm sure would work, but it would introduce inefficiency to something that should be fast and lean.

I'm not suggesting having a union construct for Python - heaven forbid! But it does feel like a 'wart' in my Matrix class. And that kind of thing can keep me up at night. :-(

 

Langton Ants in PyGame

May 18th, 2007

Many moons ago I implemented Langton Ants on a ZX Spectrum 48K, and I have been fascinated by it ever since. I thought it would be fun to implement it in PyGame.

Langton ants are simple creatures. They live in a grid of squares that can be one of two colors, and follow these two simple rules.

  • Am I on color 1? Flip the square, turn 90 degrees right, move forward 1 square.
  • Am I on color 2? Flip the square, turn 90 degrees left, move forward 1 square.

That is all they do. They don't ponder the meaning of life or current affairs, they just check the color of the square they are on and then turn and move. You would think that something this simple would quickly get in to a cyclical pattern, but it turns out that Langton ants like to make crazy complex patterns and don't repeat themselves. Humor me, while I write a Python script to test it.

First thing we need to do is define a few constants for use in the script, as follows.

GRID_SIZE = (160, 120)
GRID_SQUARE_SIZE = (4, 4)
ITERATIONS = 1
ant_image_filename = "ant.png"

The grid will be 160x120 squares, with squares that are 4x4 pixels (so that it fits inside a 640x480 pixel screen). The value of ITERATIONS is the number of moves an ant does each frame, increase it if you want the ants to move faster. Finally we have the filename of an image to represent the ant. I will be using this image: Ant.

Next we import PyGame in the usual manner.

import pygame
from pygame.locals import *

We will represent the grid with a class that contains a two dimensional list (actually a list of lists) of bools, one for each square, where False is color 1, and True is color 2. The AntGrid class is also responsible for clearing the grid, getting the square color at a coordinate, flipping a square color and drawing itself to a PyGame surface. I chose white for color 1 and dark green for color 2, but feel free to change it if you want something different.

class AntGrid(object):

    def __init__(self, width, height):

        self.width = width
        self.height = height
        self.clear()

    def clear(self):

        self.rows = []
        for col_no in xrange(self.height):
            new_row = []
            self.rows.append(new_row)
            for row_no in xrange(self.width):
                new_row.append(False)

    def swap(self, x, y):
        self.rows[y][x] = not self.rows[y][x]

    def get(self, x, y):
        return self.rows[y][x]

    def render(self, surface, colors, square_size):

        w, h = square_size
        surface.fill(colors[0])

        for y, row in enumerate(self.rows):
            rect_y = y * h
            for x, state in enumerate(row):
                if state:
                    surface.fill(colors[1], (x * w, rect_y, w, h))

Now that we have a grid, we can create a class for the ants. The move function in the Ant class implements the two rules, and the render function draws a sprite at the ants location so we can see where it is.

class Ant(object):

    directions = ( (0,-1), (+1,0), (0,+1), (-1,0) )

    def __init__(self, grid, x, y, image, direction=1):

        self.grid = grid
        self.x = x
        self.y = y
        self.image = image
        self.direction = direction

    def move(self):

        self.grid.swap(self.x, self.y)

        self.x = ( self.x + Ant.directions[self.direction][0] ) % self.grid.width
        self.y = ( self.y + Ant.directions[self.direction][1] ) % self.grid.height

        if self.grid.get(self.x, self.y):
            self.direction = (self.direction-1) % 4
        else:
            self.direction = (self.direction+1) % 4

    def render(self, surface, grid_size):

        grid_w, grid_h = grid_size
        ant_w, ant_h = self.image.get_size()
        render_x = self.x * grid_w - ant_w / 2
        render_y = self.y * grid_h - ant_h / 2
        surface.blit(self.image, (render_x, render_y))

Finally in the script, the run function handles the guts of the simulation. It sets up the screen, creates the the grid object then enters the main loop. Inside the main loop there are event handlers so that you can drop ants with the left mouse button, clear the grid with the C key and start the simulation with the SPACE key. The remaining portion of the run function moves all the ants and renders the screen.

def run():

    pygame.init()
    w = GRID_SIZE[0] * GRID_SQUARE_SIZE[0]
    h = GRID_SIZE[1] * GRID_SQUARE_SIZE[1]
    screen = pygame.display.set_mode((w, h), 0, 32)

    ant_image = pygame.image.load(ant_image_filename).convert_alpha()

    default_font = pygame.font.get_default_font()
    font = pygame.font.SysFont(default_font, 22)

    ants = []
    grid = AntGrid(*GRID_SIZE)
    running = False

    total_iterations = 0

    while True:

        for event in pygame.event.get():

            if event.type == QUIT:
                return

            if event.type == MOUSEBUTTONDOWN:

                x, y = event.pos
                x /= GRID_SQUARE_SIZE[0]
                y /= GRID_SQUARE_SIZE[1]

                ant = Ant(grid, int(x), int(y), ant_image)
                ants.append(ant)

            if event.type == KEYDOWN:

                if event.key == K_SPACE:
                    running = not running

                if event.key == K_c:
                    grid.clear()
                    total_iterations = 0
                    del ants[:]

        grid.render(screen, ((255, 255, 255), (0, 128, 0)), GRID_SQUARE_SIZE)

        if running:
            for iteration_no in xrange(ITERATIONS):
                for ant in ants:
                    ant.move()
            total_iterations += ITERATIONS

        txt = "%i iterations"%total_iterations
        txt_surface = font.render(txt, True, (0, 0, 0))
        screen.blit(txt_surface, (0, 0))

        for ant in ants:
            ant.render(screen, GRID_SQUARE_SIZE)

        pygame.display.update()

if __name__ == "__main__":
    run()

And thats our finished Langton Ant simulation. Have a play with it, then come back and explain to me how two simple rules can create such a complex pattern.

Download langtonants.zip

Update: Here's a screenshot!

Langton's Ants screenshot

 

Numbers don't lie

May 17th, 2007

My triops hatched today. I am now the proud father of four tiny crustaceans, and there are more on the way. They are barely visible - just little white specs, but I can make out a pair of swimmerets.

Apparently they double in size every day. They are about a millimeter in length at the moment, so by this time tomorrow they will be 2 millimeters long. They live about 60 days, so eventualy they will be 2 to the power of 60 millitmeters in length. Let's see... thats 1,152,921,504,606,846,976 millimeters, 1,152,921,504,606,846 meters or 1,152,921,504,606 kilometers (*). Oh. My. God. We're gonna need a bigger boat.

* For Americans, that's 716,392,209,599 miles

 

Raising little monsters

May 16th, 2007
XenomorphA few years ago I had a tank of sea monkeys. If you are not familiar with sea monkeys - they are a kind of brine shrimp that has been marketed as a kids toy. They come as a little sachet of eggs with a plastic tank. You add water and they hatch within hours. It's the most marvelous, stress-busting executive toy you can buy. I loved my sea monkeys so much, it inspired me to write an artificial life demo (for PC).

I was thinking of buying some more of these beasties, but I ended up purchasing triops, which are a similar type of instant life crustacean. They are a little bigger than sea monkeys, and carnivorous (sea monkeys just filter nutrients from the water)! Strangely though, they are a little harder to raise. The sea monkeys were almost self-sufficient; eventualy algae grew in the tank and you didn't have to feed them any more. The triops are more fussy, they need water at a specific temperature, regular feeding and water changing.

Triop

The gravel and nutrient bag have been soaking over-night. Today I shall add the eggs to the water, and by tomorrow I should have a dozen or so hatchlings!

 

I want

May 15th, 2007

I use my laptop for instant messaging and picking up my email while I'm working. It's not quite as good as having dual monitors but it means I can easily work and chat / refer to emails without having to shuffle windows about. Occasionally I need to transfer something from the laptop to my main machine - which can be a pain because I have to minimize windows, find the file, drag it on to a shortcut then find it on the other desktop. What I want is to be able to access the clipboard on the laptop from my main work PC, so that all I would have to do to copy a file from my laptop would be to copy it to the clipboard then press, say Shift+Ctrl+V on the other machine to suck it over the network. And I want it to work with text, urls and anything else that can be copied to the clipboard. And I want it to be free. :-)

And I want a pony!

 

The smell of C

May 11th, 2007

A recent post on reddit.com sparked a debate on the following snippet of C code.

int main() { int i = 5; i = ++i + ++i; printf ("%d", i); }

The denizens of reddit have been musing over the the output of the code; is it 13 or 14? It can be either depending on the compiler used - or something else entirely - as the result is undefined, which another denizen noted. Sometimes I wonder if the C language was designed purely to provide challenging job interview questions.

Even though I was a C/C++ programmer for a lot longer than I have been a Python programmer, the entire concept of a valid language construct being undefined is offensive to me. Seriously. It's like month old milk; makes me screw my face up and turn away in disgust. In contrast, Python smells like a mixture of freshly cut grass and new car smell.

As enamored with Python as I am, it still sits on top of C (at least C-Python does) and inherits a little of its unpredictable nature. I believe there are some inconsistencies across the various Python platforms, but I can't think of them right now. Most of them were floating point unit related IIRC, because CPython has little choice but to defer to the floating point implementation of the platform. I wonder if there is a web page somewhere documenting runtime differences between platforms and Python implementations. A small and concise web page I hope!

On the subject of smells. What do other languages smell like? I reckon assembler smells kind of like ammonia.

 
Search for Posts
2013
 
2012
 
2011
 
2010
 
2009
 
2008
 
2007
 
2006
 
 
© 2008 Will McGugan.

A technoblog blog, design by Will McGugan