Este EP pode ser feito em dupla.
Wumpus é um jogo interativo que se passa em uma caverna. O jogador conhece apenas a parte da caverna que já percorreu. A caverna é como um labirinto e, nela, há moedas, abismos e um monstro - o Wumpus! O objetivo do jogador é sair vivo da caverna e com o maior número de pontos. Para saber mais detalhes da apresentação e funcionamento do jogo, visite a página do Laboratório Virtual de Inteligência Artificial (o link para o jogo está aqui).
A contagem de pontos no jogo se dá da seguinte forma. Cada moeda vale 1000 pontos e, a cada movimento, o jogador perde 1 ponto. Se o jogador mata o Wumpus, ele ganha 10000 pontos. Se, por outro lado, ele é morto, pelo Wumpus ou por cair em um abismo, ele perde 10000 pontos e o jogo termina. Quando o jogador sai da caverna, ele ganha 1000 pontos e o jogo termina.
O objetivo desse exercício-programa e do próximo não é simular o jogo, mas calcular o melhor limite superior para a pontuação do jogo. Na primeira etapa desse cálculo (EP3), temos a disposição um mapa completo da caverna com a posição das moedas, dos abismos e do Wumpus. Chamaremos de posição interessante toda posição da caverna que é ou a posição de partida, ou uma posição com uma moeda, ou uma posição vizinha ao Wumpus. (Para que o limite superior seja mais razoável, consideraremos que o Wumpus pode ser morto apenas de uma posição vizinha a ele, afinal um jogador que não está simplesmente chutando onde o Wumpus está, tem que passar por uma posição vizinha a ele.)
O EP3 deve produzir a lista de posições interessantes atingíveis a partir da posição de partida e uma matriz indexada por tais posições com a distância (comprimento de um caminho mínimo no labirinto) entre quaisquer duas dessas posições.
O método mais conhecido para o cálculo de distância entre dois pontos numa estrutura finita utiliza uma fila e executa uma busca em largura. Assim, no seu EP, você deve implementar e utilizar a seguinte interface para fila:
void inicializa (int n); /* Inicializa a ED da fila considerando que ela comportará no máximo n elementos. */ int vazia (); /* Devolve 1 se a fila está vazia, 0 em caso contrário. */ void insere (elemento x); /* Insere na fila o elemento x. */ void primeiro (elemento *x); /* Devolve em *x o primeiro elemento da fila. */ void retira (elemento *x); /* Remove o primeiro elemento da fila, devolvendo-o em *x. */
Para que as coisas fiquem bem claras, tenha no seu EP a declaração do tipo t_fila, que deve ser um struct, com campos correspondendo às variáveis necessárias para representar uma fila. O tipo elemento é o tipo dos elementos armazenados na fila.
Uma caverna será descrita por duas matrizes binárias mxn. A primeira matriz indica, para cada posição (i,j), se há ou não parede do lado esquerdo de (i,j). A segunda matriz indica se há ou não parede em cima da posição (i,j). A posição (i,j) de uma destas matrizes contém 0 se há parede e 1 se não há.
Para determinar se há parede do lado direito de uma posição (i,j), basta olhar a posição (i,(j+1)%n) da primeira matriz (lembre-se que o labirinto é circular). Similarmente, para determinar se há parede abaixo da posição (i,j), basta olhar a posição ((i+1)%m,j) da segunda matriz.
Uma terceira matriz de inteiros mxn informa se há, em uma posição arbitrária (i,j), uma moeda ou o Wumpus. Note que abismos podem ser substituídos por paredes extras na caverna, assim os desconsideraremos para o cálculo de um limite superior para a pontuação. Vamos estabelecer que a terceira matriz, digamos, conteúdo, segue a seguinte convenção:
conteúdo[i][j] = 0 se a posição está livre;
1 se há uma moeda nesta posição;
2 se o Wumpus está nesta posição;
3 se há uma moeda e o Wumpus nesta posição.
Lembre-se que a entrada é sempre na posição (0,0) da caverna,
Exemplo:
A caverna
--- - - - - - | m| | |a| --- --- - --- | | | ------- ----- |m |a | | ----------- - | | | | m| - - - --- --- w |m - - - --- --- | m m m | --- - - - - -seria codificada pelas três seguintes matrizes:
esquerda cima conteúdo 0 1 0 0 1 0 0 1 1 1 1 0 0 1 0 0 0 0 0 1 0 1 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0 1 1 1 1 1 0 1 0 2 0 0 1 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 1 1 1 0 0
Note que os abismos foram substituídos por paredes a seu redor.
Na verdade, as três matrizes podem ser codificadas em apenas uma
matriz
A entrada do EP3 pode ser dada de duas maneiras: por um arquivo ou aleatoriamente. O seu programa deve, portanto, perguntar ao usuário se este deseja que os dados sejam lidos de um arquivo ou se deseja que sejam gerados aleatoriamente. Se a opção for leitura de um arquivo, o programa deve pedir que o usuário digite o nome do arquivo de entrada e proceder com a leitura do arquivo. O formato do arquivo deve seguir o seguinte padrão: m e n são dados na primeira linha, depois as três matrizes devem ser dadas, uma depois da outra. Veja aqui o arquivo correspondente ao exemplo acima. Se a opção for geração aleatória, o programa apenas pede ao usuário que digite o valor de m e n e o número de moedas que deve haver na caverna. Internamente, por meio da função rand (veja a explicação abaixo)
Importante: A função srand deve ser chamada uma única vez no seu programa, no início, para inicializar a seqüência de números aleatórios que será usada pelo seu programa.
A função rand devolve um número inteiro aleatório entre 0 e RAND_MAX. Para obter um bit aleatório, use
b = rand()%2;De forma similar, você pode obter coordenadas aleatórias, onde vai colocar as moedas ou o Wumpus.
Aqui você vê qual seria o arquivo de saída produzido a partir dos dados do exemplo. (Os sinais negativos indicam posições vizinhas ao Wumpus, conforme explicado abaixo.)
Além da saída no arquivo, seu EP deve imprimir na tela a caverna, para fins de verificação da saída produzida. A impressão não precisa ser sofistica. Use, por exemplo, o formato usado neste enunciado.
A posição inicial e todas as posições atingíveis a partir dela que contém moedas são chamadas de obrigatórias.
Uma posição interessante (i,j) é supérflua se, ao visitarmos as posições interessantes obrigatórias, necessariamente visitamos a posição (i,j). Por exemplo, a posição (0,1) no exemplo acima é supérflua. Se uma posição vizinha ao Wumpus é supérflua, todas as posições vizinhas ao Wumpus podem ser omitidas da saída.
O seu EP receberá um bônus de até 1.0 ponto se detectar posições supérfluas e omiti-las da saída. (Isso tornará a segunda fase mais rápida.) Quanto mais posições supérfluas você omitir da saída, maior o bônus.
Vai ser importante no EP4 saber quais são as posições interessantes relativas ao Wumpus e que não contém moedas ou são a posição inicial. Para diferenciar estas das demais, imprima a primeira coordenada (ou a segunda, se a primeira for zero) de uma tal posição com sinal negativo, como no exemplo acima.
O conjunto EP3+EP4 mais eficiente e bem feito será incorporado nesse jogo. Para determinar qual o melhor conjunto, organizaremos uma competição entre os EPs. Portanto, caprichem, e quem sabe o seu EP entrará na história do Wumpus!!!
/********************************************************/
/* Fulano de Tal e Beltrano de Tal */
/* Exercicio-Programa xx */
/* Disciplina yy Professor: Ciclano de Tal */
/********************************************************/