Theseus 1.0
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:
A simple orthogonal (rectangular) maze
The same maze, but with the solution rendered
A delta maze (triangular tiles) with a triangular mask
A sigma maze (hexagonal tiles)
An upsilon maze (octagonal and square tiles)
You can apply images as masks to constrain how the maze is shaped
A weave maze has passages that move over and under other passages
A braided maze has multiple solutions, due to circular loops in the graph
A unicursal maze has only a single path, with no junctions
Theseus can generate mazes with x, y, xy, or radial symmetry. This maze shows radial symmetry.
Theseus can wrap mazes in x, y, or xy. This maze is wrapped in x (cylindrically).
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.
Reader Comments
Hi Jamis.
Do you know any good resources for reading up on the maze algorithms you used? Thanks!
20 Dec 2010
@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.).
20 Dec 2010
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.
20 Dec 2010
(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
22 Dec 2010
@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.
22 Dec 2010
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.
31 Dec 2010
Thanks for chiming in, Kent! I’ll give that a shot and report back how it goes.
31 Dec 2010