MC 202 - Estruturas de Dados - Primeiro Semestre de 2011

MC 202 - Estruturas de Dados - Primeiro Semestre de 2011
Atividade Opcional - Grafos
Monitor Priscila Biller
Guilherme Franzoni
1
Especificação do Problema
O objetivo deste trabalho e implementar um dos times de uma vers~ao simplicada do jogo DotA
(http://www.playdota.com/), denindo uma boa estrategia para o time.
Este sera um laboratorio competitivo: apos o termino da atividade sera feito um campeonato onde
os times se confrontar~ao.
A nota deste laboratorio pode aumentar a media obtida. Em caso de diminuic~ao da media, a nota
n~ao sera considerada.
1.1
DotA
DotA (Defense of the Ancients: Allstars) e um excelente e famoso jogo estrategico, desenvolvido a partir
de um mapa do jogo Warcraft III. Nele existem dois times, Sentinelas e Scourge, que devem se confrontar
ate que um deles destrua a base do inimigo.
A base do lado Sentinela e chamada de World Tree (no laboratorio, \Arvore")
e a base do lado Scourge
e chamada de Frozen Throne (no laboratorio, \Cristal"). Os times podem variar entre 1 e 5 herois e,
durante um combate, em caso de morte, o heroi aguarda um tempo fora do jogo e renasce na base do
seu time.
1.2
Jogo
Neste laboratorio, vamos trabalhar com uma vers~ao simplicada do jogo. Nele, cada time possui sempre
5 herois, e cada heroi possui uma determinada quantidade de forca. A forca da mais resist^encia ao heroi
no combate.
Neste laboratorio e permitido distribuir 10 pontos de forca entre os herois do time. Pelo menos 1
ponto deve ser dado a cada heroi.
A cada iterac~ao um dos times se desloca pelo mapa. Um ou mais herois do time podem se deslocar
em uma unica iterac~ao, e pelo menos 1 heroi deve movimentar-se. O heroi deve escolher a qual posic~ao
adjacente deve se deslocar.
O mapa e representado por um grafo n~ao orientado, onde as posico~es do mapa s~ao os vertices e existe
uma aresta entre dois vertices quando e possvel se deslocar diretamente entre as duas posico~es.
Ao planejar o deslocamento, o time recebe o grafo que representa o mapa, mas desconhece as posico~es
do mapa em que o time adversario esta. Se durante o deslocamento os herois encontrarem um ou mais
herois do time adversario na posic~ao destino, havera um confronto.
Na luta, vence o time que possuir o maior total em forca. Em caso de empate, o time que ja estava
na posic~ao vence. Ao perder um combate, o heroi derrotado volta a sua base.
O objetivo e alcancar a posic~ao onde esta a base do adversario. Se apos um determinado numero de
iteraco~es nenhum dos times alcancar a base do adversario, ha um empate.
1.3
Grafo
O mapa e representado como um grafo, e a estrutura de dados utilizada e a lista de adjac^encias. O TAD
Grafo ja e disponibilizado com algumas funco~es basicas para manipulac~ao de grafos. Voc^e pode utilizar
elas ou incluir suas proprias funco~es no TAD Sentinela.
2
Implementação
2.1
Estruturas de Dados
Neste laboratorio devem ser denidos os campos da estrutura de dados Sentinela. Voc^e pode utilizar
como base o arquivo disponibilizado no site.
A estrutura Sentinela deve guardar um vetor com todos os herois do time e, alem disso, outros
campos que podem ser uteis durante a denic~ao da estrategia. Por exemplo, podem ser includos campos
para inferir a posic~ao do adversario quando um heroi e derrotado na luta, ou contadores que auxiliem
na hora de avancar ou recuar no mapa. Tambem podem ser includas informaco~es sobre o mapa, como
o numero de caminhos existentes ate uma determinada posic~ao.
2.2
Funções
obrigatorio
Escreva um programa em linguagem de programac~ao C que implemente o TAD Sentinela. E
utilizar os arquivos auxiliares disponibilizados. Voc^e pode incluir novas funco~es somente no TAD Sentinela, caso julgue necessario.
As seguintes funco~es devem ser implementadas:
2.2.1
carregar sentinela
Inicializa a estrutura de dados Sentinela, que varia conforme o time. Aloca memoria dinamicamente para
seus campos e tambem inicializa o vetor de herois, atribuindo nome e forca a cada um. O somatorio das
forcas deve ser igual ou menor que 10.
2.2.2
liberar sentinela
Libera toda a memoria que foi alocada din^amicamente para a estrutura Sentinela na func~ao carregar sentinela.
2.2.3
obter heroes sentinela
Retorna o vetor de herois do time Sentinela.
2.2.4
planejar movimento sentinela
Principal func~ao do TAD Sentinela. Recebe a estrutura Mapa e a estrutura Sentinela e implementa a
estrategia do time.
A estrutura Mapa armazena o mapa do jogo como um grafo, alem da posic~ao onde esta a base do
inimigo e a base aliada. Ja a estrutura Sentinela armazena os herois e os outros campos que comp~oem a
estrategia do time.
Com estas duas estruturas, voc^e deve determinar qual heroi movimentar e para onde movimentar. O
campo de posic~ao, denido dentro da estrutura \Hero" deve ser modicado, caso o heroi movimente-se.
Os herois devem estar armazenados dentro da estrutura Sentinela.
2.3
Requisitos e Critérios
Como requisito basico, sua implementac~ao deve utilizar os conceitos de Tipos Abstratos de Dados (TAD),
ou seja, especique um conjunto de dados e quais operaco~es podem ser executadas sobre esses dados.
Seu uso e obrigatorio, para que o codigo que bem estruturado e possa ser reaproveitado no futuro.
Todas as funco~es do TAD Sentinela devem ser implementadas utilizando uma estrutura de dados
adequada (eficiente) para armazenar e manipular as informaco~es. O n~ao cumprimento de qualquer
um dos requisitos basicos acima implicara em nota de implementac~ao 0 (zero).
Outro criterio considerado durante a correc~ao e a qualidade do seu codigo. Neste criterio inclui-se a
eci^encia e a clareza do codigo. Uma forma de aumentar a clareza do codigo e identa-lo e organiza-lo por
funco~es, por exemplo. N~ao e permitido o uso de variaveis globais: os valores devem ser passados para as
funco~es atraves de seus par^ametros.
Procure utilizar nomes intuitivos para variaveis e funco~es, para que outras pessoas possam compreender o que voc^e fez e para que voc^e tenha mais facilidade em manter e estender seu codigo. Sempre que
possvel, inclua comentarios precisos e concisos em operaco~es importantes (ou difceis de entender).
Evite repetir blocos de código na implementac~ao. Identique quais partes sempre se repetem e
quais variam e implemente uma unica func~ao, que recebe como par^ametros de entrada os dados variaveis.
A liberac~ao da memoria alocada dinamicamente e extremamente importante.
3
Relatório
3.1
Formato do Arquivo
Voc^e deve elaborar um relatorio sobre sua implementac~ao seguindo as seguintes instruco~es:
Deve estar no formato pdf,
Deve ter no maximo 4 paginas,
umero do seu RA.
O nome deve ser 08 raXXXXXX.pdf, onde XXXXXX deve ser substituido pelo n
O n~ao cumprimento de qualquer um dos itens acima implicara em nota de relatorio 0 (zero).
3.2
Estrutura
Seu relatorio deve conter (mas n~ao e limitado a):
RA, Nome e Turma de cada membro do grupo.
Identicac~ao da Atividade.
Especicac~ao do Tipo Abstrato de Dados Sentinela.
– Objetivo de cada campo denido na estrutura.
– Objetivo das funco~es implementadas.
L
ogica utilizada para a denic~ao da estrategia de movimentac~ao.
L
ogica utilizada para a distribuic~ao de pontos dos herois.
Explicac~ao detalhada sobre todas as manipulac~oes feitas com o grafo (mapa do jogo).
Explicac~ao de uma estrategia que venca a estrategia disponibilizada (caso a estrategia implementada
venca para qualquer caso, desconsidere este item).
3.3
Requisitos e Critérios
Durante a correc~ao, o criterio considerado e a qualidade do relatorio, ou seja, a clareza em abordar todos
os topicos mencionados, sem ser prolixo. Sempre que julgar necessario, utilize guras ou exemplos para
facilitar o entendimento.
Tambem ser~ao considerados erros ortogracos. Para evita-los, utilize um corretor ortograco.
4
Critério de Avaliação
Seu trabalho so sera corrigido se:
O relat
orio for entregue;
A implementac~ao do TAD Sentinela estiver correta;
For denida uma estrategia que venca em qualquer caso a estrategia disponibilizada (pode ser
proposta apenas no relatorio, caso o tempo n~ao permita implementa-la);
Caso contrario, sua nota sera 0 (zero). Em caso de tentativa de trapaça, sua nota tambem sera 0
(zero).
4.1
Bônus
Qualquer coisa que voc^e tenha feito alem do que seus colegas zeram, e seja interessante e relevante,
pode ser bonicado.
5
Entrega
Prazo para submeter o seu codigo via e-mail (pribiller [at] gmail.com):
08:00 do dia 07 de julho de 2011
Prazo para submeter o seu relatorio via e-mail (pribiller [at] gmail.com):
08:00 do dia 07 de julho de 2011
Nesta atividade, deve ser escolhido o MESMO representante do grupo que foi escolhido na atividade
anterior. O representante do grupo deve submeter a atividade no Susy e enviar o relatorio por e-mail (o
mesmo representante para as duas tarefas). N~ao e necessario que os dois membros do grupo submetam
os arquivos.
Ao enviar o relatorio, utilize a tag [MC202] Atividade 08 - raXXXXXX raYYYYYY no ttulo
do e-mail, identicando os dois RAs dos membros do grupo.