CodingTrain / CodingTrain/Wave-Function-Collapse

Optimize grid updates

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

描述

Hey, thank you very much for all your videos, I'm having a blast watching them!

I made a Pull Request [here](https://github.com/CodingTrain/Wave-Function-Collapse/pull/40) to make grid updates more efficient. Instead of watching all cells one by one hoping that there might be some change, we can start from a modified cell (i.e. options are reduced for this cell), and update the neighbours. For each neighbour that has fewer options than before, we continue and check its neighbours etc.
We stop when no update is possible anymore, and the system is stable.

The idea comes from Constraint Programming, where constraint propagation is a thing that can be done this way. Here the constraints handle the compatibility between adjacent cells, and when a cell changes (its options are reduced), it triggers the consistency check of attached constraints.

The next step will be to collapse a new cell, and check its neighbours etc.

This allows to solve much larger instances, since it doesn't consider untouched cells. Here with 100x100 cells for instance:
![wfc-100-1](https://user-images.githubusercontent.com/6671307/180328561-f9e4ff05-3de8-44ed-82b9-8aec069605f5.gif)

貢獻指南

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

研究方向

Start by reviewing pull request #40, which contains the proposed grid-update optimization, and compare it with the current update flow. Done means updates begin from modified cells, propagate to affected neighbours until stable, and avoid reconsidering untouched cells so larger instances can be solved efficiently.

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

評估

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

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

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