# "Wave Collapse Function" algorithm in Processing

**URL:** <https://discourse.processing.org/t/wave-collapse-function-algorithm-in-processing/12983>\
**Category:** Gallery\
**Created:** [July 25, 2019, 8:42pm UTC](https://discourse.processing.org/t/wave-collapse-function-algorithm-in-processing/12983 "2019-07-25T20:42:07Z")\
**Posts on this page:** 1\
**Showing post:** 2

<div class="post-metadata">

**Author:** ![solub](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/solub/32/333_2.png) [@solub](https://discourse.processing.org/u/solub)\
**Post date:** [July 31, 2019, 10:56pm UTC](https://discourse.processing.org/t/wave-collapse-function-algorithm-in-processing/12983/2 "2019-07-31T22:56:58Z")

</div>

Please find below an implementation of the “tiled model”.

![com-optimize(1)](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/7/77d6fa4b1750acc02c62aeddcfa547d241c6408c.gif)

The difference is that, unlike the “overlapping model” above, adjacency constraints are **not** inferred from a source image. As a result, constraints and frequencies (if needed) have to be entered manually (hard-coded).

**A couple of improvements**

Writing all the adjacencies of each tile can be cumbersome (especially with large tilesets) so I decided to add a _connector_-based system (inspired by this [article](https://marian42.de/article/wfc/) by Marian42) to facilitate the task. Instead of storing all the possible adjacent tiles in each direction for each tile, it is now only required to associate each face of a tile with its corresponding symmetry index. All faces sharing the same symmetry index will be adjacent.

 ![Capture%20d%E2%80%99%C3%A9cran%20(136)](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/d/d7253db0e2051eb96e04107c02f55e4267327cda.png)

Also, because most tilesets don’t come with the rotated versions of each tile, I added a mechanism that rotates a tile and stores the transformated output based on its file name.

 ![sc132](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/6/6d63d396b00c46b58405c745f4318f3894ff2926.png)

Here for example, tile “a” will be rotated 3 times at a 90-degree angle and each transformation will be added to the `tiles` array. “b” is not taken into account and “c” will be rotated only once. As a result the final array will contain 7 tiles:  
 ![Capture%20d%E2%80%99%C3%A9cran%20(134)](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/a/a8765dafbe5a282fae3444f383f2c781158cc9ec.png)

The mechanism also automatically creates and rotates the `connectors` (arrays of symmetry indices) of each new rotated tile.

**Limits**

In some cases you may want (for cosmetic reasons) to prevent a specific tile to be placed near another tile even though adjacent rules allow this placement. So far I’m writing these _avoidance rules_ (as I call them) by hand but it would be really convenient (provided it is possible) to automate that part as much as possible.

**Full script**

```auto
from random import choice, sample
from collections import deque
from java.io import File

w, h, s = 80, 45, 10
directions = ((-1, 0), (1, 0), (0, -1), (0, 1))

def setup():
    size(w*s, h*s, P2D)
    background('#FFFFFF')
    frameRate(1000)
    
    global W, A, H, tiles
    
    path = File("\Knots").listFiles()
    connectors = [(0, 1, 1, 0), (0, 0, 0, 0), (1, 0, 1, 0)]
        
    tiles = []
    count = 0
    
    # Iterating through a folder of unique tiles
    for i, png in enumerate(path):
        
        # appending tile to 'tiles' array lit
        tiles.append(loadImage(png.getAbsolutePath()))
                
        # if rotation information included in tile name --> allow rotation
        name = png.getName().split('.')[0]
        if '-' in name:

            # rotate by 90° the number of times specified in tile name 
            for rot in xrange(int(name[-1])):
                cp = tiles[-1]
                pg = createGraphics(cp.width, cp.height)
                pg.beginDraw()
                pg.pushMatrix()
                pg.translate(cp.width, 0)
                pg.rotate(HALF_PI)
                pg.image(cp, 0, 0)
                pg.popMatrix()
                pg.endDraw()
                
                # add rotated tile to 'tiles' array list
                tiles.append(pg)
  
                # create a corresponding "connector" array by rotating the indices of the previous tile
                c = deque(connectors[i + count])
                c.rotate(1)
                count += 1
                connectors.insert(i + count, tuple(c))
                
            
    ntiles = len(tiles) 

    W = dict(enumerate(tuple(set(range(ntiles)) for i in xrange(w*h)))) 
    H = dict(enumerate(sample(tuple(ntiles if i > 0 else ntiles-1 for i in xrange(w*h)), w*h)))
    A = dict(enumerate([[set() for dir in xrange(4)] for i in xrange(ntiles)]))
    
    for i1 in xrange(ntiles):
        for i2 in xrange(ntiles):
            if connectors[i1][0] == connectors[i2][2]:
                A[i1][0].add(i2)
                A[i2][1].add(i1)
                
            if connectors[i1][1] == connectors[i2][3]: 
                A[i1][2].add(i2)
                A[i2][3].add(i1)
    
                
def draw():    
    global H, W
    
    if not H:
        print 'finished'
        noLoop()
        return

    emin = min(H, key = H.get) 
    id = choice(list(W[emin]))
    W[emin] = {id}
    del H[emin]
    
    stack = {emin}
    while stack:
        idC = stack.pop() 
        for dir, t in enumerate(directions):
            x = (idC%w + t[0])%w
            y = (idC/w + t[1])%h
            idN = x + y * w 
            if idN in H: 
                possible = {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()
                        break

                    W[idN] = intersection
                    H[idN] = len(W[idN]) - random(.1)
                    stack.add(idN)
   
    image(tiles[id], (emin%w) * s, (emin/w) * s, s, s)

```

---

_[View the full topic](https://discourse.processing.org/t/wave-collapse-function-algorithm-in-processing/12983)._