[C++] Labirinto random con forzatura di una via di uscita

[AntoKr]

salve a tutti.. sto creando un labirinto "random".. cioè, che ad ogni esecuzione, lo schema del labirinto stesso cambia... sono riuscito a fare lo schema random, ma c'è un problema.. come faccio ad ASSICURARE SOLO (O ALMENO) UNA VIA D USCITA (partendo dall entrata) dal labirinto? non riesco ad implementare un algoritmo adatto... qualcuno ha qualche idea?

[Alex'87]

Il labirinto su che struttura dati si appoggia? Un grafo?

[AntoKr]

su una matrice char... ho usato alcuni caratteri della tabella ascii estesa per creare i muri.. ma il mio problema è quello... devo assicurare almeno una via d uscita per il labirinto....

[AntoKr]

ecco come risulta la matrice...



Uploaded with ImageShack.usquello che mi serve ora, è assicurare almeno un percorso calpestabile tra la E(in alto a sx) e la U(in basso a dx)... se volete posso anche postare il codice scritto fino ad ora....

[AntoKr]

nessuno?

[Celebron]

beh se la tua necessità prevede solo di creare una via di uscita, semplicemente prima di costruire il resto del labirinto esegui una funzione che, tramite movimenti random, crea un percorso che non potrà mai essere occupato da muri
quindi tutte le posizioni del "bordo" tranne quella da cui sei partito e quella in cui sei arrivato diventano per forza muri (Assicuri l'unicità della via ingresso/uscita)
quindi esegui il tuo algoritmo che costruisce tutto il resto del labirinto (dovrai perciò implementare un modo per far si che questo algoritmo non vada a occupare con dei muri il percorso creato prima)

[Rayan94]

bhe se posti il codice forse qualcosa possimo fare...

[AntoKr]

sto cercando di implementare la funzione che mi ha suggerito Celebron... ma sto incontrando delle difficoltà.. cmq per ora il codice che ho scritto per creare lo schema è questo:

void disegnaschema(char x[][dim])
{
int s=0;
srand(time(0));
for(int i=0; i<dim; i++)
for(int j=0; j<dim; j++)
{
if(i==0)
{
if(j==0)
x[i][j]=201; //ANGOLO SUPERIORE SX
else if(j==dim-1)
x[i][j]=187; //ANGOLO SUPERIORE DX
else
x[i][j]=205; //MARGINE SUPERIORE
}
else if(i==dim-1)
{
if(j==0)
x[i][j]=200; //ANGOLO INFERIORE SX
else if(j==dim-1)
x[i][j]=188; //ANGOLO INFERIORE DX
else
x[i][j]=205; //MARGINE INFERIORE
}
else
{
if(i==1 && j==0)
x[i][j]='E'; //ASSEGNA ENTRATA
else if(i==dim-2 && j==dim-1)
x[i][j]='U'; //ASSEGNA USCITA
else if(j==0 || j==dim-1)
x[i][j]=186; //MARGINI LATERALI
else
{
s=rand()%2;
if(s==0 && x[i][j]!=' ')
x[i][j]=' ';
else if(s==1 && x[i][j]!=' ')
x[i][j]=186;
}
}
}
}

scusate se le righe non sono ben tabulate, ma copiando e incollando, le tabulazioni sono andate perse...

[AntoKr]

ho risolto tutto, cn una bella funzioncina grazie lostesso.. saluti

[Alex'87]

Originariamente inviato da AntoKr
scusate se le righe non sono ben tabulate, ma copiando e incollando, le tabulazioni sono andate perse...

Magia!

void disegnaschema(char x[][dim])
{
int s=0;
srand(time(0));
for(int i=0; i<dim; i++)
	for(int j=0; j<dim; j++)
			{
			if(i==0)
				{
				if(j==0)
					x[i][j]=201;					//ANGOLO SUPERIORE SX
				else if(j==dim-1)
					x[i][j]=187;					//ANGOLO SUPERIORE DX
				else
					x[i][j]=205;					//MARGINE SUPERIORE
				}
			else if(i==dim-1)
				{
				if(j==0)
					x[i][j]=200;					//ANGOLO INFERIORE SX
				else if(j==dim-1)
					x[i][j]=188;					//ANGOLO INFERIORE DX
				else
					x[i][j]=205;					//MARGINE INFERIORE
				}
			else
				{
				if(i==1 && j==0)
					x[i][j]='E';					//ASSEGNA ENTRATA
				else if(i==dim-2 && j==dim-1)
					x[i][j]='U';				    //ASSEGNA USCITA
				else if(j==0 || j==dim-1)
					x[i][j]=186;					//MARGINI LATERALI
				else
					{
					s=rand()%2;
					if(s==0 && x[i][j]!=' ')
						x[i][j]=' ';
					else if(s==1 && x[i][j]!=' ')
						x[i][j]=186;
					}
				}
			}
}