Ruby

(Note: if you’re reading this in a feed reader, you’re going to be missing out on the illustrations and demonstrations.)

Alright, so the theme last week was “algorithms for generating uniform spanning trees.” If this week has a theme, it might be something like “algorithms that sometimes act like the recursive backtracker, but only kind...

The last algorithm I mentioned, Aldous-Broder, was (if you’ll recall) originally devised as a way to generate uniform spanning trees (UST). (Review: a spanning tree is a tree that connects all the vertices of a graph. A uniform spanning tree is any one of the possible spanning trees of a graph, selected randomly and...

The next maze algorithm I’m going to cover, the Aldous-Broder algorithm, is one of the simplest imaginable. It’s also one of the least efficient. In fact, it is so inefficient that you might wonder why anyone would even bother implementing it, let alone discovering it and having their name attached to it.

D. Aldous and A....

All of the maze algorithms I’ve covered so far (recursive backtracking, Eller’s, Kruskal’s, and Prim’s) were implemented as “passage carvers”: they started with a solid grid and hollowed the passages out of it. Some algorithms can be implemented a different way (and indeed, some must be implemented this way): as “wall...

My last post was about using Kruskal’s algorithm to generate random mazes. This article is about using another minimal spanning tree algorithm to do the same: Prim’s algorithm.

If you recall, the random variant of Kruskal’s algorithm worked by randomly selecting edges from the graph, and adding them to the maze if they connected...

For the third article in my series on maze algorithms, I’m going to take a look at Kruskal’s algorithm. (I’ve previously covered recursive backtracking and Eller’s algorithm.)

Kruskal’s algorithm is a method for producing a minimal spanning tree from a weighted graph. The algorithm I’ll cover here is actually a randomized version of...

Last time I talked about the recursive backtracker algorithm for maze generation. That’s probably always going to be my favorite algorithm for generating mazes, for a variety of reasons, but that’s not going to stop me from looking at others.

For one thing, there are some pretty crazy algorithms out there for generating mazes.

Eller’s algorithm...

I’ve said before that generating mazes is a great default project when experimenting with a new programming language. I’ve yet to find a better one (but I’d love to hear recommendations). However, before you can dive into generating a maze (especially in a syntax you are unfamiliar with), you had better have a solid grasp...