Skip to content

Wrong recursive entropy calculation #52

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.

Sign up for GitHub

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

Jump to bottom
Open
alin256 opened this issue Apr 23, 2025 · 3 comments · May be fixed by #53
Open

Wrong recursive entropy calculation #52

alin256 opened this issue Apr 23, 2025 · 3 comments · May be fixed by #53

Comments

@alin256
Copy link

alin256 commented Apr 23, 2025

I was wondering why the overlapping simulation fails so often with all new cool features.

I actually found a bug here. We mark cells as checked, which means we do not update the cell if we visit it multiple times during the entropy reduction. Removing the cell.checked condition makes things converge all the time.

Wave-Function-Collapse/p5js/overlapping-model/sketch.js

Line 145 in ecb4305

if (depth > MAX_RECURSION_DEPTH || cell.checked) return;

I can make a pull request to correct this.
@alin256
Copy link
Author

alin256 commented Apr 29, 2025 •
edited
Loading

I rewrote the recursion to a queue and there seems to be no failures due to conflicts.

I run the model with depth limit of 1e9, and it did not get stuck in the reduction yet.

@shiffman
Copy link
Member

(Sorry that i haven't replied yet, really busy with the end of the semester, but i'm SO GLAD you found this! I need to address it on a live stream or document this well somewhere. Hope to come back to it soon.)

@alin256
Copy link
Author

alin256 commented Apr 29, 2025

@shiffman, after a bit more coding I have a version without recursion with added backtracking when paradoxes occur.

I ran it through a 3Brick case which seemed particularly paradox-reach and recovered two paradoxes on a 120x120 grid. Runs quite fast.

I can pull-request the updated version after a bit of code cleaning. I did some other experimentation which does not need to be in the Main. Let me know if you have any particular timeline in mind.

If you want to check the updated model performance (it now slowly propagates changes during draw with a counter in the bottom):
https://al-digital.no/Wave-Function-Collapse/p5js/overlapping-model/

@alin256 alin256 linked a pull request Apr 29, 2025 that will close this issue
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

An Efficient queue implimintation and backtracking to avoid paradoxes alin256/Wave-Function-Collapse
2 participants
@shiffman @alin256