-
-
Notifications
You must be signed in to change notification settings - Fork 1.3k
Description
Currently WFC tracks allowed patterns per cell using bool[][] wave.
Switching this to a bitset (ulong[], dynamically sized based on T) would:
- Cut memory by 8 - 10x
- Remove branchy per-pattern loops
- Give us hardware accelerated
popcountfor free - Scale cleanly
- Unlock SMD / perhaps multithread optimizations long-term
This change keeps the API + behavior identical -- it's just a low-level data layout upgrade.
I have more or less drop-in replacement prototype.
For example with only single generation like this:
<overlapping name="Town" N="3" periodic="True" heuristic="MRV" size="300" screenshots="1"/>
Change is significant, without bitset my computer takes 60830ms vs 18092ms using updated data layout and bitset.
Generally what I've noticed with smaller map sizes the performance is identical or marginally better but with increasing sizes of maps it gets significantly faster.
Note: Not sure has anyone tested this in greater details before and found some reasons why it is not working so far I'm seeing improvements but as I haven't done extensive testing there still might be caveats.