Skip to content

Commit 6137862

Browse files
alin256alin256
authored
An Efficient queue implimintation and backtracking to avoid paradoxes (#53)
* Added debug output * Checking exit conditions * Changed to a queue system * Reduced the grid size * Added tile selector * Stopped restarting under a conflict * Improved version without backtracking * Added backtracking to avoid paradoxes. * Fixed small issue with frames * Added if statement to not show options in cell * Removed checked field * Update README.md * Bug fix for image chooser. Reinitialization corrected. * Fixed load new image behavior after a run is completed. * Changed to a reasonable grid size * Removed unneeded cell.checked flag * Improved frame-rate
1 parent ecb4305 commit 6137862

File tree

4 files changed

+287
-77
lines changed

4 files changed

+287
-77
lines changed

‎README.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -46,6 +46,7 @@ Wave Function Collapse is a constraint-satisfaction algorithm inspired by quantu
4646
- [Highly optimized version supporting both single-image and pre-tiled source images](https://github.com/pierrebai/Wave-Function-Collapse)
4747
A detailed write-up of how the changes were done and why can be found in its own
4848
[readme here](https://github.com/pierrebai/Wave-Function-Collapse/tree/main/p5js/hybrid-model/README.md)
49+
- An optimised overlaping model using queues (instead of recurcion) and backtracking to avoid paradoxes. [Version @alin256](https://github.com/alin256/Wave-Function-Collapse/tree/efficientQueueBranch). The version also adds some GUI improvements.
4950

5051

5152
## Key Resources

‎p5js/overlapping-model/cell.js‎

Lines changed: 12 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,6 @@
11
// Saving the log of 2 for shannon entropy calculation
22
const log2 = Math.log(2);
3+
const SHOW_OPTION_COUNT_IN_CELL = false;
34

45
// A Cell is a single element of the grid
56
class Cell {
@@ -16,16 +17,15 @@ class Cell {
1617

1718
// Has it been collapsed to a single tile?
1819
this.collapsed = false;
19-
// Has it already been checked during recursion?
20-
this.checked = false;
2120

2221
// Initialize the options with all possible tile indices
2322
for (let i = 0; i < tiles.length; i++) {
2423
this.options.push(i);
2524
}
2625

2726
// This keeps track of what the previous options were
28-
// Saves recalculating entropy if nothing has changed
27+
// Saves time recalculating entropy if nothing has changed
28+
// TODO (Sergey): I think this should not be needed, but let's keep until someone varifies that
2929
this.previousTotalOptions = -1;
3030

3131
// Variable to track if cell needs to be redrawn
@@ -87,6 +87,15 @@ class Cell {
8787
fill(sumR, sumG, sumB);
8888
noStroke();
8989
square(this.x, this.y, this.w);
90+
91+
if (SHOW_OPTION_COUNT_IN_CELL) {
92+
fill(0);
93+
noStroke();
94+
textSize(this.w / 2);
95+
textAlign(CENTER, CENTER);
96+
text(this.options.length, this.x + this.w / 2, this.y + this.w / 2);
97+
}
98+
9099
}
91100
// No need to redraw until something has changed
92101
this.needsRedraw = false;

‎p5js/overlapping-model/images/list.txt‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
3Bricks.png
2+
Angular.png
3+
BrownFox.png
4+
Cat.png
5+
city.png
6+
ColoredCity.png
7+
ct_logo.png
8+
Disk.png
9+
Dungeon.png
10+
example.png
11+
Flowers.png
12+
Font.png
13+
Hogs.png
14+
Knot.png
15+
Lake.png
16+
Link2.png
17+
MagicOffice.png
18+
Mazelike.png
19+
Mountains.png
20+
Office.png
21+
Office2.png
22+
Paths.png
23+
Platformer.png
24+
RedDot.png
25+
RedMaze.png
26+
Rooms.png
27+
Rule126.png
28+
Sand.png
29+
Sewers.png
30+
SimpleKnot.png
31+
SimpleWall.png
32+
Skew2.png
33+
Skyline.png
34+
SmileCity.png
35+
Spirals.png
36+
Town.png
37+
Village.png
38+
WalledDot.png
39+
water.png

0 commit comments

Comments
 (0)