Wave function collapse

Wave function collapse is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

This task has been flagged for clarification. Code on this page in its current state may be flagged incorrect once this task has been clarified. See this page's Talk page for discussion.

Write the solution for Wave Function Collapse based on the Coding Challenge 171: Wave Function Collapse and create new map 8x8 tiles with fourth T-blocks with variously directions (┤ ┴ ┬ ├) or blank tiles (space).

For this task, a "tile" represents a rectangular matrix of black or white pixels which is thought of a being potentially repeated arbitrarily in all directions with a one pixel overlap with each of its adjacent neighbors. These overlap pixels must identically match with those of its neighboring tile. The "t-blocks" are, thus, partial tiles -- when we build our 8x8 collection of "t-blocks" the individual "t-blocks" must satisfy this overlap constraint with their neighbors.

Reference WFC explained and another WFC explained

C

Translation of: J

<lang C>#include <stdio.h>

1. include <stdlib.h>
2. include <string.h>
3. include <time.h>

1. define XY(row, col, width) ((col)+(row)*(width))
2. define XYZ(page, row, col, height, width) XY(XY(page, row, height), col, width)

char blocks[5][3][3]= {

   {
       {0, 0, 0},
       {0, 0, 0},
       {0, 0, 0}
   },{
       {0, 0, 0},
       {1, 1, 1},
       {0, 1, 0}
   },{
       {0, 1, 0},
       {0, 1, 1},
       {0, 1, 0}
   },{
       {0, 1, 0},
       {1, 1, 1},
       {0, 0, 0}
   },{
       {0, 1, 0},
       {1, 1, 0},
       {0, 1, 0}
   }

};

/* avoid problems with slightly negative numbers and C's X%Y */

1. define MOD(X,Y) ((Y)+(X))%(Y)

char *wfc(char *blocks, int *bdim /* 5,3,3 */, int *tdim /* 8,8 */) {

   int N= tdim[0]*tdim[1], td0= tdim[0], td1= tdim[1];
   int *adj= calloc(N*4, sizeof (int)); /* indices in R of the four adjacent blocks */
   for (int i= 0; i<td0; i++) {
       for (int j=0; j<td1; j++) {
           adj[XYZ(i,j,0,td1,4)]= XY(MOD(i-1, td0), MOD(j,   td1), td1); /* above (index 1 in a 3x3 grid) */
           adj[XYZ(i,j,1,td1,4)]= XY(MOD(i,   td0), MOD(j-1, td1), td1); /* left  (index 3 in a 3x3 grid) */
           adj[XYZ(i,j,2,td1,4)]= XY(MOD(i,   td0), MOD(j+1, td1), td1); /* right (index 5 in a 3x3 grid) */
           adj[XYZ(i,j,3,td1,4)]= XY(MOD(i+1, td0), MOD(j,   td1), td1); /* below (index 7 in a 3x3 grid) */
       }
   }
   int bd0= bdim[0], bd1= bdim[1], bd2= bdim[2];
   char *horz= malloc(bd0*bd0); /* blocks which can sit next to each other horizontally */
   for (int i= 0; i<bd0; i++) {
       for (int j= 0; j<bd0; j++) {
           horz[XY(i,j,bd0)]= 1;
           for (int k= 0; k<bd1; k++) {
               if (blocks[XYZ(i, k, 0, bd1, bd2)] != blocks[XYZ(j, k, bd2-1, bd1, bd2)]) {
                   horz[XY(i, j, bd0)]= 0;
               }
           }
       }
   }
   char *vert= malloc(bd0*bd0); /* blocks which can sit next to each other vertically */
   for (int i= 0; i<bd0; i++) {
       for (int j= 0; j<bd0; j++) {
           vert[XY(i,j,bd0)]= 1;
           for (int k= 0; k<bd2; k++) {
               if (blocks[XYZ(i, 0, k, bd1, bd2)] != blocks[XYZ(j, bd1-1, k, bd1, bd2)]) {
                   vert[XY(i, j, bd0)]= 0;
                   break;
               }
           }
       }
   }
   char *allow= malloc(4*(bd0+1)*bd0); /* all block constraints, based on neighbors */
   memset(allow, 1, 4*(bd0+1)*bd0);
   for (int i= 0; i<bd0; i++) {
       for (int j= 0; j<bd0; j++) {
           allow[XYZ(0, i, j, bd0+1, bd0)]= vert[XY(j, i, bd0)]; /* above (north) */ 
           allow[XYZ(1, i, j, bd0+1, bd0)]= horz[XY(j, i, bd0)]; /* left (west) */ 
           allow[XYZ(2, i, j, bd0+1, bd0)]= horz[XY(i, j, bd0)]; /* right (east) */ 
           allow[XYZ(3, i, j, bd0+1, bd0)]= vert[XY(i, j, bd0)]; /* below (south) */ 
       }
   }
   free(horz);
   free(vert);
   int *todo= calloc(N, sizeof (int));
   char *wave= malloc(N*bd0);
   int *entropy= calloc(N, sizeof (int));
   int *indices= calloc(N, sizeof (int));
   int min;
   int *possible= calloc(bd0, sizeof (int));
   int *R= calloc(N, sizeof (int)); /* tile expressed as list of block indices */
   for (int i= 0; i<N; i++) R[i]= bd0;
   while (1) {
       int c= 0;
       for (int i= 0; i<N; i++)
           if (bd0==R[i])
               todo[c++]= i;
       if (!c) break;
       min= bd0;
       for (int i= 0; i<c; i++) {
           entropy[i]= 0;
           for (int j= 0; j<bd0; j++) {
               int K= 4*todo[i];
               entropy[i]+=
                   wave[XY(i, j, bd0)]=
                       allow[XYZ(0, R[adj[XY(todo[i],0,4)]], j, bd0+1, bd0)] &
                       allow[XYZ(1, R[adj[XY(todo[i],1,4)]], j, bd0+1, bd0)] &
                       allow[XYZ(2, R[adj[XY(todo[i],2,4)]], j, bd0+1, bd0)] &
                       allow[XYZ(3, R[adj[XY(todo[i],3,4)]], j, bd0+1, bd0)];
           }
           if (entropy[i] < min) min= entropy[i];
       }
       if (!min) {
           free(R);
           R= NULL;
           break;
       }
       int d= 0;
       for (int i= 0; i<c; i++) {
           if (min==entropy[i]) indices[d++]= i;
       }
       int ndx= indices[random()%d];
       int ind= ndx*bd0;
       d= 0;
       for (int i= 0; i<bd0; i++) {
           if (wave[ind+i]) possible[d++]= i;
       }
       R[todo[ndx]]= possible[random()%d];
   }
   free(adj);
   free(allow);
   free(todo);
   free(wave);
   free(entropy);
   free(indices);
   free(possible);
   if (!R) return NULL;
   char *tile= malloc((1+td0*(bd1-1))*(1+td1*(bd2-1)));
   for (int i0= 0; i0<td0; i0++)
       for (int i1= 0; i1<bd1; i1++)
           for (int j0= 0; j0<td1; j0++)
               for (int j1= 0; j1<bd2; j1++)
                   tile[XY(XY(j0, j1, bd2-1), XY(i0, i1, bd1-1), 1+td1*(bd2-1))]= 
                       blocks[XYZ(R[XY(i0, j0, td1)], i1, j1, bd1, bd2)];
   free(R);
   return tile;

}

int main() {

   int bdims[3]= {5,3,3};
   int size[2]= {8,8};
   time_t t;
   srandom((unsigned) time(&t));
   char *tile= wfc((char*)blocks, bdims, size);
   if (!tile) exit(0);
   for (int i= 0; i<17; i++) {
       for (int j= 0; j<17; j++) {
           printf("%c ", " #"[tile[XY(i, j, 17)]]);
       }
       printf("\n");
   }
   free(tile);
   exit(0);

}</lang>

Note: here we use R where J used i, because we use i as an index/loop counter (other than m, y and i, the comments on the j implementation should be directly relevant here). Also, when assembling the result at the end, it was convenient to treat the block overlap issue during indexing.

Output:

      #               #   #   #
# # # #               # # # # # #
  #   #               #
# # # #               # # # # # #
      #               #   #   #
# # # # # # # # # # # #   # # # #
  #       #   #   #   #   #
# # # # # # # # # #   # # # # # #
      #           #   #       #
      # # # # # # #   # # # # #
      #   #   #   #   #   #   #
      # # # # #   # # #   # # #
      #       #   #   #   #   #
# # # # # # # #   # # # # #   # #
  #       #   #   #       #   #
# # # # # # # # # # # # # #   # #
      #               #   #   #

J

Implementation:<lang J>blocks=: 0,(|.@|:)^:(i.4)0,1 1 1,:0 1 0 wfc=: Template:Adj=: y</lang>

We work with the 3x3 partial tiles, and the larger 17x17 tile which we are randomly generating. (17x17 because every 3x3 block contributes 2x2 pixels to the result and along a horizontal and vertical edge row and column of the tile, the 3x3 blocks contribute an additional row and column of pixels.)

Here, m is the list of tiles, and i represents an 8x8 list of indexes into that list (or, conceptually whatever dimensions were specified by y, the right argument to wfc -- but for this task y will always be 8 8), with _1 being a placeholder for the case where the index hasn't been choosen -- initially, we pick a random location in i and assign an arbitrarily picked tile to that location.

adj indexes into i -- for each item in i, adj selects that item, the item "above" it, the item to the "left" of it, the item to the "right" of it and the item "below" it (with scare quotes because the tile represented by i "wraps around" on all sides). And, allow lists the allowable tiles corresponding to each of those adj constraints.

To build allow we first matched the left side of each tile with the right side of each tile (cartesian product) forming horz and similarly matched the tops and bottoms of the tiles forming vert. Then we build north which limits tiles based on the tile above it, and similarly for west, east, and south (when the adjacent tile is a _1 tile, no limit is imposed).

Once we're set up, we drop into a loop: todo selects the unchosen tile locations, wavelists for each of the unchoosen tiles (for each todo value in i we select the tiles allowed by each of its adjacent locations and find the set intersection of all of those), entropy counts how many tiles are eligible for each of those location, and min is the smallest value in entropy. ndx is a randomly picked index into todo with minimal entropy and for that location we randomly pick one of the options and update i with it. (When there's only one option remaining, "randomly pick" here means we pick that option.)

Once we've assigned a tile to every location in i, we use those indices to assemble the result (note that the 3x3 tiles overlap at their borders so we introduce a mechanism to discard the redundant pixels).

For task purposes here, we will use space to represent a white pixel and "#" to represent a black pixel. Also, because characters are narrow, we will insert a space between each of these "pixels" to better approximate a square aspect ratio.

Task example (the initial tiles and three runs of wave function collapse (three, to illustrate randomness):<lang J> (<"2) 1j1#"1 ' #'{~ tiles ┌──────┬──────┬──────┬──────┬──────┐ │ │ │ # │ # │ # │ │ │# # # │ # # │# # # │# # │ │ │ # │ # │ │ # │ └──────┴──────┴──────┴──────┴──────┘

  task=: Template:1j1
  task&.>0 0 0

┌──────────────────────────────────┬──────────────────────────────────┬──────────────────────────────────┐ │ # # # # │ # # # # # # │ # # # # # │ │# # # # # # # # # # # # # # │ # # # # # # # # # # # # # # │ # # # # # # # # # # # # │ │ # # # # # │ # # # # # # │ # # # # # # │ │ # # # # # # # # # # # # │ # # # # # # # # # # # # # # │# # # # # # # # # # # # # # # │ │ # # # # # # │ # # # # # # │ # # # # # # │ │# # # # # # # # # # # # # # # │# # # # # # # # # # # │# # # # # # # # # # # # # # # │ │ # # # # # # │ # # # # │ # # # # # # │ │# # # # # # # # # # # # # # # │ # # # # # # # # # # # │ # # # # # # # # # # # │ │ # # # # # # │ # # # # │ # # # # # # # │ │# # # # # # # # # # # # # # # │# # # # # # # # # # # │# # # # # # # # # # # # # │ │ # # # # # # │ # # # # # # │ # # # # │ │ # # # # # # # # # # # # │# # # # # # # # # # │ # # # # # # # # │ │ # # # # # │ # # # # # # │ # # # # # │ │# # # # # # # # # # # # # # │# # # # # # # # # # # # # # # │# # # # # # # # # # # │ │ # # # # │ # # # # # # │ # # # # # │ │ # # # # # # │# # # # # # # # # # # # # # # │# # # # # # # # # # # │ │ # # # # │ # # # # # # │ # # # # # │ └──────────────────────────────────┴──────────────────────────────────┴──────────────────────────────────┘</lang>

Phix

This example is incomplete. but I'm working on it... Please ensure that it meets all task requirements and remove this message.

You can [NOT YET!] run this online here.
NOTE: For discussion purposes only. I will not lose a second's sleep should this be deleted.
Marked as incorrect to dissuade anyone slavishly copying this.
Primarily intended so you can see the results, rather than this being particularly interesting code.
For the purposes of discussing this task, ignore everything below "--<boilerplate code:>".

Wren

Translation of: C

Well, I don't know whether this task is going to be deleted or not though, given the effort Rdm has put into understanding it, I'd be in favor now of letting it stand. It is after all an interesting application of an algorithm inspired by quantum mechanics to generating images.

The following is a translation of his C version. <lang ecmascript>import "random" for Random

var rand = Random.new()

var blocks = [

   0, 0, 0,
   0, 0, 0,
   0, 0, 0,
   0, 0, 0,
   1, 1, 1,
   0, 1, 0,
   0, 1, 0,
   0, 1, 1,
   0, 1, 0,
   0, 1, 0,
   1, 1, 1,
   0, 0, 0,
   0, 1, 0,
   1, 1, 0,
   0, 1, 0

]

var wfc = Fn.new { |blocks, tdim, target|

   var N   = target[0] * target[1]
   var t0  = target[0]
   var t1  = target[1]
   var adj = List.filled(4*N, 0)
   for (i in 0...t0) {
       for (j in 0...t1) {
           var k = j + t1*i
           var m = 4 * k
           adj[m  ] =     j       + t1*((t0+i-1)%t0)  /* above (1) */
           adj[m+1] = (t1+j-1)%t1 + t1*     i         /* left  (3) */
           adj[m+2] = (   j+1)%t1 + t1*     i         /* right (5) */
           adj[m+3] =     j       + t1*((   i+1)%t0)  /* below (7) */
       }
   }
   var td0 = tdim[0]
   var td1 = tdim[1]
   var td2 = tdim[2]
   var horz = List.filled(td0*td0, 0)
   for (i in 0...td0) {
       for (j in 0...td0) {
           horz[j+i*td0] = 1
           for (k in 0...td1) {
               if (blocks[0+td2*(k+td1*i)] != blocks[(td2-1)+td2*(k+td1*j)]) {
                   horz[j+i*td0] = 0
                   break
               }
           }
       }
   }
   var vert = List.filled(td0*td0, 0)
   for (i in 0...td0) {
       for (j in 0...td0) {
           vert[j+i*td0]= 1
           for (k in 0...td2) {
               if (blocks[k+td2*(0+td1*i)] != blocks[k+td2*((td2-1)+td1*j)]) {
                   vert[j+i*td0]= 0
                   break
               }
           }
       }
   }
   var stride = (td0+1) * td0
   var allow  = List.filled(4 * stride, 1)
   for (i in 0...td0) {
       for (j in 0...td0) {
           allow[           (i*td0)+j] = vert[(j*td0)+i] /* above (north) */
           allow[   stride +(i*td0)+j] = horz[(j*td0)+i] /* left  (west)  */
           allow[(2*stride)+(i*td0)+j] = horz[(i*td0)+j] /* right (east)  */
           allow[(3*stride)+(i*td0)+j] = vert[(i*td0)+j] /* below (south) */
       }
   }
   var R        = List.filled(N, td0)
   var todo     = List.filled(N, 0)
   var wave     = List.filled(N*td0, 0)
   var entropy  = List.filled(N, 0)
   var indices  = List.filled(N, 0)
   var min      = 0
   var possible = List.filled(td0, 0)
   while (true) {
       var c = 0
       for (i in 0...N) {
           if (td0 == R[i]) {
               todo[c] = i
               c = c + 1
           }
       }
       if (c == 0) break
       min = td0
       for (i in 0...c) {
           entropy[i] = 0
           for (j in 0...td0) {
               var K = 4*todo[i]
               wave[i*td0 + j] = allow[           td0*R[adj[K  ]]+j] &  /* above */
                                 allow[   stride +td0*R[adj[K+1]]+j] &  /* left  */
                                 allow[(2*stride)+td0*R[adj[K+2]]+j] &  /* right */
                                 allow[(3*stride)+td0*R[adj[K+3]]+j]    /* below */
               entropy[i] = entropy[i] + wave[i*td0 + j]
           }
           if (entropy[i] < min) min = entropy[i]
       }
       if (min == 0) {
           R = null
           break
       }
       var d = 0
       for (i in 0...c) {
           if (min == entropy[i]) {
               indices[d] = i
               d = d + 1
           }
       }
       var ndx = indices[rand.int(0, d)]
       var ind = ndx * td0
       d = 0
       for (i in 0...td0) {
           if (wave[ind+i] != 0) {
               possible[d] = i
               d = d + 1
           }
       }
       R[todo[ndx]] = possible[rand.int(0, d)]
   }
   if (!R) return null
   var tile = List.filled((1+t0*(td1-1))*(1+t1*(td2-1)), 0)
   for (i0 in 0...t0) {
       for (i1 in 0...td1) {
           for (j0 in 0...t1) {
               for (j1 in 0...td2) {
                   var t = j1 + (td2-1)*j0 + (1+t1*(td2-1))*(i1 + (td1-1)*i0)
                   tile[t] = blocks[j1 + td2*(i1 + td1*R[j0+t1*i0])]
               }
           }
       }
   }
   return tile

}

var tdims = [5, 3, 3] var size = [8, 8] var tile = wfc.call(blocks, tdims, size) if (!tile) return for (i in 0..16) {

   for (j in 0..16) {
       System.write("%(" #"[tile[j+i*17]]) ")
   }
   System.print()

}</lang>

Output:

Sample output:

  #       #       #   #       #   
# # # # # #       # # #       # # 
      #   #       #   #       #   
# # # # # #       # # # # # # # # 
  #       #       #       #       
  # # # # #       # # # # #       
  #   #   #       #   #   #       
# # # # # #       # # #   # # # # 
          #       #   #   #   #   
# # # # # # # # # # # #   # # # # 
  #   #       #       #   #       
  # # # # # # # # # # # # #       
  #       #       #       #       
# # # # # #       # # # # # # # # 
      #   #       #   #       #   
# # # # # #       # # #       # # 
  #       #       #   #       #