Sorry, but this is just an abstraction? You just redefined the original implementation's pixels as tiles. As per the sudoku example, "pixels" are same as numeric IDs and your "tiles" are the same as numeric IDs. Inspired by the use of the name "Markov", I think a interesting followup could be the use larger neighborhood context (like n-gram) probabilistic approach. Anyway, great presentation, comparisons and problem statement/solution. :)
Pretty sure that that kernel-based version he presented first actually implements n-grams in some sense? And I agree that making this probabilistic (by counting adjacency frequencies, for example) would yield better output.
You are right in that it is just an abstraction of the existing cell based implementation. Tile maps are a common use case for games where performance is important, the approach used to perform tiling results in fewer binary image comparisons by using a hash map of tiles to a hash. This allows the algorithm to run much faster and yield interesting results as in the cell case based on defined constraints. The Markov implementation I’ve described only optimizes the tile implementation to allow the inference of constraints rather than having to rely on them being hand written. This incurs a small performance cost but produces effective results without the need to curate constraint data.
Not entirely since the 'Constraints' step can be arbitrary in tiles, but isn't in the texture version. Personally I'm working on a project where you can specify additional constraints like X minimum distance from Y tile or only X of these tiles per X area of grid. The original texture implementation functionally is the same idea, but the idea of 'constraints' and 'pixels' is just broadened.
Thanks! I don't know if there are any other resources talking about mkWFC specifically but there's some good info on WFC itself. Look at github.com/mxgmn/WaveFunctionCollapse as a good starting point :)
It looks like your increased diversity comes from including potentially undesired placements. While the Castles comparison treats the lone towers produced by MkWFC as a positive, they might not be a desired result. Same goes for MkWFC's seemingly random wall connections. The TWFC output has walls form closed loops or heading off-screen (where they presumably still form closed-loops through wrap-around); it shows "castle" walls. The MkWFC just shows randomly connected segments. The whole "castle" aspect is completely lost.
You are correct, some of the diversity in results may not actually be valuable but this is reliant of context. In some cases where the desired output may be simpler, the added diversity could be useful. This implementation only shows that a greater diversity is found in the yield but contextually it may not always make sense. The castles example makes it such that the added diversity does not yield any benefits when the context of the castle is taken into account.
In that case, you could selectively choose to ignore one of the original constraints from a tile based system to achieve the same results. The intention of the tiles for a pipe system in 21:23, was to create an image where every pipe has a starting and ending point. Which your algorithm has broken as you’ve indicated in the red box.
My implementation treats the probability of each event based on weighting the events encountered in the sample observed. If event A occurs 3 out of 5 times where as event B occurs 2 out of 5 times, the weights assigned will reflect a 60% and 40% chance respectively. I am unsure if this is the best way to handle probabilities for each event (there is probably better approaches) but it seemed to work for my needs fairly well
@@PronayP an interesting next step could be looking for other grammars or semantical relations in the source example other than immediate neighbors, that human artists might be applying intuitively. such as only placing certain furniture tiles in the same room as other furniture tiles, but not others
Great video. Can you tell me / point me to a material about what is *Left-Right constraint* or why is it so that we use it? I don't quite understand why we don't need other directions ex up, down. Thanks!
Hello, left-right is only 1 of the constraints used. We are checking a relationship where "given some left tile, what should be the right tile". Similarly we will also consider a bottom-top constraint as "given a bottom tile, what should be the top tile". This determines which tile can be placed in the cell based on our observation of tile occurances in the kernel
@@PronayP thamks a lot for the answer! I haven't yet explored the markov chains so maybe that is why I don't get it exactly. Sorry if this is a stupid follow-up question but should I understand that we define the "possible neighbours tiles" for each side of our "head" tile or is it not the case? I will check the written version of your thesis to hopefully understand it better (and explore markov chains). Thanks for sharing all this info!
@@piotrw3366 that's not a stupid follow up at all. Your understanding is correct, we will observe our kernels and establish possible neighboring tiles for our head tile. However, the term "head" tile here can cause some misunderstanding. A good way to understand the approach is to consider every observed tile as a potential "head" tile. For each of these observed tiles, we will create a chain of links. Each link describes which neighbor the observed "head" tile could have. This way we end up with a chain (Markov chain) of links(Markov links) where each tile has a list of it's potential neighboring tiles. The technical term for this is a Markov chain but in essence it is nothing more than a map of tile to array of possible neighbors.
Man, thank you so much for producing this video. You explained WFC so well. And bro, what, great job on your thesis and the implementation of the Markov chain with WFC.
Great research, I've been trying to tackle a TWFC that's fast to design and this showed me some number of ideas I hadn't considered. Symmetry especially. Thank you. Two questions though. Regarding the optimization of the process to reaching the point of real-time, how do we go about making the collapse tiling step faster? I am currently stuck with ~300ms and my only idea to make it better was some struct wrapping burst jobs shenanigan. And how to go about implementing constrains? The idea I'm going with is there are pre-implemented constrains that can be made simply by passing in some parameters (in the case of neighbooring tiles connecting to one another, just needs a delegate that takes Tile one, tile two (or null, if it's the edge of the map) and a direction and returns true if tile one can have tile two (or edge of map) in that direction or false if it can't.) and if one wants a specific constraint, designing one should be easy enough.
Sorry for my late reply, but here are my thoughts if you are still working on this. Unfortunately there's not a standard answer to this question but your strategies seem appropriate in that we want to tackle this as an implementation problem. Some approaches (like the ones you mentioned in your comment) could be threading the constraint solving, reducing any templated code that 's being used, optimize your pattern matching speed and just other general C++ (or other language) speeding techniques. To provide much more applicable advice would be hard without looking at the implementation being followed but there are numerous examples to draw inspiration from on GitHub. Late to the party but I hope that helps
If you were to use two kernel shapes, a 2x1 and a 1x2, wouldn't overlapping WFC and tiling WFC be equivalent? And if you "learned" those kernels from an example image, is that any different than the proposed method for "learning" tiling constraints?
Good question, the consideration to take is not necessarily how large the kernel shapes are in this case but rather what the goals ultimately should be. The reason we prefer tiling based WFC is to ensure scale can be achieved with tiles that contain greater detail and curating constraints on how those large detail tiles need to be placed. In Overlapping WFC however, you will lose the control that TWFC offers while relying solely on the "Color sudoku" aspect where you are doing pixel pattern matching
When propagating the constraints, is it possible to "collapse" a cell in such a way that you get an incompatible adjacency later on? Do you use backtracking, or is collapsing greedy?
It uses backtracking and not a greedy approach. Whatever cells are known to have an entropy of 1 (I.e only 1 possible outcome) are filled and the propagation proceeds to the remaining cells. The “collapse” occurs without the case of any incompatible adjacency as the propagation of data in the cell grid must always adhere to the constraints or else it cannot work. If we can’t fill the grid of cells with compatible adjacencies, the output is not solvable and will not complete
I've been thinking about this same problem, thank you for doing the research and sharing it with the rest of us! Saves me a lot of guessing!
Glad you found it helpful
Your Sudoku solution at 4:48 is incorrect; there are too many twos.
Assuming the top-left cell is 0,0: the cell at 1,1 should contain a 3.
You are right, this was a silly error on my part but thanks for pointing that out
Sorry, but this is just an abstraction? You just redefined the original implementation's pixels as tiles.
As per the sudoku example, "pixels" are same as numeric IDs and your "tiles" are the same as numeric IDs.
Inspired by the use of the name "Markov", I think a interesting followup could be the use larger neighborhood context (like n-gram) probabilistic approach.
Anyway, great presentation, comparisons and problem statement/solution. :)
Pretty sure that that kernel-based version he presented first actually implements n-grams in some sense? And I agree that making this probabilistic (by counting adjacency frequencies, for example) would yield better output.
You are right in that it is just an abstraction of the existing cell based implementation. Tile maps are a common use case for games where performance is important, the approach used to perform tiling results in fewer binary image comparisons by using a hash map of tiles to a hash.
This allows the algorithm to run much faster and yield interesting results as in the cell case based on defined constraints.
The Markov implementation I’ve described only optimizes the tile implementation to allow the inference of constraints rather than having to rely on them being hand written. This incurs a small performance cost but produces effective results without the need to curate constraint data.
Not entirely since the 'Constraints' step can be arbitrary in tiles, but isn't in the texture version. Personally I'm working on a project where you can specify additional constraints like X minimum distance from Y tile or only X of these tiles per X area of grid.
The original texture implementation functionally is the same idea, but the idea of 'constraints' and 'pixels' is just broadened.
@@PronayP Cool, thanks for the reply :)
@@chaselewis5372 Geting more hyped now!
Reminds me of solvers such as prolog. Some disjunctive logic solvers are scary performant :D
I'm a little disappointed you did not include proper algorithm complexity analysis at 21:35 and rather provided real-time measurements comparisons.
My apologies, the algorithm complexity is something I could add in an additional write up. I’ll update once I have something that describes that
Amazing, are there any other resources where I can get more information about mkwfc?
Thanks! I don't know if there are any other resources talking about mkWFC specifically but there's some good info on WFC itself. Look at github.com/mxgmn/WaveFunctionCollapse as a good starting point :)
can you add constraints (i.e. block a certain output from happening) with this ?
Yes, with Tiling WFC that is possible. Sorry for the late reply
It looks like your increased diversity comes from including potentially undesired placements. While the Castles comparison treats the lone towers produced by MkWFC as a positive, they might not be a desired result. Same goes for MkWFC's seemingly random wall connections. The TWFC output has walls form closed loops or heading off-screen (where they presumably still form closed-loops through wrap-around); it shows "castle" walls. The MkWFC just shows randomly connected segments. The whole "castle" aspect is completely lost.
You are correct, some of the diversity in results may not actually be valuable but this is reliant of context. In some cases where the desired output may be simpler, the added diversity could be useful. This implementation only shows that a greater diversity is found in the yield but contextually it may not always make sense.
The castles example makes it such that the added diversity does not yield any benefits when the context of the castle is taken into account.
In that case, you could selectively choose to ignore one of the original constraints from a tile based system to achieve the same results.
The intention of the tiles for a pipe system in 21:23, was to create an image where every pipe has a starting and ending point. Which your algorithm has broken as you’ve indicated in the red box.
About the markov chain, how do you calculate the probability of each event?
My implementation treats the probability of each event based on weighting the events encountered in the sample observed. If event A occurs 3 out of 5 times where as event B occurs 2 out of 5 times, the weights assigned will reflect a 60% and 40% chance respectively.
I am unsure if this is the best way to handle probabilities for each event (there is probably better approaches) but it seemed to work for my needs fairly well
@@PronayP an interesting next step could be looking for other grammars or semantical relations in the source example other than immediate neighbors, that human artists might be applying intuitively. such as only placing certain furniture tiles in the same room as other furniture tiles, but not others
Great video. Can you tell me / point me to a material about what is *Left-Right constraint* or why is it so that we use it?
I don't quite understand why we don't need other directions ex up, down. Thanks!
Hello, left-right is only 1 of the constraints used. We are checking a relationship where "given some left tile, what should be the right tile". Similarly we will also consider a bottom-top constraint as "given a bottom tile, what should be the top tile". This determines which tile can be placed in the cell based on our observation of tile occurances in the kernel
@@PronayP thamks a lot for the answer! I haven't yet explored the markov chains so maybe that is why I don't get it exactly.
Sorry if this is a stupid follow-up question but should I understand that we define the "possible neighbours tiles" for each side of our "head" tile or is it not the case? I will check the written version of your thesis to hopefully understand it better (and explore markov chains). Thanks for sharing all this info!
@@piotrw3366 that's not a stupid follow up at all. Your understanding is correct, we will observe our kernels and establish possible neighboring tiles for our head tile. However, the term "head" tile here can cause some misunderstanding. A good way to understand the approach is to consider every observed tile as a potential "head" tile. For each of these observed tiles, we will create a chain of links. Each link describes which neighbor the observed "head" tile could have. This way we end up with a chain (Markov chain) of links(Markov links) where each tile has a list of it's potential neighboring tiles.
The technical term for this is a Markov chain but in essence it is nothing more than a map of tile to array of possible neighbors.
At 4:17 isn't the box in the top left supposed to remove the 2 as an option and not the 3?
You are right, good callout. Although I am not sure I will be editing this video anytime soon unfortunately :P
Man, thank you so much for producing this video. You explained WFC so well. And bro, what, great job on your thesis and the implementation of the Markov chain with WFC.
Thank you!
Great research, I've been trying to tackle a TWFC that's fast to design and this showed me some number of ideas I hadn't considered. Symmetry especially. Thank you. Two questions though. Regarding the optimization of the process to reaching the point of real-time, how do we go about making the collapse tiling step faster? I am currently stuck with ~300ms and my only idea to make it better was some struct wrapping burst jobs shenanigan. And how to go about implementing constrains? The idea I'm going with is there are pre-implemented constrains that can be made simply by passing in some parameters (in the case of neighbooring tiles connecting to one another, just needs a delegate that takes Tile one, tile two (or null, if it's the edge of the map) and a direction and returns true if tile one can have tile two (or edge of map) in that direction or false if it can't.) and if one wants a specific constraint, designing one should be easy enough.
Sorry for my late reply, but here are my thoughts if you are still working on this. Unfortunately there's not a standard answer to this question but your strategies seem appropriate in that we want to tackle this as an implementation problem. Some approaches (like the ones you mentioned in your comment) could be threading the constraint solving, reducing any templated code that 's being used, optimize your pattern matching speed and just other general C++ (or other language) speeding techniques.
To provide much more applicable advice would be hard without looking at the implementation being followed but there are numerous examples to draw inspiration from on GitHub. Late to the party but I hope that helps
brilliant
does it work for 3D ?
My implementation does not but in general WFC can be applied to any dimensions so 2D, 3D even nD in theory
If you were to use two kernel shapes, a 2x1 and a 1x2, wouldn't overlapping WFC and tiling WFC be equivalent? And if you "learned" those kernels from an example image, is that any different than the proposed method for "learning" tiling constraints?
Good question, the consideration to take is not necessarily how large the kernel shapes are in this case but rather what the goals ultimately should be. The reason we prefer tiling based WFC is to ensure scale can be achieved with tiles that contain greater detail and curating constraints on how those large detail tiles need to be placed. In Overlapping WFC however, you will lose the control that TWFC offers while relying solely on the "Color sudoku" aspect where you are doing pixel pattern matching
Great video 👍💯
Thank you for sharing your interesting work! Do you have link to the PDF and/or code of your thesis?
Wow! Thanks for this. What is the video sampled at 12:47?
Both are work from Oskar Stalberg, you can find them here: procedural-generation.tumblr.com/post/136630889331/httposkarstalbergcomgameplanetplanethtml
@@PronayP Thanks! Your video has sent me down a rabbit hole, I love it! thank you!
@@JeffRusch I’m very happy to hear that! I hope you enjoy your WFC rabbit hole as much as I enjoyed mine :P
I hate quantum mechanics jargon in code.
Lol I hate it too. I’m sorry if I used some of that jargon but it helps understand the concept more clearly in my biased opinion
When propagating the constraints, is it possible to "collapse" a cell in such a way that you get an incompatible adjacency later on? Do you use backtracking, or is collapsing greedy?
It uses backtracking and not a greedy approach. Whatever cells are known to have an entropy of 1 (I.e only 1 possible outcome) are filled and the propagation proceeds to the remaining cells. The “collapse” occurs without the case of any incompatible adjacency as the propagation of data in the cell grid must always adhere to the constraints or else it cannot work. If we can’t fill the grid of cells with compatible adjacencies, the output is not solvable and will not complete
you can backtrack but for smaller scale applications youll probably just wanna start over
Is your thesis available to read anywhere?
Yes it's got a write up here: www.pronay.me/thesis-markov-chain-based-wave-function-collapse/
I am still waiting on an official publication though
@@PronayP great work! thank you for sharing!
@@PronayP was the work published?