Specific data structure for multi-algorithm maze builder

Question

I've already read this question, and done research on my question, but I find that I don't have a suitable answer yet.

I want to build a generic data structure in ruby with which I can implement any (2d, rectangular) maze-generating algorithm I see fit. To start, I'll be implementing Randomized Prim's and Depth-First Search, and later I will want to implement Sidewinder and others. The goal is to be able to generate a wide variety of different looking mazes. And FYI, a wall isn't a 'filled' cell - it's the divider between two adjacent cells and is either solid or not.

But the problem I face is that all the algorithms need to know about different things. Prim's, for instance, says to pick a Cell and add its Walls to a wall_list. That's fine, I can start with this:

class Cell
  def get_surrounding_walls
    # some code
  end
end


class Wall
  @solid = true
  def remove
    @solid = false
  end
end

wall_list = []

But now I start running into confusion about how to store specific details. Should I have a multi-dimensional array of cells? And do cells keep track of their own four walls? If I do that, then I have to multiply complexity when I toggle a Wall, as I need to get the neighboring cell's wall as well. If I get a cell to keep track of only, say, its RIGHT and DOWN walls, then I increase complexity in getting the status of the UP and LEFT walls.

If, on the other hand, cells and walls are maintained in separate lists, should I have one array for all walls, or one for UP/DOWN walls and one for LEFT/RIGHT walls? In the first case, it's easier to select a random wall, and query specific walls for their status, but harder to actually structure - walls don't line up nicely with a grid. And it makes it harder for a Cell to know about the walls that surround it.

Should I be tracking cells at all? Common sense says they need to be objects, because some later algorithms will require cells to know which set their in. But if I wanted to use some sort of Graph, like an Adjacency Matrix, then the whole structure seems set up to only track walls. Also, for large mazes, the matrix gets prohibitively large.

This is likely a case of Analysis Paralysis, but the fact remains that I don't know where to start.

To quote the great Fred Brooks: "plan to throw one away; you will, anyhow." — David Eisenstat, Oct 08 '14 at 14:51
Oh, I've written and rewritten about 100 line of code and just deleted the whole thing about 3 or 4 times now. Nothing seems to encompass everything I need it to :( — Devon Parsons, Oct 08 '14 at 14:54

score 1 · Answer 1 · answered Oct 08 '14 at 15:53

To avoid duplication of wall information, as cells can share walls. Have each cell only store the status of the top and right wall. You would need to handle the edge case of the most left column and bottom row as their wall status will not be covered. You can do this by introducing virtual cells that contain that information.

Create a hash like this

wall[[10,5]] = [1,0]

So cell in row 10 column 5 has a top wall and no right wall.

To get all the walls of a cell. You have to query it's bottom and left cell

So to get all the walls for [10,5], you need to query the hash like this

wall[[11,5]][0]
wall[[10,4]][1]

So the full set of walls for cell [10,5] is

[ wall[[10,5]][0], wall[[10,5]][1] , wall[[11,5]][0] , wall[[10,4]][1] ]

Where the array above is the status of each wall starting top going clockwise.

So the wall's information is stored, the cell's walls is inferred.

You could also use an array instead of a hash to store the locations of the walls

score 1 · Answer 2 · answered Oct 08 '14 at 15:59

Create an object for each cell and each wall. Each cell stores its coordinates and a hash like {"left"=>left_wall, "up"=>up_wall, "right"=>right_wall} where boundary cells have missing entries. Walls reference their two neighboring cells and store whether they are solid. A maze object stores a two-dimensional array of cells.

Since you're programming in Ruby, I'm assuming that speed is not the top priority. I've tried to strike a balance between simplicity of use and simplicity of implementation.

Here are some of the operations supported.

Get the up neighbor of a cell. Look up "up" in the hash to get the wall. Compare the cell for equality with one of the neighbors of the wall; return the unequal neighbor.
Get the cells neighboring a cell. Iterate through the hash values and do the previous step.
Mark a wall as solid/not. Easy.
Query the status of a wall. Easy.
Get a random cell. Easy.
Get a random wall. We don't have a list of walls, so we have to be a little clever. Pick a random cell and a random direction. If that cell has a wall in that direction, then return it. Otherwise, try again. We can get a random left/right wall using a similar technique.

Specific data structure for multi-algorithm maze builder

2 Answers2