Speed Up by only calculating entropy of cells adjacent to collapsed cells (+ naive backtracking demo)

[jakedowns]

i was trying to draw a large grid (64x64) and it was slow, so i tweaked the draw() function to skip calculating validOptions for cells that weren't adjacent to any other collapsed cells

// if ZERO adjacent cells are collapsed, skip for now...
        let at_least_one_collapsed = false;
        for(neighbor of [
          j > 0 ? grid[i + (j - 1) * DIM] : null, // up
          i < DIM - 1 ? grid[i + 1 + j * DIM] : null, // right
          j < DIM - 1 ? grid[i + (j + 1) * DIM] : null, // down
          i > 0 ? grid[i - 1 + j * DIM] : null // left
        ]){
            if(neighbor?.collapsed){
              at_least_one_collapsed = true;
            }
        }
        if(!at_least_one_collapsed){
          nextGrid[index] = new Cell(tiles.length, index); //grid[index];
          continue;
        }

you can test it out on CodePen here: https://codepen.io/jakedowns/pen/PoRbeGQ

I also implemented naive backtracking, naive in the sense that it goes backwards step by step, instead of kind of propagating re-picking options in the local neighborhood of a cell with 0 options. that would be the more efficient way. gonna try to implement that next...

https://twitter.com/i/status/1547662617749045250

chrome-hbznzh1xzk-klwyklmh_hm3twhOG.mp4

[jakedowns]

Update: i also speed things up by replacing array.concat with array.push(...array)
https://dev.to/uilicious/javascript-array-push-is-945x-faster-than-array-concat-1oki

I hosted my version here https://jakedowns.com/oasis

https://twitter.com/jakedowns/status/1548593109092552705

Also got some good local-backtracking going. Check out my fork here: https://github.com/jakedowns/Wave-Function-Collapse/blob/d94326e86baecb45109c1567625ea8d726634490/sketch.js#L423

[shiffman]

This is amazing!! (Many years later reply I know. . .) Would you like to add this to the README? (See #46). I'm working on this repo again as a new WFC video is coming out on Monday (or Tuesday)!