Lowlight.fr

Nous avons une lune de sang ce soir.
Tu connaîtras donc la mort.

The Embodiment of Scarlet Devil
Team Shanghai Alice (ZUN)

Les quadtrees

Les **quadtrees** sont une structure de données dans laquelle chaque nœud possède quatre enfants. Ceux-ci permettent, à l'instar de tout autre **base de données spatiale** de partitionner l'espace, et, en l'occurrence, les espaces bidimensionnels. Les temps d'**accès mémoire réduits** permettent de nombreux usages, comme la compression d'image ou bien la limitation des tests de collisions dans un espace 2D.

Pour les traitements dans des espaces en 3D, on optera plutôt pour des **octrees** et suivant la **répartition** des données, on préférera d'autres types d'arbres aux quadtrees, comme par exemple les **k-d trees** qui s'adapteront beaucoup mieux à un jeu de données quelconque.

Cet article consiste en une **présentation** de la bibliothèque lowlighter/quadtree (documentation) que j'ai réalisé.

Démonstration et exemples de code

Vous pouvez bouger le joueur en utilisant les touches **ZQSD** ou **WASD** après avoir activé les **contrôles au clavier**.

Sprites obtenus par **Azu** depuis **Touhou Project : Mystical Chain**.

Nombre de particules
Nombre de tests de collisions
Capacité des noeuds
Profondeur maximum
Contrôles au clavier
Motifs de générations des particules
Circulaire
Linéaire
Linéaire (avec inertie)
Dirigé
Aléatoire

    //Initialisation
        let size = 400, particles = 0
        let quadtree = new Lowlight.Quadtree({max_items:4, max_depth:7, w:size, h:size})

    //Créations de particules
        for (let i = 0; i < particles; i++) {
            quadtree.add({x:size*Math.random(), y:size*Math.random(), w:10, h:10, ax:0.5, ay:0.5})
        }

    //Ajout d'un joueur
        let player = {x:size*Math.random(), y:size*Math.random(), collide:collide.bind(null, player), w:10, h:10, ax:0.5, ay:0.5}
        quadtree.add(player)

    //Mise à jour
        ;(function update() {
            //Tests de collisions (retourne 0)
                [...quadtree.retrieve(player)].filter(item => player.collide(item)).length

            //Mise à jour des positions
                quadtree.entries.forEach(particle => {
                    particle.x += Math.random()
                    particle.y += Math.random()
                })

            //Reconstruction et frame suivante
                quadtree.rebuild()
                requestAnimationFrame(update)
        })()

    //Test de collision
        function collide(a, b) {
            return (a.x + a.w < b.x)||(b.x + b.w < a.x)||(a.y + a.h < b.y)||(b.y + b.h < a.y)
        }

                

Caractéristiques de cette bibliothèque

  • Respecte le prototype des structures de données de l'**ES6** (add, delete, clear, has, forEach, ...)
  • Capacité des nœuds et profondeur du quadtree **configurables**
  • Supporte **tout type** d'objet
  • **Légère** (2.65 ko)