21 November 2015 —
An implementation of a toroidal grid is walked through and demonstrated.
The output is mapped onto a torus via POV-Ray. Finally, a maze is
generated on the grid, and also mapped onto a torus.
When I first proposed Mazes for Programmers@amazon | @b&n, my original outline was enormous. It was going to be the de-facto reference for all things related to maze algorithms. I think I estimated the length of the book–when finished–to be somewhere in the neighborhood of 500 pages.
I went into this with big dreams. Among many other things (some of which I may blog about eventually), I was going to have a chapter that went into detail about how to map a grid onto three-dimensional objects like spheres, cubes, toruses, and so forth.
After my proposal was accepted and I got down to business, my editor (Jackie Carter) talked me down to a more reasonable 250-300 pages, which could only be done if I sacrified a significant portion of my outline. A lot of things got cut. I managed to keep the bit about spheres, cubes, and even Möbius strips, but (alas!) the toruses didn’t quite make the grade.
This is what blogs are for, I guess! I’d like to make up for that shattered dream of mine and share a bit about how I would represent a grid that can be mapped onto a torus with a minimum of distortion. (A torus, you’ll recall, is a donut shape–a tube that connects to itself and forms a circle.)
Now, you could simply take a rectangular grid of cells and map it onto a torus, like wallpapering a donut. The problem with that approach is that you’re going to wind up with a distorted grid.
Consider. A torus, viewed from above, is essentially two concentric circles:
Simple geometry–or even intuition–will tell you that the inner of those two circles has a smaller circumference than the outer circle. If you were to apply a 10x10 grid to such a torus, the ten cells on the interior circumference would be smaller than those on the outer circumference. We can show this distortion simply by drawing radial lines between the two circles. See how they are further apart on the outside, than on the inside?
Now, if you make the torus thin enough, the difference between the circumferences becomes smaller, which means the distortion grows less. You can also reduce the distoration by dividing the grid into more cells. But, really, these are very specific solutions to the problem. For a more general solution, we can instead employ adaptive subdivision to split cells in half when they begin to distort beyond some threshold.
(This is the same thing I talk about on page 103 of my book.)
Toroidal grids share a lot with spherical grids (pg. 238 of my book), so some of this may sound very familiar if you’ve been through that. A spherical grid is basically a soup-can wrapper rolled so the east and west edges touch (and then with a bit of magic applied to the north and south edges so they reduce to a point). The same is true of a torus, but with another interesting difference. Picture that soup can wrapper. Now, roll it so that the north and south boundaries touch. Then, taking that cylindrical tube, bend it around donut-style, so that the east and west boundaries touch.
See that? Toroidal grids wrap in both dimensions!
Just as I did in my book when dealing with spheres, we’re going to tackle this as simply as possible. We’ll just create a grid that wraps in both dimensions, and then map it onto the 3D geometry of a torus using POV-Ray. That is to say, our final result will look like this:
We aren’t going to be generating actual geometry for the walls, here. (Though, that’s a lot of fun, too! Maybe I’ll talk about that in another article…)
Got all that? Let’s do it. We’ll create an adaptively subdivided, toroidal grid of cells.
I’ll use Ruby for my implementation, but the underlying ideas ought to map very cleanly to whatever language you’re using. Also, while I’m not using any of the code from my book here, you could easily use the code from there to do this exercise, if you’d prefer.
We’ll start by implementing a simple Cell class. It will need to:
hold references to its neighbors to the west and east (clockwise and counterclockwise around the torus).
hold references to its neighbors to the north and south (moving poloidally around the torus). Because we’ll be adaptively subdividing the grid, a cell may have more than one neighbor in each of those directions!
indicate that a passage has linked it with a neighboring cell.
Here’s what I’ve got:
The grid, then, will be a collection of these cells, arranged very particularly.
We’ll call our grid ToroidalGrid:
It will represent a unit torus–that is, a torus with a major radius of 1.
We’ll initialize it by telling it how many rows we want in our grid (must be at least three, mostly for esthetic reasons), as well as what the minor radius is. (Because the major radius is always going to be 1, the minor radius will necessarily be a value between 0 and 1.)
The magic math happens in the configure_grid! method. This is where we’ll compute the size of the cells, determine how many cells each row has, and declare which cells are adjacent to which other cells. Brace yourself…this one is a mouthful…
Whew! The configuration code is almost done–we just need to look at how the adjacency of individual cells is accomplished. This is done in the configure_row! method:
There! That’s all (cough “all”) we need to configure the grid. It’s all set up at this point, with all cells correctly adjacent and subdivided. We’ll just add a few more methods to make it easier to interact with the grid (so we can do things like generate mazes):
All that’s lacking now is a way to display our grid. Let’s add one final method, #to_png, for generating the 2D map as an image. Note that it only has to draw the western and southern walls for each cell. Because the grid fully wraps around in both dimensions, we don’t ever need to worry about explicitly drawing the northern or eastern walls.
That’s it! I won’t lie and say it was trivial, but it’s really not as hard as you might expect. Look, we can create a toroidal image map like this now:
Here, we’re creating an grid with 16 rows, on a unit torus with minor radius 0.5. The resulting grid looks like this:
(Note the seeming absence of a border on the north and east. That’s intentional! Remember, we’re only drawing the west and south boundaries of each cell, because the entire thing wraps around. The grid’s western boundary is also its eastern boundary.)
Using POV-Ray, it’s straightforward to generate an image of this mapped onto a torus. Call the following file torus-map.pov:
Assuming you have POV-Ray installed, you can generate the corresponding image like this. (The +A0.001 instructs POV-Ray to use some pretty intense anti-aliasing; otherwise, the lines of the maze will look terribly jaggy.)
The resulting image will be called torus-map.png. Check it out!