Talk:Wave function collapse
Rebuilt task description
I've rebuilt the task description (and I threw in a couple example implementations, though some other algorithms would satisfy the task description). Does this seem clear enough or have I overlooked some important ambiguities? --Rdm (talk) 14:10, 11 July 2022 (UTC)
- Thanks, it is much better now. Maybe some explanation what is the adjacent, how sockets (suitable each other sides of blocks) are defined and overlapped by collapsed tiles. --Darkfrei (talk) 06:44, 12 July 2022 (UTC)
- I think the algorithm for solution should be moved to the talk page and the task described. The example as given can be summarized by letting " "=0 and "#"=1 and interpreting the tile's edges as binary numbers read clockwise:
Tile west north east south weight 1 0 0 0 0 12.8 2 2 2 2 0 12.8 3 0 2 2 2 12.8 4 2 0 2 2 12.8 5 2 2 0 2 12.8
I must fill an 8x8 grid called result using these tiles such that for n=0..6 g=0..6 east[result[n,g]]=west[result[n,g+1]] and south[result[n,g]]=[north[result[n+1,g]]. 64xTile1 would be a valid result thus far, the references suggest the result should contain tiles in relation to the number of each used in the initial image. This can be achieved:
let n[g]=count of Tile[g] used in result - weight of Tile[g] in minimize sum of n[g]2--Nigel Galloway (talk) 12:58, 12 July 2022 (UTC)
- That is an algorithm which works, but it's not the only valid approach. For example, instead of using indices, we could use a bitmask. Here, if a single bit is set, that selects the tile. If multiple bits are set, the tile has not yet been determined. The number of set bits in the bitmask here would be the entropy of that grid location.
- And/or, instead of scanning the full list of unassigned grid locations, we could instead maintain a list of unassigned grid locations for each level of entropy. For the current task example, this would be four lists, corresponding to entropy 2, 3, 4 or 5. Here, we would want data structure support locating a list entry from a grid location, and vice versa, and it would be convenient to also be tracking the length of each list. But the extra storage and data movement weight per-item would tend to be countered by the need to inspect fewer grid locations in each iteration (adding a tile to the grid would change entropy for at most four grid locations).
- There's probably other possibilities (some which might have better performance on large examples due to memory cache structures). That said... for rosettacode, it's probably best to ignore optimizations which introduce high code complexity. --Rdm (talk) 13:26, 12 July 2022 (UTC)
- One thing (which may stem from all the original stuff) I just don't get is why the task description has to redefine "Tiled" to mean "Overlapped[-by-one-matching-pixel]". It turned out very helpful to display things non-overlapping and hence in my mind they should co-exist. All the references are about making tiles from an image, and it should probably be clearer that's not done here, and/or stress those links are many times more complicated than this task requires. --Pete Lomax (talk) 00:32, 15 July 2022 (UTC)
- I believe that that "one pixel overlap" constraint is necessary to satisfy (C1) The output should contain only those NxN patterns of pixels that are present in the input from https://github.com/mxgmn/WaveFunctionCollapse
- If the tiles do not overlap, we are introducing a new bit pattern where the the edges lie side-by-side and thus some rows/columns would be duplicated where that never would have occurred in the original.
- Erm, what I was trying to say is you absolutely have to have overlapping, and indeed it defines the final result. What I don't get is why you[/they?] want to call that "Tiled". Not a massive deal. --Pete Lomax (talk) 06:03, 15 July 2022 (UTC)
- What I really want to say is "Note it is not possible to verify the correctness of an (overlapped) result, unless you highlight any mismatching pixels in some bright colour (or use a different character), or [optionally] display the result in non-overlappng mode." --Pete Lomax (talk) 19:35, 15 July 2022 (UTC)
Vote for deletion
We have been getting a bunch of new tasks lately with absolutely no verbiage or explanation of algorithm on the "task" page other than a link to "See the algorithm over there". If you can't be bothered to put summary a explanation of the algorithm, and better yet, an reference implementation, enough for a knowledgeable person to figure out how to do it, it comes across as a low effort attempt to drive traffic to somebodies monetized video / page. Not what RosettaCode is about. As it stands, I vote for deletion on this task. I have similar low opinions of Boyer-Moore string search, Knuth-Morris-Pratt string search and [[Execute_Computer/Zero]], but those are issues for other discussion pages. --Thundergnat (talk) 21:51, 8 July 2022 (UTC)
Seconded(rescinded 14/7). Also added a clarify task tag to the main page. --Pete Lomax (talk) 02:44, 9 July 2022 (UTC)- Thirded? I've added a ref to boristhebrave.com, couldn't not in the current climate. We need to define the input file set. Each tile could be represented by four numbers N S E W. The constraint is N must match S vertically and E W horizontally. The concept of least entropy is essentially Warndorf and I've explored extending that beyond Knights tour elsewhere on RC.--Nigel Galloway (talk) 09:17, 9 July 2022 (UTC)
I've made this task before this video, but based on other videos. https://github.com/darkfrei/love2d-lua-tests/blob/main/wave-function-collapse/main.lua Sorry that I cannot good explain this task, but just added the link to good description. --Darkfrei (talk) 22:09, 8 July 2022 (UTC)
- Could you derive from the Github code a completed working Lua example with input and output as you ask in the task, and post that as an solution? As it stands, the description seems disjointed. It is very short, yet includes details about things such as tile size and output characters that are difficult to understand without a documented example and more explanation in the task text. --Wherrera (talk) 00:59, 9 July 2022 (UTC)
First off... I agree with some of the general sentiments here. That said, I also think we should encourage new task authors to review the Rosetta_Code:Add_a_Task page -- especially the basic information section.
- Meanwhile, though https://github.com/mxgmn/WaveFunctionCollapse looks like an implementation with clarifying examples, but that alone would not be enough to determine the correctness of an implementation here. (What's a "sufficiently large number of outputs"?).
- That said, for a task like this, it might make sense to include the extensive contents of that README.md (discarding the image references, since they won't work here, maybe doing a little rephrasing in the language discussing them and maybe throwing in some ascii art for a critical example) from the top of the file down to (but not including) the How to build line, and then throw in a reference to that github implementation (especially since it links to other implementations).
- That said, this task might be a bit big for rosettacode. That's somewhat characteristic of media-oriented coding. So I could live with skipping it... --Rdm (talk) 07:20, 9 July 2022 (UTC)
- Also, ... after thinking about this a bit, it's not clear to me whether "edge of the image" (no adjacent pixels on one side or (for corners) two sides) should be treated as a "tile" (probably not: the other possibility, suggested by "tiling" is that each edge of a tile is connected to the opposite side of the image, meaning that we can select regions of pixels which would appear when repeating the image as a tile). But, ... I think that that kind of detail is an example of information which should go into the task description (if there was a task description). And... this gets back to the lack of any specific task examples presented here. --Rdm (talk) 07:40, 9 July 2022 (UTC)
- There's probably also a constraint that the replication tiles (e.g. 3x3 sized tiles) are "aligned" on a grid which matches that tile size. And, given the "tiling" concept, ... conceptually if we were generating an 11x11 image with 3x3 tiles we'd do something like construt a 12x12 image and then crop it to 11x11. --Rdm (talk) 08:14, 9 July 2022 (UTC)
- After playing with some implementations, I'm wondering if maybe there's a bit of smoke and mirrors in the implementation at https://github.com/mxgmn/WaveFunctionCollapse#. Edit: no smoke and mirrors -- but the adjacency constraint is only one layer of pixels deep. --Rdm (talk) 10:00, 10 July 2022 (UTC)
Solutions
How this solution with this tile blocks/ tiles of this blocks are correct in the list of rules? https://i.imgur.com/dUFA4Iw.png --Darkfrei (talk) 21:03, 10 July 2022 (UTC)
- I had several problems there. One was an off-by-one error on the size of the result. Another was that I had flipped the left/right top/bottom constraints, so the tiles were not matching up right. The implementation on the task page is fixed now. --Rdm (talk) 07:46, 11 July 2022 (UTC)
Task not to the point
The required task is not showcasing the point of the so-called wavefunction collapsing idea, which seems to be that it is fast and is able to generate neighboring tiles in a more coherent manner. The task asks for a routine that uses only 5 tile types, which are very easy to interconnect almost arbitrarily, thus becomes a little pointless (no doubt influenced by the initially linked silly youtube video). The following code that sequentially generates tiles indefinitely: <lang python>import random
def make_row(w):
conn = '0000 1101 1110 0111 1011'.split()
tiles = ' . ╠.═╩.═╣.═╦'.split('.')
r = []
while True:
p, r = r, []
for i in range(w):
t = [x for x in range(5) if (not r or conn[x][2] == conn[r[-1]][0])
and (not p or conn[x][1] == conn[p[i]][3])]
r.append(random.choice(t))
yield .join(tiles[x] for x in r)
for x in make_row(20):
print(x)</lang>
is a lot shorter and a lot more efficient than another piece of code I wrote using WFC, and the output between the two are pretty much indistinguishable.
I guess my point is that the task is still bad, but given the existing solutions, throwing them away would be a shame, so I don't know what's a good solution to this. --Katzenbaer (talk) 07:44, 12 July 2022 (UTC)
- Perhaps ironically, this is analogous to issues with quantum mechanics in general. (QM is not particularly efficient nor insightful, but it kinda works and throwing it away would be a shame.) --Rdm (talk) 10:15, 12 July 2022 (UTC)
- "QM is not insightful" hmmm, well that is just wrong. This task is not QM it is a simple problem in searching obfuscated to a degree worthy of Paddy3118. To move from "the initially linked silly youtube video" to using an initial image it is necessary to write code which can read the image, split it into tiles and convert the pixel data along each edge into a number using some sort of hash. The method I have described above can then generate possible values for result. Code is then needed to convert result into a new image. Is that too much for RC? remains to be seen.--Nigel Galloway (talk) 13:23, 12 July 2022 (UTC)
- I was referring to statements by notable physicists -- e.g. Einstein's well known "God does not play dice" (which of course, is not really a statement about dice, and not really a statement about God, but instead a statement about the nature of the simplifications employed by the theories). --Rdm (talk) 17:59, 12 July 2022 (UTC)