Best logic for creating a (true) random labyrinth

Question

I've been trying to make a little simple game just to test my logics, and it's a simple labyrinth, it's ugly, and so far sucky.

The engine works pretty well, given that the labyrinth already exists (a matrix), it could be even enjoyable, but I have no intention on drawing a bunch of maps, which might be setting values on 400 (20x20) fields of a matrix. not funny.

Then I've created a function to randomize it, setting floor/wall for each field, and (I expected that) not every map is winnable. then I've made another function which checks if the maps is playable (receives two points, and checks if there's a valid path between them, then I just pass the start and the end. Pretty nifty) and it worked.

If you haven't noticed, this is a VERY stupid way of creating my random labyrinth for the following reasons:

1 - It might come out really easy (giant isles of floor, or a bunch of walls together, making only one, extremely visible path, creating a stupit (though valid) labyrinth
2 - It is potentially the fastest way of creating a perfect random labyrinth EVER, but at the same time it's potentially the slowest too, taking as long as... infinite. This difference is noticed more when I set the grid for 30x30 or more (when something is not overflown)
3 - It's dumb and an offence to logic itself.

In my deffense, I didn't plan making it this way from the beginning, as described, one thing led to another.

So I've started thinking about ways to do a beautiful (full of paths, tricky and winnable) labyrinth, then I've thought about making tiny small (let's say) 5x5 blocks with predesigned entrances and mount them together in a way that it fits, but it would go against my true random desire, as well as my unwillingness to draw it by hand.

Then I've thought about a function to create a random path, run it once to the end, and run it several times to somewhere close to the end, and some crossings and stuff, some creating dead ends, which seemed better to me, but I just couldn't imagine it creating a decent labyrinth.

You can check what I've done so far in this link.

Note: I have no intentions in harming anyone's pc with anything.
First one to open it, please comment here saying that it's safe. - Done (thank you, Jonno_FTW)
If you still don't trust it, use a Virtual Machine.

OBS: I know this is not the best way of developing anything. I should get a decent game engine, bla bla bla, it was some kind of challenge for myself.

Answer 1

How you create a random labyrinth will depend on what you want it to look like. If you're creating something that's designed to have a lot of dead ends, then you can just "randomly" trace a path from the start point to the end point, and then randomly fill in the empty spaces, essentially carving the path out of a solid block of material. E.g. imagine you had a stone tablet. First step would be to carve the "solution" path. Then you'd go in and make all of the dead ends.

If you want something that's more "play" than "puzzle", then creating a bunch of tile pieces that fit together in different ways is probably the way to go. That's how the Diablo games did it as far as I can tell; a number of predesigned "sets" and rules about how they fit together. You'd mark the four sides of the block with things like "three open spaces followed by two closed," and then if another piece also has a matching description, they can be put together.

After that, all you have to do is figure out how you can consistently render "random" behavior.

Answer 2

Your question makes me think of the XScreensaver Maze program. Look at its screenshots to see if that's the desired effect.

It looks like it took its maze generation algorithm from Wikipedia.

Answer 3

I've done maze generation. You don't want to place stuff randomly and validate. Instead, you generate it out from a starting point.

Pick a starting point, move in a random direction. Have a random probability of picking a new direction. Never move into an occupied square, if you bump into one the current trail ends. If the current trail ends pick a square you have already visited and pick a new direction and do a random walk like you did for the first one. Repeat until the maze is as full as you want it to be.

The probability of the direction change should be an input parameter as it makes quite a difference. Note that if you are doing a 3D maze the odds of a vertical turn should be a lot lower than the odds of a horizontal move.

Answer 4

Have a look at the source code in my Roguelike game, Tyrant:

Code for Dungeon.java

There are a lot of diferent map generation techniques used to produce the different level types. But the most basic pattern is to iterate the following:

1. Start with a blank map
2. Create a single random room / open space in the map
3. Randomly select a tile at the edge of the currently open area
4. Attempt to "grow" a corridor or room randomly out from that space (if it doesn't fit, do nothing)
5. Loop back to step 3 as many times as you need to create a decent maze
6. Finally, do a pass over the whole map and convert and remaining blank space to walls

Here's a screenshot of the type of thing you get (Look at the mini-map from the maze structure):

Answer 5

Wikipedia has a great article on Maze generation algorithms

Answer 6

Here's an expansive website dedicated to labyrinths: http://www.astrolog.org/labyrnth/algrithm.htm

Explains what types of labyrinths there are, goes over the generation algorithms and the solution algorithms, has a lot of cool pictures.