CodingTrain / CodingTrain/Wave-Function-Collapse

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

未關閉
#38 2 則留言 0 個 reaction 已指派 0 人 在 GitHub 檢視
主要語言
JavaScript
星號
218
分支
64
PR 合併指標
30 天內沒有已合併 PR

描述

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

https://user-images.githubusercontent.com/1683122/179131109-84e6a5e7-0d79-4005-9073-d4cbae7e23e8.mp4

貢獻指南

這個儲存庫沒有索引到貢獻指南

研究方向

從 draw() 函式開始,將其 validOptions 計算與連結的 CodePen 實作進行比較。查看連結的示範和影片,以了解提議的相鄰儲存格最佳化和樸素回溯行為;完成標準應包括確認對大型網格有所改進,並就回溯工作的範圍達成共識。

由索引模型根據 Issue 內容生成。

評估

技術堆疊
javascript
領域
performance
Issue 類型
功能
難度
4/5
預估耗時
3-5 天
活躍度
停滯
描述清晰度
基本清楚
新手友好度
35/100

把新 issue 寄到你的電子郵件信箱

精選適合新手參與的 GitHub issue 摘要。