Hacktoberfest 2026: as issues que os mantenedores marcaram para outubro, abertas e boas para iniciantes. Ver issues do Hacktoberfest

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

Aberta
  • Algo errado?
#38 2 comentários 0 reações 0 responsáveis Ver no GitHub

Ninguém assumiu esta issue ainda.

Avaliação

Dificuldade
4/5
Tempo estimado
3-5 dias
Facilidade para iniciantes
35/100
Tipo de issue
Funcionalidade
Clareza
Razoavelmente clara
Status de atividade
Estagnada
Stack de tecnologia
javascript
Domínio
performance

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.

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

Linguagem predominante
JavaScript
Estrelas
219
Forks
64
Nenhum PR com merge em 30d

Preparar o ambiente

Este projeto não oferece contêiner de desenvolvimento, Dockerfile nem guia de contribuição, então a configuração fica por sua conta: comece pelo README e veja nosso guia da primeira contribuição para os passos gerais.

Primeiros passos

  1. Leia a issue inteira e depois o guia de contribuição do projeto.
  2. Comente na issue dizendo que vai assumir — evita que duas pessoas façam o mesmo trabalho.
  3. Faça um fork do repositório e trabalhe em uma branch.
  4. Abra um pull request que referencie o número da issue.

Mais de CodingTrain/Wave-Function-Collapse

Todas as issues de CodingTrain/Wave-Function-Collapse

Issues semelhantes

Mais issues de JavaScript

Receba novas issues na sua caixa de entrada

Um resumo curto de issues do GitHub para quem está começando.