CodingTrain / CodingTrain/Wave-Function-Collapse
Speed Up by only calculating entropy of cells adjacent to collapsed cells (+ naive backtracking demo)
- Linguagem predominante
- JavaScript
- Estrelas
- 218
- Forks
- 64
- Métricas de merge de PRs
- Nenhum PR com merge em 30d
Descrição
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
Guia de contribuição
Nenhum guia de contribuição indexado para este repositório
Direção de pesquisa
Comece pela função draw() e compare o cálculo de validOptions com a implementação do CodePen vinculada. Revise a demo e o vídeo vinculados para entender a otimização proposta de células adjacentes e o comportamento do backtracking ingênuo; o trabalho deve ser considerado concluído quando incluir uma melhoria confirmada para grades grandes e um escopo acordado para o trabalho de backtracking.
Escrita pelo modelo de indexação a partir do texto da issue.
Avaliação
- Stack de tecnologia
- javascript
- Domínio
- performance
- Tipo de issue
- Funcionalidade
- Dificuldade
- 4/5
- Tempo estimado
- 3-5 dias
- Status de atividade
- Estagnada
- Clareza
- Razoavelmente clara
- Facilidade para iniciantes
- 35/100