MC 202 - Estruturas de Dados - Primeiro Semestre de 2011
Transcrição
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.