I''ve been inspired to write a game where you try to get through a maze within a certain time limit and with things (monsters or something ) chasing you through the maze. My only stumbling block so far is how to actually generate the maze. I don''t want to use predefined mazes, I''d prefer them to be randomly generated on the fly. Only real stipulation be that it is solvable every time. IE, it will never generate an impossible maze. Anyone have any ideas on this? Any help would be appreciated greatly. Thanks

quote: Original post by Krank99
I''ve been inspired to write a game where you try to get through a maze within a certain time limit and with things (monsters or something ) chasing you through the maze. My only stumbling block so far is how to actually generate the maze. I don''t want to use predefined mazes, I''d prefer them to be randomly generated on the fly.

Only real stipulation be that it is solvable every time. IE, it will never generate an impossible maze.

Anyone have any ideas on this? Any help would be appreciated greatly. Thanks

Well, there are any number of great resources on solving this problem (with code), including our very own GameDev "Articles and Resources" link (at the top of the forum list here). They''ve got a great link to a Random Maze Generation FAQ, though it seemed to be down as I wrote this.

A quick search on Google found some other interesting possibilities, including:

• Maze Generation



• The Maze Generation Applet



• Dr. Dobb''s Maze Generation Forum

I should think any of those will give you a start.

Good luck!




Ferretman

ferretman@gameai.com
www.gameai.com
From the High Mountains of Colorado

The best method I have ever heard of (and I haven''t looked very hard) is having a 2D array of cells, and each cell is it''s own set. Then you randomly select one wall to break down at a time, and then that new cells joins the old cell''s set. You continue to do this until you have only 1 set left, and it''s solvable every time, and (I think) only has 1 solution. Search for it in the gamedev forum archives, that''s where I heard about it.

Russell

Another method I read in France about 15 years ago came from a topological analysis of a 2D square maze.
The first observation that was made is that a simple maze is constituted of trees growing from a border (by trees and leaf I describe a wall structure). This method is easy to implement:
1- you start with an empty square
2- you seed trunks at each maze border
3- for each trunk/leaf you assign a random leaf if that leaf does not connect the tree to a border or another tree (to avoid locking entire maze area out of reach of the player).

There is only one default to that maze: it can be easily solved using the right hand algorithm.

From this default stems the second observation: you can have mazes constituted of islands (their leaves never touch any of the borders of the maze). If you put the maze entrance at one border of the maze and the exit of the maze inside an island, you cannot use the right hand algorithm to solve it. To implement it:
1- you start with an empty square
2- you seed islands inside the square: the seeds should not touch any of the borders
3- for each island/leaf you assign a random leaf if that leaf does not connect the island to a border or another island (to avoid locking entire maze area out of reach of the player or to avoid creating trees, thus defeating the initial purpose).

A maze only constituted of islands has another default: a part of the maze may never be explored. Maze may also be simpler to solve (you just identify the island where the exit is located)

The general maze implementation to partly solve both problems is to create a maze with trees and islands.

The trouble is that it generates classic mazes (it is a maze not a dungeon with corridors and rooms).

The ridge 6444 game programming site (It seems to have disappeared, BTW anybody knows if the articles were stored somewhere ?) proposed another algorithm.
They just described that a dungeon is always built/carved from existing rooms or corridors. The implementation was something along:
1- you start from a full square (no rooms or corridors)
2- you seed the entrance either with a room or corridor.
3- you randomly select a wall part for each room and corridor.
4- you destroy that wall part and you create either a room or a corridor.
5- goto 3 until you cannot add anymore rooms or corridors

example:



You have three iteration:
1- a 3x1 corridor is initiated at the entrance
2- a 4x3 room is created from the corridor
3- a 2x2 room is created from the corridor and a 3x1 corridor is created from the room

Hope that helps.
Ghostly yours,
Red Ghost.

[edited by - Red Ghost on July 5, 2002 4:21:37 AM - straightening the graphs]

[edited by - Red Ghost on July 5, 2002 4:23:11 AM - straightening the graphs]

[edited by - Red Ghost on July 5, 2002 4:24:53 AM]