This page offers a brief summary of some of the hobby projects I work on in my free time. It's not a complete list, but I've been trying to keep the bigger or more interesting projects listed.

Time Lapse Photo App

Time Lapse Photo App Screenshot

This is a Qt application using the Canon SDK (on Windows) and libgphoto2 (on everything else) to create time lapse movies.

My friend Rob and I have been working on it off and on for a few months now. Honestly, we could have done it in a lot less time, but we've both been pretty busy. The most difficult so far has been learning the APIs, and designing the app in a way that it can use both of them simultaneously.

Right now the app just spits out a bunch of JPEG files into a directoy. The next step is going to be incorporating ffmpeg so that the video file gets created automatically.

Sample output of Rob and his girlfriend carving pumpkins.

So far it's been tested on both Linux and Windows. The code is available in Rob's Subversion repository at svn://

Python "Stuff"

Web Tester Early Screenshot

This is another "project" that's more of an expirement at this point.

Some of the scripts at my new job are written in Python, so I thought I would read up on it a little bit. I've found it a lot more fun than I expected. The code is simple to read and write, it has a lot of neat libraries, and the syntax is intuitive and easy to write.

The program in the screenshot is a web browser and editor, using PyQt4, QtWebKit, and QScintilla, in about 90 lines of code. It has a minimal interface, but the important navigation actions are available through the right click context menu, the text editor pane has syntax highlighting, and edits show up in real-time - not bad for 90 lines of code.

That program is more or less a very early iteration of a GUI for specifying and running web page unit tests. I'm thinking it will be similar to Selenium, but with a fancier user interface. Unfortunately, QtWebKit doesn't implement some of the features I was counting on, so I'm not quite sure where the project is going to end up.

The problem is a limitation in the QtWebKit API. The API lets you know when the user does stuff like click a link or when the URL changes, but it only gives you very limited information about how the user is interacting with the page. Specifically, I was hoping I could get a reference to the DOM element the user clicks on, or the XPath of the element, or something. It's not an entire loss, though. It does let you "inject" Javascript into the page and get the page's HTML.

So my new plan is to get rid of the HTML edit pane and use that space to dynamically create PyQt4 widgets for each non-hidden HTML form element. I'll highlight the HTML form element that corresponds to the selected Qt widget.

I'm still not exactly sure how to specify whether the tests pass. This is where QtWebKit's API really hurts. Selenium uses XPath to get each form element, and that's the part I was hoping to "fix". It would be a lot easier if the user could click on a section of web page, specify the expected value, and have the program figure out the XPath or DOM structure automatically.

On the bright side, as I understand it, a future version of Qt is supposed to change QWebKit to do almost exactly what I need. I just have to figure out a solution that's good enough until then...

The code is available here.

NFA to DFA converter

NFA image DFA image

This isn't really a definite "project" - it's more just a few ongoing excercises in compiler writing and learning Haskell.

I've been reading the new edition of "Compilers: Principles, Techniques and Tools" and wanted to implement a few of the algorithms, specifically the non-deterministic finite automaton to deterministic finite automaton algorithm. And the task just grew from there.

Right now the code parses a regular expression, creates a parse tree, transforms it into an NFA, and then converts that to a DFA. It also has some functionality to spit out "dot" files that can be used with the dot tool from the AT&T GraphViz utilities to display the resulting finite automata. And, of course, it can tell whether a string matches a particular regular expression.

This is the first "real" program I've written in Haskell, and it's been an interesting experience. I actually had most of the code written in C++ before I decided to use Haskell, so I had an opportunity to compare the two languages. The end result is that the finished Haskell code is about 3/4th the length of the incomplete C++ code. That's partly due to the Parsec parsing library, while the C++ code was using a (broken) hand written regular expression parser.

Overall I've enjoyed using Haskell, and I'm going to try it again for some other projects.

The regular expressions accepted by the library are rather limited compared to Perl or even POSIX regular expressions. It supports closure (*), one or more (+), character classes ([a-z0-9$#@]), alternation (a|b), and parenthesis.

I'll eventually be adding more stuff to this as I work my way through the book.

The code is available here.

Centipede Clone

Centipede clone screenshot

Following the theme of cloning simple games, I decided to create a Centipede game. Ironically, the only portion of the game I haven't got around to implementing is the actual centipede. Everything else seems to be working.

From a programming perspective, this is one of the more interesting projects I've worked on recently because the game can use a joystick, has sound effects, and has a lot of fast action.

Like most of the GUI projects I write, I used QT for the interface. Unfortunately, QT doesn't include joystick support, and its sound support is a bit limited. To get around these issues, I used the sound and joystick portions of SDL. All of the SDL code is in the QJoystick and QSdlSound classes, so it should be easy to replace it with a different library if needed. One of my only complaints about QT is the lack of integration with GNU autotools. qmake works great for QT applications, but when using it with third-party libraries, it would be nice to have "./configure" to figure out include directories, library paths and compiler flags.

The graphics were also a bit of a challenge. All of the sprites in the game are SVG images. The nice thing about using SVG is that the game can scale to almost any size - it should look equally good at 1920x1440 as it would at 640x480. The down side is that SVG take longer to paint than a bitmap. At 19200x1440 drawing a few hundred fancy SVG images causes a noticeable lag.

The solution I came up with is to have a blank image for each sprite and to keep track of which images need to be erased, redrawn, or moved for each new frame of animation. Instead of repainting the entire screen, I just blank out the images that have changed. This seems to work fast enough, but the implementation is a bit messy right now, and still has a few bugs to work out.

The other problem, which I haven't quite solved yet, is the interaction between all of the "actors" in the game. There's the player's ship, the spider, the scorpion, the mushrooms, the centipede segments, the bullets, and the fleas, and they can all potentially interact with each other. My gut feeling is that there must be a convenient way to use polymorphism to simplify things, but I can't quite put my finger one what it is. Right now there's a big glob of ugly code more or less handling all of the permutations individually, which feels like the wrong solution. I've been putting off adding the actual centipede until I get this part figured out.

The code, so far, is available here.

Rodent's Revenge Clone

Rodent's Revenge Clone Screenshot

One of my first computers had a game called "Rodent's Revenge." The premise of the game is that you're a mouse, being chased by cats, and to survive you have to trap the cats using movable blocks. The Wikipedia article explains the game play better than I can, so if you're really interested, go there.

A while back I was bored and got the idea that it would be fun to make a Rodent's Revenge clone.

The final result, so far, is more like a prototype than an actual game. What works so far is the graphics display, the movement of the "mouse" and the "cats" the scoring, trapping of cats, and eatting cheese. That's about just enough stuff to play the first level all the way through. And that's where I got stuck.

I initially thought the original game had 50 preset level patterns. That turns out to not be the case. Although some levels have a preset pattern, most of the levels follow a rough template, but are randomly generated. So, for example, the first and thrid levels are always exactly the same, but the second level has a dozen randomly placed fixed blocks surrounded by movable blocks.

The random levels thwarted my plan to use simple text files to describe the levels. I thought about it for a few days and didn't come up with anything, and eventually got side tracked by other stuff. At some point I'll probably come back and finish the game, but it's on the back burner for now.

Despite not being complete, the code is available here.

Minesweeper 3D

Minesweeper3D screenshot

The other day at work a couple of coworkers and I had the idea for a 3D minesweeper game. We weren't exactly sure what that would be like, so I decided to find out. Unfortunately it's even less fun than regular Minesweeper.

The game uses the Qt GUI toolkit and OpenGL for all of the 3D graphics. As far as I know it will work on all platforms with OpenGL and a Qt port, but I've only tried it on the AMD64 port of Debian Linux.

The code is a little messy, and the documentation could be a better, but I don't think the overall design is too bad. The application is divided into 4 parts:

The code is available here. Radio Ripper

I recently bought a Cowon iAudio A2, so I needed to get some new music. I'm a big fan of, and it occured to me that I could get an almost endless supply of music if I could record it.

So, after a few days of thinking it over, I sat down for a few hours and wrote a nifty radio ripper in Erlang. Surprisingly, the whole thing only comes to about 160 lines of code. Unfortunately, mainly due to my unfamiliarity with Erlang, the code is pretty buggy. After a few songs (around 10), it'd fail.

I decided to start from scratch in C++. This version is much better, and records for hours.

Unfortunately, I don't think I'm going to release the source code for this.

QLines (Five Or More clone)

QLines screenshot

I got a little bored over the five day weekend between jobs, so I started playing "glines", the GNOME Five Or More clone. After a few hours of frustration, I realized I could probably make my own clone of the game without too much trouble.

A few hours later, I had this. It's a really simple implementation, without any of the "fancy" features of the GNOME version, but it's playable, if a little limited. There's only one board size (9x9), and the score keeping is different than the GNOME version, but it wouldn't be hard to add additional board sizes and correct scoring, I just lost interest.

I used Qt for the GUI, so the game should compile without problem on Linux, Mac, Windows and several other platforms, however I've only tested it on Debian.

The only real interesting part of the implementation is the algorithm to detect whether a piece could move to a new location, and the path it would take getting there. After about half an hour, I realized a simple depth-first search would work nicely. The current implementation isn't very smart, but handles the "Large" 20x15 grid size quite efficiently.

The second challenge I faced was determining when a "line" of 5 or more pieces had been formed. Fortunately, a brute force search seems to work well enough for the grid sizes used. Even with a 50x50 grid the search is almost instantaneous and does not noticeably slow down game play. With the 9x9 and 20x15 grid sizes, the search is very quick.

I also began work on a clone of the GNOME game Same, although this hasn't gone very far, and will probably never get finished ;-).

Ray Tracer

Ray Tracer scene

About a week ago, I started working on a simple ray tracer. After a little work, I decided to add spatial subdivision to make it faster. The image shown was generated in about 2 minutes, and contains a few thousand spheres.

The simple ray tracing algorithm works by tracing rays for each pixel on the screen, and testing for intersection with every object in the scene. After finding the closest intersection, new rays need to be traced for shadows, reflection and refraction, and each of those needs to be tested against every object in the scene as well. That can take a really long time for complex scenes.

The spatial subdivision method I'm using is from a paper by Akira Fujimoto, Takayuki Tanaka, and Kansei Iwata, published in 1986. It helps reduce the number of intersection tests required by placing the scene in a large grid. Each cell of the grid contains a list of objects that are completely or partially in the grid cell. A 3d version of Bresneham's line drawing algorithm is then used to traverse the grid along the path of a ray, and each object in each grid cell along the path is tested for intersection. This may result in significantly faster rendering times.

The algorithm reduces the number of intersection tests required because it only needs to test objects contained in the grid cells it visits. Also, once it finds the closest intersection in a cell, it's no longer necessary to continue searching. In addition, the Bresenham algorithm uses only integer additions and subtractions, which is significantly faster than the floating point vector operations that are usually involved in intersection testing.

Although this method can result in significant speed ups, it is not without problems. The biggest problem is the memory usage. A 100x100x100 grid requires 1,000,000 lists. Assuming 4 bytes for a pointer, and a very simple list structure, that comes to about 8 MB for an empty grid. Also, for scenes with a few objects and a large grid, it may actually take more time to traverse the grid than it would to simply test each object for intersection.

I have a few bugs to fix before I release the source code. Occassionally images will have some small areas missing, where an object isn't added to a grid cell when it should have been, or the traversal algorithm went to the wrong cell. The problem is almost entirely fixed, but needs more testing.

I also need to debug some of the shading algorithms. Specifically the refraction.

The code is available here.

TSP Solver

I've had an interest in the symetric travelling salesman problem for quite some time. The problem is to visit a collection of cities and minimize the travelled distance, with each city being visited exactly once. The symetric restriction means that the distance between cities A and B is the same as between B and A. As simple as it sounds, the problem is NP-hard, which more or less means that there's no reasonably fast algorithms to solve it for large instances. The difficulty of the problem stems from the fact that for an instance with n cities, there are (n-1)!/2 possible tours through the cities. For more than a few dozen cities, the sheer number of combinations is overwhelming.

QTsp Screenshot

Fortunately, there are a number of heuristic algorithms available. The goal of a heuristic algorithm is to find a suitable solution in a reasonable amount of time. The resulting solutions are usually not optimal, but are close enough to make extra computation unnecessary. As an example, a TSP with thousands of cities may take thousands of years to solve optimally, but a heuristic solution may be able to find a solution within 1-5% of the optimal solution, in as little as few minutes.

Occassionally I like to try my hand at creating programs to solve instances of the TSP. Usually this involved writing a lot of boilerplate code to do things like reading in data files, manipulating the data, and displaying the results. To save myself from reinventing the wheel every time I become interested in the TSP, I created a GUI program, using Qt, which handles most of the mundane details for me. It reads the data files, displays the current tour, computes the current tour length, and can save the current data.

To avoid digging around in the full source code, the application uses plugins to do all of the solving. At runtime the main program scans the plugins directory and loads all the plugins it finds. Each plugin implements a particular algorithm for solving the TSP. For example, one plugin may use a greedy algorithm, another a three-opt algorithm, and another an evolutionary algorithm.

The screenshot above shows the program running with a 13508 city tour of US cities, solved (poorly) with a greedy algorithm.

In the next few days I plan on cleaning up the source code and making it available for download.

For more information about the travelling salesman problem, visit here.

The code is available here.

Parametric Surface Plotter

Plotter Screenshot

I've also been working on a Qt program to plot 3D parametric surfaces using OpenGL. The plan is to let the user enter in the x, y, and z equations, the ranges for u and v, and possibly some viewing info. It will also allow the view to be zoomed and rotated with the mouse. It's not particularly interesting, but I'm primarily doing it to better learn Qt, and to get some practice writing parsers.

The screenshot shows a very early version running. The equation is hard coded and there's no user input yet.