Theseus 1.0

Posted by Jamis on December 20, 2010 @ 08:29 AM

Whenever I tackle a new programming language, I need a project to apply it to. Just experimenting with syntax isn’t enough; there has to be a real context for it, or it doesn’t stick. Some years ago I discovered a great “default” project: generating mazes.

Mazes explore a lot of the nooks and crannies of a language: random numbers, decision making, recursion and/or iteration, and several data structures, at the very least. If you want to be able to tweak your mazes without changing code, you then need to learn about passing arguments via the command-line, or environment variables, or even configuration files. Add the possibilty of actually displaying the maze and you introduce string manipulation and console IO (if emitting ASCII art), or graphics libraries and file IO (if writing to an image file).

The actual algorithms behind building a maze are pretty straightforward, which is ideal. You don’t want to waste time understanding algorithms when you’re trying to learn a new programming language.

This has served me well for several years. C++, C#, Haskell, Erlang, Scala, Io, and even Prolog! But I realized I’d never actually tried it in my favorite language: Ruby.

So, I gave it a try. And I had a blast. It kind of took on a life of its own, with features evolving as fast as I could implement them. The result: Theseus.

I released Theseus 1.0 last night, and it is available for installation via RubyGems. (You’ll get syntax errors if you try it on Ruby 1.8, though, so beware.) Feel free to fork it on GitHub, too. It’s in the public domain, so you can do whatever you want with it.

I am rather ashamed of the lack of tests, though. I realized as I was building this out that I need a good lesson in real test-driven development. I had a difficult time seeing how to test something like this. I’m going to be reading Kent Beck’s book next, I think.

Here are some examples of stuff that Theseus can do:

simple orthogonal maze
A simple orthogonal (rectangular) maze
simple maze with solution
The same maze, but with the solution rendered
triangular delta maze
A delta maze (triangular tiles) with a triangular mask
sigma maze
A sigma maze (hexagonal tiles)
upsilon maze
An upsilon maze (octagonal and square tiles)
maze with custom mask
You can apply images as masks to constrain how the maze is shaped
weave maze
A weave maze has passages that move over and under other passages
braided maze
A braided maze has multiple solutions, due to circular loops in the graph
unicursal maze
A unicursal maze has only a single path, with no junctions
symmetrical maze
Theseus can generate mazes with x, y, xy, or radial symmetry. This maze shows radial symmetry.
wrapped maze
Theseus can wrap mazes in x, y, or xy. This maze is wrapped in x (cylindrically).
sparse maze
A sparse maze is one with unfilled areas in the field.

Give it a try! All of these examples were generated using the command-line utility that is installed with the gem. It’s remarkably flexible.

Posted in Announcements Projects

Comments

Have something to add? Click here to leave a comment.

20 Dec 2010

1. Bradly Feeley said...

Hi Jamis.

Do you know any good resources for reading up on the maze algorithms you used? Thanks!

2. Jamis said...

@Bradly, http://www.astrolog.org/labyrnth/algrithm.htm is a TREMENDOUS resource. It doesn’t go into real depth as far as how things are done, but it’s enough to set you thinking. Theseus uses a tweaked recursive backtracker to generate the maze, and it works fast and well, but it would be cool to eventually allow selection of the algorithm (e.g. Prim’s, Kruskal’s, etc.).

3. Alex said...

I have absolutely no use for mazes but I just have to say Theseus looks amazing!

Next time I’m learning a new language, I’ll have to try generating mazes. What to implement was always my main question when starting out with a language.

22 Dec 2010

4. Anthony Bailey said...

(Ooh, maze generation sounds like an excellent example domain for language exploration. I may follow that thread myself.)

Re TDD for this kind of thing: when I’m developing code that produces large and complicated renderable structures whose details matter, I’ve found two testing techniques to be particularly valuable: checking universal properties, and (tool-assisted) content regression.

Here’s a quick presentation in the context of an example Ruby kata:

http://anthonybailey.net/blog/2009/11/30/testing-with-less-manual-calculation

5. Jamis said...

@Alex, thanks for the kind words!

@Anthony, thanks for the insight into TDD—that does give me some ideas. I’ll have to explore that a bit.

31 Dec 2010

6. Kent Beck said...

Another testing technique I would try is injecting a not-so-random number generator. You can create a generator that returns 1, 0, 1, 0, or whatever sequence exercises your code. If the random number generator is a function, you can wrap it in an object, and then pass that object around wherever a random number is needed.

7. Jamis said...

Thanks for chiming in, Kent! I’ll give that a shot and report back how it goes.