🎮 Créer un jeu de Morpion en ligne : partie 1. Mécanique de Jeu et Rust

Introduction

Dans le but d’apprendre le rust et d’autres technologies en m’amusant. J’ai décidé de commencer un projet de jeux de morpion en rust.

À l’instar des générateurs d’avatars, c’est un projet d’exploration qui ne va pas droit au but, mais sert de fil conducteurs à divers problèmes et technologie que j’ai envie de tester dans des cas un minimum réels.

Les règles du jeu :

Si les jeux de base du Gomoku se fait sur un pavage de 15x15 elements et le gagnant gagne lors d’un 5 à la suite, j’envisage que les briques de mon jeu puissent me permettre un peu de souplesse :

• Nombre de joueurs possible entre 2 et 10.
• Taille du plateau variable.
• Nombre de coups pour gagner variable.

D’autres évolutions sont envisageables :

• variante avec besoin de n fois la suite pour gagner, peut-être jusqu’à que la grille soit complête ?
• variante sans gestion de tours.
• etc…

Poc Rust:

Pour mon projet, mon idée est de pouvoir me baser sur des 🧱 briques assez génériques pour pouvoir implémenter plein de variantes facilement.

J’ai ainsi réalisé 2 classes de base :

• MorpionBoard : le plateau de jeu qui:

  • garde le plateau en mémoire.
  • contrôle la validité des coups.
  • calcule si le jeu est gagné.

• Turn : Une surcouche d’un vecteur permettant d’itérer sur les identifiants de joueurs en boucle.

J’ai aussi pas mal joué avec les traits et la généricité de Rust, c’est super agréable d’avoir autant de liberté là-dessus, reste à savoir jusqu’où pousser le curseur, en particulier dans un projet perso. On a vite fait de vouloir rendre tout générique sans cas d’usage pertinent derrière.

Vérifier la victoire ?

Il existe divers moyens de vérifier la victoire pour un tel jeu, mais j’ai trouvé une optimisation particulièrement efficace, je cherche les segments de n éléments contenant la dernière position jouée, ainsi, je limite ainsi énormément l’espace parcouru :

Je les cherche donc pour chaque direction¹ :

    pub(super) fn check_win(&self, position: Dimension, winning_row_length: u8) -> bool {
        self.check_win_direction(position, HORIZONTAL, winning_row_length)
            || self.check_win_direction(position, VERTICAL, winning_row_length)
            || self.check_win_direction(position, DIAG_UP, winning_row_length)
            || self.check_win_direction(position, DIAG_DOWN, winning_row_length)
    }

Et je cherche pour chaque sens de ces directions le nombre d’éléments consécutifs, auquel j’ajoute l’élément d’origine.

fn count_consecutive_in_direction(&self, position: Dimension, direction: Direction) -> u8 {
    let res = self.count_consecutive_in_way(position, direction.0)
        + self.count_consecutive_in_way(position, direction.1)
        + 1;

Ainsi si j’obtiens pour une direction, une longueur égale ou supérieure à la valeur pour gagner, je sais donc que le dernier coup a été gagnant.

Ce mécanisme est très efficace.

Tentative de parallélisme

Par ailleurs, pour m’amuser², j’ai tenté d’aller encore plus loin à l’aide des scoped threads de Rust. L’idée est de séparer le travail en plusieurs tâches réalisé séparément, si possible en parallèle grâce à l’existence de plusieurs cœurs sur la machine :

    pub(super) fn check_win_multiple_core(&self, position: Dimension, winning_row_length: u8) -> bool {
        let (mut h,mut v,mut du,mut dd) = (false,false,false,false);
        thread::scope(|s| {
            s.spawn(|| {
                h = self.check_win_direction(position, HORIZONTAL, winning_row_length);
            });
            s.spawn(|| {
                v = self.check_win_direction(position, VERTICAL, winning_row_length);
            });
            s.spawn(|| {
                du = self.check_win_direction(position, DIAG_UP, winning_row_length);
            });
            s.spawn(|| {
                dd = self.check_win_direction(position, DIAG_DOWN, winning_row_length);
            });
        });
        h || v || du || dd
    }

Mais il s’avère que cette solution qui divise le travail en 4 calculs n’est pas optimal du tout. Après un test rapide avec criterion, le temps explose (ça reste très court cependant).

En effet, le coût de création des threads est beaucoup trop grand par rapport au coût du parcours de quelques éléments dans chaque direction. Pour que ça soit intéressant, il faudrait donc beaucoup plus d’éléments à parcourir d’une part, mais probablement aussi de quoi pouvoir arrêter les threads dès que l’un d’entre a fini le travail, une sorte de « ou optimisé en multicœur » en quelque-sorte.

La mécanique de scoped threads reste néanmoins super intéressante et facile à mettre en place, il me manque juste une bonne raison de l’utiliser.

Gestion des chaînes de caractères

La gestion des chaînes de caractères en rust s’avère un peu difficile provenant du python. Il est ainsi impossible d’avoir des constantes facilement pour le modèle du format des chaînes avec la macro println! car le 1er paramètre est nécessairement une valeur littérale :

const mon_text: &str = "🌷";
const pattern: &str = "--{}--";
fn main() {
    println!("--{}--", "🍓"); // --🍓--
    println!("--{}--", mon_text); // --🌷--
    println!(pattern, mon_text); // error: format argument must be a string literal
}

Je ne trouve pas cela super souple. Après un peu de recherche, j’ai finalement contourné pour partie le problème avec une solution, plus complexe, mais plus générique : l’internationalisation via fluent, avec les packages i18n-embed et i18n-embed-fl ainsi un peu de code, on peut arriver à faire des choses comme ça :

/i18n/fr/morpion.ftl:

game-title = Jeu de Morpion
user-turn = Tour du joueur {$name} utilisant le symbole '{$p_char}':

/i18n/eo/morpion.ftl:

game-title = Ludo de Morpion
user-turn = Vico de la ludanto {$name} kun la simbolo '{$p_char}':

/src/main.rs:

println!("{}", fl!("game-title"));
println!(
    "{}",
    fl!(
        "user-turn",
        name = players_data.names[&player_id],
        p_char = format!("{}", players_data.symbols[&player_id])
    )
);

Ce n’est pas encore parfait (je n’aime pas trop les « {} »), mais c’est déjà plus pratique, et j’ai obtenu, d’une pierre, deux coups :

• un mécanisme assez souple pour gérer des chaînes de caractères permettant de séparer un peu le code des jeux, du texte utilisé dans le jeu.
• la possibilité de gérer différentes langues. Dans mon cas, le français, l’espéranto et l’anglais.

Interface CLI

La première version du projet est toute simple en ligne de commande³ :

À suivre…