[ProgJuegos] Generador de laberintos, pequeño aporte.

#include "laberinto.h"
#include <stdio.h>

int main(){
FILE *arc;
laberinto lab;
int alto, ancho, contx,conty,semilla;
char celda;
alto=20;
ancho=30;

printf("ingrece la semilla para el laberinto:");
scanf("%d",&semilla);
printf("\n");
arc=fopen("imagen.ppm","w+");
fprintf(arc,"P6 %d %d 255 ",ancho*2+1,alto*2+1);
laberinto_inicializar(&lab,ancho,alto);

//Antes de crear el laberinto, agrego un salon, para ver que tal anda
laberinto_agregar_salon(&lab,10,5,8,7);
laberinto_agregar_acceso(&lab,9,5,AC_DERECHA);

//creo el laberinto!
laberinto_crear_westnort(&lab,semilla);

//primero dibujo la linea superior
for(contx=0;contx<(ancho*2+1);contx++)
fprintf(arc,"%c%c%c",0,0,0);
//ahora dibujo todo!
for(conty=0;conty<alto;conty++){
//primero dibujo cada celda, y las pared derecha.
fprintf(arc,"%c%c%c",0,0,0);
for(contx=0;contx<ancho;contx++){
fprintf(arc,"%c%c%c",255,255,255);
celda=laberinto_accede(&lab,contx,conty);
if(celda&AC_DERECHA){
fprintf(arc,"%c%c%c",255,255,255);
}else{
fprintf(arc,"%c%c%c",0,0,0);
}
}
//Ahora dibujamos los accesos hacia abajo, y las esquinas
fprintf(arc,"%c%c%c",0,0,0);
for(contx=0;contx<ancho;contx++){
celda=laberinto_accede(&lab,contx,conty);
if(celda&AC_ABAJO){
fprintf(arc,"%c%c%c",255,255,255);
}else{
fprintf(arc,"%c%c%c",0,0,0);
}
fprintf(arc,"%c%c%c",0,0,0);
}
}
fclose(arc);
return 0;
}
#include "laberinto.h"

#define M_DERECHA 0x1
#define M_ABAJO 0x2
#define M_SALON 0x4

/*
* Cada celda es reprecentada como un char, donde cada bit tiene un significado
* especial. A continuacion, se especifican el significado de cada bit, desde
* el menos significativo, hasta el mas significativo.
*
* -bit- -significado-
*
* 1º Indica si la celda se conecta hacia la derecha. La mascara esta definida
* como M_DERECHA y es igual a 0x1
*
* 2º Indica si la celda se conecta hacia abajo. La mascara esta definida como
* M_ABAJO y es igual a 0x2
*
* NOTA: Para saber si la celda esta conectada havia arriba o su izquierda,
* devera accederce a la celda superior o izquierda segun corresponda, y
* fijarce si esta conecta a derecha o hacia abajo.
*
* 3º Bit salon, indica que la celda ya fue procesada, y por lo tanto no deve
* volver a ser revisada, ya sea por que es un salon o un laberinto que fue
* creado. Cada algoritmo de creacion de laberintos devera tener encuenta
* este bit de forma especial. Su mascara esta definida como M_SALON y es
* igual a 0x4
*
* 4º El resto de los bits esta libre para uso posterior.
*
*/

int laberinto_inicializar(laberinto *lab, int ancho ,int alto){
int err=0;
if((alto>0) && (ancho>0)){
lab->alto=alto;
lab->ancho=ancho;
lab->celdas=calloc((ancho*alto),sizeof(char));
}else{
err=LABERINTO_ERR_DIMENCION_NEGATIVA;
}
return err;
}

int laberinto_agregar_salon(laberinto *lab, int x0, int y0, int ancho, int alto){
int err=0;
int contx,conty;
int maxx,maxy;
int mascara;
int basey;
if((ancho<=0)||(alto<=0)){
//Si las dimenciones son negativas, genera un error
err=LABERINTO_ERR_DIMENCION_NEGATIVA;
}else if((x0<0)||(y0<0)||((x0+ancho)>=lab->ancho)||((y0+alto)>=lab->alto)){
//Si x0 o y0 son menores que cero,
//o si el salon se sale del rango
//devemos generar un error.
err=LABERINTO_ERR_FUERADERANGO;
}else{
//todo parece estar correcto!
maxx=x0+ancho-1;
maxy=y0+alto-1;
mascara=M_DERECHA|M_ABAJO|M_SALON;
//Para todas las columnas, menos la ultima, seteamos que cada
//celda conecta con su vecino inferior y derecho(a excepcion de
//la ultima de la derecha), y tambien la definimos como un
//salon.
for(conty=y0;conty<maxy;conty++){
basey=conty*(lab->ancho);
for(contx=x0;contx<maxx;contx++){
//para cada una de las celdas de la fila, menos
//la ultima, seteamos la mascara como que es
//accede a sus dos vecinos y es un salon.
lab->celdas[basey+contx]=mascara;
}
lab->celdas[basey+contx]=M_SALON|M_ABAJO;
}
mascara=M_DERECHA|M_SALON;
basey=conty*(lab->ancho);
for(contx=x0;contx<maxx;contx++){
//para cada una de las celdas de la fila, menos
//la ultima, seteamos la mascara como que es
//accede a su vecino derecho y es un salon.
lab->celdas[basey+contx]=mascara;
}
lab->celdas[basey+contx]=M_SALON;
}
return err;
}

char laberinto_accede(laberinto *lab, int x, int y){
int resul,ancho,alto;
char *celda;
ancho=lab->ancho;
alto=lab->alto;
if((x<0)||(y<0)||(ancho<=x)||(alto<=y)){
resul=0;
}else{
celda=&(lab->celdas[y*(ancho)+x]);
resul=(*celda)&(M_DERECHA|M_ABAJO);
if(x>0){
//Recuperamos el valor de la celda que esta a la izquierda.
resul=resul|(((*celda-1)&(M_DERECHA))<<2);
}
if(y>0){
//Recuperamos el valor de la celda que esta por encima.
resul=resul|(((*celda-ancho)&(M_ABAJO))<<2);;
}
}
return resul;
}

char laberinto_agregar_acceso(laberinto *lab, int x, int y, char accesos){
char *celda,*celdaAux;
if((x<0)||(y<0)||(lab->ancho<=x)||(lab->alto<=y)){
//no se puede realizar ninguna accion
}else{
celda=&(lab->celdas[y*(lab->ancho)+x]);
(*celda)=(*celda)|((accesos&AC_SALON)>>4);
if(x<(lab->ancho-1)&&(accesos&AC_DERECHA)){
(*celda)=(*celda)|M_DERECHA;
accesos=accesos&(~AC_DERECHA);
}
if(y<(lab->alto-1)&&(accesos&AC_ABAJO)){
(*celda)=(*celda)|M_ABAJO;
accesos=accesos&(~AC_ABAJO);
}
if((x>0)&&(accesos&AC_IZQUIERDA)){
celdaAux=celda-1;
(*celdaAux)=(*celdaAux)|M_DERECHA;
accesos=accesos&(~AC_IZQUIERDA);
}
if((y>0)&&(accesos&AC_ARRIBA)){
celdaAux=celda-(lab->ancho);
(*celdaAux)=(*celdaAux)|M_ABAJO;
accesos=accesos&(~AC_IZQUIERDA);
}
}
return accesos;
}

int laberinto_crear_westnort(laberinto *lab, int semilla){
int cont=1;
char *celda;
int max;
int ancho,alto;
int posibilidad;
ancho=lab->ancho;
alto=lab->alto;
srand(semilla);
celda=lab->celdas;
max=(alto*ancho);
//Para simplificar el calculo de las celdas del borde derecho, empezamos
//a contar desde 1.
//En primer lugar creamos todas las columnas menos la ultima, para
//simplificar el algoritmo.
while(cont<=max){
if(!((*celda)&M_SALON)){
posibilidad=0;
//chequeo si es posible ir hacia la derecha
if((cont%ancho)&&!((*(celda+1))&M_SALON)){
posibilidad=M_DERECHA;
}
//chequo si puedo bajar
if(((cont+ancho)<=max)&&!((*(celda+ancho))&M_SALON)){
posibilidad=posibilidad|M_ABAJO;
}

//Toma de decicion
if(posibilidad==M_DERECHA){
*celda=(*celda)|M_DERECHA;
}else if(posibilidad==M_ABAJO){
*celda=(*celda)|M_ABAJO;
}else if(posibilidad==(M_ABAJO|M_DERECHA)){
//tomamos un numero al azar, si es impar nos
//vamos nos vamos a la derecha, sino, nos vamos
//hacia abajo.
posibilidad=rand()&0x1;
if(posibilidad){
*celda=(*celda)|M_DERECHA;
}else{
*celda=(*celda)|M_ABAJO;
}
}else{
//No se puede mover hacia ningun lado, llegamos
//a un callejos sin salida. T_T
}
}
cont++;
celda++;
}
return 0;
}
#ifndef LABERINTO_H
/*
* Libreria para crear laberintos, vercion -0.4.6
* Ya me hare cargo de hacer algo util de todas estas horas perdidas.
*/

#define LABERINTO_H

#include <stdlib.h>
#include <stdbool.h>

typedef struct{
int alto;
int ancho;
char *celdas;
//La expicacion de que contienen las celdas, esta en laberinto.c
}laberinto;

//Mascaras para obtener hacia donde se puede acceder desde una celda
#define AC_DERECHA 0x1
#define AC_ABAJO 0x2
#define AC_IZQUIERDA 0x4
#define AC_ARRIBA 0x8
#define AC_SALON 0x10


//Inicializa el laberinto, se espera que el puntero contenta una direccion
//valida, ya que la funcion no chequera el valor de este.
int laberinto_inicializar(laberinto *lab, int ancho ,int alto);

//Agrega un salon al laberinto, para asegurar la correcta conectividad esto
//deveria hacerse antes de correr los algoritmos de creacion de laberinto.
int laberinto_agregar_salon(laberinto *lab, int x0, int y0, int ancho, int alto);

/*
* Devuelte un entero indicando hacia que celdas vecinas tiene acceso la celda
* indicada. Para conocer cada uno de las celdas a las que accede, se hace uso de
* las mascaras AC_DERECHA, AC_ABAJO, AC_IZQUIERDA y AC_ARRIBA.
* Tambien se puede conocer si se trata de un salon, utilizando la mascara
* AC_SALON.
* Queda abierto a agregar mas datos, todos se agruparan en las mascaras AC_*.
* En caso de error, si el valor esta fuera del rango, se devolvera 0, es decir,
* una celda que no puede accedera ningun vecino, ni es salon, o cualquiera de
* las demas propiedades que se definan. El unico caso donde esto no es un error,
* es cuando el laberinto es de 1x1. Si se tratara de un salon, al cual no se le
* agregaron puertas, el resultado seria de 0x10.
*/
char laberinto_accede(laberinto *lab, int x, int y);

/*
* Agrega accesos a la celda indicada. Que direccion tienen los accesos esta
* indicado por la variable accesos, cuyo valor deve crearce utilicando los
* valores de las mascaras AC_*.
* El valor de retorno tendra codificados aquellos accesos que no pudieron ser
* creados, ya sea por que se salen del laberinto, o que se culpla cualquier
* otra condicion. Por ende, si todo es correcto, el resultado sera 0.
* Para permitir una mayor libertad, se permite agregar el valor AC_SALON a una
* celda.
*
* NOTA: Hay que tener en cuenta, que los accesos creados de esta forma no son
* considerados por el argoritmo de creaccion de laberintos, por lo que al
* agregarlos se pueden llegar a crear laberintos no perfectos.
*/
char laberinto_agregar_acceso(laberinto *lab, int x, int y, char accesos);

/*
* Crea un laberinto utilizando el argoritmo de west nort, aunque enrealidad lo
* hace en este/sur.
*
* NOTA: Si dos salones se tocan en sus esquinas, es decir, si se producen
* figuras convexas, este algoritmo no puede asegurar la conectividad.
*
* NOTA2: Otra condicion necesaria para que se cumpla con la conectividad,
* generada por el hecho de que este algoritmo crea caminos que convergen en los
* bordes, es que el borde derecho y el izquierdo, esten libres de salones.
*/
int laberinto_crear_westnort(laberinto *lab,int semilla);

//ERRORES
enum LABERINTO_ERRORES{
//No hay error.
NO_ERROR=0,

//Alguna de las dimenciones (alto, ancho y posiblemente otros) es
//negativa, por lo que el area resultaria en un area negativa.
LABERINTO_ERR_DIMENCION_NEGATIVA,

//Cuando se inten acceder a una celda fuera de rango, se genera un
//error.
LABERINTO_ERR_FUERADERANGO,


//Error generico cuya causa es desconocida
LABERINTO_ERR_INESPERADO
};

#endif
Dado que ya no tengo excusas para no programar, el dia de hoy me pase haciendo solo eso.

Hace unos dias, me encontre con este link www.jamisbuck.org/presentations/rubyconf2011/ que habla sobre algoritmos para crear laberintos perfectos.

En resumen, un laberinto perfecto es uno donde para cada par de puntos dentro de el, solo existe un camino que los conecte, y ademas este siempre existe.

Hice esto para poder ver si podia encontrar una manera eficiente de almacenar el laberinto, ademas de agregarle elementos que nos son propios de los laberintos.

Hasta ahora lo que tengo es lo siguiente:
-Al final almacene cada celda del laberinto como un char, donde los dos ultimos bits (los menos significativos) indican si este tiene una puerta hacia la derecha y/o abajo. Para saber si puede acceder a la izquierda o hacia arriba, hay que acceder a estas celdas y ver si pueden ir hacia abajo o derecha, segun corresponda.
-Lo extra que agrege fueron los salones, espacios grandes sin paredes. Ya saben, habitaciones. Se los puede definir facilmente y los algoritmos de creacion de laberintos deverian funcionar bien apesar de ellos, y darles la vuelta(bajo ciertas condiciones). Para poder identificar estas areas, utilice un bit mas del char, asi que me quedan 5 para uso futuro.
-Por ahora solo hay una funcion para crear el laberinto, lo llame "westnort" pero ahora que chequeo se llama arbol binario, asi que lo corregire mas tarde.

Esta todo programado en C, y tengo que chequar despues un par de cosas para hacerlo mas consistente y rapido.

laberinto.h es el header, laberinto.c es donde estan implementadas las funciones. Todo esta autodocumentado, espero que sirva de algo.
main.c, es un principal rapido que hice, crea un laberinto y crea un archivo de imagen "ppm"(un formato que brilla por su sencilles).

Para aquellos que quieran compilarlo, pero no sepan como hacerlo (yo no sabia como compilar archivos con headers hasta este año T_T), los comandos con el gcc son:
gcc -c laberinto.c
gcc main.c laberinto.o -o test

Espero que a alguien le sirva de algo!
Sugerencias o dudas seran felizmente recividas.

PD: No adjunto el archivo compilado, por que no se que politicas tienen ustedes, pero si quieren lo puedo subir tanto para windows como para linux.

PD2: Mi castellano es horrible, lo se, y creanme que lo lamento yo tambien.

--
El grupo en GoogleGroups: http://groups.google.com/group/ProgJuegos
 
** Usted recibió este mensaje porque es miembro del grupo "Programacion de Juegos" de en Google Groups.