Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Optimize grid updates #41

Open
gverger opened this issue Jul 21, 2022 · 0 comments
Open

Optimize grid updates #41

gverger opened this issue Jul 21, 2022 · 0 comments

Comments

@gverger
Copy link

gverger commented Jul 21, 2022

Hey, thank you very much for all your videos, I'm having a blast watching them!

I made a Pull Request here to make grid updates more efficient. Instead of watching all cells one by one hoping that there might be some change, we can start from a modified cell (i.e. options are reduced for this cell), and update the neighbours. For each neighbour that has fewer options than before, we continue and check its neighbours etc.
We stop when no update is possible anymore, and the system is stable.

The idea comes from Constraint Programming, where constraint propagation is a thing that can be done this way. Here the constraints handle the compatibility between adjacent cells, and when a cell changes (its options are reduced), it triggers the consistency check of attached constraints.

The next step will be to collapse a new cell, and check its neighbours etc.

This allows to solve much larger instances, since it doesn't consider untouched cells. Here with 100x100 cells for instance:
wfc-100-1

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant