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

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 2

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.