Special

Introducing the “Welcome to Xojo” Bundle!

New to Xojo and looking for guidance? We've put together a terrific bundle to welcome you! Xojo Bundle

This bundle includes six back issues of the magazine -- all of year 15 in printed book and digital formats -- plus a one-year subscription so you'll be learning all about Xojo for the next year. It's the perfect way to get started programming with Xojo. And you save as much as $35 over the non-bundle price!

This offer is only available for a limited time as supplies are limited, so hurry today and order this special bundle before the offer goes away!

Article Preview


Buy Now

Issue 3.6

FEATURE

Maze Generation

How to Get Lost in Your Work

Issue: 3.6 (July/August 2005)
Author: Joe Strout
Author Bio: Joe always loved mazes as a child, and spent many long hours generating them by hand, the dolt.
Article Description: No description available.
Article Length (in bytes): 16,530
Starting Page Number: 18
Article Number: 3610
Related Link(s): None

Excerpt of article text...

Mazes are one of those simple puzzles that have been enjoyed throughout history. For most of that history, designing a maze required a lot of careful work. Nowadays, we can let our computers do the grunt work for us. In this article, we'll see how to write REALbasic code that automatically generates a maze of any size and shape we like.

Let's start by considering some of the properties of a good maze. It should certainly be solvable; that is, there must be a path from the start location to the goal location. More generally, it should probably be possible to get from any point in the maze to any other. However, it shouldn't be too easy; there should be only one or a few ways to get from point A to point B.

For a maze composed of square cells, each cell has four walls (ignoring for now the edge cells around the outside of the maze). However, each wall is shared between two cells -- assuming we don't want to support one-way doors -- so really, there are two walls per cell. In the code for this article, I'll assume that a cell "owns" the walls above and to the left of that cell.

Now consider the extreme cases. If every cell is completely enclosed by walls, then there is no path from any one to any other one. This satisfies the difficulty constraint, but it's not solvable. Conversely, a maze with no walls at all is always solvable, but is clearly not difficult. So we need a maze that has just the right walls to satisfy our two constraints. Conceptually, a good way to do that might be to start with a maze that has all the walls in place, then carefully knock down walls just as needed to make it solvable, and then stop, since knocking down any further walls would make it too easy.

How can we tell whether knocking down a wall helps in making it solvable? A wall separates two cells; if there is already a path from one cell to the other, then we don't need to remove the wall between them (and indeed we shouldn't, if we want the maze to be as difficult as possible). If there is no such path, then removing this wall makes possible a path among those two cells, plus all the other cells connected to them.

...End of Excerpt. Please purchase the magazine to read the full article.