Maze Generation Algorithm(s)

[Brosert]

I am writing (or trying to) a small program to draw a maze, that can then be traversed by a user. I have set up a grid of squares that can be either present (blocking the path) or not (allowing the user to navigate into that square).
My first problem, is that all algorithms I can find on the net (Prim, Kruskal etc) deal with a cell having walls (or Nodes having edges/vertexes, if you prefer) - and I can't think of a way to convert my current design.

I have written a small routine to draw a (random) path from bottom left to a random point at the top or right, and have played with some different ways to randomly populate the remaining board (first time literally random whether a particular block was presentor not, then differing probability based on how many blocks surround it, and finally by drawing different paths at random through the maze in different directions). None of these options give a very nice looking maze - sometimes the path is obvious (or the only way you could legitimately access), sometimes it's too open, and sometimes it just looks, well, just messy.

To cut a long story short, I wondered whether anyone might know (of) an algorithm that might be suited to this type of maze - or whetehr anyone had any ideas on how I might adapt one of the more common Node-edge or Cell-Wall algorithms to this purpose (ie: Prim/Jarnek (DJP), Kruskal are probably no good to me unless you can suggest how to modify them)...
I suspect I could use a Recursive Division algorithm, but am unsure where to find a definitive explanation of exactly how it works.

Any suggestions welcome....

<Edit> I just realised my algorithm to create the original path wasn't quite correct (the path would only go up or right, never left or down). Having corrected it, I now get way too much whitespace (I think its making very intricate paths - the problem is I have no 'boundary' between cells....)
</edit>

[sicarie]

As this question is more about an algorithm than the language, I'm moving it over to the Software Development forum.

[Brosert]

Which says:

Please do not post Technical Questions here

I also considered Miscellaneous Questions

[JosAH]

Given the following constraints and definitions:

1) a maze consists of a rectangle of rectangular rooms;
2) a room is 'open' if it doesn't have four walls around it;
3) a room is 'closed" if it has four walls around it.

A maze can be generated as follows:

0) all rooms are closed;
1) start in a random room in the rectangle;
2) find a random closed adjacent room; if not found go to step 4
3) open the wall between the two rooms; move to the other room; go to step 2.
4) if all the rooms are open goto step 6
5) find an random open room with an adjacent closed room; go to step 2
6) stop

After the algorithm has stopped you have created a maze with no entry and exit
yet; open two random walls at the border of the rectangle. Only one path leads
from the entry to the exit and there are no cycles in the maze which makes it
quite easy to solve the maze (the 'right hand wall rule'). If you break down a few
other random walls in the maze you have created a complex maze with cycles.

kind regards,

Jos

[Brosert]

Thanks Jos,

Actually the problem was that I was using cells without the concept of walls - that is, this cell is either filled in or it isn't. In this way, each 'cell' was a filled square - and was either there or not (so the whole thing could be stored in a boolean array.
Everything I found on the net seemed to suggest the same sort of method you specified, but I really didn't want to change the way I was drawing the maze on the screen.
Eventually, I decided to bring the concept of walls in, but in such a way that only squares with both x & y coordinates even would be cells, and any other cell would be a wall (with odd x & y ALWAYS being a wall).
Using an algorithm similar to yours, I manged to generate a maze as desired (in non language-specific code):

Pick Random_Cell
RandomCell->Visited=true;
wallList Add(Random_Cell's Surrounding_walls)
while( wallList Not Empty) loop
 
   wall = wallList->getRandomWall();
   if(wall has unvisited cell on either side)
   {
     unvisited cell = visited;
     wallList Add(wall->newly_visited_cell's- Surrounding_walls);
   }
   Remove wall from wallList;
}
 

Same principle, I suppose...Gives you a unique path to any cell in the maze.

Currently, the maze is 29x29 cells, and the pattern generated is sufficiently complex to make the RH rule tedious, and lengthy (for a human user), although I will consider removing some random walls just to add to the challenge!!

Although counting the steps taken and reporting back to the user how many they took, and the minimum they could have taken works well for now.

Tanks Again!!

[JosAH]

Currently, the maze is 29x29 cells, and the pattern generated is sufficiently complex to make the RH rule tedious, and lengthy (for a human user), although I will consider removing some random walls just to add to the challenge!!

You do that; it makes those mazes much more complex; human beings aren't
that good in seeing a complex cycle hidden in those mazes.

kind regards,

Jos