Geração aleatória de labirintos. Escreva uma função mazeGenerator que use um array de 12 por 12 caracteres de duplo subscrito como argumento e que produza um labirinto aleatoriamente. A função também deverá fornecer os locais em que o labirinto começa e termina. Experimente sua função mazeTraverse a partir do Exercício 7.22 usando diversos labirintos gerados aleatoriamente.

Passo 1

Neste exercício, vamos escrever uma função que receberá um array de 1212 por 1212 caracteres com subscrito duplo como argumento e gerará um labirinto aleatório.

Juntamente com a matriz de caracteres, a função terá três ponteiros int. Os dois primeiros serão usados para informar a localização atual no labirinto e o terceiro será usado para armazenar a localização da saída.

Começaremos incluindo as bibliotecas que precisaremos e definindo quatro macros. Eles serão nomeados UP, LEFT, DOWN e RIGHT e armazenarão os números de 00 a 33.

Também escreveremos o protótipo da função. A função será denominada generateMaze() e é uma função recursiva.

#include "stdio.h"

#include "stdlib.h"

#include "time.h"

#define UP 0

#define LEFT 1

#define DOWN 2

#define RIGHT 3

void generateMaze(char maze[][12], int* x, int* y, int* end);

Na função main(), definiremos os arrays necessários para armazenar o labirinto e as localizações do início e da saída. Os valores dos elementos dos arrays start e exit serão inicializados com -1−1, para indicar a função que deve gerar esses valores aleatoriamente.

Também inicializaremos os elementos da matriz do labirinto com o caractere '#', que representa as paredes do labirinto.

Passaremos esses valores como argumentos para a função generateMaze(). Vamos passá-los como referência. Dessa forma, poderemos retornar todos os dados da função.

Após a chamada para a função generateMaze(), o conteúdo dos três arrays será exibido, representando o local inicial, o local de saída e o labirinto.

Passo 2

int main()

{

char maze[12][12];

int start[2] = { -1, -1 };

int exit[2] = { -1, -1 };

srand(time(NULL));

for (int i = 0; i

for (int j = 0; j

maze[i][j] = '#';

}

}

generateMaze(maze, &start[0], &start[1], exit);

printf("Start: (%d, %d)\n", start[0], start[1]);

printf("Exit: (%d, %d)\n\n", exit[0], exit[1]);

for (int i = 0; i

for (int j = 0; j

printf("%c ", maze[i][j]);

}

printf("\n");

}

printf("\n");

}

A função generateMaze()

Esta é a função que será usada para gerar um labirinto. Ele fará isso fazendo chamadas recursivas, passando valores diferentes como a localização atual, que é representada com parâmetros de ponteiro inteiro x e y.

Na primeira chamada da função, os valores dos locais inicial e de saída serão -1−1. Este será um indicador para a função de que ela deve gerar valores aleatórios para representar esses locais. O local de partida será sempre do lado esquerdo do labirinto e a saída do lado direito.

Depois que esses valores forem gerados, definiremos os elementos do labirinto nesses locais para o '.' personagem.

Os valores gerados na primeira chamada serão devolvidos à função main() e serão passados ​​em cada chamada recursiva.

void generateMaze(char maze[][12], int* x, int* y, int* exit)

{

if (exit[0] == -1 && exit[1] == -1 && *x == -1 && *y == -1) {

*x = rand() % 10 + 1;

*y = 0;

exit[0] = rand() % 10 + 1;

exit[1] = 11;

maze[*x][*y] = '.';

maze[exit[0]][exit[1]] = '.';

}

Agora definimos o local de início e de saída.

Se esta não for a primeira chamada para a função, xey apontarão para valores inteiros aleatórios entre 00 e 1111. Se esses valores não estiverem representando um local de borda na matriz do labirinto, definiremos o elemento atual como a '.' personagem. Isso deve ser verificado para que não tenhamos mais de uma saída do labirinto.

if(*x != 11 && *y != 11 && *x != 0 && *y != 0)

maze[*x][*y] = '.';

Passo 3

Em seguida, definiremos um array int chamado randomDirection. Essa matriz armazenará as quatro direções possíveis para as quais definimos macros. Usaremos um loop for simples para embaralhar aleatoriamente essas direções dentro desse array. Isso contribuirá para a aleatoriedade do labirinto.

int randomDirections[4] = { UP, DOWN, RIGHT, LEFT };

for (int i = 0; i

int random = rand() % 4;

int tmp = randomDirections[i];

randomDirections[i] = randomDirections[random];

randomDirections[random] = tmp;

}

Para cada posição no labirinto a que chegamos, ou seja, para cada chamada à função, verificaremos se é possível se mover em cada uma das direções.

Começaremos inicializando as variáveis ​​inteiras offsetX e offsetY como 00. Logo em seguida, definiremos uma delas para 11 ou -1−1. Esses dois valores representarão o deslocamento da localização atual se formos na direção atual.

Logo em seguida, usaremos essas duas variáveis ​​inteiras para definir duas novas variáveis ​​inteiras x2 e y2 para seus valores. Essas duas variáveis ​​representarão a localização da posição que está a dois passos da localização atual, na direção atual (adicionamos 2∗offsetX e 2∗offsetY valores para as variáveis ​​xey).

for (int i = 0; i

int offsetX = 0, offsetY = 0;

switch (randomDirections[i]) {

case UP:

offsetY = -1; break;

case LEFT:

offsetX = -1; break;

case DOWN:

offsetY = 1; break;

case RIGHT:

offsetX = 1; break;

}

int x2 = *x + 2 * offsetX;

int y2 = *y + 2 * offsetY;

Ao final de cada iteração, para cada direção, verificaremos se a localização a dois lugares da posição atual está dentro dos limites da matriz do labirinto.

Se for, vamos verificar se a parede '#' está nesse local ou talvez seja a saída do labirinto.

Se isso também for verdade, faremos uma verificação final para garantir que não seja um local de fronteira.

Se todas essas três condições forem verdadeiras, definiremos o local que está a um passo da posição atual para o '.' caractere, representando um caminho. Logo em seguida, faremos uma chamada recursiva para a função generateMaze() passando a posição do local a dois passos da posição atual.

if (x2 >= 0 && x2 = 0 && y2

if (maze[x2][y2] == '#' || (x2 == exit[0] && y2 == exit[1]))

{

if (*x + offsetX != 11 && *y + offsetY != 11

&& *x + offsetX != 0 && *y + offsetY != 0) {

maze[*x + offsetX][*y + offsetY] = '.';

generateMaze(maze, &x2, &y2, exit);

}

}

}

}

}

Resposta

#include "stdio.h"

#include "stdlib.h"

#include "time.h"

#define UP 0

#define LEFT 1

#define DOWN 2

#define RIGHT 3

void generateMaze(char maze[][12], int* x, int* y, int* end);

int main()

{

char maze[12][12];

int start[2] = { -1, -1 };

int exit[2] = { -1, -1 };

srand(time(NULL));

for (int i = 0; i

for (int j = 0; j

maze[i][j] = '#';

}

}

generateMaze(maze, &start[0], &start[1], exit);

printf("Start: (%d, %d)\n", start[0], start[1]);

printf("Exit: (%d, %d)\n\n", exit[0], exit[1]);

for (int i = 0; i

for (int j = 0; j

printf("%c ", maze[i][j]);

}

printf("\n");

}

printf("\n");

}

void generateMaze(char maze[][12], int* x, int* y, int* exit)

{

if (exit[0] == -1 && exit[1] == -1 && *x == -1 && *y == -1) {

*x = rand() % 10 + 1;

*y = 0;

exit[0] = rand() % 10 + 1;

exit[1] = 11;

maze[*x][*y] = '.';

maze[exit[0]][exit[1]] = '.';

}

if(*x != 11 && *y != 11 && *x != 0 && *y != 0)

maze[*x][*y] = '.';

int randomDirections[4] = { UP, DOWN, RIGHT, LEFT };

for (int i = 0; i

int random = rand() % 4;

int tmp = randomDirections[i];

randomDirections[i] = randomDirections[random];

randomDirections[random] = tmp;

}

for (int i = 0; i

int offsetX = 0, offsetY = 0;

switch (randomDirections[i]) {

case UP:

offsetY = -1; break;

case LEFT:

offsetX = -1; break;

case DOWN:

offsetY = 1; break;

case RIGHT:

offsetX = 1; break;

}

int x2 = *x + 2 * offsetX;

int y2 = *y + 2 * offsetY;

if (x2 >= 0 && x2 = 0 && y2

if (maze[x2][y2] == '#' || (x2 == exit[0] && y2 == exit[1]))

{

if (*x + offsetX != 11 && *y + offsetY != 11

&& *x + offsetX != 0 && *y + offsetY != 0) {

maze[*x + offsetX][*y + offsetY] = '.';

generateMaze(maze, &x2, &y2, exit);

}

}

}

}

}