CodingTrain / CodingTrain/Wave-Function-Collapse

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

オープン
#38 コメント 2 件 リアクション 0 件 担当者 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 を短くまとめたダイジェスト。