O labirinto recorrente

Um garoto se encontra perdido em um labirinto, o qual é compreendido por N matrizes quadráticas de mesmo tamanho. A posição do garoto é definida por valores x e y e, caso o garoto exceda os limites da matriz, ele será teletransportado para uma posição aleatória da próxima matriz. No labirinto, existem paredes (#) que bloqueiam certos passos, perigos (*) que consomem parte de sua vida e trajetórias contendo itens.

As casas que possuem itens são representadas por números positivos. Cada vez que o garoto passa por uma dessas casas, um item é consumido pelo garoto, subtraindo um item da casa atual. Após consumir quatro itens, o garoto ganha uma vida extra e seus itens zeram. O garoto começa o jogo com 10 vidas, sendo este o máximo de vidas que ele pode acumular. As casas que não possuem mais itens ainda podem ser utilizadas, mas sem consumir um item.

O garoto percorrerá as matrizes dando um passo de cada vez de forma aleatória. Ao escolher a direção, o garoto, se possível, irá até a casa definida. Caso exista uma parede na posição definida, está será descartada, e então uma nova direção válida será definida. Os perigos não podem ser evitados, então, se a posição escolhida for um, o garoto o enfrentará e perderá uma vida. a intenção global do problema não é encontrar uma não é encontrar uma saída, mas sim, tentar consumir o máximo possível de itens até chegar a zerar as possibilidades desse tipo ou morrer tentando.

O labirinto é lido do arquivo localizado em ./dataset/input.data, o qual apresentará várias matrizes, todas quadráticas. A primeira linha do arquivo informa, respectivamente, a largura, a altura e a quantidade de matrizes que o arquivo contém. O objetivo do garoto é percorrer as matrizes até que todo o caminho percorrido se torne zero ou que ele venha a morrer devido aos perigos enfrentados. No final é apresentado como resultado:

1. Quantas casas foram percorridas ao todo;
2. Qual a soma de itens consumidos pelo caminho;
3. Quantas casas do labirinto ficaram inexploradas;
4. Total de perigos enfrentados ao decorrer do percurso.

Quanto as paredes, não o garoto irá desviar e continuar a rota. Já os perigos, a cada passada, será subtraída uma vida do total de 10. Assim, ao ficar sem pontos de vida, o algoritmo irá parar e indicar a derrota do garoto.

O garoto andará aleatoriamente nas oito direções, ou ficará parado no mesmo lugar. Quando o garoto fica parado, ele interage com a casa novamente. Ou seja, caso a casa possua um inimigo, o garoto perderá mais uma vida e, se for um item, consumirá mais um item.

⇖	⇑	⇗
⇐	⟳	⇒
⇙	⇓	⇘

A seguir, é mostrado um exemplo de um labirinto de apenas um matriz como entrada. O garoto começará na primeira coluna da primeira linha, e caminhará na diagonal até a última coluna da última linha. Supondo que o garoto comece com 10 vidas, 0 itens, a interação dele com as casas mudará estas estatísticas. A tabela de cima representa a entrada, enquanto a de baixo mostra a saída.

$\colorbox{olive}{2}$	#	*
4	$\colorbox{olive}{*}$	#
#	#	$\colorbox{olive}{0}$

$\colorbox{olive}{1}$	#	*
4	$\colorbox{olive}{*}$	#
#	#	$\colorbox{olive}{0}$

É possível perceber que o garoto consumiu um item na primeira casa, que tinha dois itens e passou a ter apenas um. O garoto ainda enfrentou um perigo no meio da matriz, e chegou a última casa que não tinha nehum item. Com isso, o garoto passou a ter 9 vidas e 1 item no inventário.

Decisões de implementação

Ao contar o número de casas inexploradas, foram consideradas as paredes. Ou seja, caso haja paredes no labirinto, o garoto não conseguirá visitar todas as casas. Caso a casa em que o garoto se encontra não tenha sido somada ao total de casas únicas visitadas, esta é somada e a casa é marcada na matriz booleana como já explorada. No final do programa, é multiplicado a largura pela altura, para então multiplicar pelo número de matrizes e subtrair pelo número de casas visitadas, resultando assim no número de casas inexploradas.

Optou-se por ler as matrizes do arquivo de entrada um por um, pois esta escolha diminui o uso de memória primária do computador. Com isso, é possível utilizar o programa em labirintos com várias martizes, ficando estas armazenadas no próprio arquivo de entrada.

Arquivos

• main.cpp Possui a função int main(), que define o local de início (entry point) do programa e returna o exit code.
• Maze.hpp Arquivo header que define a classe Maze, assim como seus atributos e métodos que será compartilhado entre os arquivos do programa.
• Maze.cpp Possui o corpo do construtor, destrutor e métodos da classe Maze definidos no arquivo Maze.hpp.
• Player.hpp Arquivo header que define a classe Player, assim como seus atributos e métodos que será compartilhado entre os arquivos do programa.
• Player.cpp Possui o corpo do construtor, destrutor e métodos da classe Player definidos no arquivo Player.hpp.

Casos especiais

Conforme discorrido anteriormente, pode ser que o garoto, de acordo com a função que define a sua direção aleatoriamente, fique parado no mesmo lugar. Caso isto ocorra, ele interage novamente com a mesma casa, consumindo um item ou tomando dano, dependendo do que a casa for.

Com isso, o algoritmo considera que o garoto consumiu mais um item ou enfrentou mais um inimigo, porém, não considera que o garoto andou. Por isso, pode ser que ocorra o caso em que o garoto consuma, por exemplo, 25 itens, enfrente 7 inimigos, e tenha percorrido um caminho de apenas 29 casas.

Casos sem tratamento

O programa não verifica se o labirinto possui casas em que o garoto não pode sair. Logo, se for inserida uma matriz com casas isoladas por paredes, o programa terá um comportamento indefinido (provavelmente entrando em um loop infinito.

O algoritmo é altamente dependente da entrada do arquivo input.data. Isto significa que, caso o usuário insira um labirinto válido, no formato pré-determinado, o programa não fará tal verificação, resultando também terá um compotamento indefinido.

Caso o arquivo input.data possua apenas paredes, o programa não aceitará nenhuma posição inicial. Com isso, o programa deverá ser fechado manualmente no terminal, e a entrada deverá ser então corrigida para uma nova entrada válida.

Código-fonte

main.cpp

O arquivo main.cpp possui apenas a função int main. Nela, é feita uma instanciação da classe Maze, para então requerir ao usuário uma posição inicial válida na primeira matriz. Logo, é iniciado o jogo e, caso o programa seja finalizado com sucesso, é retornado zero como exit code.

Maze.hpp e Maze.cpp

Em C++, a biblioteca padrão é uma coleção de classes, funções e variáveis escritas na própria linguagem para facilitar o desenvolvimento de aplicações. O C++ ainda permite utilizar a biblioteca padrão do C, garantindo assim uma ampla gama de possibilidades para criar um programa. No arquivo de cabeçalho Maze.hpp, forma incluídas cinco bibliotecas: fstream, vector, random, limits e unistd.h.

Primeiramente, quando o construtor da classe Maze é invocado, o arquivo input.data é copiado com nome de saída de output.data. Este novo arquivo contém uma matriz booleana de mesmo tamanho das matrizes originais ao lado das próprias matrizes, que informa as casas visitadas. Logicamente, esta matriz começa apenas com zeros, sendo preenchidas com um após o garoto visitá-las.

A classe Maze possui uma instância da classe Player, que representa o garoto. Os caracteres presentes no arquivo serão lidos e armazenados no vector mat. Já as casas visitadas serão armazenadas no vector mat_visited. É válido destacar que o programa lê uma matriz de cada vez e armazena os dados nos vectors até que chegue ao final do arquivo. Caso o labirinto ainda possua itens, ou o garoto tenha pego algum item desde que começou a percorrer o labirinto, o arquivo tmp.data é sobrescrito no lugar de output.data, e este é relido novamente.

O arquivo output.data funciona como entrada, enquanto o tmp.data funciona como saída. O programa lê a matriz do output.data, a utiliza no jogo, e salva as modificações no tmp.data. Por exemplo, assim que o garoto é teletransportado para a próxima matriz, a matriz atual é salvada no tmp.data, e a próxima matriz é carregada do output.data. Isso ocorre até que o programa leia as N matrizes. Quando isso ocorre, o tmp.data se torna o novo output.data, o tmp.data fica em branco para as novas entradas e o programa retorna até o a primeira matriz.

A entrada de posição inicial do garoto, fornecida pelo usuário, é verificada, para que os valores nem passem dos limites da matriz e nem sejam referentes a uma parede. Ainda existe uma verificação do valor do retorno da função cin que garante que a entrada seja válida.

Ao iniciar o programa, o garoto já interage com a primeira casa, tomando dano ou pegando o item desta casa. Esta casa é então marcada como visitada, a fim de verificar a quantidade de casas inexploradas posteriormente. O garoto caminha até que acabe suas vidas, ou ele ganhe, seja por acabar os itens no labirinto, ou por caminhar todas as matrizes sem consumir um item.

A classe Maze ainda possui atributos que definem o tamanho da matriz, a quantidade de matrizes e qual matriz está no vector mat, além de duas streams de arquivo e dois booleanos que informam se o garoto ganhou o jogo e se foi encontrado um item nas matrizes lidas até então.

Métodos da classe Maze

• Maze() Construtor da classe Maze que lê o arquivo input.data, o reescreve com as matrizes booleanas no arquivo output.data, define o tamanho e a quantidade de matrizes e coloca o arquivo output.data como entrada e o tmp.data como saída;
• ~Maze() Destrutor da classe que fecha os arquivos de entrada e saída;
• void open_files(const std::string &in, const std::string &out) Abre os arquivos de entrada e saída de acordo com as strings de entrada;
• write_sizes() Escreve a primeira linha que contém o tamanho e a quantidade de matrizes no arquivo de saída;
• void read(const bool &read_visited = true) Lê uma matriz do arquivo de entrada (possui uma argumento com default=true que define se a matriz de booleanas também deve ser lida);
• void run() Começa o jogo, chamando todas as funções necessárias para executar o jogo de acordo com as regras previamente estabelecidas;
• void action() Faz o garoto interagir com a casa e adiciona esta casa à matriz booleana de casas visitadas;
• void joystick() Define aleatoriamente a casa para a qual o garoto deve se mover, em um loop que continua até que a casa escolhida não seja uma parede;
• void out_of_bounds(const short &move_x, const short &move_y) Verifica se a casa em que o garoto deseja se mover está dentro dos limites da matriz;
• void teleport() Caso a casa não esteja dentro dos limites da matriz, está função é chamada, fazendo com que o garoto se teletransporte para a próxima matriz;
• void write_matrix() A matriz atual é escrita no arquivo de saída;
• void write_file() A matriz atual e as matrizes restantes são escritas no arquivo de saída;
• void rewind() Caso o garoto ultrapasse os limites da última matriz do arquivo de entrada e tenha coletado algum item, esta função volta à primeira matriz atualizada pela última vez que o garoto caminhou nela;
• void random_start() Quando o garoto é teletransportado, esta função é chamada para que o garoto apareça em alguma casa aleatória válida da nova matriz;
• void mat_have_item() Verifica se a matriz atual possui itens;
• bool only_zeros() Verifica se ainda restam itens no labirinto e, caso não hajam, concede a vitória no jogo;
• void print() Imprime a mensagem de fim de jogo, dando informações relativas ao caminhamento do garoto durante o jogo.

Player.hpp e Player.cpp

O arquivo Player.hpp contém o cabeçalho que define a classe Player. Nele, estão os atributos relativos à posição do garoto, número de vidas, itens na mochila, distância percorrida, total de itens consumidos, casas únicas visitadas, perigos enfrentados e dois booleanos que informam se o garoto pegou algum item na rodada e se ele excedeu os limites da matriz atual.

Métodos da classe Player

• Player() Construtor da classe Player que o instancia com valores padrão;
• void action(char &item) Faz com que o garoto interaja com a casa em que ele se encontra;
• bool is_alive() Retorna verdadeiro se o garoto ainda estiver vivo.

Exemplo

Foi realizada um teste com um arquivo de entrada input.data com duas matrizes quadráticas de tamanho três, a fim de demonstrar a execução do programa.

2	1	#
4	4	4
3	5	#

#	#	2
3	5	#
*	3	5

Após compilar e executar o programa, este requere ao usuário um ponto de início para o garoto. Foi escolhida a primeira coluna da primeira matriz. A partir disso, o programa faz com que o garoto ande até que, ou suas vidas acabem, ou ele percorra o labirinto sem pegar um item, ou acabe os itens no labirinto. A seguir é mostrado as matrizes do arquivo de saída output.data.

0	0	#
4	0	0
0	2	#

#	#	0
0	0	#
*	0	3

Ao lado da saída das matrizes de entrada, ainda são geradas matrizes de booleanos que informam por quais casas o garoto passou.

1	1	0
0	1	1
1	1	0

0	0	1
1	1	0
1	1	1

Neste exemplo, o garoto percourreu um total de 49 casas, consumiu 32 itens, deixou de explorar 6 casas e enfrentou 3 perigos.

O exemplo aqui exposto foi compilado com o GNU Compiler Collection (gcc) versão 4:11.2.0-1ubuntu1, no sistema operacional Ubuntu 22.04.2 LTS (Jammy Jellyfish). O computador possuia uma placa-mãe ASUS AM1M-A/BR, 8 GB de memória RAM DDR3 e um processador AMD Athlon 5150 (arquitetura x86_64).

Conclusão

Pode-se afirmar que a código cumpriu com o que foi proposto na atividade, criando um jogo em que o player se move de forma aleatória no labirinto. A execução do programa ocorreu conforme esperado, como foi possível verificar no exemplo citado.

Dessa forma, é possível afirmar que a utilização de classes para representar o garoto e o labirinto mostrou-se eficiente, uma vez que a agregação, formada pelo objeto filho (Player) em conjunto com o objeto pai (Maze), constitui uma maneira útil de realizar a lógica do programa.

Ainda existem alguns pontos de possível melhora no programa, como a verificação das exceções vistas nos casos sem tratamento. Portanto, uma revisão do programa o tornaria ainda melhor, pois, nestas atuais condições, o usuário poderá comprometer a execução do programa, dependendo do que este colocar como entrada no input.data.

Compilação e Execução

O algoritmo do labirinto decorrente disponibilizado possui um arquivo Makefile que realiza todo o procedimento de compilação e execução. Para tanto, temos as seguintes diretrizes de execução:

Comando	Função
make clean	Apaga a última compilação realizada contida na pasta build
make	Executa a compilação do programa utilizando o gcc, e o resultado vai para a pasta build
make run	Executa o programa da pasta build após a realização da compilação

Contato

✉️ [email protected]