Wave function collapse: Difference between revisions
Content added Content deleted
m (→{{header|C}}) |
(Rebuild the task description) |
||
| Line 1: | Line 1: | ||
{{draft task}} |
{{draft task}} |
||
{{Clarify task}} |
{{Clarify task}} |
||
The '''Wave Function Collapse''' algorithm is a heuristic for generating tiled images. |
|||
Write the solution for Wave Function Collapse based on the [https://youtu.be/rI_y2GAlQFM Coding Challenge 171: Wave Function Collapse] and create new map 8x8 tiles with fourth T-blocks with variously directions (┤ ┴ ┬ ├) or blank tiles (space). |
|||
The algorithm begins with a collection of equal sized image blocks and randomly places them, one at a time, within a grid subject to the tiling constraint and an entropy constraint, and it wraps (the top row of blocks in the grid is treated as ''adjacent'' to the bottom row of blocks, and similarly the left and right columns of blocks are treated as adjacent to each other). |
|||
The blocks are tiled within the grid. ''Tiled'' means they are placed with a one pixel overlap and the tiling constraint requires that the pixels overlapping border between two adjacent blocks match. |
|||
''Entropy'', here, means the number of blocks eligible to be placed in an unassigned grid location. The entropy constraint here is that each block is placed in a grid location with minimum entropy. (Placing a block may constrain the entropy of its four nearest neighbors -- up, down, left, right.) |
|||
For this task, we start with five blocks of 3x3 pixels and place them in an 8x8 grid to form a 17x17 tile. A tile is a block which may be tiled with itself. Here, we show these five blocks adjacent but not ''tiled'': |
|||
<table border="1px"><tr><td> |
|||
<table><tr><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td></tr><tr><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td></tr><tr><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td></tr></table> |
|||
</td><td> |
|||
<table><tr><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td></tr><tr><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td></tr><tr><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td></tr></table> |
|||
</td><td> |
|||
<table><tr><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td></tr><tr><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td></tr><tr><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td></tr></table> |
|||
</td><td> |
|||
<table><tr><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td></tr><tr><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td></tr><tr><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td></tr></table> |
|||
</td><td> |
|||
<table><tr><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td></tr><tr><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td></tr><tr><td style="background-color: white; height: 20px; width: 20px"> </td><td style="background-color: black; height: 20px; width: 20px"> </td><td style="background-color: white; height: 20px; width: 20px"> </td></tr></table> |
|||
</td></tr></table> |
|||
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 [https://www.boristhebrave.com/2020/04/13/wave-function-collapse-explained/ WFC explained] and [https://github.com/mxgmn/WaveFunctionCollapse another WFC explained] |
;Reference [https://www.boristhebrave.com/2020/04/13/wave-function-collapse-explained/ WFC explained] and [https://github.com/mxgmn/WaveFunctionCollapse another WFC explained] |
||