Wave function collapse
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).
- Reference WFC explained and another WFC explained
C
<lang C>#include <assert.h>
- include <stdio.h>
- include <stdlib.h>
- include <string.h>
- include <time.h>
char tiles[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} }
};
char *wfc(char *tiles, int *tdim /* 5,3,3 */, int *target /* 8,8 */) {
int N= target[0]*target[1], t0= target[0], t1= target[1]; int *adj= calloc(N*4, sizeof (int)); for (int i= 0; i<target[0]; i++) { for (int j=0; j<t1; j++) { int k= j+t1*i; int 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) */ } } int td0= tdim[0], td1= tdim[1], td2= tdim[2]; char *horz= malloc(td0*td0); for (int i= 0; i<td0; i++) { for (int j= 0; j<td0; j++) { horz[j+i*td0]= 1; for (int k= 0; k<td1; k++) { if (tiles[0+td2*(k+td1*i)] != tiles[(td2-1)+td2*(k+td1*j)]) { horz[j+i*td0]= 0; break; } } } } char *vert= malloc(td0*td0); for (int i= 0; i<td0; i++) { for (int j= 0; j<td0; j++) { vert[j+i*td0]= 1; for (int k= 0; k<td2; k++) { if (tiles[k+td2*(0+td1*i)] != tiles[k+td2*((td2-1)+td1*j)]) { vert[j+i*td0]= 0; break; } } } } int stride= (td0+1)*td0; char *allow= malloc(4*stride); memset(allow, 1, 4*stride); for (int i= 0; i<td0; i++) { for (int j= 0; j<td0; j++) { allow[ (i*td0)+j]= vert[(i*td0)+j]; /* above (north) */ allow[ stride +(i*td0)+j]= horz[(i*td0)+j]; /* left (west) */ allow[(2*stride)+(i*td0)+j]= horz[(j*td0)+i]; /* right (east) */ allow[(3*stride)+(i*td0)+j]= vert[(j*td0)+i]; /* below (south) */ } } free(horz); free(vert); int *R= calloc(N, sizeof (int)); int *todo= calloc(N, sizeof (int)); char *wave= malloc(N*td0); int *entropy= calloc(N, sizeof (int)); int *indices= calloc(N, sizeof (int)); int min; int *possible= calloc(td0, sizeof (int)); for (int i= 0; i<N; i++) R[i]= td0; while (1) { int c= 0; for (int i= 0; i<N; i++) if (td0==R[i]) todo[c++]= i; if (!c) break; min= td0; for (int i= 0; i<c; i++) { entropy[i]= 0; for (int j= 0; j<td0; j++) { int K= 4*todo[i]; char t= 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]+= t; } 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*td0; d= 0; for (int i= 0; i<td0; 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 *tiled= malloc(t0*t1*(td1-1)*(td2-1)); for (int i0= 0; i0<t0; i0++) for (int i1= 0; i1<td1; i1++) for (int j0= 0; j0<t1; j0++) for (int j1= 0; j1<td2; j1++) tiled[j1 + (td2-1)*(j0 + t1*(i1 + (td1-1)*i0))]= tiles[j1 + td1*(i1 + td2*R[j0+t1*i0])]; free(R); return tiled;
}
int main() {
int tdims[3]= {5,3,3}; int size[2]= {8,8}; time_t t; srandom((unsigned) time(&t)); char *tiled= wfc((char*)tiles, tdims, size); if (!tiled) exit(0); for (int i= 0; i<16; i++) { for (int j= 0; j<16; j++) { printf("%c ", " #"[tiled[j+i*16]]); } printf("\n"); } exit(0);
}</lang>
Note: here we use R
where J used i
, because we use i as an index/loop counter. Also, when assembling the result at the end, it was more convenient to drop the final row and column of the small tiles. Hopefully no significant translation errors have been introduced here.
- Output:
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
J
Implementation:<lang J>tiles=: 0,(|.@|:)^:(i.4)0,1 1 1,:0 1 0 wfc=: Template:Adj=. y</lang>
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, we work with two kinds of tiles: the 3x3 argument tiles, and the 16x16 larger tile which we are randomly generating. (Conceptually, of the argument tiles overlaps with its neighbors by one pixel, thus each argument tile only contributes a 2x2 pixel region to the result. (Perhaps we should make a one pixel exception for two borders in the larger tile which we are assembling -- creating a 17x17 tile -- but if it's actually a tile, regularity of structure in its larger tiling space suggests that that would be a bad idea.))
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, wave
lists 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. Here, we drop the first row and column of each of the small tiles before assembling them.
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
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
Well, I don't know whether this task is going to be deleted or not and, as I don't fully understand it anyway, I can't say I'm bothered either way.
However, as Rdm has obviously put a lot of effort into understanding it and has written a C version, I thought I'd have a go at translating it into Wren.
It's difficult with something like this where the results are random to know whether you've translated it correctly or not but one thing I did notice about the C version is that, in the final set of loops in the wfc function, the indexing is overflowing the allocated size of the tiled array (256) getting up to 272. I don't know whether the intention was to wrap around (as tiled is a char*) but, for now, I've simply ignored indices above 255 in the Wren version. <lang ecmascript>import "random" for Random
var rand = Random.new()
var tiles = [
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 { |tiles, 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 (tiles[0+td2*(k+td1*i)] != tiles[(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 (tiles[k+td2*(0+td1*i)] != tiles[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[(i*td0)+j] /* above (north) */ allow[ stride +(i*td0)+j] = horz[(i*td0)+j] /* left (west) */ allow[(2*stride)+(i*td0)+j] = horz[(j*td0)+i] /* right (east) */ allow[(3*stride)+(i*td0)+j] = vert[(j*td0)+i] /* 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 tiled = List.filled(t0*t1*(td1-1)*(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 + t1*(i1 + (td1-1)*i0)) if (t < tiled.count) { tiled[t] = tiles[j1 + td1*(i1 + td2*R[j0+t1*i0])] } } } } } return tiled
}
var tdims = [5, 3, 3] var size = [8, 8] var tiled = wfc.call(tiles, tdims, size) if (!tiled) return for (i in 0..15) {
for (j in 0..15) { System.write("%(" #"[tiled[j+i*16]]) ") } System.print()
}</lang>
- Output:
Sample output:
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #