Galcon Games
Phil Hassey - game dev blog
Phil Hassey as Syndrome
"Look, stores don't sell
costumes like this to just anyone."

xkcd “Self-Description” solved with python+pygame

Well, something about this xkcd comic drew me in …

The 3rd panel reminded me of a study I did in college on iterated function system fractals.  These fractals are known for creating ferns, trees, and the Sierpinski triangle.  There are a number of ways of creating these fractals, but one of them is called (something like) the reducing photo copier method.  Where you can start with ANY starting image on your photo copier, and just shrink the images, make a few copies, position them on the copier, and repeat.  Eventually your image converges towards the fern / triangle / whatever if you are precise.  (This can be done with a ‘Real Life’ photo copier for simple IFS like the Sierpinski triangle.)

So as a way to avoid work that I’m supposed to be doing this evening, I figured I’d see how “accurate” this comic was.  Here’s my pygame code that checks it out.  If you run main.py it will start with an image (the xkcd logo) and each time you press a key it will do an iteration of re-creating the comic.  You can see it flashing between the current iteration and the original strip.  After about 4-5 iterations the images converge (pretty closely.)

The most interesting bit was trying different starting images and seeing how long it took to converge.  Starting with all black  it takes 6 iterations.  Starting with all white takes 5 iterations.  And starting with the xkcd logo takes 4 iterations.  The logo probably goes the quickest because it has some black and white in it (like this image) so it converges faster.  (You can edit main.py towards the bottom page to try these different starting points.)

So .. there ya go!  Enjoy!

-Phil

8 Responses to “xkcd “Self-Description” solved with python+pygame”

  1. Tenoch Says:

    Ahah brilliant!

  2. Simon Hibbs Says:

    I particularly like the way the two label lines into the pie chart exactly cancel each other out so the pie chart remains correct.

  3. Shad Sharma Says:

    Very interesting.

    Just a note for Ubuntu users. You need pygame installed:
    # aptitude install python-pygame

  4. Ariel Says:

    When I run it I get:

    Traceback (most recent call last):
    File “main.py”, line 88, in
    main()
    File “main.py”, line 62, in main
    screen.blit(pygame.transform.smoothscale(pygame.image.load(‘xkcdLogo.png’),(SW,SH)),(0,0)) # 4 iterations
    AttributeError: ‘module’ object has no attribute ‘smoothscale’

    I’m on debian, I could not find any package with a file called transform.

  5. Ariel Says:

    When I run it I get:

    Traceback (most recent call last):
    File “main.py”, line 88, in
    main()
    File “main.py”, line 62, in main
    screen.blit(pygame.transform.smoothscale(pygame.image.load(‘xkcdLogo.png’),(SW,SH)),(0,0)) # 4 iterations
    AttributeError: ‘module’ object has no attribute ‘smoothscale’

    I’m on debian, I could not find any package with a file called smoothscale.

  6. gislan Says:

    Ariel: you need to update your python-pygame package. I had same problem, “apt-get update; apt-get install python-pygame” fixed the problem (unstable)

  7. Ariel Says:

    Sorry, about the double post. Delete the first one.

    I changed smoothscale to scale and it ran, and I made this sequence of images, so people who don’t have phygame, etc, can see it:

    http://news.ycombinator.com/item?id=1054079

  8. philhassey Says:

    smoothscale is in the latest pygame, so yeah, older builds of it won’t have it.

    Thanks for taking screenshots :)


Galcon   Watermelons   Dynamite   The Hairy Chestival
All content of imitation pickles (c) 1999-2008 - Phil Hassey  "we care"