Javascript - Randomized Prim's algorithm problemRandomized Prim's algorithm

Question

I'm trying to create a random maze generator in javascript.

There may already be working examples out there but I'm trying to solve this one myself (well, as much as possible)

The problem I'm having is my script only runs for a few blocks then stops.

I think the issue is with my understanding of the explanation I'm following (from this Wikipedia page http://en.wikipedia.org/wiki/Maze_generation_algorithm)

This algorithm is a randomized version of Prim's algorithm.

1. Start with a grid full of walls.

2. Pick a cell, mark it as part of the maze.Add the walls of the cell to the wall list.

3. While there are walls in the list:

   1. Pick a random wall from the list. If the cell on the opposite side isn't in the maze yet:

      1. Make the wall a passage and mark the cell on the opposite side as part of the maze.

      2. Add the neighboring walls of the cell to the wall list.

   2. If the cell on the opposite side already was in the maze, remove the wall from the list.

As I've hi-lighted my problem is with the opposite side part of this. Does this mean any adjacent cell that is in our wall list? Or does it mean something else?

I've tried it with adjacent cells and it ends up just blocking itself in.

Any idea's would be appreciated.

If I can get it working I'll post the code when it's done. Just as I said I want to get as far by myself before getting help with a full solution.

Answer 1

A wall represents the connection between two different cells. When you add a wall to your wall list, it's because you are visiting a cell that will be part of your maze, so when it refers to the opposite one it means the cell 'behind' that wall, where a passage would lead to if that wall was not there.