João Araujo
Dr. en Informatique, Université de Versailles, França.

O Mundo de Darwin

Darwin Em 2009 comemoramos os 150 anos do livro A Origem das Espécies, de Charles Darwin, assim como os 200 anos do nascimento de seu autor. Nada mais justo que, em homenagem a este grande cientista, façamos um simulador da vida na Terra… Bom, não precisamente de TODA a vida na Terra… Mas poderemos brincar um pouco de criar algumas criaturas e vê-las interagir num mundo simulado. Seremos deuses de pequenas criaturas de bits… Para isso, faremos algumas simplificações:

Nossa simulação roda num planeta imaginário chamado… Darwin. Este planeta é um mundo bidimensional, dividido em pequenos quadrados com uma população de “criaturas”. Cada criatura vive em um dos quadrados e olha para uma das direções cardeais (Norte, Sul, Leste e Oeste) e pertence a uma “espécie”, que determina o comportamento da criatura. Por exemplo, um mundo possível seria o seguinte:

O mundo mostrado tem uma população de 20 criaturas, 10 da espécie chamada “Vênus papa-moscas” e 10 da espécie Roedor. Em cada caso, a criatura é identificada com a primeira letra do nome. A orientação é indicada pela forma da figura que tem dois pontos para onde a criatura olha. O comportamento de cada criatura, que pode ser pensada como um robô, é controlada por um programa que é particular para cada espécie. Desta forma, Roedores se comportam da mesma maneira, assim como as Vênus Papa-moscas, mas o comportamento de cada espécie é diferente das outras.

O desenrolar da simulação dá a cada criatura sua vez de executar seu comportamento. Na sua vez, a criatura executa um pequeno programa em que ela pode olhar a sua frente e tomar alguma atitude. As possíveis ações são mover-se para frente, virar para esquerda ou direita ou infectar alguma outra criatura que esteja no quadrado imediatamente à sua frente, o que transforma a criatura infectada em uma criatura da espécie infectante. Assim que uma dessas ações seja executada, a vez da criatura termina e outra criatura tem a vez. Quando todas as criaturas tenham tido sua vez, o processo inicia de novo e cada criatura tem uma segunda vez para executar seu comportamento. O objetivo de cada espécie é infectar tantas outras criaturas quanto possível e assim aumentar a população de sua própria espécie.

Programação da Espécie

Para saber o que fazer em sua vez, a criatura executa algumas instruções de um programa específico para sua espécie. Por exemplo, o programa para a Vênus Papa-moscas poderia ser:

passo instrução comentário
1 SeInimigo 4 Se existe um inimigo à frente, vá para o passo 4
2 esquerda Vire para esquerda
3 VaPara 1 Vá para o passo 1
4 infecte Infecte a criatura à frente
5 VaPara 1 Vá para o passo 1

Os números dos passos não fazem parte do programa, mas foram incluídos para facilitar o entendimento do programa. Na sua vez, A Vênus Papa-moscas confere se está em face com uma criatura inimiga no quadrado adjacente. Se está, o programa pula para o passo 4 e infecta a pobre criatura. Se não, o programa vai para o passo 2 no qual ela simplesmente vira para esquerda. Nos dois casos, a instrução seguinte é um VaPara que faz o programa reiniciar. Os programas são executados começando pela instrução do passo 1 e continua normalmente com cada nova instrução na sequência, embora esta ordem possa ser mudada por certas instruções do programa. Cada criatura é responsável por lembrar o número do próximo passo a ser executado.

Instruções do mundo Darwin

frente a criatura avança, desde que o quadrado à frente esteja vazio. Se ir para frente põe a criatura fora dos limites do mundo ou provoque que ele suba em cima de outra criatura, a instrução frente não faz nada.
esquerda Vira a criatura 90 graus à esquerda
direita Vira a criatura 90 graus à direita
infecta n Se o quadrado imediatamente na frente da criatura está ocupado por uma criatura de espécie diferente (um inimigo), esta criatura é infectada e se torna uma criatura da espécie infectante. Quando uma criatura é infectada, ela mantém sua posição e orientação, porém muda seu indicador interno de espécie e vai iniciar executando o mesmo programa da espécie infectante, começando pelo passo n. O parâmetro n é opcional. Se não for apresentado, a nova criatura começa do passo 1 do seu novo programa. Desta forma, a instrução infecta sem parâmetro é equivalente a infecta 1.
SeVazio n Se o quadrado na frente da criatura está desocupado, vá pra o passo n. Se não, executa a próxima instrução.
SeBorda n Se a criatura está no limite do mundo, vá para o passo n, senão, execute a próxima instrução.
SeIgual n Se o quadrado que a criatura está olhando é ocupado por uma criatura de mesma espécie, vá para passo n, senão, execute a próxima instrução.
SeInimigo Se o quadrado que a criatura está olhando é ocupado por uma criatura de outra espécie, vá para passo n, senão, execute a próxima instrução.
SeAleatorioPara tentar simular o livre arbítrio, esta instrução vai para a instrução n metade do tempo e executa a próxima instrução a outra metade.
VaPara n Esta instrução sempre vai para o passo n, independente de qualquer condição.

Uma criatura pode executar qualquer número de instruções se… ou “VaPara” sem ceder sua vez. A vez termina somente quando o programa executa uma instrução frente,esquerda, direita ou infecte. Nas vezes subequentes, o programa inicia do ponto onde parou da última vez.

O programa para cada espécie é guardado em um arquivo no subdiretório Criaturas. Cada arquivo neste diretório consiste do nome da espécie, seguido pelos passos do programa da espécie. O programa termina com o fim do arquivo, ou uma linha em branco. Comentários podem aparecer após uma linha em branco. O programa para a vênus papa-moscas poderia ser:

Programa Vênus Papa-moscas

VenusPapaMoscas
SeInimigo 4
esquerda
VaPara 1
infecte
VaPara 1

A Vênus Papa-Moscas fica parada em um lugar e gira. Ela infecta quanquer coisa que esteja na sua frente.

Criaturas Pré-estabelecidas

Existem diversas criaturas pré-estabelecidas:

Comida Esta criatura gira num quadrado, mas nunca infecta. Seu único propósito é servir como alimento para outras criaturas.
Saltador Esta criatura apenas se dirige para frente até encontrar uma parede. Não é uma criatura interessante, mas serve para testar se o programa está funcionando.
VenusPapaMoscas Esta criatura gira num quadrado, infectando qualquer inimigo que veja.
Roedor Esta criatura anda em linhas retas até ser bloqueada, infectando qualquer criatura que veja. Se ele não pode se mover, ele gira 90 graus.

Você pode criar suas próprias criaturas.

Trabalho

Sua tarefa é escrever o simulador Darwin e fazê-lo funcionar. O trabalho é individual com arguição oral. O programa é grande o suficiente para ser dividido em 6 módulos separados que trabalham juntos para resolver o problema.

Os módulos

darwin

Este módulo contém o programa principal, que é responsável pelo estabelecimento do mundo, populando-o com as criaturas e executando o loop principal da simulação que dá a cada criatura sua vez de executar. Os detalhes destas operações são geralmente executadas por outros módulos. Criaturas novas devem ser criadas em quadrados vazios escolhidos aleatoriamente, olhando para direções também aleatórias.

criatura

Este módulo define um tipo abstrato de dados que representa uma criatura individual, assim como funções para criar novas criaturas e para usar a sua vez.

especies

Este módulos define um tipo abstrato de dados que representa espécies, e fornece operações para ler a descrição das espécies de um arquivo e para trabalhar com os programas que a criatura executa.

mundo

Este módulo contém uma abstração de um mundo bidimensional em que serão colocadas as criaturas.

Os dois módulos seguintes são fornecidos

geometria

Este módulo define os tipos que representam os pontos e as direções.

mapamundi

Este módulo fornece uma visão gráfica do mundo (pode ser feito usando apenas o console).

Constantes

Constantes

Na sua implementação, você deve usar as seguintes constantes para controlar a operação do seu programa:
/* 
 * Constants 
 * --------- 
 * Nlinhas		Número de linhas no mundo Darwin 
 * NColunas         	Número de colunas 
 * MaxEspecies       	Número máximo de diferentes espécies 
 * MaxCriaturas     	Número máximo de criaturas individuais 
 * MaxPrograma         Tamanho máximo do programa da criatura(em linhas) 
 * ContagemInicial      Número inicial de criaturas por espécie. 
 
 */ 
#define  Nlinhas           15 
#define  NColunas        15 
#define  MaxEspecies      10 
#define  MaxCriaturas   100 
#define  MaxPrograma     250 
#define  ContagemInicial    10

Obs: Estas constantes não devem aparecer no mesmo arquivo-fonte, sendo portanto sua tarefa determinar a qual módulo cada uma pertence.

Arquivos h

Aqui são apresentados os arquivos .h que devem ser utilizados:

Arquivo: geometria.h

tipos novos para uma grade x-y
Este módulo fornece dois tipos de baixo nível (pontoT e direcaoT), que são usados em diversos dos outros módulos.

geometria.h

/* 
 * Arquivo: geometria.h 
 * ---------------- 
 * Esta interface fornece alguns tipos extremamente simples 
 * e operações que são úteis para a manipulação dos pontos 
 * numa grade x-y 
 */ 
#ifndef _geometria_h 
#define _geometria_h 
 
/* 
 * Tipo: pontoT 
 * ------------ 
 * O tipo pontoT é usado para encapsular um par de coordenadas 
 * em um único valor. 
 */ 
typedef struct { 
    int x, y; 
} pontoT; 
/* 
 * Tipo: direcaoT 
 * ---------------- 
 * Este tipo é um exemplo de uma “enumeração” em C. Os 
 * valores do tipo enumeração são simplesmente constantes listadas entre 
 * chaves após a palavra reservada enum. Desta forma, uma variável 
 * do tipo direcaoT pode assumir um dos 4 valores Norte, Leste, 
 * Sul e Oeste. 
 */ 
typedef enum { Norte, Leste, Sul, Oeste} direcaoT; 
/* 
 * Função: CriaPonto
 * Uso: pt = CriaPonto(x, y); 
 * ------------------------------ 
 * Esta função combina as coordenadas x e y em uma estrutura
 *  pontoT e retornar este valor. 
 */ 
pontoT CriaPonto(int x, int y); 
/* 
 * Função: PontoAdjacente 
 * Uso: novopt = PontoAdjacente(pt, dir); 
 * -------------------------------------- 
 * Esta função retorna o pontoT que resulta do movimento de um 
 * quadrado na direção indicada de pt. 
 */ 
pontoT PontoAdjacente(pontoT pt, direcaoT dir); 
/* 
 * Funções: VirarParaEsquerda, VirarParaDireita 
 * Uso: novadir = VirarParaEsquerda(dir); 
 *        novadir = VirarParaDireita(dir); 
 * ------------------------------- 
 * Estas funções retornam as direções que resultam do ato de virar
 * para esquerda ou para direita a partir de uma direção incial. 
 */ 
direcaoT VirarParaEsquerda(direcaoT dir); 
direcaoT VirarParaDireita(direcaoT dir); 
#endif

Arquivo: mundo.h

Abstração que representa a grade x-y.

Este módulo inclui as funções necessárias para acompanhar a posição das criaturas no mundo bidimensional. Para termos uma padronização das soluções, a interface adota as seguintes normas:
1.O mundo é implementado como um tipo abstrato de dados.
2.O conteúdo de objetos não específicados é representado por ponteiro void *
3. As dimensões do vetor do mundo são especificados pelo cliente e deve ser alocado dinamicamente.

Este design implica que a estrutura interna é, ao menos em parte, um array bidimensional de ponteiros para void. Você deve ser cuidadoso em como você pode implementar e iniciar tal array em C.

mundo.h

/* 
 * File: mundo.h 
 * ------------- 
 * Esta interface define uma abstração que pode ser usada 
 * para armazenar objetos em um mundo cartesiano x/y. Esta abstração 
 * é completamente independente do display gráfico e o cliente 
 * é responsável por qualquer atualização da tela que seja necessária. 
 */ 
#ifndef _mundo_h 
#define _mundo_h 
#include "geometria.h" 
/* 
 * Tipo: mundoTAD 
 * -------------- 
 * Este tipo abstrato armazena os dados de um mundo que é definido 
 * como uma grade bidimensional capaz de armazenar 
 * objetos arbitrários representados como ponteiros, cujo tipo é 
 * compreendido apenas pelo cliente. 
 */ 
typedef struct worldCDT *mundoTAD; 
/* 
 * Função: NovoMundo
 * Uso: mundo = NovoMundo(comprimento, altura); 
 * --------------------------------------- 
 * Esta função cria um novo mundo que consiste de comprimento 
 * colunas e altura linhas, cada uma das quais numeradas a partir de zero. 
 * Um mundo recém criado não possui nenhum objeto. 
 */ 
mundoTAD NovoMundo(int comprimento, int altura); 
/* 
 * Função: LiberaMundo 
 * Uso: LiberaMundo (mundo); 
 * ------------------------ 
 * Esta função libera todo armazenamento associado com um mundo. 
 */ 
void LiberaMundo ( mundoTAD mundo); 
/* 
 * Funções: ComprimentoMundo, AlturaMundo
 * Uso: comprimento = ComprimentoMundo(mundo); 
 *        altura = AlturaMundo(mundo); 
 * ----------------------------------- 
 * Esdtas funções retornam o comprimento e a altura de um mundo, 
 * respectivamente. 
 */ 
int ComprimentoMundo( mundoTAD mundo); 
int AlturaMundo( mundoTAD mundo); 
/* 
 * Função: Dentro 
 * Uso: if (Dentro(mundo, pt)) . . . 
 * ------------------------------------ 
 * Esta função retorna  1 se o ponto especificado 
 * está dentro dos limites do mundo . 
 */ 
int Dentro( mundoTAD mundo, pontoT pt); 
/* 
 * Função: FixaConteudo 
 * Uso: FixaConteudo(mundo, pt, obj); 
 * ----------------------------------- 
 * Esta função coloca o objeto no mundo 
 * na posição indicada por pt. 
 */ 
void FixaConteudo( mundoTAD mundo, pontoT pt, void *obj); 
/* 
 * Função: ObtemConteudo 
 * Uso: obj = ObtemConteudo (mundo, pt); 
 * ------------------------------------ 
 * Esta função retorna o objeto atualmente no mundo 
 * na posição pt. 
 */ 
void *ObtemConteudo( mundoTAD mundo, pontoT pt); 
 
#endif

Arquivo: especies.h

Abstração para representar cada espécie de criatura.

As criaturas individuais no mundo são representativas de algumas classes de espécies e compartilham características comuns, tais como nome da espécie e o programa que executam. Em vez de copiar esta informação para cada criatura, este dado pode ser gravado uma vez como parte da descrição da espécie e então cada criatura pode simplesmente incluir o ponteiro apropriado para a espécie como parte de sua estrutura interna de dados.

Para encapsular todas as operações de uma espécie dentro de uma abstração, esta interface exporta a função LerEspecies, cuja tarefa é ler um arquivo contendo o nome de uma criatura e seu programa, como descrito anteriormente. Para fazer a estrutura de diretórios mais fácil de ser manuseada, o arquivo de espécies para cada criatura é armazenado num diretório de nome Criaturas. Para abrir um arquivo num subdiretório, você necessita concatenar a string “Criaturas/” com o início do nome do arquivo antes de chamar fopen (cap 7 do livro-texto).

especies.h

/* 
 * File: especies.h 
 * --------------- 
 * Esta interface define a abstração especies. 
 */ 
#ifndef _especies_h 
#define _especies_h 
 
/* 
 * Type: especiesTAD 
 * ---------------- 
 * Este é o tipo abstrato de dados para as espécies. 
 */ 
typedef struct especiesCDT *especiesTAD; 
/* 
 * Tipo: opcodeT 
 * ------------- 
 * O tipo opcodeT é uma enumeração dos comandos válidos .
 */ 
typedef enum { 
    frente, esquerda, direita, infecta, 
    SeVazio, SeBorda, SeIgual, SeInimigo, SeAleatorio, 
    VaPara 
} opcodeT; 
 
 
/* 
 * Tipo: instrucaoT 
 * ------------------ 
 * O tipo instrucaoT é usado para representar uma instrução 
 * e consiste de um par de um código de operação e um inteiro. 
 */ 
typedef struct { 
    opcodeT op; 
    int endereco; 
} instrucaoT; 
 
/* 
 * Função: LerEspecies 
 * Uso: especies = LerEspecies(nomearquivo); 
 * --------------------------------------- 
 * Esta função lê para uma nova espécie a partir de um arquivo específico. 
 * Para encontrar o arquivo, a função procura em um subdiretório denominado 
 * "Criaturas". Se não existe um arquivo com o nome indicado 
 * naquele subdiretório, a função retorna NULL. 
 */ 
especiesTAD LerEspecies(string nomearquivo); 
/* 
 * Função: NomeEspecies 
 * Uso: nome = NomeEspecies(especies); 
 * ----------------------------------- 
 * Esta função retorna o nome de uma espécie existente. 
 */ 
char * NomeEspecies(especiesTAD especies); 
/* 
 * Função: TamanhoPrograma 
 * Uso: nPassos = TamanhoPrograma(especies); 
 * ------------------------------------- 
 * Esta função retorna o número de instruções no programa 
 * para aquela espécie. 
 */ 
int TamanhoPrograma(especiesTAD especies); 
/* 
 * Função: PassoPrograma 
 * Uso: comando = PassoPrograma(especies, k); 
 * ------------------------------------------- 
 * Esta função retorna a  k-ésima instrução no programa para 
 * aquela espécie, sendo os passos numerados no início a partir de 1. 
 * Atente que selecionar uma instrução fora da faixa do programa 
 * gera um erro. 
 */ 
instrucaoT PassoPrograma(especiesTAD especies, int k); 
 
#endif

Arquivo: criatura.h

Abstração para representar uma criatura individual.

Criaturas também são representadas como um tipo abstrato de dados, que é definido por criatura.h:

especies.h

/* 
 * Arquivo: criatura.h 
 * ---------------- 
 * Esta interface define a abstração de criatura. 
 */ 
#ifndef _criatura_h 
#define _criatura_h 
#include "geometria.h" 
#include "especies.h" 
#include "mundo.h" 
/* 
 * Tipo: criaturaTAD 
 * ----------------- 
 * Este tipo é o tipo abstrato de dados para criatura. 
 */ 
typedef struct criaturaCDT *criaturaTAD; 
/* 
 * Função: NovaCriatura 
 * Uso: criatura = NovaCriatura(especies, mundo, pt, dir); 
 * ------------------------------------------------------- 
 * Esta função cria uma nova criatura da espécie indicada 
 * que vive no mundo específico. A criatura é incialmente 
 * posicionada na posição pt olhando para a direção dir. 
 */ 
criaturaTAD NovaCriatura(especiesTAD especies, mundoTAD mundo, 
                         pontoT pt, direcaoT dir); 
/* 
 * Função: ObtemEspecies 
 * Uso: especies = ObtemEspecies(criatura); 
 * -------------------------------------- 
 * esta função retorna as espécies à qual esta criatura 
 * pertence. 
 */ 
especiesTAD ObtemEspecies(criaturaTAD criatura); 
/* 
 * Função: ExecutaUmaVez 
 * Uso: ExecutaUmaVez(criatura); 
 * ----------------------------- 
 * Esta função executa um vez para esta criatura. 
 */ 
void ExecutaUmaVez(criaturaTAD criatura); 
 
#endif

Arquivo: mapamundi.h

Desenha o mundo Darwin

Este módulo exporta as funções necessárias para exibir as criaturas na tela.

especies.h

/* 
 * Arquivo: mapamundi.h 
 * ---------------- 
 * Esta interface suporta a apresentação do mundo darwin. 
 */ 
#ifndef _mapamundi_h 
#define _mapamundi_h 

#include "geometria.h" 
/* 
 * Função: IniciaMapaMundi 
 * Uso: IniciaMapaMundi(colunas, linhas); 
 * ----------------------------------- 
 * Esta função abre e mostra uma janela na tela. A chamada a esta função 
 * deve ser feita antes de qualquer outra chamada 
 * e antes de qualquer saída para os canais de E/S padrão. Os parâmetros 
 * colunas e linhas especificam o tamanho do mundo, embora 
 * alguns quadrados possam ficar fora da tela visível se o 
 * mundo for muito grande. 
 */ 
void IniciaMapaMundi(int colunas, int linhas); 
/* 
 * Função: MostraQuadrado 
 * Uso: MostraQuadrado(qd, letrachave, dir); 
 * --------------------------------------- 
 * Esta função muda o desenho da tela para o quadrado indicado 
 * (cuja posição é expressa por um ponto) de tal modo
 * que ele contenha uma criatura indicada pelo caractere letrachave ,
 * olhando para a direção especificada por dir. Se a letrachave é um 
 * espaço, o quadrado é mostrado como vazio e a direção 
 * é ignorada. 
 */ 
void MostraQuadrado(pontoT qd, char letrachave, direcaoT dir); 

#endif

Sua solução deve ser enviada para araujo.uerj@gmail.com

Os alunos que quiserem poderão usar a nota do trabalho para substituir a segunda prova. Neste caso e para trabalhos em dupla será feita uma arguição para comprovar a efetiva participação no trabalho. Alunos que fizerem sozinhos são dispensados da arguição. Alunos que perderam a primeira prova não estão dispensados da segunda prova, mesmo usando o trabalho para substituir a segunda prova.

A política de plágio é a de sempre. Os trabalhos devem ser originais e é melhor um programa incompleto do que um que seja fruto de cópia ou plágio. Se bem que admitida a troca salutar de idéias, não de código, trabalhos semelhantes têm uma única nota que será dividida entre os participantes, ou seja, a nota é para o trabalho. Se ele vale 10, cada colaborador recebe 10 dividido pelo número de equipes colaborativas. A cópia pura e simples, sem o consentimento do outro, recebe nota zero.

Anexos

Para facilitar o trabalho, será fornecida as rotinas do pacote gráfico, que deve ser compilada com a biblioteca SDL e SDL_ttf. No linux basta usar o synaptic para instalar.

A rotina gráfica está na biblioteca libdarwin.a

Para usá-la, compile com

 gcc <seuprograma1.c seuprograma2.c ... seuprograman.c> -L. -ldarwin -o seuexecutavel  -lSDL -lSDL_ttf

O arquivo fonte, para quem quiser melhorar: mapamundi.c e .h mais fonte ttf usado Os outros .h, cujos arquivos fontes deverão ser desenvolvidos : darwin.zip

A proposta original deste problema é de Nick Parlante, da Universidade de Stanford. Não. Não existe solução online.

Dica

O arquivo .ttf deve ser posto no mesmo diretório do seu programa executável, para permitir a renderização correta das letras das criaturas.
trabalho_2008-2.txt · Última modificação: 23/07/2009 16:03:03 (edição externa)
geomatica Creative Commons License Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0