Understanding the "Propagation" step

[op-rt]

Dear @Coac ,

Thank you for this clear, pythonic and efficient port of the original C# script. I learned a lot from reading it.

A point is still obscure to me, during propagation:

• Why are you starting to iterate over the neighbors of the neighbors of the collapsed cell ?
  (Every other implementation start by iterating over the 4 direct nighbors of the collapsed cell, not the neighbors of its neighbors)

• Are you iterating over neighbors that have been collapsed as well ? (updating collapsed cell ?)

• What happens when you remove the last available pattern of a cell (line 62 of propagator.py) ? (How do you handle cells with 0 patterns left ? Normally, this should throw an error)

In other words:

def propagate(cell):
        to_update = [neighbour for neighbour, _ in cell.get_neighbors()] 

       # Why putting the neighbors of the collapsed cell in the stack ?
       # Other implementations put the collapsed cell in the stack, then iterate over its neighbors

        while len(to_update) > 0:
            cell = to_update.pop(0)
            for neighbour, offset in cell.get_neighbors():

                # Usually, other implementations have an "if" statement here: "if neighbour is not collapsed:"

                for pattern_index in cell.allowed_patterns:
                    pattern = Pattern.from_index(pattern_index)
                    pattern_still_compatible = False
                    for neighbour_pattern_index in neighbour.allowed_patterns:
                        neighbour_pattern = Pattern.from_index(neighbour_pattern_index)

                        if pattern.is_compatible(neighbour_pattern, offset):
                            pattern_still_compatible = True
                            break

                    if not pattern_still_compatible:
                        cell.allowed_patterns.remove(pattern_index)  
               
                       # What happens if the cell has now 0 pattern available because of this removal ?

                        for neigh, _ in cell.get_neighbors():
                            if neigh not in to_update:
                                to_update.append(neigh)

                               # Also, what happens if you put in the stack a neighbor that a has been collapsed ?

[Coac]

Hi @solub

Why are you starting to iterate over the neighbors of the neighbors of the collapsed cell ?
(Every other implementation start by iterating over the 4 direct nighbors of the collapsed cell, not the neighbors of its neighbors)

For the popped cell, I check for its remaining possible pattern by looking to its neighbours. It's not updating its neighbours, but only the current cell.
At start, the cell in the parameter of propagate(cell), has already collapsed, it has only one pattern compatible, so no need to check again for what to remove.

Are you iterating over neighbors that have been collapsed as well ? (updating collapsed cell ?)

Yes you are right, I think it's a mistake, need to put a check to improve speed.

What happens when you remove the last available pattern of a cell (line 62 of propagator.py) ? (How do you handle cells with 0 patterns left ? Normally, this should throw an error)

I do not check for 0 pattern in propagate method, but it's inside observe, I call check_contradiction.

[op-rt]

Thank you so much for the swift reply @Coac

May I suggest a couple of minor improvements regarding that propagate function ?

For example, your stack (to_update) could be a set() instead of list. Then you wouldn't have to check if neigh not in to_update on line 65.
Also you could enumerate the pattern indices on line 51 so you can del it directly on line 62.

def propagate(cell):
        to_update = set([neighbour for neighbour, _ in cell.get_neighbors()] )

        while to_update:
            cell = to_update.pop()
            for neighbour, offset in cell.get_neighbors():

                for idP, pattern_index in enumerate(cell.allowed_patterns):
                    pattern = Pattern.from_index(pattern_index)
                    pattern_still_compatible = False
                    for neighbour_pattern_index in neighbour.allowed_patterns:
                        neighbour_pattern = Pattern.from_index(neighbour_pattern_index)

                        if pattern.is_compatible(neighbour_pattern, offset):
                            pattern_still_compatible = True
                            break

                    if not pattern_still_compatible:
                        del cell.allowed_patterns[idP]
               
                        for neigh, _ in cell.get_neighbors():
                            to_update.add(neigh)

I find your version of the propagate function very interesting because, for some reasons that I still can't explain, it is much faster than mine. (edit: apologies, I made a mistake when copying your code. Turns out the version below is much faster. Feel free to implement it in your code.)

Mine goes like this:

stack = set([emin]) # emin = index of cell with minimum entropy

while stack:
    idC = stack.pop() # index of 'current' cell

    # iterate over 4 directions (-1, 0), (1, 0), (0, -1) and (0, 1)
    for dir, t in enumerate(directions): 
  
        # make sure to wrap around
        x = (idC%w + t[0])%w   
        y = (idC/w + t[1])%h   
        idN = x + y * w    # index of 'neighboring' cell

        if E[idN] != 'c':  # If neighboring cell not marked as 'collapsed' in the entropies array 'E'

            # indices of patterns available in the neighboring cell
            available = Wave[idN]
            
            # indices of all patterns that can be placed at that neighbor location, for each pattern available in the current cell
            possible = set.union(*[A[idP][dir] for idP in Wave[idC]]) # A is a dict that contains all the legal Adjacencies in each direction, for each pattern
            
            if not available.issubset(possible):
                    intersection = possible & available 
                
                     if not intersection:
                         print 'contradiction'
                         break
                         noLoop() # some mechanism to stop the WFC algorithm
                        
                     # Updating neighboring cell with that refined list of pattern indices
                     Wave[idN] = intersection

                     # Updating entropy of that neighboring cell
                     E[idN] = len(Wave[idN])
                     
                     # Adding the neighboring cell to stack so it becomes the 'current' cell during the next while loop. The one whose 4 neighbors will be updated next
                     stack.add(idN)

[Coac]

Thanks you @solub for your insights. I will check it when I have freetime.