We've played around with some mental gymnastics, hovering around the idea of making mazes. We've looked into some of the details involved in designing a data structure for doing so, as well. These are important considerations and it's often a good idea to imagine your data design before developing an algorithm. But it's now time to work out the details of an algorithm for making mazes.
Maze algorithm
Here's an algorithm, in my form of pidgeon BASIC:
Empty the path list of rooms.
Set up the west walls for each room.
Set up the south walls for each room.
Set up the visitation status of each room.
Set up a count of rooms that remain to be visited.
Pick a starting location in the maze, at random.
DO WHILE (more rooms to visit),
Decrement the count of rooms to visit.
Mark the current room as visited.
Count the number of valid exits from this room.
DO WHILE (no exits from this room),
Pick an entry from the path list, at random.
Remove that entry from the path list.
Count the number of valid exits from this new room.
LOOP
IF (count of exits > 1) THEN
Add this room to the path list.
END IF
Select one of the available exits, at random.
Break the intervening wall in that selected direction.
Move into the new room in that direction.
LOOP
Try this out with paper and pencil, first. See how it seems to work for a very small, hand managed maze. It will help a lot to do so, when it comes to actually programming this up. But this captures a workable algorithm.
What do you think of it?
Last updated: Tuesday, July 06, 2004 19:13