Quadrillage de jeu: liste en python

Bonjour,

Malheureusement il n'y a pas de manière intelligente de faire un tel tirage : dans le cas général, le nombre de chemin dans un graphe (ici il s'agit d'une grille 2D, c'est un cas particulier) entre deux sommets croit exponentiellement avec le nombre d'arcs (ici, les transitions entre deux cases). Ici il n'y a aucun critère pour privilégier un chemin plus qu'un autre et guider la recherche.

Du coup, sans plus de précision, la seule approche que je vois pour le moment consiste à  faire un tirage aléatoire par rapport à la position courante C récursif, (où C est initialisée D) permettant de choisir vers quelle case S se déplacer.

• on interdit toute case S voisine d'une case déjà à l'état de chemin autre que C (cela évite des culs de sacs, des carrefours et des boucles)
• si F fait partie des case S atteignable, on se jette dessus, car on a alors trouvé un chemin qui connecte D à S : on stoppe la récursion et on retourne le chemin trouvé (critère d'arrêt)
• si aucune direction n'est possible depuis la case C, alors la trajectoire en cours de construction s'est enfermée et on ne peut plus atteindre F (famine) : on stoppe la récursion et on recommence le tirage aléatoire.

Pour faire cette recherche aléatoire, on peut faire un algorithme de branchement :

• À chaque étape, on branche sur l'une des directions admissibles et on choisit aléatoirement une branche dans laquelle plonger.
• On arrête l'exploration d'une branche en cas de rejet, ou si l'on a trouvé une configuration qui atteint le critère d'arrêt.

Voici à quoi ça peut ressembler (j'utilise numpy pour avoir un code plus concis et plus lisible mais on peut s'en sortir avec des listes de listes).

#!/usr/bin/env python3

import numpy as np
import random


GROUND = 0
PATH = 1


def neighbors(a: np.array, c: tuple) -> list:
    (i, j) = c
    (m, n) = a.shape
    return [
        (i + d, j)
        for d in (-1, 1)
        if 0 <= i + d < m
    ] + [
        (i, j + d)
        for d in (-1, 1)
        if 0 <= j + d < n
    ]


def is_valid_neighbor(a: np.array, c: tuple, s: tuple) -> bool:
    if a[s] == PATH:
        return False
    for s_ in neighbors(a, s):
        if a[s_] == PATH and s_ != c:
            return False
    return True


def valid_neighbors(a: np.array, c: tuple) -> list:
    return [
        s
        for s in neighbors(a, c)
        if is_valid_neighbor(a, c, s)
    ]


def branch(a: np.array, c: tuple, f: tuple) -> (np.array, bool):
    neighborhood = valid_neighbors(a, c)
    if neighborhood:
        if f in neighborhood:
            a[f] = PATH  # Critère d'arrêt
            return (a, True)
        else:
            random.shuffle(neighborhood)
            for s in neighborhood:
                a_ = a.copy()  # Important !
                a_[s] = PATH
                (a_, found) = branch(a_, s, f)
                if found:
                    return (a_, found)
    return (None, False)  # Famine


def on_border(shape: tuple, c: tuple) -> bool:
    return (
        c[0] in {0, shape[0] - 1} or
        c[1] in {0, shape[1] - 1}
    )


def find_path(shape: tuple, d: tuple, f: tuple) -> np.array:
    assert len(shape) == 2      # Grille 2D
    assert (0, 0) <= d < shape  # La case D est dans la grille
    assert (0, 0) <= f < shape  # La case F est dans la grille
    assert d != f               # Les cases D et F sont distinctes
    assert on_border(shape, d)  # La case D est sur un bord
    assert on_border(shape, f)  # La case F est sur un bord
    a = np.zeros(shape, dtype=np.uint8)
    a[d] = PATH
    (a_, found) = branch(a, d, f)
    assert found  # Il y a toujours une solution
    return a_


def main():
    shape = (3, 4)  # Matrice 3x4 
    d = (0, 0)      # Case de départ: en haut à gauche
    f = (2, 3)      # Case d'arrivée: 2e ligne (en bas), 3e colonne
    for _ in range(5):
        print(find_path(shape, d, f))
        print()

main()

Ce qui donne (sortie aléatoire) :

[[1 0 0 0]
 [1 1 1 1]
 [0 0 0 1]]

[[1 0 0 0]
 [1 1 0 0]
 [0 1 1 1]]

[[1 1 1 0]
 [0 0 1 1]
 [0 0 0 1]]

[[1 0 0 0]
 [1 1 1 0]
 [0 0 1 1]]

[[1 1 0 0]
 [0 1 1 0]
 [0 0 1 1]]

Bonne chance