search

mxgmn / WaveFunctionCollapse

Bitmap & tilemap generation from a single example with the help of ideas from quantum mechanics
Other
23.18k stars 1.24k forks source link

Code cleanup suggestion #20

Closed petersvp closed 7 years ago

petersvp commented 7 years ago

Hi. It will be good if you divide away the I/O part from actual logic part so we can actually extract whatever we need. I also suggest thinking about adding a C++ implementation. Also i'm getting too much contradictions if I specify high image sizes for some samples.

kchapelier commented 7 years ago

Regarding the C++ implementation, you might want to check the port by Emil Ernerfeldt https://github.com/emilk/wfc

nanodeath commented 7 years ago

Not speaking for the maintainer here, but there are a lot of little enhancements that could be made to this codebase, but I'm not necessarily sure that we should make them. I'm treating this repo as a "reference implementation" for how (algorithmically) to do various things, and not how to, uh, actually organize code. If there was another C# version that was usable as a library (along with the inevitable C/Java/whatever ports that spring up), that would be the optimal place to put optimizations like the one you're speaking of, IMO. Just a thought.

nanodeath commented 7 years ago

A wild bot appears!

mxgmn commented 7 years ago

@petersvp You can try setting periodic="False" for smaller contradiction rate. To decrease them even further I would have to modify the algorithm: adding backtracking or Merrell's heuristic.

Asmageddon commented 7 years ago

@mxgmn I believe what @petersvp wanted to suggest was making the code easier to dissect, which I think is a valid recommendation.

Also, out of curiosity, what is Merrell's heuristic?

Asmageddon commented 7 years ago

Also, would it perhaps be possible to solve contradictions with backtracking not the algorithm, but rather, say, 2^X regions/pixels around the contradiction, and trying to solve again for that?

mxgmn commented 7 years ago

@Asmageddon @petersvp I don't see any particular way to make code structure better. If I make I/O completely independent from logic, I would have to sacrifice much in brevity, they are already separated quite well. If you have a specific suggestion, please make a PR.

@Asmageddon Merrell's heuristic is a heuristic Paul Merrell uses in a paper that is the main inspiration for this work, I linked it in the reference section.

2^X regions/pixels around the contradiction, and trying to solve again for that

Yeah, it's a possible alternative. It's easier to implement, but I think that Merrell's method or backtracking will be better, because contradictions have nonlocal nature.

Asmageddon commented 7 years ago

Oh, they do? I suppose that was something to be expected.