Problèmes d'implémentation de l'algorithme "Wave Collapse Function" en Python

Question

En un mot :

Ma mise en œuvre de la Fonction d'effondrement des ondes algorithme dans Python 2.7 est défectueux mais je ne parviens pas à identifier où se situe le problème. J'aurais besoin d'aide pour trouver ce que j'ai pu manquer ou faire de travers.

Quel est le Fonction d'effondrement des ondes algorithme ?

C'est un algorithme écrit en 2016 par Maxim Gumin qui peut générer des motifs procéduraux à partir d'un échantillon d'image. Vous pouvez le voir en action aquí (modèle de superposition en 2D) et aquí (modèle de tuile 3D).

Objectif de cette mise en œuvre :

Pour ramener l'algorithme (modèle de chevauchement 2D) à son essence et éviter les redondances et les maladresses de l'algorithme de la original C# script (étonnamment long et difficile à lire). Ceci est une tentative de faire une version plus courte, plus claire et plus pythique de cet algorithme.

Caractéristiques de cette mise en œuvre :

J'utilise Traitement (mode Python), un logiciel de conception visuelle qui facilite la manipulation des images (pas de PIL, pas de Matplotlib, ...). Les principaux inconvénients sont que je suis limité à Python 2.7 et que je ne peux PAS importer numpy.

Contrairement à la version originale, cette mise en œuvre :

• n'est pas orienté objet (dans son état actuel), ce qui le rend plus facile à comprendre / plus proche du pseudo-code
• utilise des tableaux 1D au lieu de tableaux 2D.
• utilise le découpage en tableaux pour la manipulation des matrices

L'algorithme (tel que je le comprends)

1/ Lire le bitmap d'entrée, stocker tous les NxN motifs et compter leurs occurrences. ( facultatif : Augmentez les données du modèle avec des rotations et des réflexions).

Par exemple, lorsque N = 3 :

2/ Pré-calculer et stocker toutes les relations d'adjacence possibles entre les motifs. Dans l'exemple ci-dessous, les motifs 207, 242, 182 et 125 peuvent chevaucher le côté droit du motif 246.

3/ Créez un tableau avec les dimensions de la sortie (appelé W pour onde). Chaque élément de ce tableau est un tableau contenant l'état ( True de False ) de chaque motif.

Par exemple, disons que nous comptons 326 modèles uniques en entrée et que nous voulons que notre sortie soit de dimensions 20 par 20 (400 cellules). Alors le tableau "Wave" contiendra 400 tableaux (20x20), chacun d'entre eux contenant 326 valeurs de boolans.

Au départ, tous les booléens sont définis comme suit True car chaque motif est autorisé à n'importe quelle position de la vague.

W = [[True for pattern in xrange(len(patterns))] for cell in xrange(20*20)]

4/ Créez un autre tableau avec les dimensions de la sortie (appelé H ). Chaque élément de ce tableau est un flottant contenant la valeur d'"entropie" de sa cellule correspondante en sortie.

L'entropie fait ici référence à Entropie de Shannon et est calculé sur la base du nombre de motifs valides à un endroit spécifique de l'onde. Plus une cellule a de motifs valides (définis sur True dans l'onde), plus son entropie est élevée.

Par exemple, pour calculer l'entropie de la cellule 22, on regarde son indice correspondant dans l'onde ( W[22] ) et comptez le nombre de booléens mis en place à True . Avec ce compte, nous pouvons maintenant calculer l'entropie avec la formule de Shannon. Le résultat de ce calcul sera alors stocké dans H au même indice H[22]

Au départ, toutes les cellules ont la même valeur d'entropie (même valeur flottante à chaque position dans la cellule). H ) puisque tous les motifs sont définis sur True pour chaque cellule.

H = [entropyValue for cell in xrange(20*20)]

Ces 4 étapes sont des étapes d'introduction, elles sont nécessaires pour initialiser l'algorithme. Maintenant commence le noyau dur de l'algorithme :

5/ Observation :

Trouvez l'index de la cellule avec le minimum non nul entropie (Notez qu'à la toute première itération, toutes les entropies sont égales, nous devons donc choisir l'indice d'une cellule au hasard).

Ensuite, on examine les motifs encore valides à l'indice correspondant dans la vague et on en choisit un au hasard, pondéré par la fréquence d'apparition de ce motif dans l'image d'entrée (choix pondéré).

Par exemple, si la valeur la plus basse dans H est à l'indice 22 ( H[22] ), nous regardons tous les modèles définis sur True à l'adresse W[22] et en choisir un au hasard en fonction du nombre de fois qu'il apparaît dans l'entrée. (Rappelez-vous qu'à l'étape 1, nous avons compté le nombre d'occurrences de chaque motif). Cela permet de s'assurer que les motifs apparaissent avec une distribution similaire dans la sortie et dans l'entrée.

6/ Effondrement :

Nous attribuons maintenant l'indice du motif sélectionné à la cellule ayant l'entropie minimale. Ce qui signifie que chaque motif à l'endroit correspondant dans la vague est fixé à False sauf pour celui qui a été choisi.

Par exemple, si le motif 246 en W[22] a été fixé à True et a été sélectionné, alors tous les autres motifs sont réglés sur False . Cellule 22 est affecté au motif 246 . En sortie, la cellule 22 sera remplie de la première couleur (coin supérieur gauche) du motif 246. (bleu dans cet exemple)

7/ Propagation :

En raison des contraintes d'adjacence, cette sélection de motifs a des conséquences sur les cellules voisines de la vague. Les tableaux de booléens correspondant aux cellules situées à gauche et à droite, au-dessus et en dessous de la cellule récemment effondrée doivent être mis à jour en conséquence.

Par exemple, si la cellule 22 a été réduit et affecté d'un motif 246 alors W[21] (à gauche), W[23] (à droite), W[2] (en haut) et W[42] (vers le bas) doivent être modifiés de manière à ce qu'ils ne gardent que les True les motifs qui sont adjacents au motif 246 .

Par exemple, en regardant l'image de l'étape 2, nous pouvons voir que seuls les motifs 207, 242, 182 et 125 peuvent être placés sur le droite du motif 246. Cela signifie que W[23] (à droite de la cellule 22 ) doit conserver les patrons 207, 242, 182 et 125 en tant que True et définir tous les autres motifs du tableau comme False . Si ces motifs ne sont plus valides (déjà mis à la valeur False en raison d'une contrainte précédente), l'algorithme est alors confronté à une contradiction .

8/ Mise à jour des entropies

Parce qu'une cellule a été réduite (un motif sélectionné, mis sur True ) et ses cellules environnantes sont mises à jour en conséquence (en fixant les motifs non adjacents à False ) l'entropie de toutes ces cellules a changé et doit être calculée à nouveau. (Rappelez-vous que l'entropie d'une cellule est corrélée au nombre de motifs valides qu'elle contient dans l'onde).

Dans l'exemple, l'entropie de la cellule 22 est maintenant de 0, ( H[22] = 0 car seul le modèle 246 est réglé sur True sur W[22] ) et l'entropie de ses cellules voisines a diminué (les motifs qui n'étaient pas adjacents au motif 246 ont été réglés sur False ).

À présent, l'algorithme arrive à la fin de la première itération et boucle sur les étapes 5 (trouver la cellule avec l'entropie minimale non nulle) à 8 (mettre à jour les entropies) jusqu'à ce que toutes les cellules soient effondrées.

Mon script

Vous aurez besoin de Traitement con Mode Python installé pour exécuter ce script. Il contient environ 80 lignes de code (court comparé aux ~1000 lignes du script original) qui sont entièrement annotées afin d'être rapidement comprises. Vous aurez également besoin de télécharger le image entrée et modifiez le chemin de la ligne 16 en conséquence.

from collections import Counter
from itertools import chain, izip
import math

d = 20  # dimensions of output (array of dxd cells)
N = 3 # dimensions of a pattern (NxN matrix)

Output = [120 for i in xrange(d*d)] # array holding the color value for each cell in the output (at start each cell is grey = 120)

def setup():
    size(800, 800, P2D)
    textSize(11)

    global W, H, A, freqs, patterns, directions, xs, ys, npat

    img = loadImage('Flowers.png') # path to the input image
    iw, ih = img.width, img.height # dimensions of input image
    xs, ys = width//d, height//d # dimensions of cells (squares) in output
    kernel = [[i + n*iw for i in xrange(N)] for n in xrange(N)] # NxN matrix to read every patterns contained in input image
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # (x, y) tuples to access the 4 neighboring cells of a collapsed cell
    all = [] # array list to store all the patterns found in input

    # Stores the different patterns found in input
    for y in xrange(ih):
        for x in xrange(iw):

            ''' The one-liner below (cmat) creates a NxN matrix with (x, y) being its top left corner.
                This matrix will wrap around the edges of the input image.
                The whole snippet reads every NxN part of the input image and store the associated colors.
                Each NxN part is called a 'pattern' (of colors). Each pattern can be rotated or flipped (not mandatory). '''

            cmat = [[img.pixels[((x+n)%iw)+(((a[0]+iw*y)/iw)%ih)*iw] for n in a] for a in kernel]

            # Storing rotated patterns (90°, 180°, 270°, 360°) 
            for r in xrange(4):
                cmat = zip(*cmat[::-1]) # +90° rotation
                all.append(cmat) 

            # Storing reflected patterns (vertical/horizontal flip)
            all.append(cmat[::-1])
            all.append([a[::-1] for a in cmat])

    # Flatten pattern matrices + count occurences 

    ''' Once every pattern has been stored,
        - we flatten them (convert to 1D) for convenience
        - count the number of occurences for each one of them (one pattern can be found multiple times in input)
        - select unique patterns only
        - store them from less common to most common (needed for weighted choice)'''

    all = [tuple(chain.from_iterable(p)) for p in all] # flattern pattern matrices (NxN --> [])
    c = Counter(all)
    freqs = sorted(c.values()) # number of occurences for each unique pattern, in sorted order
    npat = len(freqs) # number of unique patterns
    total = sum(freqs) # sum of frequencies of unique patterns
    patterns = [p[0] for p in c.most_common()[:-npat-1:-1]] # list of unique patterns sorted from less common to most common

    # Computes entropy

    ''' The entropy of a cell is correlated to the number of possible patterns that cell holds.
        The more a cell has valid patterns (set to 'True'), the higher its entropy is.
        At start, every pattern is set to 'True' for each cell. So each cell holds the same high entropy value'''

    ent = math.log(total) - sum(map(lambda x: x * math.log(x), freqs)) / total

    # Initializes the 'wave' (W), entropy (H) and adjacencies (A) array lists

    W = [[True for _ in xrange(npat)] for i in xrange(d*d)] # every pattern is set to 'True' at start, for each cell
    H = [ent for i in xrange(d*d)] # same entropy for each cell at start (every pattern is valid)
    A = [[set() for dir in xrange(len(directions))] for i in xrange(npat)] #see below for explanation

    # Compute patterns compatibilities (check if some patterns are adjacent, if so -> store them based on their location)

    ''' EXAMPLE:
    If pattern index 42 can placed to the right of pattern index 120,
    we will store this adjacency rule as follow:

                     A[120][1].add(42)

    Here '1' stands for 'right' or 'East'/'E'

    0 = left or West/W
    1 = right or East/E
    2 = up or North/N
    3 = down or South/S '''

    # Comparing patterns to each other
    for i1 in xrange(npat):
        for i2 in xrange(npat):
            for dir in (0, 2):
                if compatible(patterns[i1], patterns[i2], dir):
                    A[i1][dir].add(i2)
                    A[i2][dir+1].add(i1)

def compatible(p1, p2, dir):

    '''NOTE: 
    what is refered as 'columns' and 'rows' here below is not really columns and rows 
    since we are dealing with 1D patterns. Remember here N = 3'''

    # If the first two columns of pattern 1 == the last two columns of pattern 2 
    # --> pattern 2 can be placed to the left (0) of pattern 1
    if dir == 0:
        return [n for i, n in enumerate(p1) if i%N!=2] == [n for i, n in enumerate(p2) if i%N!=0]

    # If the first two rows of pattern 1 == the last two rows of pattern 2
    # --> pattern 2 can be placed on top (2) of pattern 1
    if dir == 2:
        return p1[:6] == p2[-6:]

def draw():    # Equivalent of a 'while' loop in Processing (all the code below will be looped over and over until all cells are collapsed)
    global H, W, grid

    ### OBSERVATION
    # Find cell with minimum non-zero entropy (not collapsed yet)

    '''Randomly select 1 cell at the first iteration (when all entropies are equal), 
       otherwise select cell with minimum non-zero entropy'''

    emin = int(random(d*d)) if frameCount <= 1 else H.index(min(H)) 

    # Stoping mechanism

    ''' When 'H' array is full of 'collapsed' cells --> stop iteration '''

    if H[emin] == 'CONT' or H[emin] == 'collapsed': 
        print 'stopped'
        noLoop()
        return

    ### COLLAPSE
    # Weighted choice of a pattern

    ''' Among the patterns available in the selected cell (the one with min entropy), 
        select one pattern randomly, weighted by the frequency that pattern appears in the input image.
        With Python 2.7 no possibility to use random.choice(x, weight) so we have to hard code the weighted choice '''

    lfreqs = [b * freqs[i] for i, b in enumerate(W[emin])] # frequencies of the patterns available in the selected cell
    weights = [float(f) / sum(lfreqs) for f in lfreqs] # normalizing these frequencies
    cumsum = [sum(weights[:i]) for i in xrange(1, len(weights)+1)] # cumulative sums of normalized frequencies
    r = random(1)
    idP = sum([cs < r for cs in cumsum])  # index of selected pattern 

    # Set all patterns to False except for the one that has been chosen   
    W[emin] = [0 if i != idP else 1 for i, b in enumerate(W[emin])]

    # Marking selected cell as 'collapsed' in H (array of entropies)
    H[emin] = 'collapsed' 

    # Storing first color (top left corner) of the selected pattern at the location of the collapsed cell
    Output[emin] = patterns[idP][0]

    ### PROPAGATION
    # For each neighbor (left, right, up, down) of the recently collapsed cell
    for dir, t in enumerate(directions):
        x = (emin%d + t[0])%d
        y = (emin/d + t[1])%d
        idN = x + y * d #index of neighbor

        # If that neighbor hasn't been collapsed yet
        if H[idN] != 'collapsed': 

            # Check indices of all available patterns in that neighboring cell
            available = [i for i, b in enumerate(W[idN]) if b]

            # Among these indices, select indices of patterns that can be adjacent to the collapsed cell at this location
            intersection = A[idP][dir] & set(available) 

            # If the neighboring cell contains indices of patterns that can be adjacent to the collapsed cell
            if intersection:

                # Remove indices of all other patterns that cannot be adjacent to the collapsed cell
                W[idN] = [True if i in list(intersection) else False for i in xrange(npat)]

                ### Update entropy of that neighboring cell accordingly (less patterns = lower entropy)

                # If only 1 pattern available left, no need to compute entropy because entropy is necessarily 0
                if len(intersection) == 1: 
                    H[idN] = '0' # Putting a str at this location in 'H' (array of entropies) so that it doesn't return 0 (float) when looking for minimum entropy (min(H)) at next iteration

                # If more than 1 pattern available left --> compute/update entropy + add noise (to prevent cells to share the same minimum entropy value)
                else:
                    lfreqs = [b * f for b, f in izip(W[idN], freqs) if b] 
                    ent = math.log(sum(lfreqs)) - sum(map(lambda x: x * math.log(x), lfreqs)) / sum(lfreqs)
                    H[idN] = ent + random(.001)

            # If no index of adjacent pattern in the list of pattern indices of the neighboring cell
            # --> mark cell as a 'contradiction'
            else:
                H[idN] = 'CONT'

    # Draw output

    ''' dxd grid of cells (squares) filled with their corresponding color.      
        That color is the first (top-left) color of the pattern assigned to that cell '''

    for i, c in enumerate(Output):
        x, y = i%d, i/d
        fill(c)
        rect(x * xs, y * ys, xs, ys)

        # Displaying corresponding entropy value
        fill(0)
        text(H[i], x * xs + xs/2 - 12, y * ys + ys/2)

Problème

Malgré tous mes efforts pour mettre soigneusement en code toutes les étapes décrites ci-dessus, cette implémentation renvoie des résultats très étranges et décevants :

Exemple d'une sortie 20x20

La distribution des motifs et les contraintes d'adjacence semblent à respecter (même quantité de couleurs bleues, vertes, jaunes et brunes que dans l'entrée et mêmes type de motifs : sol horizontal, tiges vertes).

Cependant, ces modèles :

• sont souvent déconnectés
• sont souvent incomplètes (absence de "têtes" composées de 4 pétales jaunes)
• se heurter à beaucoup trop d'états contradictoires (cellules grises marquées "CONT")

Sur ce dernier point, je dois préciser que les états contradictoires sont normaux mais ne devraient se produire que très rarement (comme indiqué au milieu de la page 6 du document este et dans este article)

Des heures de débogage m'ont convaincu que les étapes d'introduction (1 à 5) sont correctes (comptage et stockage des motifs, calculs d'adjacence et d'entropie, initialisation des tableaux). Cela m'a conduit à penser que quelque chose doit être désactivé avec la partie centrale de l'algorithme (étapes 6 à 8) . Soit je n'applique pas correctement l'une de ces étapes, soit il me manque un élément clé de la logique.

Toute aide à ce sujet serait donc immensément appréciée !

De plus, toute réponse basée sur le script fourni (utilisant Processing ou non) est la bienvenue. .

Ressources supplémentaires utiles :

Ce document détaillé article de Stephen Sherratt et cette explication papier de Karth & Smith. Par ailleurs, à titre de comparaison, je vous suggère de consulter cet autre site Mise en œuvre de Python (contient un mécanisme de retour en arrière qui n'est pas obligatoire) .

Note : J'ai fait de mon mieux pour rendre cette question aussi claire que possible (explication complète avec des GIFs et des illustrations, code entièrement annoté avec des liens et des ressources utiles) mais si, pour une raison quelconque, vous décidez de la rejeter, veuillez laisser un bref commentaire pour expliquer pourquoi vous le faites.

Answer 1

L'hypothèse suggérée par @mbrig et @Leon selon laquelle l'étape de propagation itère sur une pile entière de cellules (au lieu d'être limitée à un ensemble de 4 voisins directs) était correcte. Ce qui suit est une tentative de fournir des détails supplémentaires tout en répondant à mes propres questions.

Le problème est survenu à l'étape 7, lors de la propagation. L'algorithme original met à jour les 4 voisins directs d'une cellule spécifique MAIS :

• l'indice de cette cellule spécifique est à leur tour remplacés par les indices des voisins précédemment mis à jour .
• ce processus en cascade est déclenché à chaque fois qu'une cellule est effondrée
• et enfin tant que les motifs adjacents d'une cellule spécifique sont disponibles dans une de ses cellules voisines.

En d'autres termes, et comme mentionné dans les commentaires, il s'agit d'une récursif type de propagation qui met à jour non seulement les voisins de la cellule effondrée, mais aussi les voisins des voisins... et ainsi de suite tant que des adjacences sont possibles.

Algorithme détaillé

Une fois qu'une cellule est écrasée, son index est placé dans une pile. Cette pile sera utilisée plus tard pour temporairement stocker les indices des cellules voisines

stack = set([emin]) #emin = index of cell with minimum entropy that has been collapsed

La propagation durera aussi longtemps que cette pile sera remplie d'indices :

while stack:

La première chose que nous faisons est pop() le dernier indice contenu dans la pile (le seul pour l'instant) et obtenir les indices de ses 4 cellules voisines (E, W, N, S). Nous devons les garder à l'intérieur des limites et nous assurer qu'ils s'enroulent autour.

while stack:
    idC = stack.pop() # index of current cell
    for dir, t in enumerate(mat):
        x = (idC%w + t[0])%w
        y = (idC/w + t[1])%h
        idN = x + y * w  # index of neighboring cell

Avant d'aller plus loin, nous nous assurons que la cellule voisine n'est pas encore effondrée (nous ne voulons pas mettre à jour une cellule qui n'a qu'un seul motif disponible) :

        if H[idN] != 'c': 

Ensuite, nous vérifions tous les modèles qui pourrait être placé à cet endroit. ex : si la cellule voisine est à gauche de la cellule courante (côté est), on regarde tous les motifs qui peuvent être placés à gauche de chaque motif contenu dans la cellule courante.

            possible = set([n for idP in W[idC] for n in A[idP][dir]])

Nous examinons également les modèles qui sont disponible sur dans la cellule voisine :

            available = W[idN]

Maintenant, nous nous assurons que la cellule voisine vraiment doivent être mis à jour. Si tous ses motifs disponibles sont déjà dans la liste de tous les motifs possibles -> il n'y a pas besoin de le mettre à jour (l'algorithme saute ce voisin et passe au suivant) :

            if not available.issubset(possible):

Cependant, s'il est no un sous-ensemble de la possible liste -> nous regardons la intersection des deux ensembles (tous les motifs qui peuvent être placés à cet endroit et qui, "par chance", sont disponibles à ce même endroit) :

                intersection = possible & available

S'ils ne se croisent pas (motifs qui auraient pu être placés là mais qui ne sont pas disponibles), cela signifie que nous sommes tombés sur une "contradiction". Nous devons arrêter tout l'algorithme WFC.

                if not intersection:
                    print 'contradiction'
                    noLoop()

Si, au contraire, ils se croisent --> nous mettons à jour la cellule voisine avec cette liste affinée d'indices de motifs :

                W[idN] = intersection

Comme cette cellule voisine a été mise à jour, son entropie doit l'être aussi :

                lfreqs = [freqs[i] for i in W[idN]]
                H[idN] = (log(sum(lfreqs)) - sum(map(lambda x: x * log(x), lfreqs)) / sum(lfreqs)) - random(.001)

Enfin, et c'est le plus important, nous ajoutons l'indice de cette cellule voisine à la pile pour qu'elle devienne la prochaine cellule de la pile. actuel cellule à tour de rôle (celle dont les voisins seront mis à jour au cours de l'épisode suivant). while boucle) :

                stack.add(idN)

Mise à jour complète du script.

from collections import Counter
from itertools import chain
from random import choice

w, h = 40, 25
N = 3

def setup():
    size(w*20, h*20, P2D)
    background('#FFFFFF')
    frameRate(1000)
    noStroke()

    global W, A, H, patterns, freqs, npat, mat, xs, ys

    img = loadImage('Flowers.png') 
    iw, ih = img.width, img.height
    xs, ys = width//w, height//h
    kernel = [[i + n*iw for i in xrange(N)] for n in xrange(N)]
    mat = ((-1, 0), (1, 0), (0, -1), (0, 1))
    all = []

    for y in xrange(ih):
        for x in xrange(iw):
            cmat = [[img.pixels[((x+n)%iw)+(((a[0]+iw*y)/iw)%ih)*iw] for n in a] for a in kernel]
            for r in xrange(4):
                cmat = zip(*cmat[::-1])
                all.append(cmat)
                all.append(cmat[::-1])
                all.append([a[::-1] for a in cmat])

    all = [tuple(chain.from_iterable(p)) for p in all] 
    c = Counter(all)
    patterns = c.keys()
    freqs = c.values()
    npat = len(freqs) 

    W = [set(range(npat)) for i in xrange(w*h)] 
    A = [[set() for dir in xrange(len(mat))] for i in xrange(npat)]
    H = [100 for i in xrange(w*h)] 

    for i1 in xrange(npat):
        for i2 in xrange(npat):
            if [n for i, n in enumerate(patterns[i1]) if i%N!=(N-1)] == [n for i, n in enumerate(patterns[i2]) if i%N!=0]:
                A[i1][0].add(i2)
                A[i2][1].add(i1)
            if patterns[i1][:(N*N)-N] == patterns[i2][N:]:
                A[i1][2].add(i2)
                A[i2][3].add(i1)

def draw():    
    global H, W

    emin = int(random(w*h)) if frameCount <= 1 else H.index(min(H)) 

    if H[emin] == 'c': 
        print 'finished'
        noLoop()

    id = choice([idP for idP in W[emin] for i in xrange(freqs[idP])])
    W[emin] = [id]
    H[emin] = 'c' 

    stack = set([emin])
    while stack:
        idC = stack.pop() 
        for dir, t in enumerate(mat):
            x = (idC%w + t[0])%w
            y = (idC/w + t[1])%h
            idN = x + y * w 
            if H[idN] != 'c': 
                possible = set([n for idP in W[idC] for n in A[idP][dir]])
                if not W[idN].issubset(possible):
                    intersection = possible & W[idN] 
                    if not intersection:
                        print 'contradiction'
                        noLoop()
                        return

                    W[idN] = intersection
                    lfreqs = [freqs[i] for i in W[idN]]
                    H[idN] = (log(sum(lfreqs)) - sum(map(lambda x: x * log(x), lfreqs)) / sum(lfreqs)) - random(.001)
                    stack.add(idN)

    fill(patterns[id][0])
    rect((emin%w) * xs, (emin/w) * ys, xs, ys)

Améliorations générales

En plus de ces corrections, j'ai également effectué quelques optimisations mineures du code pour accélérer les étapes d'observation et de propagation, et raccourcir le calcul du choix pondéré.

• La "Vague" est maintenant composée de Python fixe de indices dont la taille diminue au fur et à mesure que les cellules sont "réduites" (ce qui remplace les grandes listes de booléens de taille fixe).

• Les entropies sont stockées dans un Par défaut, dont les clés sont progressivement effacées.

• La valeur d'entropie de départ est remplacée par un nombre entier aléatoire (le premier calcul d'entropie n'est pas nécessaire puisque le niveau d'incertitude est équiprobable au départ).

• Les cellules sont affichées une fois (ce qui évite de les stocker dans un tableau et de les redessiner à chaque image).

• Le choix pondéré est maintenant une ligne unique (évitant plusieurs lignes inutiles de compréhension de liste)

Answer 2

En regardant le Démonstration en direct lié à l'un de vos exemples, et sur la base d'un examen rapide du code de l'algorithme original, je crois que votre erreur se situe dans l'étape "Propagation".

La propagation ne consiste pas seulement à mettre à jour les 4 cellules voisines de la cellule effondrée. Il faut aussi mettre à jour tous les voisins de ces cellules, puis les voisins de ces cellules, etc, de manière récursive. Pour être plus précis, dès que vous mettez à jour une seule cellule voisine, vous mettez ensuite à jour sa voisine (avant d'arriver aux autres voisines de la première cellule), c'est-à-dire des mises à jour en profondeur d'abord, et non en largeur d'abord. En tout cas, c'est ce que j'ai compris de la démo en direct.

L'implémentation du code C# de l'algorithme original est assez complexe et je ne le comprends pas entièrement, mais les points clés semblent être la création de l'objet "propagateur". aquí ainsi que la fonction Propagate elle-même, aquí .