Hacktoberfest 2026 : les issues que les mainteneurs ont marquées pour octobre, ouvertes et accessibles aux débutants. Parcourir les issues Hacktoberfest

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

Ouverte
  • Quelque chose ne va pas ?
#38 2 commentaires 0 réactions 0 personnes assignées Voir sur GitHub

Personne n'a encore pris cette issue.

Évaluation

Difficulté
4/5
Temps estimé
3-5 jours
Accessibilité débutants
35/100
Type d'issue
Fonctionnalité
Clarté
Plutôt claire
Activité
À l'abandon
Stack technique
javascript
Domaine
performance

Piste de recherche

Commencez par la fonction draw() et comparez son calcul de validOptions avec l’implémentation CodePen liée. Examinez la démo et la vidéo liées pour comprendre l’optimisation proposée des cellules adjacentes et le comportement du backtracking naïf ; le travail devrait être considéré comme terminé lorsqu’une amélioration confirmée pour les grandes grilles et un périmètre convenu pour le travail de backtracking auront été définis.

Rédigé par le modèle d'indexation à partir du texte de l'issue.

Description

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

Langage dominant
JavaScript
Étoiles
219
Forks
64
Aucune PR mergée en 30 j

Préparer son environnement

Ce projet ne fournit ni conteneur de développement, ni Dockerfile, ni guide de contribution : l'installation est à votre charge. Commencez par son README, et consultez notre guide de la première contribution pour les étapes générales.

Par où commencer

  1. Lisez l'issue en entier, puis le guide de contribution du projet.
  2. Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
  3. Forkez le dépôt et travaillez sur une branche.
  4. Ouvrez une pull request qui référence le numéro de l'issue.

Autres issues de CodingTrain/Wave-Function-Collapse

Toutes les issues de CodingTrain/Wave-Function-Collapse

Issues similaires

Plus d'issues JavaScript

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.