Spirales et chevaliers | 2. plateau et joueur

♟2026.05.15
Spirales et chevaliers | 2. plateau et joueur

Nous sommes capables de dessiner une spirale carrée. C’est sympa, mais ce n’est pas vraiment ce dont on a besoin.

Que faire ?

On doit pouvoir répondre à la question: “quelle est la prochaine case que nous pouvons colorier”. Pour rappel, en commençant avec la version “simple” du problème, avec un seul joueur:

La case ne doit pas encore être coloriée.
La case ne doit pas se trouver à un déplacement de cavalier d’échec d’une case coloriée.

Notre générateur de positions sera (peut-être) utile pour la visualisation, mais il n’est certainement pas suffisant pour répondre à la question. On doit pouvoir, déjà, retenir si une case est coloriée. Vu qu’on veut pouvoir traiter une grille “infinie”, le plus pratique sera sans doute d’utiliser un dictionnaire avec comme clé la position (ou l’index de la spirale?) et comme valeur un identifiant de joueur. Ou une couleur directement. On verra ce qui est le plus utile.

Réfléchissons par l’exemple. Si je me place au début d’un tour quelconque, que dois-je faire pour trouver la prochaine case à colorier ?

Parcourir toutes les cases (ça, je peux le faire avec mon générateur).
Si la case est coloriée, je passe.
Vérifier toutes les cases à un déplacement de cavalier: si l’une d’entre elle est coloriée, je passe.
Si j’arrive ici: je colorie.

Pour pouvoir facilement vérifier les cases “à un déplacement de cavalier”, ce sera clairement plus simple en utilisant la position comme clé. Faisons donc cela.

Petite modification préalable

Notre générateur reçoit un nombre maximal de points. Mais je ne pense pas que ce sera au générateur de déterminer quand il doit s’arrêter. Je préfèrerais que ce soit décidé ailleurs. On va donc en faire un générateur infini:

def position_generator() -> Generator[tuple[int, int], None, None]:
    x, y = 0, 0
    dx, dy = 0, 0
    length = 0
    current_pos_in_segment = 0
    cycle = itertools.cycle(SPIRAL_CYCLE)
    
    while True:
        yield x, y 
        if current_pos_in_segment == length:
            direction, dl = next(cycle)
            dx, dy = direction
            length += dl
            current_pos_in_segment = 0
        x += dx
        y += dy
        current_pos_in_segment += 1

Pour l’instant, on modifie le code de visualisation pour qu’il s’arrête, lui, après 10 points:

def show_points(positions: Iterable[tuple[int, int]]) -> None:
    plt.figure()
    i = 0
    for (x1, y1), (x2, y2) in itertools.pairwise(positions):
        if i >= 10:
            break
        plt.plot(x1, y1, 'bo')
        plt.plot([x1, x2], [y1, y2], 'k-')
        i += 1
    plt.show()

Plateau de jeu

Définissons un plateau de jeu comme un dictionnaire liant un tuple (la position) à un entier (l’identifiant de son joueur / sa couleur), qui vaudra -1 si la case n’est pas coloriée. On peut utiliser un defaultdict pour se faciliter la vie, qui attribuera la valeur -1 par défaut si la clé n’existe pas.

type Board = dict[tuple[int, int], int]

# ...

if __name__ == "__main__":
    board : Board = defaultdict(default_factory=lambda: -1)

La fonction qui générera les positions à colorier devrait prendre une forme comme ceci, je crois:

def valid_points_generator(board: Board, max_points: int) -> Generator[tuple[int, int], None, None]:
    ...

Elle devra faire appel au générateur de points. Le prochain point est le premier renvoyé par le générateur qui est libre, et qui n’est pas à un déplacement de cavalier d’échec d’un point occupé. Essayons de traduire ça en code:

def valid_points_generator(board: Board, max_points: int) -> Generator[tuple[int, int], None, None]:
    offsets = [(1, 2), (-1, 2), (2, 1), (-2, 1), (1, -2), (-1, -2), (2, -1), (-2, -1)]
    n_points = 0
    for x, y in position_generator():
        if board[(x, y)] != -1: 
            continue
        if any(board[(x+dx, y+dy)] != -1 for dx, dy in offsets):
            continue
        board[(x, y)] = 1
        n_points += 1
        yield x, y
        if n_points >= max_points:
            break

On peut faire une affichage similaire à ce qu’on faisait avant, sauf qu’on ne veut pas relier les points entre eux. En fait, renommons notre ancien show_points en show_points_with_line, et réécrivons show_points:

def show_points(positions: Iterable[tuple[int, int]]) -> None:
    plt.figure()
    for x, y in positions:
        plt.plot(x, y, 'b+')
    plt.axis('equal')
    plt.show()

Le main devient:

if __name__ == "__main__":
    board : Board = defaultdict(lambda: -1)
    
    show_points(valid_points_generator(board, 100))

Ce qui nous donne l’image:

Ce qui ressemble bien à ce qu’on est supposé obtenir. Avec 1000 points:

Pas mal du tout! Mais un peu de refactorisation est nécessaire, si on veut pouvoir étendre par la suite à différentes pièces, joueurs, etc.

Plateau de jeu: objet

La première chose, c’est que je pense que le plateau de jeu mériterait d’être un objet. Je crois que cela permettra de rendre le code plus lisible. Le rôle du Board, dans un premier temps, sera de dire si une position est libre, ou visible à partir d’une série de déplacements.

# board.py
from collections import defaultdict
from typing import Iterable

class Board:
    def __init__(self):
        self.values = defaultdict(lambda: -1)
    
    def is_available(self, position: tuple[int, int]) -> bool:
        return self.values[position] == -1
    
    def is_visible_from(self, 
                        position: tuple[int, int], 
                        offsets: Iterable[tuple[int, int]]) -> bool:
        x, y = position
        return any(self.values[x+dx, y+dy] != -1 for dx, dy in offsets)
    
    def put(self, position: tuple[int, int], value: int) -> None:
        self.values[position] = value

Et dans le fichier principal — que j’appelle pour l’instant spiral.py — il faut retirer la définition du type Board et la remplacer par un import:

# spiral.py
from board import Board

On doit aussi changer le main:

# spiral.py
if __name__ == "__main__":
    board = Board()
    # ...

Et le générateur de points doit utiliser les méthodes de Board:

# spiral.py
def valid_points_generator(board: Board, max_points: int) -> Generator[tuple[int, int], None, None]:
    offsets = [(1, 2), (-1, 2), (2, 1), (-2, 1), (1, -2), (-1, -2), (2, -1), (-2, -1)]
    n_points = 0
    for x, y in position_generator():
        if not board.is_available((x, y)): 
            continue
        if board.is_visible_from((x, y), offsets):
            continue
        board.put((x, y), 1)
        n_points += 1
        yield x, y
        if n_points >= max_points:
            break

Le joueur

On peut maintenant introduire le “joueur”, qui aura une couleur et une liste de déplacements. Il n’aura, en tout cas pour l’instant, pas trop d’autre chose à faire: utilisons simplement une dataclass:

# player.py
from typing import Iterable
from dataclasses import dataclass

@dataclass
class Player:
    color: str
    offsets: Iterable[tuple[int, int]]

Cela va nous permettre de créer le joueur dans le main et de le passer, avec donc sa “configuration”, au générateur:

# spiral.py
if __name__ == "__main__":
    board = Board()
    player = Player(color='b', offsets=[(1, 2), (-1, 2), (2, 1), (-2, 1), (1, -2), (-1, -2), (2, -1), (-2, -1)])
    show_points(valid_points_generator(board, 1000, player))

Le générateur va pouvoir transmettre ce joueur au Board: c’est maintenant lui qui sera associé à une case remplie. Pour l’affichage, on va aussi renvoyer le Player en même temps que la position.

# spiral.py
def valid_points_generator(board: Board, max_points: int, player: Player) -> Generator[tuple[int, int, Player], None, None]:
    n_points = 0
    for x, y in position_generator():
        if not board.is_available((x, y)): 
            continue
        if board.is_visible_from((x, y), player):
            continue
        board.put((x, y), player)
        n_points += 1
        yield x, y, player
        if n_points >= max_points:
            break

Le Board doit maintenant utiliser ce joueur. Le dictionnaire associera maintenant un tuple à un Player, et pour rester cohérent on utilisera None comme valeur vide par défaut. is_available est changé en conséquence. is_visible_from récupère l’offset à partir du player, et vérifie spécifiquement si la case est visible par ce joueur. Cela nous permettra, je crois, d’étendre plus facilement à plusieurs joueurs par la suite.

# board.py
from collections import defaultdict
from typing import Iterable

from player import Player

class Board:
    def __init__(self):
        self.values: dict[tuple[int, int], Player | None] = defaultdict(lambda: None)
    
    def is_available(self, position: tuple[int, int]) -> bool:
        return self.values[position] is None
    
    def is_visible_from(self, 
                        position: tuple[int, int], 
                        player: Player) -> bool:
        x, y = position
        return any(self.values[x+dx, y+dy] == player for dx, dy in player.offsets)
    
    def put(self, position: tuple[int, int], player: Player) -> None:
        self.values[position] = player

Et finalement l’affichage utilisera la couleur du joueur:

# spiral.py
def show_points(positions: Iterable[tuple[int, int, Player]]) -> None:
    plt.figure()
    for x, y, player in positions:
        plt.plot(x, y, f'{player.color}+')
    plt.axis('equal')
    plt.show()

On relance le code, et tout fonctionne toujours. Ca me parait un bon endroit pour s’arrêter.

[lien permanent]

Commentaires, remarques, erreurs qu'il faut absolument me faire remarquer? Contactez-moi sur Mastodon ou par mail (adrien@adfoucart.be)

♟2026.05.15Spirales et chevaliers | 2. plateau et joueur