search

mxgmn / WaveFunctionCollapse

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

Update README.md with port to Julia. #50

Closed roberthoenig closed 5 years ago

roberthoenig commented 5 years ago

I did a port of the overlapping model to Julia -- along with a little heuristic optimization. Hope it's fine to update the README :-)

ifelsebreak commented 5 years ago

Wrong adress

Il giorno mer 2 gen 2019, 11:54 Robert Hönig notifications@github.com ha scritto:

I did a port of the overlapping model to Julia -- along with a little heuristic optimization. Hope it's fine to update the README :-)

You can view, comment on, or merge this pull request online at:

https://github.com/mxgmn/WaveFunctionCollapse/pull/50 Commit Summary

  • Update README.md with port to Julia.

File Changes

Patch Links:

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/mxgmn/WaveFunctionCollapse/pull/50, or mute the thread https://github.com/notifications/unsubscribe-auth/Ao4eqOfVVuQeeoDi5Qv8OsSk7Vo5Muv2ks5u_I_MgaJpZM4ZmfHb .

mxgmn commented 5 years ago

Nice! So what is this option (by only propagating constraints locally)?

roberthoenig commented 5 years ago

So what is this option (by only propagating constraints locally)?

In the original algorithm, whenever a field is collapsed, the new constraints on the patterns are propagated with a flood fill algorithm, from field to field, until all fields have a minimum number of possible patterns they could still collapse to. That propagation is very time-consuming. Local constraint propagation limits the flood fill to fields that are within a certain distance from fully collapsed fields. The idea is that usually, the next field to be collapsed is one that is adjacent to some other already collapsed field. Thus, it should be fine to only ever propagate constraints wihin a certain radius around the collapsed fields. In practice, I found that there is a trade-off between convergence to a solution and length of the radius. The bigger the radius, the more fields we are going to propagate constraints to (the close it is to the original algorithm), so the more time it takes. I found that with a radius of ~3 fields, the speedup was around x2 - x3, with good convergence until ~40x40. I haven't yet fully examined these ratios for higher radiis.

mxgmn commented 5 years ago

I see. So we are trading a single propagation speed with a success rate. How much it speeds up (or if at all) depends very much on the example of course (consider the Chess example where a single nonlocal propagation is enough). I remember Remy proposed it here https://trasevol.dog/2017/09/01/di19/.