Sign in to follow this  

maze generation

This topic is 4493 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi. I was just wondering if anyone knows of any good methods for generating a computerized maze. Thanks. mike http://www.coolgroups.com/

Share this post


Link to post
Share on other sites
No, not obfuscated C again...[grin]

It depends on what kind of "maze" you want.
Classic one-entry, one-exit, one-path, find-in-5-minutes? With this I can't help you.
Complicated dungeon? Well, I wrote a generator for those some time ago. It was working in 3 main steps.
At first I used only 1 and 3, but I wasn't giving me good results. See below.

1. prepare a rectangular graph, each node connects with neighbours. node will represent path. No link - you can't go from one path to another (wall).

x - x - x
| | |
x - x - x
| | |
x - x - x (only bigger)

2. randomly subdivide it a few/several times. each division line will be a wall (delete links on the division line trace). Each time leave one-three links (doors).

3. Run DFS through the graph. When you get to a previously visited node, clear the link from current node to it (wall). The DFS will inevitably lead you through the entire maze.

x - x - x
| | |
q ~ C - q
| $ |
q - q - q
| | |
x - x - x

If you are in node 'C', and already visited nodes 'q', you have to erase links '~' and '$', before going up.

Point 2. was to ensure that the DFS will not be a one-big-branch (which happened often). It was also use to create rooms, which I pre-marked as visited, before running DFS, so they would be left intact (after ensuring that doors wil not be deleted, a little tweaking here).

Not sure if this is what you're looing for, but anyway.
Cheers.
~def

Share this post


Link to post
Share on other sites
Ok now for any given cell there are 16 possible combinations of wall, that would require 4-bits of data so an array of chars might be good, you can either set the bits using the bit operators or simply use the numbers 0-15 to represent all 16 shapes.



For better results you don't want to actually visit every cell in the maze, rather: set a cell - skip a cell - set a cell - etc

so that you visit cells as below: X = set; O = skipped

+--+--+--+--+
|X |O |X |O |
+--+--+--+--+
|O |X |O |X |
+--+--+--+--+
|X |O |X |O |
+--+--+--+--+

Take this psuedo code:

for each row
{
for each column
{
/*pick a wall configuration - 16 possible combinations*/
cell = rnd(0 to 15)
/*skip a cell*/
column = column + 1
}
/*skip a cell*/
row = row + 1
}


The four relevant bits of each cell represent the north, south, east and west walls so that you can read the bit value and output the cell state (rendered or ascii output).

Share this post


Link to post
Share on other sites
dmatter, I don't think that will turn out very well. You could easily have just a bunch of small closed rectangles.

deffer, can you tell me more about that subdivide step?

Also, does anyone know why there are no books on this? I know there's not that much to it, but I've seen books on more trivial stuff.

mike
http://www.coolgroups.com/

Share this post


Link to post
Share on other sites
I looked briefly through tutorials blizzard999 has pointed out. And it seems they all simply do "DFS with random path choosing" (nevertheless it's still DFS), one way or another. The problem is, with a base graph that is dense enough (high nodes/links proportion), you will most likely end up with one huge DFS branch, and many minor branchies, only a few "units" long, somethimes somewhat longer (imagine a lightning).

To prevent that (and still use DFS, because it is quick and easy[grin]), we need a way to stop the branch from expanding, and force the algorithm to trace back.

Here's where pre-division comes in.
You make a few artificial barricades (walls), then a few ways out (doors), so the algorithm would never block itself completely.

subdivisions

A few random subdivisions (can be of any type you want, I only tried out the most common one, it may be too "geometric", but may suffice). Leave some entrances (marked in red).

walking

As you randomly walk throug the maze with DFS, if you come by an another visited node, block it with a wall (green on the picture) by removing the link between it and the current node.

Cheers.
~def

Share this post


Link to post
Share on other sites

This topic is 4493 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this