Résoudre le jeu snake, premier essai: Pathfinding et Python

Pour mon premier projet court, je ne sais pas du tout à quoi m'attendre. François m'apprend que je dois développer en cinq jours un solveur du jeu Snake en Python. La dernière fois que j'ai joué à ce jeu ça devait être sur mon vieux Nokia 3310 et je n'ai pas le souvenir de l'avoir terminé une seule fois...

NDLR: Joachim, en stage chez marmelab depuis déjà plusieurs mois, passe la vitesse au-dessus. Il suit le parcours d'intégration standard de marmelab, fait de projets très courts dans des technos à chaque fois différentes.

Le jeu Snake

Les règles du jeu de Snake sont simples : le serpent doit manger le plus de pommes possible sans toucher ni les murs ni son propre corps. La difficulté vient du fait que la queue grandit à chaque fois que le serpent mange un fruit. Alors que le serpent avance, le joueur peut contrôler ses déplacements avec les touches haut, bas, gauche droite.

"Résoudre" le jeu, ça veut dire arriver à contrôler le serpent pour remplir tout l'écran. Vous croyez que c'est simple ?

Dessiner un serpent en Python

Mon premier reflexe a donc été de sortir mes livres python, de jeter un oeil sur les awesome-python de github.com et d'installer un linter python sur atom (linter-pylint).

Dans un premier temps je dois réaliser le snake, le solveur viendra plus tard. J'ai décidé de ne pas utiliser d'interface GUI, mais un rendu dans un terminal (pour des raisons de simplicité et parce que j'adore la console :p). Pour cela, j'affiche la grille, le serpent et la pomme avec des caractères ASCII.

La boucle de jeu

Il est temps de rendre le jeu dynamique en ajoutant la boucle principale du jeu. Elle doit gérer plusieurs tâches :

• Récupérer les actions utilisateurs
• Mettre à jour l'état du jeu
• Dessiner le jeu

while True:
    window.erase()
    window.border(0)
    window.timeout(100)

    key = window.getch()

    # (R)eset
    if key == 114 or key == 82:
        reset()

    # (Q)uit
    if key == 113 or key == 81:
        break

    if key in [KEY_UP, KEY_DOWN, KEY_LEFT, KEY_RIGHT]:
        snake.move(key)

    if snake.is_collide():
        reset()

    grid = Grid(snake, apple)
    grid.display(window)

Ensuite il a fallu réfléchir à comment faire avancer le serpent. L'astuce (trouvée sur internet) consiste à faire passer le bout de la queue devant la tête à chaque mouvement, pour cela j'utilise une liste pour ajouter et supprimer mes éléments.

def move(self, position):
	"""Move snake"""
	self.position.pop(0)
	self.position.append(position)

Pour autoriser les actions clavier, quelques recherches m'ont amené à utiliser la librairie curses.

Modèle objet

Après avoir obtenu un rendu fonctionnel en procédural, je fais un petit diagramme de classe et ajoute un peu de POO à mon jeu.

Je dois maintenant chercher comment générer la pomme aléatoirement, une petite recherche du mot clé random sur zeal et je tombe sur random.choice qui permet de faire un choix aléatoire dans une liste. Pour des questions de performance, j'évite d'utiliser une fonction récursive.

Résoudre le jeu : utilisation du Pathfinder A*

A présent il est temps de passer à la partie la plus difficile... L'algorithme qui va résoudre le jeu et terminer la partie. Après avoir entendu des expressions comme pathfinding, théorie des graphes, je me suis rappelé mes anciens cours d'école. Après plusieurs recherches, l'algorithme A star semble correspondre au besoin.

A star est un algorithme de recherche de chemin (pathfinding) entre deux points. Le chemin étant recalculé à chaque déplacement du serpent on choisira A* de préférence car il dispose d'une faible complexité comparé à d'autre comme dijkstra.

En revanche, utiliser uniquement cet algorithme ne me permet pas de finir le jeu mais seulement d'automatiser le déplacement du serpent. Et donc un premier problème se présente : A star ne peut pas calculer le chemin si le corps du serpent bloque le passage. L'idée est donc de faire patienter le serpent le temps que le chemin se libère.

Le défi n'est donc pas relevé, puisque le serpent finit toujours par se rentrer dedans. Le pathfinding n'est donc pas la bonne approche...

Conclusion

J'ai rencontré quelques problèmes, je me suis un peu emmêlé les pinceaux pour merger mes PRs. Quand je travaille seul, j'ai pour habitude de ne travailler qu'avec les branches.

L'utilisation de la libraire curses, ne permet pas de faire des print sur la sortie standard de la console, j'ai passé plusieurs heures à commenter/décommenter mon code alors qu'un simple import de la libraire logging permet de sortir les logs débugger mon application.

J'ai passé beaucoup de temps à chercher le moyen d'empêcher le serpent d'entrer dans une "zone close", la solution étant de calculer à l'avance la surface de cette zone pour la comparer a celle de sa queue.

Au final, je suis content de ce que j'ai réalisé, j'ai progressé dans le langage python et en algorithmie même si je reste un peu déçu de ne pas avoir été jusqu'au bout.

Maintenant, le snake comprend le python, comprendra t-il le React.js ? À suivre...

P.S. : Le code est disponible sur marmelab/snake_solver_one