473,836 Members | 2,080 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Maze Generation Algorithm(s)

57 New Member
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>
Jul 23 '08 #1
5 9704
sicarie
4,677 Recognized Expert Moderator Specialist
As this question is more about an algorithm than the language, I'm moving it over to the Software Development forum.
Jul 23 '08 #2
Brosert
57 New Member
Which says:
Please do not post Technical Questions here
I also considered Miscellaneous Questions
Jul 24 '08 #3
JosAH
11,448 Recognized Expert MVP
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
Jul 27 '08 #4
Brosert
57 New Member
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):

Expand|Select|Wrap|Line Numbers
  1. Pick Random_Cell
  2. RandomCell->Visited=true;
  3. wallList Add(Random_Cell's Surrounding_walls)
  4. while( wallList Not Empty) loop
  5.  
  6.    wall = wallList->getRandomWall();
  7.    if(wall has unvisited cell on either side)
  8.    {
  9.      unvisited cell = visited;
  10.      wallList Add(wall->newly_visited_cell's- Surrounding_walls);
  11.    }
  12.    Remove wall from wallList;
  13. }
  14.  
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!!
Jul 30 '08 #5
JosAH
11,448 Recognized Expert MVP
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
Jul 30 '08 #6

Sign in to post your reply or Sign up for a free account.

Similar topics

22
9942
by: Bernard Fields | last post by:
Greets, all. As the title suggests, I'm trying to make a maze. Specifically, it's a top-down, 2-d maze, preferably randomly generated, though I'm willing to forego that particular aspect as this point. I've done many, many web-searches, but nothing that I've found so far has provided any clues....
2
21422
by: Roger Douglass | last post by:
I've been working on this program for school and I just about got it before I had to turn it in. Here's my final code on it. I didn't finish it, but I think I'm pretty close. M is the starting point in the maze and W the finish. Using recursion the program is to leave a trail of asterisks (*) showing the solution. Well, I got stumped on this one. I found something similar to it online, but not quite what I was looking for.
1
7433
by: Ghada Al-Mashaqbeh via DotNetMonster.com | last post by:
Hi all, I want to implement Lee Maze routing algorithm in C#, I have many problems especially in gaining usefull resources about the algorithm work, please if can any body help me to find usefull resources. Also, if anybody can send me the a link to the full artice of the following paper I will be very glad, the paper is: “An Algorithm for Path Connection And Its Application”, CY Lee, IRE
1
3393
by: daneshjo | last post by:
Hi im an IT student.I have registered as a member of this site recently.I have a question about the solution of maze program. I want to write maze program in c++ .I want to solve the maze class includes two methods: 1)makeMaze & 2)runMaze. I write the method of makeMaze in a way that fulls a n*n matrix. one of my problem is about the writing the code of dynamic 2D array allocation . an another is about the writing the method of runMaze in a...
2
3445
by: dev24 | last post by:
Hi guys, I was looking at random maze generators on the web. I found this prims algorithm but everytime I run it, it doesnt display the random maze as it should. It just displays a blank applet. Also, does any one know how to save this generated applet to a png or jpg format? Source code is attached below. Thanks. ********************************************************************************************* package ares; import...
1
2782
by: faroz | last post by:
anyone has any idea about sokoban maze algorithm?? thx for helping...
0
9811
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, well explore What is ONU, What Is Router, ONU & Routers main usage, and What is the difference between ONU and Router. Lets take a closer look ! Part I. Meaning of...
0
10822
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
1
10577
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
10241
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
9359
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development projectplanning, coding, testing, and deploymentwithout human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
7774
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupr who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
5642
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
5812
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
3
3103
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.