The maze book for programmers!
mazesforprogrammers.com

Algorithms, circle mazes, hex grids, masking, weaving, braiding, 3D and 4D grids, spheres, and more!

DRM-Free Ebook

The Buckblog

assorted ramblings by Jamis Buck

Kaleidoscope

19 February 2011 — A brief observation on the nature of discovery. The author's introduction to Wythoff constructions, and an announcement of a novel uniform tiling library. Sample tilings are demonstrated — 2-minute read

It’s funny how knowledge leads to knowledge. You start digging deeper into one thing, and discover threads leading off into related fields. I began by researching maze algorithms, decided I wanted to see what mazes in more complex tesselations would look like, and after one thing or another found myself learning about Wythoff constructions.

The result is Kaleidoscope, a library for generating uniform tilings using Wythoff constructions.

gem install kaleidoscope

A uniform tiling is a tesselation of a plane using regular polygons (with a few other constraints that I won’t go into here). What this means is that, in essense, you give Kaleidoscope a few input parameters, and it hands you a bunch of regular polygons.

1
2
3
4
5
6
7
8
9
10
11
require 'kaleidoscope'

pattern = Kaleidoscope::Pattern.new(6, 3)

pattern.generate! do |point|
  point.x * point.x + point.y * point.y < 10
end

pattern.polygons.each do |polygon|
  # ...
end

The polygons are generated around the origin of the plane, within a region you specify via the block to the generate! method. Once done, you can translate and scale the polygons to wherever you like, for rendering purposes. Kaleidoscope will even include basic tricoloring data for the polygons, to make it easy to decorate your pattern.

Some obligatory pretty pictures:








The real reason I got into all this, though, was to find interesting tesselations to build mazes in:




It was a fascinating a project, and I had a lot of fun. Oh, and I did it all test-first—a first for me! I learned a ton about TDD.

That said, I’m ready to move on to other projects. I don’t expect I’ll do much more with this library, although there is definitely more that could be done. I’m releasing the code because others might find it interesting. If you do anything nifty with it, let me know!

Reader Comments

Your mazes are awesome. Will try it out. Thank you Jamis.

Wow! Almost worth re-installing Ruby to try it! Do you have working demos online beyond your pics above?

@Joe, no online demos; it’s a pretty CPU-intensive beast at the moment. And I’ll be honest: to make the pretty pictures, you’ll need to wire in your own display routines. I used ChunkyPNG for the images above. The library includes two demos (both of which use ChunkyPNG for display), one that demonstrates the tricolor data, and one that draws (and solves) mazes.

I’m somehow gratified to learn that such an awesome rubyist (that’s you) just did his first TDD. Any tips?

@cal, ha :) for the record, I’ve been writing tests for years, just never actually did things purely test-first before. My advice is to read Kent Beck’s book, “Test Driven Development”. It made all the difference for me.