¿cómo generar un laberinto al azar?

[reethok]

Primero que nada, sólo pido ideas, no código, no quiero que me hagan la "tarea" ni nada parecido (en realidad estudio por mi cuenta xD).

El laberinto debe estar contenido en un arreglo bidimensional de caracteres.

Bueno, aquí les pongo lo (poco) que se me ha ocurrido.

1.- Generar la posición de la "entrada" y de la "salida" al azar en los extremos del arreglo, las única s limitante serían que deben estar separados mínimo por un espacio (que sería pared), y que ni la entrada ni la salida deben de estar en las 4 esquinas, o sea algo así:

Código C++:

##E#S#
#    #
######
 

Y entonces llenar todos los extremos del arreglo con pared.

2.- Ir al azar avanzando para formar el camino de la entrada a la salida, con la condición de que no se amontonen las "casillas" (cada casilla sería una posicion del arreglo), con amontonar me refiero a que no se hagan nudos, sino que sea completamente lineal, no sé si me explico, que no haya camino con doble esperos, por así decirlo, sinoq ue igual deba estar separado por una "pared", aunque las paredes aún no estén puestas.

Mi PROBLEMA llega aquí, ¿cómo hacer las "ramificaciones" para que el laberinto no sea un simple camino de la entrada a la salida, sino que haya bifurcaciones y todo eso que no lleven a ningún lado (como en todo laberinto, pues)?

Les agradecería mucho ideas, comentarios, etc.

¡Saludos! y de antemano, gracias.

[Malenko]

Generar laberintos no es algo trivial y más dependiendo del tipo de complejidad que le quieras dotar (como por ejemplo los bucles). Hace tiempo que lei sobre ello y te recomiendo este enlance de la wiki que está muy bien explicado:

http://en.wikipedia.org/wiki/Maze_generation_algorithm