2º Projeto de Introdução à Computação 2017/2018

O projeto deve ser realizado em grupos de 2 a 3 alunos. A constituição dos grupos deve ser comunicada ao docente até 11 de janeiro, data a partir da qual se assume que os alunos não pretendem realizar o projeto na 1ª época.

Descrição do problema

Pretende-se que os alunos desenvolvam um jogo/simulador no qual zombies perseguem e infetam humanos. O jogo desenrola-se numa grelha 2D toroidal¹ com dimensões X e Y e vizinhança de Moore². Em cada célula da grelha pode estar no máximo um agente, que pode ser um zombie ou um humano. No início da simulação existem n_z zombies e n_h humanos, num total de n = n_z + n_h agentes. Os agentes devem ser espalhados aleatoriamente pela grelha no início de cada jogo.

O jogo é turn-based, e em cada turn (iteração) cada agente pode realizar uma ação. Os humanos podem apenas realizar um tipo de ação: movimento. Os zombies podem realizar dois diferentes tipos de ação: 1) movimento; e, 2) infeção de humanos. O movimento dos agentes pode ser realizado para uma célula vazia numa vizinhança de Moore de raio 1. A infeção de humanos pode ser realizada por zombies quando o humano está numa célula adjacente na vizinhança de Moore. A ordem em que os agentes executam as suas ações em cada turn é aleatória³, de modo a que nenhum agente em específico obtenha a vantagem de agir cedo durante todo o jogo.

Os agentes podem ser controlados pelo computador através de uma Inteligência Artificial (IA) básica, ou podem ser controlados por jogadores. Neste último caso, um jogador que controle determinado agente pode decidir o destino do mesmo. Se o agente for um zombie, a ação de infeção equivale à indicação de movimento para o local onde está um humano. Nesse caso o zombie não se move (pois o local já está ocupado pelo humano), mas o humano é convertido em zombie. Se o humano era controlado por um jogador, deixa de o ser, e passa a ser controlado pela IA. O jogo termina quando não existirem mais agentes do tipo humano na grelha.

Caso um agente seja controlado pela IA, as suas decisões dependem do tipo de agente:

• Humano - Tenta mover-se na direção oposta ao zombie mais próximo. Se a célula para onde o humano deseja mover-se estiver ocupada, o humano fica no mesmo local.
• Zombie - Caso exista um humano numa célula adjacente, infeta-o. Caso contrário, tenta mover-se na direção do humano mais próximo. Se a célula para onde o zombie deseja mover-se estiver ocupada, o zombie fica no mesmo local.

O jogo termina quando o número máximo de turns for atingido, ou quando não existirem mais humanos na simulação.

Modo de funcionamento

Invocação do programa

O programa deve aceitar como único parâmetro um ficheiro de configuração em formato INI⁴, de acordo com o seguinte exemplo:

; Dimensao da grelha de jogo
xdim=20
ydim=20
; Numero inicial de zombies e humanos
nzombies=20
nhumans=20
; Numero de zombies e humanos controlados por jogadores
nzplayers=0
nhplayers=1
; Numero de turns maximo
maxturns=1000

Os campos indicados no exemplo anterior são obrigatórios e o programa deve saber interpretá-los corretamente. O programa deve ainda ignorar campos que não conheça. Os alunos podem acrescentar campos que considerem úteis para o desenvolvimento do projeto, mas estes devem ser opcionais. Por outras palavras, o programa deve assumir valores por omissão para campos opcionais extra. Um ficheiro INI usado para um projeto deve funcionar sem erros noutro projeto.

Senão for indicado o ficheiro de configuração, o programa deve terminar com uma mensagem de erro para stderr, indicando o modo de uso.

Modos de jogo

Modo automático

O programa entra em modo automático quando não existem agentes controlados por jogadores. Neste modo o jogo desenrola-se sem intervenção direta do utilizador. A visualização deve ser atualizada no fim de cada turn (pelo menos). No entanto, de modo a ser possível observar a evolução da simulação, poderá ser boa ideia solicitar ao utilizador para pressionar uma tecla ou clicar num botão antes de se dar início à próxima turn.

Modo interativo

Este modo é semelhante ao automático, apenas com duas pequenas diferenças: 1) cada vez que um agente controlado pelo jogador é chamado a agir, o programa fica a aguardar o input do jogador sobre que ação tomar; e, 2) a visualização do jogo deve ser atualizada imediatamente antes de ser solicitado input a um jogador (pelo menos). Se a dada altura deixarem de existir agentes controlados pelo jogador, o programa entra em modo automático.

Visualização do jogo

A visualização do jogo deve ser feita com recurso a uma biblioteca gráfica ou de jogos, e deve obedecer à interface fornecida no ficheiro showworld.h. Relativamente à biblioteca, algumas sugestões:

• g2 - Simples mas limitada.
• Ncurses - ASCII art (texto), ver referência [2].
• Allegro5 - Bom meio termo, com bons exemplos em C.
• SDL2 - Muito versátil e abrangente, mas poucos exemplos em C.
• Raylib - Muito interessante, mas instalação no Ubuntu não é trivial (ver instruções no Wiki da página no GitHub).

Relativamente à interface fornecida no ficheiro showworld.h, a mesma declara uma série de tipos e funções que devem ser respeitados na parte de visualização do jogo. Os alunos devem ler com atenção os comentários no código deste ficheiro para perceberem como devem implementar o corpo das funções de visualização. O ficheiro showworld_simple.c oferece uma implementação simples desta interface, com visualização em modo de texto, e que pode ser usada numa primeira fase de desenvolvimento do projeto. A secção Código exemplo contém mais informações sobre a visualização do jogo.

Objetivos, critério de avaliação e entrega

Objetivos

• Jogo deve funcionar como especificado.
• Código deve compilar sem erros no compilador GCC e/ou Clang com as opções -std=c99 -Wall -Wextra -Wpedantic.
• Código deve estar devidamente comentado e indentado.
• Tamanho da grelha e número de agentes não deve ser fixado no código, mas sim especificado no ficheiro de configuração.
• Documentação do projeto deve ser feita com Doxygen (ver secção Documentação automática do código com Doxygen).
• Programa deve estar organizado em vários ficheiros .c e .h com uso de Makefile (ver secção Divisão do código em vários ficheiros).
• Visualização do jogo deve ser feita com recurso a uma biblioteca gráfica ou de jogos (ver secções Visualização do jogo e Código exemplo).

Critério de avaliação

O projeto, que tem um peso de 8 valores na nota final da disciplina, será avaliado segundo os critérios indicados na Tabela 1.

Tabela 1 - Critérios de avaliação.

Critério	Peso
Funcionamento segundo especificações	1,5 val.
Qualidade do código e das soluções6	1,0 val.
Comentários e documentação com Doxygen	1,0 val.
Relatório	1,0 val.
Desenvolvimento do projeto com Git7	0,5 val.
Tamanho da grelha/número de agentes variável	1,0 val.
Visualização com recurso a biblioteca externa	1,0 val.
Organização do projecto e Makefile	1,0 val.
Extensões opcionais e Global Game Jam	Bónus!

Entrega

O projeto deve ser entregue via Moodle até às 23h de 24 de janeiro de 2018. Deve ser submetido um ficheiro zip com os seguintes conteúdos:

• Ficheiros .c e .h, ficheiro Makefile, ficheiro Doxyfile e ficheiro .gitignore.
• Pasta escondida .git contendo o repositório Git local do projeto.
• Ficheiro README.md contendo o relatório do projeto em formato Markdown organizado da seguinte forma:
  • Título do projeto.
  • Nome dos autores (primeiro e último) e respetivos números de aluno.
  • Descrição da solução:
    • Arquitetura da solução, com breve explicação de como o programa foi estruturado.
      • Um fluxograma simples ou gráficos semelhantes às Figuras 1 e 3 são bem vindos.
    • Estruturas de dados: grelha de simulação, agentes, outras estruturas auxiliares relevantes.
    • Algoritmos: procura de agente mais próximo, cálculo de direção na grelha, shuffling (embaralhamento) dos agentes antes de cada turn, outros algoritmos relevantes.
  • Manual de utilizador:
    • Como compilar: qual o comando ou comandos gerar uma build do jogo (ver secção Divisão do código em vários ficheiros).
    • Como jogar: que teclas pressionar e/ou onde clicar para mover agentes (modo interativo); tecla e/ou botão para passar para a próxima turn (modo automático); outras funcionalidades importantes que o utilizador possa controlar.
  • Conclusões e matéria aprendida.
  • Referências:
    • Incluindo trocas de ideias com colegas, código aberto reutilizado e bibliotecas de terceiros utilizadas. Devem ser o mais detalhados possível.
  • Nota: o relatório deve ser simples e breve, com informação mínima e suficiente para que seja possível ter uma boa ideia do que foi feito.

Atenção: Todos os ficheiros C e Markdown devem ser gravados em codificação UTF-8⁵.

Extensões opcionais, trabalho futuro e Global Game Jam

Caso os alunos atinjam todos os objetivos pretendidos, é possível estender e melhorar o jogo de várias formas. A melhor forma de o fazer é durante a Global Game Jam. Não existem restrições sobre melhorias a fazer, desde que o jogo mantenha a suas premissas básicas:

• Zombies vs. Humanos numa grelha 2D toroidal.
• Implementado em C99 com bibliotecas C auxiliares.
• O ponto de partida deve ser o código entregue a 21 de janeiro.

Algumas sugestões:

• Melhor IA, sobretudo da parte dos humanos.
• Dar aos humanos alguma forma de se defenderem.
• Agentes com propriedades individuais como energia, capacidade de movimento, etc.
• Power-ups.
• Melhor integração com biblioteca preferida (Ncurses, Allegro5, SDL2 ou Raylib – infelizmente a g2 não é apropriada para jogos "a sério"):
  • Possibilitar controlo com o rato.
  • Adicionar som.
  • etc...

Caso optem por melhorar o jogo, podem fazer nova entrega até 29 de janeiro (ou seja, logo após a Global Game Jam) para as melhorias e extensões serem tidas em conta no bónus da nota final do projeto.

Notas adicionais e material didático para desenvolvimento do projeto

Esta secção apresenta algumas notas adicionais, bem como algum material didático para auxiliar no desenvolvimento do projeto.

Sugestões para o desenvolvimento do projeto

1. Devem começar o projeto a partir do código disponibilizado na pasta code. Se usarem Git, o primeiro commit do projeto pode conter exatamente os ficheiros que compõem este exemplo¹¹.
2. Ler e reler o enunciado até deixarem de existir dúvidas sobre o mesmo. Se as mesmas persistirem, entrem em contato com o docente para esclarecimentos adicionais.
3. Fazer um plano de desenvolvimento do projeto. As seguintes limitações são aceitáveis numa primeira fase: 1) fixar no código (usando constantes) o tamanho do mundo de jogo, o número de agentes, e restantes parâmetros de configuração do jogo; e, 2) usar as funções no ficheiro showworld_simple.c (ver secção Visualização do jogo) para visualização do mundo de jogo. Numa segunda fase, quando os básicos estiverem todos a funcionar, podem então: 1) implementar a leitura do ficheiro INI; 2) usar alocação/libertação de memória para terem tamanhos variáveis do mundo e número de agentes; e, 3) implementar visualização com uma biblioteca gráfica externa.
4. Dividir bem o trabalho entre os diferentes elementos do grupo.
5. Organizar as estruturas e funções em ficheiros separados em volta de um conceito comum: coordenada, agente, grelha, etc. Por exemplo, no caso das coordenadas podem desenvolver um módulo (e.g. coordenadas.c e coordenadas.h), onde definem o tipo COORD para coordenadas 2D em grelha toroidal com vizinhança de Moore, e todas as funções que operam sobre variáveis desse tipo (e.g. deslocamento, comparação de coordenadas, distância, direção entre uma coordenada e outra, etc).
6. As funções devem ser pequenas e com responsabilidades bem definidas. Se uma função começar a ficar muito grande, devem considerar dividir a função em várias funções.
7. Existem uma série de ferramentas úteis que podem facilitar bastante o desenvolvimento do projeto, como por exemplo:
   • Git para colaboração e controlo de versões do código fonte.
     • Tendo em conta a complexidade do projeto, que requer a experimentação de diferentes abordagens e uma colaboração de facto entre todos os membros do grupo, o uso de Git pode facilitar bastante o desenvolvimento do projeto^7,11.
   • cppcheck para verificação estática do código fonte.
     • O cppcheck (e outras ferramentas similares) fazem uma verificação mais aprofundada do código, detetando possíveis problemas como operações entre tipos diferentes, ficheiros não devidamente fechados ou acesso potencial a zonas inválidas da memória. Para o código deste projeto, o cppcheck pode ser invocado na pasta do projeto da seguinte forma: cppcheck --enable=all --language=c --platform=unix64 --std=c99 *.c.
   • Valgrind para verificação dinâmica do programa.
     • Ao contrário do cppcheck, o Valgrind tenta detetar bugs no programa enquanto o mesmo está a ser executado. É especialmente útil para descobrir erros de acesso à memória e verificar se toda a memória alocada foi devidamente libertada. Caso o executável do projeto se chame zombies, o Valgrind pode ser usado para verificar o programa da seguinte forma: valgrind --leak-check=full ./zombies.
   • GDB para execução passo a passo e debugging do programa.
     • Tal como discutido na aula 4, o GDB permite executar programas passo a passo (desde que tenham sido compilados com a opção -g). Muitas vezes é a única forma de se perceber o que o código está realmente a fazer e corrigir bugs complicados. Caso o executável do projeto se chame zombies, o GDB pode ser usado para executar o programa da seguinte forma: gdb ./zombies.

Divisão do código em vários ficheiros

Vantagens

Existem várias vantagens em dividir um programa por vários ficheiros, como por exemplo [3],[4]:

• Facilita cooperação entre vários programadores, uma vez que cada programador pode trabalhar num ficheiro ou grupo de ficheiros diferente sem receio de conflitos.
• Permite uma abordagem orientada a objetos. Por outras palavras, cada módulo (par de ficheiros .c e .h) pode definir um tipo (ou vários tipos relacionados), bem como, bem como operações (funções) sobre esse tipo ou tipo(s), e até possíveis constantes associadas. Isto leva a que os programas fiquem muito bem estruturados.
• Na sequência do ponto anterior, o código fica organizado em forma de módulos ou bibliotecas, sendo facilmente reutilizável noutros projetos e programas, reduzindo o tempo de desenvolvimento.
• Quando um ficheiro é modificado, apenas esse ficheiro precisa de ser recompilado para o programa ser reconstruído. O programa make automatiza este processo.

Como dividir um programa em vários ficheiros

Regra geral, existe um ficheiro .c principal que contém a função main e eventualmente outras funções, variáveis ou definições diretamente relevantes para o programa a ser desenvolvido. Os restantes ficheiros devem ser agrupados em pares .c e .h (módulos) e disponibilizam funcionalidades específicas, na prática sendo usados como bibliotecas locais de funções.

Tipicamente, quando se define um tipo, por exemplo uma struct, todas as funções que acedem e/ou manipulam variáveis desse tipo são colocadas no mesmo par .c e .h (módulo). Numa linguagem de programação orientada a objetos, como o Java ou C#, os tipos são chamados de classes, as variáveis de dado tipo são chamadas de objetos, e as funções que operam sobre dado tipo são chamadas de métodos.

De modo a que os tipos (classes) e funções que operam sobre esses tipos (métodos) possam ser utilizados por outros programas e funções, é necessário colocar as declarações de tipos e os protótipos (cabeçalhos) das funções associadas no ficheiro .h (header file), e posteriormente incluir (#include) esse ficheiro no código no qual se pretende ter acesso à funcionalidade desenvolvida. Cada ficheiro .h tem um (ou mais) ficheiro(s) .c correspondente(s), onde são colocados os corpos (definições) das funções, bem como tipos e variáveis que apenas tenham relevância no contexto desse ficheiro (ou seja, que não valha a pena tornar públicos). O ficheiro .h pode ser considerado a parte pública do módulo (que pode ser usada por outro código), enquanto o ficheiro .c contém a parte privada. A parte pública é também denominada de interface ou API⁸ do módulo/biblioteca.

O exemplo dado na secção Código exemplo segue esta abordagem. As seguintes referências oferecem informação mais detalhada sobre este tópico: [4], [5], [6], [7], [8], [9] e [10].

Como compilar e ligar (construir) um programa dividido em vários ficheiros

Embora seja normal usar o termo compilação para nos referirmos à criação de um ficheiro executável a partir de código C, o termo mais correto seria construção. Na realidade, a construção (do inglês build) de um ficheiro executável passa por duas fases: compilação e ligação (do inglês compile e link, respetivamente). A primeira fase, compilação, consiste em processar e converter um ficheiro .c num ficheiro objeto com extensão .o contendo código máquina (zeros e uns). No entanto estes ficheiros não podem ser executados. Para tal, é necessário ligar (link) um ou mais ficheiros objeto num ficheiro executável [11]. O processo de compilação e ligação é chamado de construção (build), e é realizado implicitamente pelo compilador quando invocado da forma que temos feito até agora. Por exemplo:

$ gcc -Wall -Wextra -Wpedantic -std=c99 -o meuprograma meuprograma.c

É possível construir (compilar e ligar) um programa dividido em vários ficheiros numa só invocação do compilador, bastando para isso indicar todos os ficheiros .c a serem incluídos. Nesse caso, a função main terá de existir num e apenas num dos ficheiros .c. No caso do exemplo disponibilizado na pasta code, que contém dois ficheiros .c, o comando de construção (compilação e ligação) será o seguinte:

$ gcc -Wall -Wextra -Wpedantic -std=c99 -o example example.c showworld_simple.c

Neste caso são apenas dois ficheiros, mas regra geral os projetos podem conter muitos ficheiros, caso no qual o comando anterior fica bastante comprido. Além disso, esta abordagem obriga a recompilar todos os ficheiros .c, mesmo aqueles que não tenham sido alterados, tornando o processo de compilação muito lento. Desta forma, é comum realizar as fases de compilação e ligação de forma separada. A opção -c indica ao compilador para apenas compilar o ficheiro .c especificado. No caso do exemplo disponibilizado, os seguintes comandos vão compilar separadamente os ficheiros example.c e showworld_simple.c, dando origem aos ficheiros example.o e showworld_simple.o:

$ gcc -Wall -Wextra -Wpedantic -std=c99 -c example.c
$ gcc -Wall -Wextra -Wpedantic -std=c99 -c showworld_simple.c

Agora podemos ligar os dois ficheiros objeto, de modo a criar o ficheiro executável:

$ gcc example.o showworld_simple.o -o example

É de realçar que as opções típicas de compilação, -Wall -Wextra -Wpedantic -std=c99, só são relevantes para a fase de compilação, não sendo necessárias na fase de ligação. No entanto, se o programa a construir usar bibliotecas de terceiros, as opções para especificar tais bibliotecas (-l e -L) são passadas na fase de ligação.

No entanto esta abordagem manual para construção de um executável, com compilação individual de módulos e posterior ligação dos mesmos, está ainda longe de ser perfeita. Em primeiro lugar, seria necessário tomar nota dos módulos que precisam de ser recompilados (ou poderíamos recompilar todos e voltar à estaca zero em termos de eficiência). Além disso, é sempre necessário executar vários comandos (um ou mais para compilação e um para fazer a ligação). A forma clássica de automatizar o build (construção) de projetos C/C++ é através da ferramenta make⁹, discutida na próxima secção.

Builds automáticas com a ferramenta Make

A ferramenta make automatiza todo o processo de construção (building), nomeadamente as fases de compilação (compiling) e ligação (linking), de projetos C/C++. Basta executar o comando make e o projeto é automaticamente construído de forma eficiente, sendo recompilados apenas os módulos que foram modificados. Experimenta fazê-lo com o código disponibilizado na pasta code (cd code seguido de make).

A configuração de um projeto a ser construído com a ferramenta make é realizada com recurso a um ficheiro de nome Makefile, que indica ao make como compilar e ligar um programa. Uma Makefile simples consiste num conjunto de "regras", cada uma com a seguinte forma:

target ... : prerequisites ...
	recipe
	...
	...

O target (alvo) é geralmente o nome de um ficheiro a ser gerado, como por exemplo ficheiros executáveis ou ficheiros objeto. Um target também pode ser o nome de uma ação a realizar, como por exemplo clean. Neste último caso diz-se que o target é "Phony" (falso). Um prerequisite (pré-requisito) é um ficheiro usado como input para geração do target. Geralmente um target depende de vários ficheiros. Uma recipe (receita) é uma ação a ser executada pelo make, e pode ser composta por um ou mais comandos. É necessário colocar um TAB no início de cada linha da receita, caso contrário o make não funciona como pretendido. Tipicamente uma recipe está numa regra com pré-requisitos e serve para gerar o target caso algum dos pré-requisitos tenha sido modificado desde a última geração desse target. Nem todas as regras precisam de pré-requisitos. Por exemplo, a regra para apagar todos os ficheiros gerados (cujo target é normalmente chamado clean) não tem pré-requisitos. Uma possível Makefile para o exemplo disponibilizado na pasta code terá o seguinte conteúdo:

example: example.o showworld_simple.o
	gcc example.o showworld_simple.o -o example

example.o: example.c showworld.h
	gcc -Wall -Wextra -Wpedantic -std=c99 -g -c -o example.o example.c

showworld_simple.o: showworld_simple.c
	gcc -Wall -Wextra -Wpedantic -std=c99 -g -c -o showworld_simple.o showworld_simple.c

clean:
	rm -f example *.o

A primeira regra é invocada por omissão quando o make é executado sem argumentos. O target desta regra é o ficheiro executável example, que depende dos ficheiros example.o e showworld_simple.o para ser gerado (neste caso através de ligação/linking). Uma vez que inicialmente nenhum dos ficheiros objeto existe, a receita dessa regra não pode ser imediatamente executada. O make vai então procurar outras regras cujo target tem o nome de cada um desses pré-requisitos. Uma vez que a segunda e terceira regras têm targets com esses nomes, o make vai tentar executar as respetivas receitas. Dado que os pré-requisitos destas regras já existem (ficheiros .c e .h), as respetivas receitas podem ser executadas, gerando dessa forma os dois ficheiros objeto através de compilação dos respetivos ficheiros .c. Após esta fase, o make já pode então invocar a receita da primeira regra, que vai criar o ficheiro executável example ligando (linking) os ficheiros objeto entretanto gerados.

Posteriormente, se modificarmos apenas o ficheiro example.c e voltarmos a executar o make, apenas a segunda regra (compilação de example.c) e a primeira regra (ligação dos ficheiros .o) serão executadas. O make sabe que não é necessário voltar a gerar, através de compilação, o ficheiro showworld_simple.o, uma vez que nenhum dos seus pré-requisitos foi modificado.

O comando make pode aceitar como argumentos o nome dos targets. Ou seja, se executarmos o comando make clean, a receita cujo target tem esse nome vai ser executada. Neste caso, esta receita corre o comando rm -f example *.o, que elimina o ficheiro executável e os ficheiros objeto gerados.

Esta versão da Makefile funciona perfeitamente, mas pode ser melhorada. Em primeiro lugar, estamos a repetir os argumentos de compilação em dois locais. Além disso, o nome do executável aparece em vários locais. Felizmente as Makefiles suportam variáveis nas quais podemos guardar opções que são utilizadas várias vezes. A segunda versão da nossa Makefile poderia ter então a seguinte forma:

CC=gcc
CFLAGS=-Wall -Wextra -Wpedantic -std=c99 -g
PROGRAM=example

$(PROGRAM): $(PROGRAM).o showworld_simple.o
	$(CC) $(PROGRAM).o showworld_simple.o -o $(PROGRAM)

$(PROGRAM).o: $(PROGRAM).c showworld.h
	$(CC) $(CFLAGS) -c -o $(PROGRAM).o $(PROGRAM).c

showworld_simple.o: showworld_simple.c
	$(CC) $(CFLAGS) -c -o showworld_simple.o showworld_simple.c

clean:
	rm -f $(PROGRAM) *.o

É conveniente usar comentários para um melhor entendimento do conteúdo das Makefiles. Os comentários começam com o caráter # (cardinal), tal como nos shell scripts. Além disso, como o target clean não corresponde a um ficheiro, é boa prática indicar este facto na Makefile, de modo a que o make não se confunda caso venha a existir um ficheiro com esse nome. Esta indicação é feita com o target especial .PHONY, colocado imediatamente antes do target em questão. Com esta informação chegamos a uma terceira versão da nossa Makefile:

# Compilador C
CC=gcc
# Argumentos (flags) de compilacao
CFLAGS=-Wall -Wextra -Wpedantic -std=c99 -g

# Nome do programa
PROGRAM=example

# Regra para geral executavel
$(PROGRAM): $(PROGRAM).o showworld_simple.o
	$(CC) $(PROGRAM).o showworld_simple.o -o $(PROGRAM)

# Regra para gerar o ficheiro objeto com o mesmo nome do executavel
$(PROGRAM).o: $(PROGRAM).c showworld.h
	$(CC) $(CFLAGS) -c -o $(PROGRAM).o $(PROGRAM).c

# Regra para gerar o ficheiro objeto showworld_simple.o
showworld_simple.o: showworld_simple.c
	$(CC) $(CFLAGS) -c -o showworld_simple.o showworld_simple.c

# Regra para limpar todos os ficheiros gerados (executavel e objetos)
.PHONY: clean
clean:
	rm -f $(PROGRAM) *.o

A ferramenta make é bastante "inteligente", sobretudo quando se trata da construção (building) de projetos C/C++. Nomeadamente, o make pode determinar automaticamente as receitas para compilação e ligação (compiling and linking) dos diferentes targets. Para o efeito é necessário definir algumas variáveis especiais. Na Makefile anterior já usamos duas destas variáveis: CC e CFLAGS. A primeira especifica o programa a ser usado como compilador C, enquanto a segunda define as opções (flags) a usar na fase de compilação. Existem outras variáveis especiais importantes para compilação de projetos C, das quais duas serão importantes neste projeto:

• LDFLAGS - Opções de ligação (linking) para localização de bibliotecas no sistema de ficheiros, como por exemplo a flag -L.
• LDLIBS - Opções de ligação (linking) para especificação de bibliotecas a usar, como por exemplo a flag -l.

No caso do exemplo apresentado não são usadas bibliotecas extra, pelo que estas duas variáveis podem não ter conteúdos. No entanto é útil especificá-las explicitamente na Makefile, pois podemos vir a querer adicionar bibliotecas no futuro. Usando esta abordagem podemos omitir as receitas, pois o make vai fazê-las corretamente. Desta forma, os conteúdos da próxima versão da nossa Makefile são os seguintes:

# Compilador C
CC=gcc
# Argumentos (flags) de compilacao
CFLAGS=-Wall -Wextra -Wpedantic -std=c99 -g
# Opções de ligação para localização de bibliotecas (e.g. -L)
LDFLAGS=
# Opções de ligação, como por exemplo especificação de bibliotecas (e.g. -l)
LDLIBS=

# Nome do programa
PROGRAM=example

# Regra para geral executavel (deixar make fazer a receita)
$(PROGRAM): $(PROGRAM).o showworld_simple.o

# Regra para gerar o ficheiro objeto com o mesmo nome do executavel (deixar
# make fazer a receita)
$(PROGRAM).o: $(PROGRAM).c showworld.h

# Regra para gerar o ficheiro objeto showworld_simple.o (deixar make fazer a
# receita)
showworld_simple.o: showworld_simple.c

# Regra para limpar todos os ficheiros gerados (executavel e objetos)
.PHONY: clean
clean:
	rm -f $(PROGRAM) *.o

A linguagem das Makefiles oferece bastante possibilidades, como é possível concluir olhando para o respetivo manual. Na prática, e nomeadamente para o projeto em questão, as possibilidades aqui descritas são mais do que suficientes para uma boa automatização da build do jogo.

É de realçar que, ao contrário de linguagens imperativas como o C ou scripts de linha de comandos (Shell/Bash), a linguagem das Makefiles é declarativa. Ou seja, ao contrário dessas linguagens, a linguagem das Makefile descreve o resultado desejado, mas não necessariamente os passos para o obter.

Código exemplo

A pasta code contém codigo auxiliar para desenhar o mundo do jogo. A Figura 1 mostra como o código está organizado.

Figura 1 - Organização do código auxiliar para desenhar o mundo do jogo no ecrã.

O ficheiro showworld.h declara seis tipos e/ou funções que devem ser usados para o desenvolvimento da parte de visualização do projeto, nomeadamente:

• AGENT_TYPE - Enumeração que define os diferentes tipos de agente, tal como indicado na Tabela 3.
• SHOWWORLD - Tipo abstrato que representa o display ou visualização do mundo de simulação.
• get_agent_info_at - Tipo de função que retorna informação sobre um agente em dado local do mundo de jogo.
• showworld_new - Função para criar um display ou visualização do mundo de jogo (objeto do tipo SHOWWORLD).
• showworld_destroy - Função para libertar memória associada a um display ou visualização do mundo de jogo (objeto do tipo SHOWWORLD).
• showworld_update - Função que atualiza o display / visualização do mundo de jogo.

O ficheiro showworld_simple.c define uma implementação concreta dos tipos e/ou funções declaradas de forma abstrata na interface showworld.h, podendo ser utilizado numa primeira fase de desenvolvimento do projeto. Quando o projeto estiver a funcionar adequadamente, os alunos devem criar uma implementação concreta da visualização do jogo que faça uso de uma biblioteca gráfica, tal como indicado anteriormente. Para o efeito devem substituir o ficheiro showworld_simple.c por outra implementação, mas que continue a obedecer à interface definida em showworld.h.

Por sua vez, o ficheiro example.c contém um exemplo de como usar a interface definida em showworld.h.

As próximas subsecções descrevem em detalhe a implementação showworld_simple.c, e como os alunos podem criar a sua própria implementação da visualização.

Exemplo de implementação: showworld_simple.c

A implementação de visualização definida no ficheiro showworld_simple.c mostra o mundo do jogo no terminal, indicando se o agente é zombie (z) ou humano (h), o ID do agente em hexadecimal (por exemplo, z0A), e diferenciando com Z ou H maiúsculo caso o agente em questão seja controlado por um jogador (por exemplo, H19). Caso não exista um agente na célula em questão, é impresso um ponto (.). Para um mundo 5x5 com 4 zombies e 1 humano, com um dos zombies controlado por um jogador, a implementação mostra algo parecido com a Figura 2.

.   .  Z02  .   .

.  z00  .   .   .

.   .   .   .   .

.   .  z03  .   .

.  z01  .  h04  .

Figura 2 - Exemplo do mundo de jogo com dimensões 5x5, tal como mostrado na implementação de visualização definida em showworld_simple.c.

Implementação do objeto SHOWWORLD para visualização do mundo de simulação

O tipo concreto SHOWWORLD está definido como uma estrutura com três campos: xdim, ydim e aginfo_func. Os dois primeiros campos representam o tamanho horizontal e vertical do mundo de jogo, respetivamente. O terceito campo é do tipo get_agent_info_at, ou seja, representa um apontador para uma função que retorna informação sobre um agente em dado local do mundo de jogo.

Não é preciso nada de mais, uma vez que este tipo de visualização é muito simples.

Implementação da função showworld_new()

A implementação desta função aloca memória para um objeto do tipo SHOWWORLD, guardando nos campos dessa estrutura o tamanho do mundo e o apontador para a função que retorna informação sobre um agente em dado local do mundo de jogo, do tipo get_agent_info_at.

Implementação da função showworld_destroy()

Uma vez que apenas foi efetuada uma alocação de memória para criação do objeto SHOWWORLD, a função showworld_destroy() simplesmente liberta essa memória usando a função free().

Implementação da função showworld_update()

Esta função vai mostrar o mundo do jogo tal como aparece na Figura 2. A função não devolve nada (void), mas aceita dois argumentos. O primeiro, de nome sw, é um objeto do tipo SHOWWORLD que contém informação sobre o display / visualização do jogo. O segundo, de nome w, é do tipo void * (apontador genérico), e aponta para a estrutura de dados que contém o mundo do jogo.

Como é possível observar no código, esta implementação da função showworld_update() percorre todas as células da grelha de simulação, por linha e por coluna, obtém informação sobre o agente em cada posição (usando o apontador para função guardado num dos campos da variável sw), e imprime no ecrã, de forma formatada, a informação obtida. Esta função não precisa de saber nada sobre o mundo de simulação, apontado pela variável w, pois este é passado como argumento e interpretado pela função apontada por sw->aginfo_func.

Apontador para função do tipo get_agent_info_at

Existe ainda uma questão crucial e não esclarecida. Onde está definida a estrutura de dados que contém o mundo de simulação, bem como a função que a sabe interpretar? A reposta é a seguinte: tanto a estrutura de dados, bem como a função que a interpreta, devem ser desenvolvidas no código do projeto. Uma vez que o mundo de simulação vai ser definido de forma específica por cada grupo, faz então sentido que a função que obtém informação sobre um agente em determinada localização no mundo seja também definida pelo grupo. Esta função deve obedecer ao tipo get_agent_info_at, definido na interface showworld.h. No caso do código exemplo, a função está definida no ficheiro example.c.

Como funcionam as funções do tipo get_agent_info_at?

As funções do tipo get_agent_info_at devem devolver um unsigned int contendo informação sobre um agente, recebendo como argumentos a variável w (apontador genérico para o mundo do jogo), bem como as coordenadas (x,y) da posição sobre a qual se pretende obter informação. O unsigned int com informação sobre um agente está organizado internamente como indicado na Tabela 2.

Tabela 2 - Informação sobre um agente tal como devolvida por funções do tipo get_agent_info_at.

Bits	31–19	18–3	2	1–0
Significado	Livre	ID do agente	Agente jogável?	Tipo de agente

Os dois bits menos significativos, nas posições 0 e 1, representam o tipo de agente. O bit na posição 2 indica se o agente é controlado por um jogador (1) ou pela IA (0). Os bits entre as posições 3 e 18 contêm o ID do agente. Finalmente, os bits mais significativos (posições 19 a 31) estão livres para uso do aluno, caso assim o entenda.

Os possíveis tipos de agente (posições 0 e 1) estão definidos numa enumeração de nome AGENT_TYPE no ficheiro showworld.h, tal como indicado na Tabela 3. O tipo Unknown nunca deve ocorrer. Se tal acontecer, significa que o jogo tem um bug.

Tabela 3 - Tipos de agentes definidos na enumeração AGENT_TYPE.

Tipo	Significado	Código (dec.)	Código (bin.)
None	Nenhum agente presente	0	00
Human	Agente humano	1	01
Zombie	Agente zombie	2	10
Unknown	Agente desconhecido	3	11

Exemplo de uso

Um exemplo desta abordagem está disponível no ficheiro example.c. Este programa cria uma grelha de simulação de dimensões 20x20, na qual os agentes são colocados em cada célula com uma probabilidade de 10%, invocando depois a função showworld_update() para mostrar o mundo aleatoriamente gerado. A grelha de simulação (mundo do jogo) é definida como um array bidimensional de agentes, onde cada posição [i][j] do array, correspondente a uma coordenada (x,y) no mundo do jogo, contém um agente. Por sua vez, os agentes são definidos como uma estrutura de nome AGENT com três campos: tipo de agente (AGENT_TYPE), agente jogável (unsigned char, 0 ou 1), e ID do agente (unsigned short). A função example_get_ag_info(), que obedece ao tipo get_agent_info_at, sabe interpretar a variável w como array de agentes, sabendo também como obter informação sobre um agente em determinada posição do array. Esta função é dada a conhecer ao código de visualização durante a criação do objeto SHOWWORLD, sendo passada como último argumento da função showworld_new().

Convém referir que as estruturas de dados usadas neste exemplo poderão não ser adequadas ou suficientes para o desenvolvimento do projeto.

Sugestão de organização do projeto

A Figura 3 mostra uma possível organização de um projeto com visualização baseada em SDL2, omitindo possíveis ficheiros associados a funcionalidades não discutidas nesta secção. É de notar a substituição da implementação showworld_simple.c por uma implementação em SDL2, que obedece de igual forma à interface showworld.h.

Figura 3 - Possível organização de um projeto, omitindo possíveis componentes associadas com outras funcionalidades específicas.

Documentação automática do código com Doxygen

O código de um projeto deve estar devidamente documentado, sendo boa prática escrever documentação específica sobre:

• Ficheiros e módulos: descrição e objetivos.
• Funções: descrição, entradas (argumentos) e saídas (valor retornado).
• Tipos: descrição geral e descrição específica para cada campo ou valor no caso de estruturas e enumerações, respetivamente.
• Variáveis globais: descrição.
• Constantes: descrição.

Esta documentação é especialmente importante para a parte pública (interface) de um projeto, uma vez que a mesma pode vir a ser utilizada por outros programadores ou incorporada noutros projetos. No entanto não é nada prático escrever esta documentação em ficheiros ou documentos separados. A ferramenta Doxygen¹⁰ permite converter comentários especialmente formatados no código em documentação do projeto. A ferramenta permite exportar documentação em formato HTML, PDF, RTF (compatível com DOC), man pages e por ai fora. Uma vez que comentários bem escritos são essenciais em qualquer programa, é possível juntar dois em um (comentários e documentação) bastando para isso seguir algumas regras de formatação de escrita de comentários.

O código exemplo foi comentado com as regras de documentação do Doxygen. Para gerar a documentação basta entrar na pasta code e executar o comando doxygen. A documentação é gerada em formato HTML e é colocada na pasta doc dentro da pasta code (podem ver a documentação online em https://videojogoslusofona.github.io/ic2017p2/). As definições do Doxygen para cada projeto são especificadas num ficheiro chamado Doxyfile, como é o caso do ficheiro Doxyfile incluido no exemplo.

O Doxygen suporta formatação Markdown dentro dos comentários, bem com a inclusão de ficheiros Markdown na documentação (como é caso no exemplo disponibilizado). Além das linguagens C e C++, o Doxygen suporta outras linguagens comuns tais como Java, C#, Python ou PHP. Um grande número de projetos usa Doxygen para gerar a respetiva documentação, como por exemplo a biblioteca g2 para gráficos, a biblioteca de funções C Apache Portable Runtime, ou a biblioteca cf4ocl para execução de programas em GPU.

O manual do Doxygen está disponível aqui. De particular interesse poderão ser a lista de comandos especiais reconhecidos nos comentários no código, bem como o sumário de todas as etiquetas de configuração aceitáveis no ficheiro Doxyfile.

Honestidade académica

Nesta disciplina, espera-se que cada aluno siga os mais altos padrões de honestidade académica. Isto significa que cada ideia que não seja do aluno deve ser claramente indicada, com devida referência ao respectivo autor. O não cumprimento desta regra constitui plágio.

O plágio inclui a utilização de ideias, código ou conjuntos de soluções de outros alunos ou indivíduos, ou quaisquer outras fontes para além dos textos de apoio à disciplina, sem dar o respectivo crédito a essas fontes. Os alunos são encorajados a discutir os problemas com outros alunos e devem mencionar essa discussão quando submetem os projetos. Essa menção não influenciará a nota. Os alunos não deverão, no entanto, copiar códigos, documentação e relatórios de outros alunos, ou dar os seus próprios códigos, documentação e relatórios a outros em qualquer circunstância. De facto, não devem sequer deixar códigos, documentação e relatórios em computadores de uso partilhado.

Nesta disciplina, a desonestidade académica é considerada fraude, com todas as consequências legais que daí advêm. Qualquer fraude terá como consequência imediata a anulação dos projetos de todos os alunos envolvidos (incluindo os que possibilitaram a ocorrência). Qualquer suspeita de desonestidade académica será relatada aos órgãos superiores da escola para possível instauração de um processo disciplinar. Este poderá resultar em reprovação à disciplina, reprovação de ano ou mesmo suspensão temporária ou definitiva da ULHT¹².

Notas

¹ Num mapa toroidal 2D, a grelha "dá a volta" na vertical e na horizontal. Por exemplo, num mapa 20x20, se um agente localizado na coordenada (0,10), margem esquerda da grelha, decidir mover-se para a esquerda, vai na realidade mover-se para a coordenada (19,10).

² Numa grelha 2D, a vizinhança de Moore é composta pela célula central e pelas oito células que a rodeiam.

³ Por outras palavras, a lista de agentes deve ser embaralhada (shuffled) no início de cada turn. O algoritmo de Fisher–Yates é um método de embaralhamento (shuffling) tipicamente utilizado para este fim.

⁴ Embora seja relativamente simples criar uma função ou biblioteca para leitura básica de ficheiros INI, existem algumas prontas a utilizar, como por exemplo iniparser, inih, minIni ou ini. A biblioteca de jogos Allegro5 também oferece um módulo para processamento de ficheiros INI.

⁵ Este pormenor é especialmente importante em Windows pois regra geral a codificação UTF-8 não é usada por omissão. Em todo o caso, e dependendo do editor usado, a codificação UTF-8 pode ser selecionada na janela de "Save as"/"Guardar como", ou então nas preferências do editor.

⁶ A qualidade do código e das soluções inclui vários aspetos, como por exemplo: 1) código bem indentado; 2) evitar código "morto", que não faz nada, tal como variáveis ou funções nunca usadas; 3) as soluções desenvolvidas são simples e/ou eficientes; 4) código compila sem erros e warnings; 5) código devidamente organizado e dividido em funções e ficheiros de forma lógica e bem estruturada; 6) código não acede a zonas não alocadas da memória, como por exemplo índices fora dos limites de um array; ou, 7) toda a memória alocada com as funções malloc e calloc é devidamente libertada com a função free.

⁷ Neste projeto não é necessário fazer fork deste repositório. Caso usem Git, os alunos podem inicializar um repositório local vazio ou com os conteúdos da pasta code e desenvolver o projeto a partir desse ponto. Dito isto, para um projeto desta dimensão e com grupos de 2 a 3 alunos, o uso de Git não é apenas recomendado para uma colaboração eficiente: é absolutamente essencial. Caso usem um ou mais repositórios remotos para colaboração devem indicar esse facto no relatório.

⁸ Application Programming Interface.

⁹ Mais especificamente a ferramenta GNU Make, uma vez que existem várias variantes desta abordagem de automatização de builds, nomeadamente o programa NMake incluido com o Microsoft Visual Studio. Apesar de ser orientada ao C e C++, a ferramenta Make pode ser usada em projetos desenvolvidos em qualquer linguagem de programação.

¹⁰ O Doxygen está disponível para download aqui (Linux/Windows/Mac). Pode também ser instalado em Ubuntu com o comando sudo apt install doxygen, ou através dos gestores de pacotes Homebrew (macOS) e Chocolatey (Windows).

¹¹ É também boa ideia criarem um ficheiro .gitignore para evitar a inclusão de ficheiros binários no repositório (como por exemplo ficheiros objeto ou o executável do projeto). O ficheiro .gitignore incluido neste repositório é um bom ponto de partida.

¹² Texto adaptado da disciplina de Algoritmos e Estruturas de Dados do Instituto Superior Técnico.

Referências

• [1] Pereira, A. (2017). C e Algoritmos, 2ª edição. Sílabo.
• [2] Reagan, P. (2014). Game Programming in C with the Ncurses Library, Viget Labs.
• [3] Marshall, D. (1999). Writing Larger Programs, Cardiff School of Computer Science and Informatics.
• [4] Sizer, B. (2013). Organizing Code Files in C and C++, GameDev.net.
• [5] Kieras, D. (2012). C Header File Guidelines, EECS Department, University of Michigan.
• [6] Ekstrand, J. (2013). Header file best practices, Math Department, Iowa State University.
• [7] Magnes, M. et al. (2012). What should and what shouldn't be in a header file?, Software Engineering, StackExchange.com.
• [8] Backus, J. et al. (2009). Code organization style for C?, StackOverflow.com.
• [9] Cronin, K. et al. Organization of C files, StackOverflow.com.
• [10] "horseyguy" et al. Good way to organize C source files?, StackOverflow.com.
• [11] Allain, A. (2017). Compiling and Linking, CProgramming.com.

Licenças

Todo o código neste repositório é disponibilizado através da licença GPLv3. O enunciado e restante documentação são disponibilizados através da licença CC BY-NC-SA 4.0.

Metadados

• Autor: Nuno Fachada
• Curso: Licenciatura em Aplicações Multimédia e Videojogos
• Instituição: Universidade Lusófona de Humanidades e Tecnologias