search

BorisTheBrave / DeBroglie

DeBroglie is a C# library implementing the Wave Function Collapse algorithm with support for additional non-local constraints, and other useful features.
https://boristhebrave.github.io/DeBroglie/
MIT License
456 stars 37 forks source link

Added MaxConsecutiveTilesConstraint #9

Closed justonia closed 5 years ago

justonia commented 5 years ago

I found this new constraint useful when I was messing around with the platformer example (especially when using an AdjacentModel).

BorisTheBrave commented 5 years ago

Interesting. There's a few issues with this before I'd approve. I appreicate this is probably more work than you are willing to invest:

1) The biggest thing is this doesn't actually catch all cases. What if you've have a cap of at most 2 in a row, and you have tile, undecided, tile in a row. This constraint should block undecided from being tile. My intuition says this should be implementable while keeping the algorithm linear time, though I haven't worked through the details.

2) I'm trying to keep the library with reasonably high quality code. As such, there's lots of ancilliary work that any new feature needs:

I can appreciate that even as is, this might be useful to others. Maybe I need an "extras" folder or something.

justonia commented 5 years ago
  1. The biggest thing is this doesn't actually catch all cases. What if you've have a cap of at most 2 in a row, and you have tile, undecided, tile in a row. This constraint should block undecided from being tile. My intuition says this should be implementable while keeping the algorithm linear time, though I haven't worked through the details.

So just to be clear, it's consecutive max not total in row. Is the issue here that my implementation would ban a tile after it has been placed (thus forcing a contradiction), instead of looking in advance what should be blocked? If this is what you mean I'm pretty confident linear time would be doable.

  1. I'm trying to keep the library with reasonably high quality code. As such, there's lots of ancilliary work that any new feature needs:
  • Unit test
  • Support in DeBroglieConfig.cs
  • Docs
  • At least one sample demonstrating usage

Docs and maybe some tests might be doable, but the other two are probably out-of-scope for what I have time for since my repro case motivating this constraint is deeply tied into my Unity workflow at the moment.

BorisTheBrave commented 5 years ago

my implementation would ban a tile after it has been placed

Yes, exactly.

the other two are probably out-of-scope

Ok. How about I add a link from the custom constraints docs to your branch, rather than merging, then?

justonia commented 5 years ago

my implementation would ban a tile after it has been placed

Yes, exactly.

the other two are probably out-of-scope

Ok. How about I add a link from the custom constraints docs to your branch, rather than merging, then?

Either that or an Extras folder is fine with me until it gets fixed up enough to go mainline.

justonia commented 5 years ago

Oh and question for you. Is the order of topology indices always going to go from min->max on all dimensions? And if so, is this an API guarantee or an assumption of internals?

Also I believe I have fixed the 1) issue you pointed out while keeping the algorithm O(N), but I had to explicitly not support periodicity because I cannot see a way to implement it without ballooning to O(N^2). I may later on consider adding support for it, and have a fast-path and a slow-path depending on the setup of the topology.

BorisTheBrave commented 5 years ago

Oh and question for you. Is the order of topology indices always going to go from min->max on all dimensions? And if so, is this an API guarantee or an assumption of internals?

Please take that as internal. If you need navigation options better than TryMove (and it's often necessary), use x,y,z tuples, and convert to and from indicies. But the indices themselves should not have meaning. I think if we stick to that convention it'll be easier for me to add new topologies later.

BorisTheBrave commented 5 years ago

Hi @justonia,

I've now done my own implementation of this: https://github.com/BorisTheBrave/DeBroglie/commit/baf942d1b948f7ef32b3df2234f303b4576dacbf

In the end, I went with a different implementation that runs in linear time. In addition, I added all the extras like documentation and serialization.

Thank you for the excellent suggestion, and I hope you find the new feature useful.