MC346 - Projeto de Programação - Campeonato

Criada: 2014-07-26
Modificada: 2014-08-29

Jogo

O jogo será Corrida de Vetores. Como este jogo apresenta inúmeras variações de regras, vamos aqui estabelecer claramente as que serão usadas em nossa disciplina.

Regras

• O jogo transcorrerá em sentido anti-horário.
• Apenas dois jogadores por corrida.
• Apenas uma volta por corrida.
• Há um limite máximo de jogadas por jogador em cada corrida.
• A linha de partida é também a linha de chegada.
• Em cada corrida, o jogador que primeiro escolhe a posição de largada é o segundo a realizar o movimento.
• Jogada inválida acarreta abandono da prova.
• Um carro não pode escolher como posição final de seu movimento a posição atualmente ocupada pelo outro carro. Caso isto aconteça, o carro que bateu abandona a prova.
• Apenas a posição inicial e final de um movimento devem estar dentro da pista (e não todo o comprimento do vetor) para caracterizar que o carro não bateu no guardrail.
• Em caso do ponto final de um movimento cair fora da pista, o carro sofrerá dano computado da seguinte forma:
  • dano leve: se sua posição final for vizinha (ou seja, diferença de no máximo 1 unidade em cada componente) de um ponto dentro da pista.
  • dano severo: caso contrário.
• Dois eventos de dano leve configuram dano severo.
• Um carro que sofre dano severo abandona a prova.
• Em caso de dano leve, o carro recomeça na sua última posição dentro da pista, e com velocidade zero.
• Quando um carro abandona a prova ele é retirado da pista e vai para os boxes.
• Quando um carro abandona a prova, o outro deve prosseguir em direção à linha de chegada sozinho.
• A corrida termina quando:
  • pelo menos um dos carros cruzar a linha de chegada, ou
  • quando ambos os carros foram obrigados a abandonar a prova, ou
  • quando o limite máximo de jogadas para esta prova for atingido.
• Se o carro que fez o primeiro movimento cruzar a linha de chegada, o gerenciador esperará mais uma jogada do segundo a jogar para determinar o vencedor.
• Ao término da corrida, será declarado vencedor:
  • o carro que tiver cruzado a linha de chegada, se apenas um cruzou-a;
  • o carro com menos dano, se ambos cruzaram-na;
  • o carro que alcançou um ponto mais distance da linha de chegada, se ambos cruzaram-na com igual nível de dano;
  • ambos os carros (empate), se ambos cruzaram a linha de chegada e nenhuma das condições anteriores for observada.
  • nenhum dos carros, se ambos abandonaram ou chegou-se ao limite de jogadas sem que ninguém cruzasse a linha de chegada.
• Pontuação: Carros que não chegarem ganham 0 pontos. Cruzar a linha de chegada vale 1 ponto. Em caso de empate, cada carro ganha mais 1 ponto. Em caso de vitória, o vencedor ganha mais 2 pontos.

Interface Prolog

Posições, velocidades e acelerações são sempre indicadas como listas [X, Y], com as componentes dos vetores nos eixos x e y, respectivamente. As componentes são sempre números inteiros (positivos ou negativos). A pista sempre circula em torno da origem [0, 0], mas este ponto nunca pertencerá a nenhuma pista.

Os alunos deverão escrever todo o seu jogador dentro de um módulo, cujo nome é formado por seu RA mais uma string à sua escolha. Desta forma, você pode ter vários jogadores diferentes na fase de treinos, variando a string escolhida. Ao término da fase de treinos, apenas um deles deve ser escolhido para ser o seu jogador oficial.

As corridas serão gerenciadas por um gerenciador, que está preparado para coordenar o andamento da corrida, determinar a ocorrência de eventos como colisões e término da prova, e atribuir pontos aos jogadores. Cada pista usada no jogo será implementada também como um módulo, sendo que o nome deste módulo será passado aos jogadores nos predicados de inicialização conforme detalhado mais adiante neste documento.

A interface será composta pelos seguintes predicados. Um módulo de pista exporta predicados para informar sua linha de largada/chegada (que é uma lista de posições), para saber se um ponto está ou não dentro da pista, e para saber o limite de jogadas da pista. Um módulo jogador deverá exportar predicados para escolha do ponto incial e para a execução de jogadas. Convenciona-se que as jogadas serão indicadas pela aceleração, que é a diferença entre o vetor de velocidade desejado para esta jogada e o vetor de velocidade anterior. Assim, acelerações válidas são vetores nos quais cada componente é igual a -1, 0 ou 1.

A especificação exata das interfaces segue. Todos os predicados a seguir devem ser programados para falhar na ressatisfação.

Da parte da pista:

• dentro(+Pos): satisfeito quando Pos é uma posição dentro da pista.
• linha(-Linha): satisfeito quando Linha é uma lista de posições que constitui a linha de largada/chegada desta pista.
• limite(?N): satisfeito quando N é o limite de jogadas da pista; N pode vir não instanciada, caso em que receberá o valor correto.

Da parte do jogador:

• inic1(+Pista, -Pos1): satisfeito quando Pos1 é uma posição dentro da linha de largada/chegada da pista; a variável Pos1 virá não instanciada e deverá ser instanciada pelo jogador com a sua escolha para posição inicial de seu carro, que será o segundo a se mover. A variável Pista é o nome do módulo que contém os predicados relativos à pista. O módulo do jogador deverá registar este nome para usá-lo nas chamadas aos predicados da pista.
• inic2(+Pista, +Pos1, -Pos2, -Acel0): satisfeito quando Pos2 é uma posição dentro da linha de largada/chegada da pista, mas diferente de Pos1 (que foi a posição escolhida pelo primeiro a escolher) e Acel0 é uma aceleração válida; as variáveis Pos2 e Acel0 virão não instanciadas e deverão ser instanciadas pelo jogador, a primeira com a sua escolha para a posição inicial de seu carro, que será o primeiro a se mover, e a segunda já com a aceleração inicial de seu carro. A variável Pista é novamente o nome do módulo da pista, que deve ser registrado pelo jogador. A variável Pos1 pode vir com valor [0, 0], indicando que o primeiro jogador abandonou a prova.
• acel1(+Pos2, +Acel0, -Acel1): satisfeito quando Acel1 é uma aceleração válida; Pos2 é a posição de largada escolhida por seu oponente e Acel0 é a primeira aceleração usada por seu oponente. A variável Pos2 pode vir com valor [0, 0], indicando que o segundo jogador abandonou a prova. Neste caso, a aceleração Acel0 virá com valor [0, 0].
• acel2(+AcelA, -AcelB): satisfeito quando AcelB é uma aceleração válida; AcelA é a última aceleração usada por seu oponente. Quando um jogador abandona a prova, seu predicado acel2 não será mais chamado, e suas jogadas subsequentes irão com valor [0, 0] para seu oponente.

Cada corrida é iniciada com uma chamada ao predicado inic1 do módulo do Carro 1, para o qual se passa a Pista, e espera-se como resposta a escolha da posição de partida do Carro 1. A seguir, é chamado o predicado inic2 do módulo do Carro 2, passando-se a Pista e a posição já escolhida na Linha pelo Carro 1 para sua largada. O Carro 2 então escolhe uma posição diferente, ainda dentro da Linha, para sua largada, e também sua primeira jogada, em forma de aceleração aplicada à sua velocidade anterior, que é zero.

Neste momento é chamado o precidado acel1 do Carro 1, passando-se como parâmetros a posição de partida escolhida pelo Carro 2 e a aceleração inicial do Carro 2. O Carro 1 retorna com a sua primeira aceleração.

A partir dai, os predicados acel2 de cada módulo são chamados alternadamente, até que um dos jogadores cruze a linha de chegada, ou ambos abandonem, ou o limite de jogadas se esgote. O argumento AcelA corresponde à última aceleração feita pelo adversário, e AcelB é a jogada que está sendo retornada pelo predicado acel2.

Haverá um limite de tempo de 5 segundos para os predicados inic1 e inic2 e 1 segundo de tempo para os predicados acel1 e acel2. Caso o limite de tempo seja excedido, considera-se que foi feita uma jogada inválida e o carro abandona a prova.

Haverá também um limite de tamanho de 1 MB para o código fonte de cada jogador. O sistema de submissão não aceitará arquivos acima deste limite.

A figura ao lado mostra um diagrama de sequência com as chamadas que o gerenciador fará durante a corrida.

Interface LISP

A interface em LISP será diferente da interface Prolog. A experiência adquirida nos treinos Prolog nos permitiu identificar oportunidades de melhoria, que esperamos venham a diminuir a dificuldade de programar gerenciadores e corredores. Com a nova interface, os gerenciadores deverão ficar mais livres de erro, e os alunos poderão concentrar seus esforços nas estratégias de jogo, ao invés de gastar tempo em atualizações de estado.

O estado de um carro é uma lista ( T D (X Y) (VX VY) ) de quatro elementos: o número de quadrantes cobertos, o dano, a posição e a velocidade atuais do carro. Vamos à explicação detalhada de cada um destes elementos:

• T: é um valor inteiro que indica o número de quadrantes cobertos, no sentido anti-horário, pelo carro.
• D: é um valor inteiro que indica o nível de dano do carro. 0 significa sem dano; 1 signfica dano leve; 2 ou mais significa dano severo e consequente abandono da prova.
• (X Y): posição do carro.
• (VX VY): velocidade do carro.

A ideia básica é que haverá apenas uma função a implementar, que receberá os estados de ambos os jogadores, e deverá retornar uma posição no grid de largada (apenas na primeira chamada) ou uma aceleração (nas demais jogadas). A interface LISP completa e suas diferenças em relação à interface Prolog são dadas a seguir:

• as listas para posições, velocidades e acelerações serão da forma (X Y) ao invés de [X, Y].
• ao invés de predicados, a interface é composta de funções (na verdade, uma função apenas).
• módulos são chamados de pacotes em LISP.
• o pacote da pista exportará três funções:
  • (dentro pos) que retorna T ou NIL conforme pos esteja ou não dentro da pista.
  • (linha) que retorna uma lista com as posições que correspondem à linha de largada e chegada.
  • (limite) que retorna o número máximo de jogadas por partida nesta pista.
• o pacote de um carro exportará uma função:
  • (pos-acel pista s-meu s-adv) que recebe o pacote da pista sendo usada, os estados do próprio carro e do carro adversário, e retorna uma posição ou aceleração conforme a situação de jogo:
    • se ambos os estados estão zerados, ou seja, são iguais a ( 0 0 (0 0) (0 0) ), isto significa que a corrida ainda não começou. O jogador deve retornar sua posição escolhida na linha de largada.
    • se s-meu está zerado mas s-adv não, sigifica que o adversário já escolheu sua posição inicial, mas nenhum outro movimento foi feito. O jogador deverá retornar sua escolha de posição na linha de largada.
    • em qualquer outro caso, o jogador deverá retornar uma aceleração válida para seu carro.

O número de quadrantes cobertos, T, que inicialmente é igual a zero, se modifica de uma em uma unidade, para mais ou para menos, cada vez que um carro passa de um quadrante para outro. Existem quatro quadrantes, Q1, Q2, Q3 e Q4. Um ponto (X Y) está num quadrante Qi quando:

• Q1: X > 0 e Y ≥ 0.
• Q2: X ≤ 0 e Y > 0.
• Q3: X < 0 e Y ≤ 0.
• Q4: X ≥ 0 e Y < 0.

Observe que a origem (0 0) não está em nenhum quadrante. As pistas são sempre desenhadas de forma a origem não esteja nelas, e que seja impossível passar diretamente de Q1 para Q3 ou vice-versa, ou passar diretamente de Q2 para Q4 ou vice-versa. Desta forma, o contador de quadrantes sempre se modificará no máximo uma unidade, para mais ou para menos, em cada jogada. Quando T chega a 4, o carro conseguiu completar uma volta.

Como serão calculadas as notas

A nota será de 0 a 10, dependendo da colocação do jogador no campeonato. Na fase de treinos (entre o início do período de submissão para uma certa linguagem e o término deste período para a mesma linguagem), cada aluno ou aluna pode submeter vários jogadores, para exercitar diversas estratégias. Porém, ao final do período de submissão, cada aluno ou aluna deve indicar apenas um de seus jogadores para ser o seu jogador oficial, que participará do camponato oficial.

A nota dependerá do desempenho do jogador no campeonato oficial. A nota será proporcional à pontuação no campeonato, da seguinte forma. A nota de um jogador será igual a 10*P/PM, onde P é sua pontuação no campeonato e PM é maior pontuação obtida no campeonato.

Datas

Datas importantes:

Código malicioso

Os códigos dos alunos serão analisados para ver se contém comandos maliciosos, como tentatva de subverter código do gerenciador ou de colegas, tentativa indevida de acesso ao sistema de arquivos local, tentativa indevida de acesso à rede, etc. Quaisquer arquivos fonte que contiverem comandos considerados maliciosos serão descartados e o aluno que os tiver submetido receberá zero na disicplina como punição, sem prejuízo de outras sanções.

MC346 Home

© 2014 João Meidanis