Laberintos

Friday, 26 February 2010

La piedra angular de Maziaks reside en la generación de laberintos. Por eso creo que es bueno que explique como funciona, aunque sea superficialmente.

Necesitaba un modo de crear laberintos al azar. Tenían que ser del tipo "Perfecto", que consiste en que toda parte del laberinto sea accesible, y sin bucles. Esto haría que girando en el mismo sentido recorrieras todo el laberinto. También necesitaba que solo hubiera una entrada/salida de el.

El algoritmo que uso como base se le llama Descenso Recursivo (Recursive Descent), usado en multitud de campos. Este es uno de los mas simples, y mas apropiados para ser adaptado a las necesidades de Maziaks.

Para el funcionamiento de este algoritmo necesito una manera de representar el mapa de forma adecuada. Por eso he usado un tablero en el que cada casilla puede estar marcada como llena o vacía. Todas las casillas son separadas por paredes que también se pueden quitar. También necesito una lista donde poder apuntar casillas, para recordar "Donde estábamos".

Para empezar se ponen todas las casillas como llenas y con todas las paredes, también se elige un punto de inicio, En el nuestro caso el punto de inicio es una casilla en los lados del tablero, para que funcione como la entrada y salida del laberinto. El proceso consiste en "escavar" el laberinto, empezando desde la casilla elegida:

  • Se marca la casilla como vacía.
  • Se comprueba las direcciones posibles, comprobando que casillas adyacentes están llenas.
  • Nos movemos hacia la siguiente casilla eligiendo de entre las direcciones posibles una al azar y continuamos desde el primer punto.
  • Si no se puede ir en ninguna dirección, leer y volver a la ultima casilla apuntada en la lista, tacharla de la lista y continuamos desde el primer punto.
  • Si tampoco queda nada en la lista, eso significa que el laberinto esta completo.

Faltaría explicar como se puebla el laberinto con Bayas, Espadas y Criaturas. O como escojo es sitio adecuado para el Tesoro. Pero si lo hiciera ¿Donde estaría la diversión?


Coments

Anonymous Anonymous Monday, 8 March 2010 10:43

Tengo Pensado el concepto de uno

Ya te lo explicaré. Aunque si te digo la verdad, es una idea un poco simple, pero es eficiente. además no creo que cueste mucho hacerlo ya lo que primero se genera es una solución con camino aleatorio.... Ya te lo explicaré por pidgin.
Anonymous Anonymous Monday, 20 June 2011 23:54

esta guay

Coment

Anonymous Anonymous Tuesday, 20 April 10:05