Wave function collapse: Difference between revisions

{{trans|J}}<langsyntaxhighlight Clang="c">#include <stdio.h>

for (int i= 0; i<td0; i++) int m= 4*k;{

for (int adj[m ]j=0; j<td1; j + t1*((t0+i-1)%t0); /* above (1) */{

adj[m+1XYZ(i,j,0,td1,4)]= XY(t1+jMOD(i-1, td0)%t1 + t1*, MOD(j, td1), itd1); /* above (index 1 in a 3x3 /* left (3grid) */

adj[m+2XYZ(i,j,1,td1,4)]= XY(MOD(i, td0), MOD(j+-1, td1)%t1, +td1); t1/* left (index 3 i;in a 3x3 /* right (5grid) */

adj[m+3XYZ(i,j,2,td1,4)]= XY(MOD(i, td0), MOD(j+1, td1), td1); /* right + t1*((index 5 in i+1)%t0);a 3x3 /* below (7grid) */

int td0bd0= tdimbdim[0], td1bd1= tdimbdim[1], td2bd2= tdimbdim[2];

char *horz= malloc(td0bd0*td0bd0); /* blocks which can sit next to each other horizontally */

for (int i= 0; i<td0bd0; i++) {

for (int j= 0; j<td0bd0; j++) {

horz[j+XY(i*td0,j,bd0)]= 1;

for (int k= 0; k<td1bd1; k++) {

if (tilesblocks[0+td2*XYZ(k+td1*i, k, 0, bd1, bd2)] != tilesblocks[XYZ(td2j, k, bd2-1)+td2*(k+td1*j, bd1, bd2)]) {

horz[j+XY(i*td0, j, bd0)]= 0;

char *vert= malloc(td0bd0*td0bd0); /* blocks which can sit next to each other vertically */

for (int i= 0; i<td0bd0; i++) {

for (int j= 0; j<td0bd0; j++) {

vert[j+XY(i*td0,j,bd0)]= 1;

for (int k= 0; k<td2bd2; k++) {

if (tilesblocks[k+td2*XYZ(0+td1*i, 0, k, bd1, bd2)] != tilesblocks[k+td2*XYZ((td2j, bd1-1)+td1*j, k, bd1, bd2)]) {

vert[j+XY(i*td0, j, bd0)]= 0;

char *memset(allow=, 1, malloc(4*stride(bd0+1)*bd0);

for (int ij= 0; ij<td0bd0; ij++) {

for allow[XYZ(int0, i, j=, 0;bd0+1, bd0)]= vert[XY(j<td0, i, bd0)]; j++/* above (north) {*/

allow[XYZ(1, i, j, bd0+1, (i*td0bd0)+j]= verthorz[XY(j, i*td0, bd0)+j]; /* aboveleft (northwest) */

allow[XYZ(2, i, j, stridebd0+1, +(i*td0bd0)+j]= horz[XY(i*td0, j, bd0)+j]; /* left right (westeast) */

allow[XYZ(2*stride)+(3, i*td0)+, j, bd0+1, bd0)]= horzvert[XY(i, j*td0, bd0)+i]; /* rightbelow (eastsouth) */

char *wave= malloc(N*td0bd0);

int *possible= calloc(td0bd0, sizeof (int));

if (td0bd0==R[i])

min= td0bd0;

for (int j= 0; j<td0bd0; j++) {

char tentropy[i]+=

wave[XY(i*td0)+, j, bd0)]=

allow[XYZ(0, td0*R[adj[K XY(todo[i],0,4)]+j], &j, bd0+1, /*bd0)] above */&

allow[XYZ(1, stride +td0*R[adj[K+XY(todo[i],1,4)]], j, bd0+j1, bd0)] & /* left */

allow[XYZ(2*stride)+td0*, R[adj[K+XY(todo[i],2,4)]]+, j], &bd0+1, bd0)] /* right */&

allow[XYZ(3*stride)+td0*, R[adj[K+XY(todo[i],3,4)]]+, j]; , bd0+1, /* below */bd0)];

int ind= ndx*td0bd0;

for (int i= 0; i<td0bd0; i++) {

char *tiledtile= malloc(t0(1+td0*t1(bd1-1))*(1+td1*td2(bd2-1)));

for (int i0= 0; i0<t0td0; i0++)

for (int i1= 0; i1<td1bd1; i1++)

for (int j0= 0; j0<t1td1; j0++)

for (int j1= 0; j1<td2bd2; j1++)

tiledtile[j1 + td2*XY(XY(j0, +j1, (t1*td1bd2-1)*, XY(i0, i1, bd1-1), 1+ td1*i0(bd2-1))]=

tilesblocks[j1 + td2*XYZ(i1 + td1*R[j0+t1*XY(i0, j0, td1)], i1, j1, bd1, bd2)];

return tiledtile;

int tdimsbdims[3]= {5,3,3};

char *tiledtile= wfc((char*)tilesblocks, tdimsbdims, size);

if (!tiledtile) exit(0);

for (int i= 0; i<2417; i++) {

for (int j= 0; j<2417; j++) {

printf("%c ", " #"[tiledtile[j+XY(i*24, j, 17)]]);

}</langsyntaxhighlight>

<pre> # # # # # #

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

# # # # #

# # # # # # # # # # #

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

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

# # # # # # #

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

# # # # #

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

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

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

# # # # # #

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

# # # # # # # #

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

# # # # # #</pre>

Implementation:<langsyntaxhighlight Jlang="j">tilesblocks=: 0,(|.@|:)^:(i.4)0,1 1 1,:0 1 0

north=: 1,~|:vert NB. adj 1 constraint

south=: 1,~|:vert NB. adj 7 constraint

west=: 1,~|:horz NB. adj 3 constrint

east=: 1,~|:horz NB. adj 5 constraint

i=: (?#m) (?#i)} i=: ,y$_1

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. And, weWe work with two kinds of tiles: the 3x3 argumentpartial tiles, and the 16x16 larger 17x17 tile which we are randomly generating. (Conceptually,17x17 ofbecause theevery argument3x3 tiles overlaps with its neighbors by one pixel, thus each argument tile onlyblock contributes a 2x2 pixel regionpixels to the result. (Perhapsand wealong shoulda makehorizontal aand onevertical pixeledge exceptionrow forand twocolumn borders inof the larger tile, whichthe we3x3 areblocks assemblingcontribute --an creatingadditional arow 17x17and tile -- but if it's actually a tile, regularitycolumn of structure in its larger tiling space suggests that that would be a bad ideapixels.))

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

<code>adj</code> indexes into <code>i</code> -- for each item in <code>i</code>, <code>adj</code> 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 constructed tile represented by <code>i</code> "wraps around" on all sides). And, <code>allow</code> lists the allowable tilesblocks corresponding to each of those <code>adj</code> constraints (there's no particular order to the items in <code>allow</code> -- it must include all four directions, but it does not matter which direction we look at "first").

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

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

Once we've assigned a tileblock to every location in <code>i</code>, we use those indices to assemble the result (the 3x3 blocks 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 tilesblocks and three runs of wave function collapse (twothree, to illustrate randomness):<lang J> (<"2) 1j1#"1 ' #'{~ tiles

task=: {{ 1j1#"1 ' #'{~ tilesblocks wfc 8 8}}

task&.>0 0 0

│ # # # # # │ # # # # │ # # # # │ # # # # # # │

│# # # # # # # # # # # # # # # # # │ # # # │# # # # # # # # # # # # │ # # # # # # # # # # # # │

│ # # # # # # │ # │ # # # # # │ # # # # # # │

│ # # # # # # # # # # # # │ # # # # # # # # # # # # # # │# # # # # # # # # # # # # # # │

│# # # # # # # # # │ # # # # # # # # │# # │ # # # # # # # # # # # # # # # # # # # │

│# # # # # # # # # # # # # # # │# # # # # # # # # # # │# # # # # # # # # # # # # # # │

│ # # # # # # # │ # # # # │ # # # │ # # # # # # # │

│# # # # # # # # # # # # # # # │ # # # # # # # # # # # # # # │# # # │ # # # # # # # # # # # # # # # # # # # # │

│ # # # # # # # │ # │ # # # # │ # # # # # # # # │

│ # # # # # # # # # # # # # # # │# # # # # # # # # # # │ # # # # # # # # # # # # # │

│# # # # # # # # # # │ # # # # # # │# # # # # # # # # # # # # # # # # # # # # # # # │

│ # # # # # # # # # # # # │# # # # # # # │ # # # │ # # # # # # # # # │

│ # # # # # # │ # # # │ # # # │ # # # # # # │

│ # # # # # # # # # # # # # # # # # # # # │# # │# # # # # # # # # # # # # │# # # # # # # # # # # │

│ # # # # # # # │ # # │# # # # │ # # # # # # │

│ # # # # # # # # # # │# # # # # # # # # # # # # # # │# # # # # # # # # # # │

│ # # # # # # # # # # # # # # # # # # # # │# # # # # # # # # # # # # # # # # # # │ # # # # # │

var tilesblocks = [

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

if (tilesblocks[0+td2*(k+td1*i)] != tilesblocks[(td2-1)+td2*(k+td1*j)]) {

if (tilesblocks[k+td2*(0+td1*i)] != tilesblocks[k+td2*((td2-1)+td1*j)]) {

allow[ (i*td0)+j] = vert[(ij*td0)+ji] /* above (north) */

allow[ stride +(i*td0)+j] = horz[(ij*td0)+ji] /* left (west) */

allow[(2*stride)+(i*td0)+j] = horz[(ji*td0)+ij] /* right (east) */

allow[(3*stride)+(i*td0)+j] = vert[(ji*td0)+ij] /* below (south) */

possible[d] = i

var tiledtile = List.filled((1+t0*t1*(td1-1))*(1+t1*(td2-1)), 0)

var t = j1 + (td2-1)*(j0 + (1+t1*(td2-1))*(i1 + (td1-1)*i0))

iftile[t] = blocks[j1 + td2*(ti1 <+ tiled.counttd1*R[j0+t1*i0]) {]

return tiledtile

var tiledtile = wfc.call(tilesblocks, tdims, size)

if (!tiledtile) return

for (i in 0..1516) {

for (j in 0..1516) {

System.write("%(" #"[tiledtile[j+i*1617]]) ")

}</langsyntaxhighlight>

# # # # #

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

# # # # # # #

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

# # # # # # #

# # # # # # # # # # #

# # # # # # #

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

# # # # # # #

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

# # # # # # # #

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

# # # # # # # #

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

# # # # # # #

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