Sommaire
Bonjour à tous,
Relativement nouveau dans le domaine de la programmation, je m’entraîne sur différents sites. L'un d'entre eux propose des problèmes sous forme de jeux et je bloque un peu sur un en particulier. Si je poste ici c'est parce que :
- j’apprécie cette communauté et je sais que des gens compétents viennent régulièrement ici
- le but du problème en question est caché : on connaît les variables en input et on doit donner en output une lettre (A, B, C, D ou E). À la fin du programme, on obtient un score qui est plus ou moins élevé. La première partie du problème consiste donc à découvrir le fonctionnement de ce jeu. C’est pourquoi je ne veux pas poster un message sur leur forum afin de ne pas trop en dévoiler.
Le jeu
Voici à quoi ressemble l’algorithme au départ avant de commencer le jeu :
import sys
import math
# Auto-generated code below aims at helping you parse
# the standard input according to the problem statement.
first_init_input = int(input())
second_init_input = int(input())
third_init_input = int(input())
# game loop
while True:
first_input = input()
second_input = input()
third_input = input()
fourth_input = input()
for i in range(third_init_input):
fifth_input, sixth_input = [int(j) for j in input().split()]
# Write an action using print
# To debug: print("Debug messages...", file=sys.stderr)
print("A, B, C, D or E")En affichant les différentes variables, on trouve assez rapidement leur signification et le but du jeu.
Le jeu est donc un jeu de plateau en tour par tour qui simule le jeu Pac-Man.
- Les variables d’initialisations
first_init_inputetsecond_init_inputdéterminent à la taille du plateau etthird_init_inputnous donne le nombre de joueurs sur le plateau (nombres de fantômes + 1, Pac-Man). - À chaque tour la position des joueurs est donnée par les variables
fifth_inputetsixth_input - les autres variables (
first... fourth_input) contiennent un caractère (#ou_). Ils déterminent l'environnement de Pac-Man : 4 variables pour les 4 directions dans lequel il peut aller.#correspond à un mur (impossible d'aller dans cette direction) et_à un chemin libre.
Par conséquent, la lettre donnée que l'on doit afficher donne la direction de Pac-Man pour le tour suivant. Le jeu s’arrête lorsqu'un fantôme et Pac-Man se trouve sur la même case. Plus Pac-Man explore la carte, plus notre score sera élevé.
Un algorithme relativement simple
Pour découvrir le jeu et voir ce qu'on peut faire, j'ai implémenté un algorithme dans lequel Pac-Man explore la carte sans jamais se soucier des fantômes et sans revenir en arrière. Et pour visualiser ce qu'il se passe, j'ai créé une classe.
import sys
import math
from string import ascii_uppercase
class Graph:
'''
At the beginning, all nodes are supposed to be connected
'''
def __init__(self, width, height):
self.width = width
self.height = height
self.node = {}
for y in range(self.height):
for x in range(self.width):
if x > 0:
self.addEdge(self.getNode(x, y), self.getNode(x - 1, y))
if x < self.width - 1:
self.addEdge(self.getNode(x, y), self.getNode(x + 1, y))
if y > 0:
self.addEdge(self.getNode(x, y), self.getNode(x, y - 1))
if y < self.height - 1:
self.addEdge(self.getNode(x, y), self.getNode(x, y + 1))
def getNode(self, x, y):
return str(y * self.width + x)
def addNode(self, i):
if self.node.get(i) == None:
self.node[i] = {'name': '?', 'neighbours': [], 'type': 'unknown'}
def addEdge(self, i, j):
self.addNode(i)
if not j in self.node[i]:
self.node[i]['neighbours'].append(j)
def removeEdge(self, i, j):
self.node[i]['neighbours'].remove(j)
self.node[j]['neighbours'].remove(i)
def updateNode(self, entity = None):
i = self.getNode(entity.getPos()['x'], entity.getPos()['y'])
if 0 <= int(i) <= self.width * self.height:
self.node[i]['name'] = str(entity.getName())
self.node[i]['type'] = str(entity.getType())
def constructWall(self, i):
self.node[i]['type'] = 'wall'
self.node[i]['name'] = '{:^3}'.format('#')
for n in self.node[i]['neighbours']:
self.removeEdge(n, i)
def manhatanDistance(self, pacman, ghosts):
x1 = pacman.getPos()['x']
y1 = pacman.getPos()['y']
distance = {}
direction = []
for g in ghosts:
x2 = g.getPos()['x']
y2 = g.getPos()['y']
distance[g.getName()] = abs(x1 - x2) + abs(y1 - y2)
return distance
def __str__(self):
s = ""
for y in range(self.height):
for x in range(self.width):
s = s + '{:^3}'.format(self.node[self.getNode(x, y)]['name'])
if x < self.width - 1:
s += str(' ')
if y < self.height - 1:
s += str('\n')
return str(s)
class Ghost:
def __init__(self, name, x = -1, y = -1):
self.pos = {"x": x, "y": y}
self.name = name
self.type = 'ghost'
def setPos(self, x, y):
self.pos['x'] = x
self.pos['y'] = y
def getPos(self):
return self.pos
def getName(self):
return self.name
def getType(self):
return self.type
class Pacman:
def __init__(self, x = -1, y = -1):
self.pos = {"x": x, "y": y}
self.name = 0
self.type = 'pacman'
def setPos(self, x, y):
self.pos['x'] = x
self.pos['y'] = y
self.name += 1
def getPos(self):
return self.pos
def getName(self):
return self.name
def getType(self):
return self.type
height = int(input())
width = int(input())
maze = Graph(width, height)
players = int(input())
ghosts = [Ghost(name) for name in ascii_uppercase[:(players - 1)]]
pacman = Pacman()
turn = 0
go = 'right'
# game loop
while True:
down = input() == '_'
right = input() == '_'
up = input() == '_'
left = input() == '_'
for i in range(players):
x, y = [int(j) for j in input().split()]
if i < players - 1:
ghosts[i].setPos(x, y)
maze.updateNode(ghosts[i])
else:
pacman.setPos(x, y)
maze.updateNode(pacman)
if not down:
maze.constructWall(maze.getNode(x, y - 1))
if not up:
maze.constructWall(maze.getNode(x, y + 1))
if not left:
maze.constructWall(maze.getNode(x - 1, y))
if not right:
maze.constructWall(maze.getNode(x + 1, y))
# Just don't go back where you were
if (go == 'right') & (not right):
go = [dir for dir in ["right", "left", "up", "down"] if eval(dir) & (dir != "left")][0]
if (go == 'left') & (not left):
go = [dir for dir in ["right", "left", "up", "down"] if eval(dir) & (dir != "right")][0]
if (go == 'down') & (not down):
go = [dir for dir in ["right", "left", "up", "down"] if eval(dir) & (dir != "up")][0]
if (go == 'up') & (not up):
go = [dir for dir in ["right", "left", "up", "down"] if eval(dir) & (dir != "down")][0]
dir = {"right":"A", "left":"E", "up":"D", "down":"C"}
print(dir[go])
# If I'm close to lose the game, print the maze
if min(maze.manhatanDistance(pacman, ghosts).values()) <= 2:
print(maze, file=sys.stderr)
turn += 1Le résultat juste avant de perdre ressemble à ça :
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? B B B B B B B B B B B B ? ? ? ? ? ? ? ? A A A A A A ?
? B ? ? ? ? B ? ? ? ? ? B ? ? ? ? ? ? ? ? A ? ? ? ? A ?
? B ? ? ? ? B ? ? ? ? ? B ? ? ? ? ? ? ? ? A ? ? ? ? A ?
? B ? ? ? ? B ? ? ? ? ? B ? ? ? ? ? ? ? ? A ? ? ? ? A ?
? B ? ? ? ? B B B B B B B ? ? ? ? ? A A A A A A A A A ?
? B ? ? ? ? ? ? ? B ? ? ? ? ? ? ? ? A ? ? A ? ? ? ? ? ?
? B ? ? ? ? ? ? ? B ? ? ? ? ? ? ? ? A ? ? A ? ? ? ? ? ?
? B B B B B B ? ? B B B B ? ? A A A A ? ? A ? ? ? ? ? ?
? ? ? ? ? ? B ? ? ? ? ? B ? ? A ? ? ? ? ? A ? ? ? ? ? ?
? ? ? ? ? ? B ? ? ? ? ? B ? ? A ? ? ? ? ? A ? ? ? ? ? ?
? ? ? ? ? ? B ? ? ? ? ? B B A A ? ? ? ? ? A ? ? ? ? ? ?
? ? ? ? ? ? B ? ? ? ? ? ? ? A ? ? ? ? ? ? A ? ? ? ? ? ?
? ? ? ? ? ? B ? ? ? ? A A A A B B ? ? ? ? A ? ? ? ? ? ?
? ? ? ? ? # 65 # ? ? ? ? ? ? ? ? ? ? ? ? ? A ? ? ? ? ? ?
? ? ? ? ? # 64 # ? ? ? C C C ? ? D ? ? ? ? A ? ? ? ? ? ?
? ? ? ? ? # 63 # ? ? ? ? ? C ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? # 62 # ? ? ? ? ? C C C C C C ? ? ? ? ? ? ? ? ?
? ? ? ? ? # 61 # ? ? ? ? ? ? ? ? ? ? C ? ? ? ? ? ? ? ? ?
? ? ? ? ? # 60 # ? ? ? ? ? ? ? ? ? ? C ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? 59 ? ? ? ? ? ? ? ? ? ? ? C C C C ? ? C C C ?
? ? ? ? ? # 58 # ? ? ? ? ? ? ? ? ? ? ? ? ? C ? ? ? ? C ?
? ? ? ? ? # 57 # ? ? ? ? ? # # ? # # # # # C ? ? ? ? C ?
? ? ? ? ? # 56 ? ? ? ? ? ? 1 2 3 4 5 6 7 8 C # ? C C C ?
? ? ? ? ? # 55 # ? ? ? ? ? # # # # # ? # # C # ? C ? ? ?
? # # ? # # 54 # ? ? ? ? ? ? ? ? ? ? ? ? # C # # C # # ?
# 48 49 50 51 52 53 # ? ? ? ? ? ? ? ? ? ? ? ? # C C C C 16 17 #
# 47 # # # # # ? ? ? ? ? ? ? ? ? ? ? ? ? ? # # # # # 18 #
# 46 # # # # # # # # # # ? # # ? # # # # # # # # # # 19 #
# 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 #
? # # # # # # # # # # # # # # # # # # # # # # # # # # ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
Améliorations
Voilà, maintenant j'aimerais aller un plus loin et développer un algorithme qui permettrait d'optimiser le parcours du labyrinthe pour le découvrir le plus possible.
La classe que j'ai implémenté me permet d'ajouter facilement des fonctions de recherche de chemin le plus court (BFS par exemple) entre les fantômes et Pac-Man, mais ce n'est pas ce qu'on veut ici.
Une idée que j'ai eu a été d'établir un score correspondant à la distance séparant un fantôme de Pac-Man dans une direction donnée. La direction à prendre étant celle dont le score est le plus haut. Mais après avoir implémenté cette fonction, Pac-Man s'est mis à tourner en rond sans explorer le labyrinthe.
Avez-vous des idées pour explorer le labyrinthe sans se faire attraper ? Une recherche d'IA et pacman sur un moteur de recherche ne renvoie des informations que sur l'IA des fantômes et souvent en connaissant le labyrinthe (dans ce cas une recherche de chemin le plus court marche bien).
Je reste également ouvert à toutes les critiques que vous pourriez avoir sur mon code, je ne demande qu'à progresser.
# Exploration ?
Posté par Jiehong (site web personnel) . Évalué à 2.
Salut,
Déjà, bravo pour le code. Si tu apprends, je ne peux que te conseiller d'essayer d'écrire ton code en TDD, et aussi de passer un coup de
pylint, qui va te dire pas mal de chose sur le format de ton code (comme le manque de docstring presque partout, nom de variables, trucs inutilisés, etc.).Ensuit, pour la carte, c'est pas facile à lire comme ça. Tu pourrais simplement afficher des "." si le lieu est inconnu, puis tes murs et c'est tout. Tu peux afficher une deuxième carte avec le trajet de Pacman pour voir ce qu'il fait.
De plus, tu connais la position des fantômes, et ils ne peuvent pas (?) être sur des murs. Ils te donnent donc des indications sur les emplacements possibles pour Pacman. Tu peux donc construire ta carte beaucoup plus vite (pour toi-même).
Enfin, ton problème me rappelle comment les abeilles font pour déterminer la taille et le volume d'un lieu noir avec une quantité limitée d'info : quand tu arrives à une intersection, tu peux choisir la direction d'une manière pseudo-aléatoire.
Tu pourrais aussi poursuivre les fantômes, minimiser le rebrousse chemin, etc.
Bon courage !
# Mon implémentation
Posté par daikinee . Évalué à 1.
Salut,
Pour être également sur le jeu en question, quelques pistes que j'ai implémenté et qui m'ont mené pour l'instant à un score pas trop mal :
tenir compte du mouvement des fantômes pour en déduire une partie du labyrinthe
à chaque tour sélectionner une cible parmi les cases non encore visitées : j'ai essayé différentes tentatives avec plus ou moins de succès basées sur les distances estimées (manhattan actuellement) aux fantômes et à pacman
recherche de la route la plus courte et la plus sure (affectation d'un coût de mouvement supérieur si je passe proche d'un fantôme) vers la cible
Bon courage à toi !
# Quel site ? et un possible optimisation
Posté par Xavier Combelle (site web personnel) . Évalué à 1.
Quel est le site du jeu ?
Une optimisation possible est d'essayer de s'éloigner du fantôme le plus proche en distance manhatan pour survivre plus longtemps
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.