Descrição do jogo

Pac-Man é um jogo eletrônico criado por Tōru Iwatani para a empresa Namco, e sendo distribuído para o mercado americano pela Midway Games. Produzido originalmente para Arcade no início dos anos 1980, tornou-se um dos jogos mais jogados e populares no momento, tendo versões modernas para diversos consoles e continuações para tantos outros, inclusive na atualidade.

A mecânica do jogo consiste do jogador controlar uma cabeça redonda amarela que a boca abre e fecha, percorrendo labirintos simples repletos de pastilhas e 4 fantasmas que o perseguem. Se o jogador conseguir comer todas as pastilhas sem ser tocado pelos fantasmas, ele vence o nível. Um elemento extra do jogo é a possibilidade de eliminar os fantasmas, pois, com frutas distribuídas ao longo do mapa, caso o jogador coma elas, por determinado período de tempo, a colisão com o fantasma elimina ele, e não o jogador.

Para esta versão mojificada do Pac-Man, o objetivo do jogo será mojificado. De acordo com a track disputada pelo competidor, o objetivo será:

• Agile: matar todos os fantasmas o mais rápido possível;
• Satisficing: matar todos os fantasmas e coletar o máximo de pastilhas possíveis nesse meio tempo, para ter o menor custo de movimentos que conseguir;
• Optimal: Eliminar todos os fantasmas no menor custo de movimentos;

O jogo, por não ser em tempo real como o original, será dividido em turnos, ou seja, a cada turno o Pac-Man pode se locomover uma célula, após isso, ocorrem os movimentos de todos os fantasmas, para assim o Pac-Man se mover novamente. O jogador está sempre em movimento, ou seja, independente de coletar fruta ou pastilha ou colidir com fantasma, o Pac-Man deve sempre se movimentar para algum lugar.

Além disso, apesar de não obrigatório por mapa terem todos eles, existem 3 tipos de fantasmas:

• Vermelho: se movimenta no sentido horário, mudando a direção do movimento caso ache uma parede. Ou seja, começa se movimentando para a direita, até colidir com alguma parede, depois se movimenta para baixo, depois para esquerda, depois para cima. Este fantasma nunca fica sem andar, ou seja, caso encontre uma parede, tenta andar na direção seguinte;
• Verde: o fantasma faz o mesmo movimento do Pac-Man, ou seja, caso o Pac-Man vá para baixo, este fantasma vai para baixo, caso vá para esquerda, o fantasma vai para a esquerda, e assim por diante;
• Azul: possui o movimento contrário ao Pac-Man, ou seja, caso o Pac-Man vá para baixo, este fantasma vai para cima, caso vá para esquerda, o fantasma vai para a direita, e assim por diante;

Importante ressaltar que, caso ocorra, dois fantasmas podem sim coexistir na mesma célula. Outro pormenor do jogo é, como ele acontece em turno, pode vir a acontecer do Pac-Man se mover para uma célula sem o fantasma mas o fantasma em seu turno se mover até ela. Caso isso ocorra, se o Pac-Man tiver com a fruta certa ativada, o fantasma morre, caso contrário, "game-over".

Ademais, cada fantasma possui uma fruta de mesma cor correspondente a ele, na qual, quando o jogador comer ela, poderá eliminar o fantasma a qualquer momento do jogo, em vez de como era no jogo original de apenas por um tempo determinado isso estar disponível. Um ponto importante é: o jogador não pode estar com duas frutas ativas ao mesmo tempo, ou seja, caso ele tenha comido a fruta vermelha (portanto pode comer o fantasma vermelho agora), e, alguns movimentos a seguir, ele comer a fruta azul, então agora ele apenas pode eliminar o fantasma azul.

Outra adição para o Pac-Man Mojificado são os diferentes tipos de chãos:

• Chão normal: representado por um caracter de espaço, é um chão normal, sem nada de especial. Embaixo de todo fantasma e Pac-Man, no momento de nascimento deles no jogo, tem um chão como esse;
• Chão de gelo: o Pac-Man desliza por esse tipo de chão, na direção que entra, até a última celula de gelo, entretanto, caso encontre uma parede no meio do caminho, ele baterá nela e seguirá o caminho contrário, até sair do gelo;
• Portal: O chão de portal funciona como uma ligação para outro ponto do mapa. Caso o Pac-Man entre em um portal, ele sai na outra célula de portal;

Esses diferentes tipos de chãos valem apenas para o Pac-Man, já que um fantasma flutua, e, dessa forma, não pode ser afetado nem pelo gelo e nem por portais. Vale ressaltar que, caso um fantasma esteja em cima do gelo e o pacman vá de encontro a ele, as regras de eliminação do fantasma serão aplicadas, e ele continuará seu movimento até o final do gelo, caso tenha o matado, senão, game over. O mesmo vale para os portais, o Pac-Man deverá checar se existe um fantasma tanto na entrada quanto na saída.

Pontuação do jogo

O objetivo do Pac-Man Mojificado, como progressão de aprendizado da classe, é adicionar o conceito de ACTION-COST ao domínio, ou seja, adicionar um "custo" para cada ação realizada pelo jogador. O objetivo do competidor é ter o menor custo possível. Dessa forma, as seguintes regras de jogo também serão adicionadas ao nosso Pac-Man:

• O competidor deve adicionar um sistema de pontuação em seu domínio com os conceitos de total-cost e action-cost;
• O movimento do Pac-Man de andar, para qualquer direção tem o custo de $2$;
• Caso o jogador se mova para uma célula que possua pastilha, o custo de movimento será apenas $1$;
• Caso o jogador tenha uma fruta ativa em si mesmo, o custo de seu movimento será $4$;
• Caso o jogador ande por cima do gelo, o custo total dos movimentos será proporcional ao número de células andadas, ou seja, caso ele entre no gelo, e, até sua saída (que é chegar a uma célula que não seja nem gelo e nem parede) ele ande $3$ células, o custo do movimento será $3$ vezes o número de um só movimento. Caso o jogador tenha fruta ativa, será $3 * 4$, caso não tenha, será $3 * 2$;
• Caso o jogador pegue o portal, o custo de seu movimento será o mesmo que se ele andasse para uma célula vazia, ou seja, $2$ caso não tenha fruta ativa e $4$ caso tenha;
• Caso o jogador aplique o denominado "movimento burro", ou, "dummy move", o movimento tera o dobro de seu custo normal, ou seja, sem fruta ativa custa $4$ e com fruta ativa custa $8$;
• O jogo encerra após o jogador comer o último fantasma vivo.

O dummy move referido acima é uma tentativa do jogo de emular a possibilidade do Pac-Man ficar parado. Em algumas versões do jogo o Pac-Man está sempre em movimento, em outras não, dessa forma, caso o jogador queira que o Pac-Man fique um turno parado enquanto todos os fantasmas andam, ele aplica o dummy move, tentando se mover na direção de uma parede. Por ter uma parede na frente de seu movimento, o Pac-Man não se move, mas todos os fantasmas tentam fazer seus respectivos movimentos, de acordo com a direção do dummy move.

Dessa forma, caso o jogador opte por aplicar um dummy move para a esquerda, por exemplo, o fantasma verde tentará andar para a esquerda, e o azul para a direita. Esta funcionalidade é opcional, ou seja, o jogador não possui nenhuma obrigatoriedade de tentar implementar ela, apesar de existir uma possibilidade de melhora de desempenho do código com essa mecânica.

Outro detalhe importante do dummy move é, caso tente ser realizado um dummy move e o jogador esteja em cima de um portal, o jogador não deve ativar o portal novamente, apenas realizar o dummy move. Dessa forma, para o jogador reativar um portal, depois de ter entrado em um deles, deve sair de cima dele e voltar para ele.

Descrição do problema

Você deve desenvolver um programa que leia a especificação do desafio, via stdin, obtenha o plano para a conclusão do mapa lido, e gere uma saída, via stdout, no formato especificado na descrição do trabalho. Caso não encontre um plano, encerre seu programa com um exit(120).

Ferramentas e auxiliares

Esta seção descreve as várias ferramentas auxiliares disponíveis para resolver o problema do jogo Pacman. As ferramentas estão organizadas em categorias: planejadores PDDL, planejadores HDDL, SAT-solvers e bibliotecas auxiliares. A localização e a forma de chamada de cada ferramenta estão descritas a seguir.

Planejadores PDDL

Para utilizar dos planejadores PDDL, você precisará de um modelo PDDL do jogo Pacman mojificado, crie os arquivos de domínio e problema PDDL correspondentes, chame o planejador selecionado com os parâmetros corretos. Aqui estão os planejadores PDDL disponíveis:

1. Planejadores Madagascar (M, Mp, MpC):
   • Localização: /tmp/dir/software/planners/madagascar/{M,Mp,MpC}.
2. Fast Downward:
   • Localização: /tmp/dir/software/planners/downward/fast-downward.py.
   • Localização: /tmp/dir/software/planners/downward-fdss23/fast-downward.py.
   • Localização: /tmp/dir/software/planners/scorpion-maidu/fast-downward.py.
3. Planejador em Julia:
   • Localização: /tmp/dir/software/planners/julia/planner.jl.

Planejadores HDDL

Para utilizar dos planejadores HDDL, você precisará de um modelo HDDL do jogo Pacman mojificado, crie os arquivos de domínio e problema HDDL correspondentes, chame o planejador selecionado com os parâmetros corretos. Aqui estão os planejadores HDDL disponíveis:

1. Panda:
   • Localização: /tmp/dir/software/planners/panda/panda.jar.
2. PandaPI:
   • Localização: /tmp/dir/software/planners/pandaPI/pandasolver.

SAT-solvers

Para utilizar dos SAT-solvers, você precisará de uma formulação do problema Pacman mojificado em forma de CNF (Conjunctive Normal Form). Aqui estão os SAT-solvers disponíveis e como utilizá-los:

1. Clasp:
   • Localização: /usr/bin/clasp.
2. CryptoMiniSat:
   • Localização: /usr/bin/cryptominisat.
3. MiniSat:
   • Localização: /usr/bin/minisat.
4. MiniSat+:
   • Localização: /usr/bin/minisat+.
5. PackUp:
   • Localização: /usr/bin/packup.
6. PicoSAT:
   • Localização: /usr/bin/picosat.
7. SAT4J:
   • Localização: /usr/bin/sat4j.
8. Python-SAT:
   • https://pysathq.github.io/docs/html.

Como classificar nesta modalidade

Nesta modalidade de classificação, o problema é dividido em três categorias: AGILE, SATISFICING e OPTIMAL. A pontuação é computada da seguinte forma:

• Categoria AGILE:
  • A pontuação é obtida pela fórmula $log(TEMPO\_DE\_EXECUCAO) / log(30)$.
  • Se o tempo de execução for menor ou igual a $1$ segundo, a pontuação é $1$.
  • A track tem um time limit de $30$ s.
• Categoria SATISFICING:
  • A pontuação é calculada pela fórmula $C^*/C$, onde $C^*$ é a quantidade de passos do plano de referência e $C$ é a quantidade de passos do plano encontrado.
  • Quanto menor for a quantidade de passos do plano encontrado em relação ao plano de referência, melhor será a pontuação.
  • A track tem um time limit de $180$ s.
• Categoria OPTIMAL:
  • O objetivo é responder o plano ótimo.
  • O desempenho é avaliado pela corretude do plano e não pela pontuação.
  • A track tem um time limit de $180$ s.

Entrada

A entrada é composta com um conjunto de linhas, e deverão ser lidas da entrada padrão. As linhas, da entrada, representam a matriz do jogo, com dimensões sempre retangulares. A entrada termina em EOF.

A seguir são todos os caracteres e seus respectivos significados:

• # : Indica as paredes do mapa;
• * : Indica as pastilhas;
• ␣ (Espaço Vazio) : Célula sem pastilha;
• I : Indica o chão de gelo;
• O : Indica um chão de portal;
• P : Indica onde está o Pac-Man no início do jogo;
• R : Indica onde o Fantasma Vermelho inicia o jogo;
• G : Indica onde o Fantasma Verde inicia o jogo;
• B : Indica onde o Fantasma Azul inicia o jogo;
• ! : Indica onde a Fruta Vermelha inicia o jogo;
• @ : Indica onde a Fruta Verde inicia o jogo;
• $ : Indica onde a Fruta Azul inicia o jogo;

Saída

A saída é composta por uma única linha contendo os movimentos do Pac-Man na ordem de seu acontecimento. Cada movimento é representado por uma letra sendo N para norte, S para sul, E para leste e W para oeste. As letras devem ser separadas pelo caracter ";" (ponto-vírgula). Ao final de todos os movimentos, deve ser passado o valor total dos movimentos e uma quebra de linha em sequência. Para a track Agile, como o valor total dos movimentos é irrelevante, a saída deve terminar com um 0 no final, em vez do custo dos movimentos.

Exemplo

Exemplo de entrada 1

##########
#P$*****B#
#*######*#
#*#  R #*#
#@# *! #*#
#*#    #*#
#*##**##*#
#********#
#        #
#G       #
##########

Saída para o exemplo

E;E;E;E;W;W;W;W;S;S;S;S;S;S;S;S;N;N;E;E;E;N;N;N;E;W;W;67

Saída para o exemplo na track Agile

E;E;E;E;W;W;W;W;S;S;S;S;S;S;S;S;N;N;E;E;E;N;N;N;E;W;W;0

Experimente você mesmo