QT Source

// COPYRIGHT CANDYAPPLECORN 2014
// ALL RIGHTS RESERVED
// Send me an email at [email protected] if you'd like to use this script
// otherwise this script is copyrighted under the
// http://creativecommons.org/licenses/by-nc-nd/4.0/
// license

var c = document.getElementById("myCanvas");
        var ctx = c.getContext('2d');
        var gravity = 9.8;
        var objects = 100;

        function quadTree(x, y, w){
          // data - this could be a seperate object if written in C++
          this. entities = [];

          // child nodes
          this. children = [null, null, null, null];

          // node info
          this. bounds = { x: x, y: y, x2: x + w, y2: y + w };

          this. center = { x: x + w / 2, y: y + w / 2 };

          this. width = w;

          this. maxEntities = 4;

          // functions

          // ------------------------------------------------
          // boundsCheck returns true if co is out of bounds.
          // invert its value to see if co is within bounds.
          // if extra parameters sent, checks to see if co is
          // within bounds of the parameterized square
          this. boundsCheck = function (co, x, y, w) {
            if (x == null)
              return co.x < this.bounds.x || co.x > this.bounds.x2 || co.y < this.bounds.y || co.y > this.bounds.y2;
            return co.x < x || co.x > x + w || co.y < y || co.y > y + w;
          };

          // ------------------------------------------------
          // childrenNull returns true if all children are null
          this. childrenNull = function(){
            return this.children[0] == null && this.children[1] == null && this.children[2] == null && this.children[3] == null;
          };

          // ------------------------------------------------
          // useless returns true if this node is void of children AND data
          this. useless = function(){
            return this.entities.length === 0 && this.childrenNull();
          };

          // ------------------------------------------------
          // which takes a coordinate and finds its quadrant.
          // 0 = ne, 1 = se, 2 = sw, 3 = nw
          this. which = function(co){
            if      (co.x > this.center.x && co.y > this.center.y)     return 0;
            else if (co.x > this.center.x && co.y <= this.center.y)    return 1;
            else if (co.x <= this.center.x && co.y <= this.center.y)   return 2;
            else if (co.x <= this.center.x && co.y > this.center.y)    return 3;
          };

          // ------------------------------------------------
          // split defines each null child.
          this. split = function(){
            this.children[0] = new quadTree (this.center.x, this.bounds.y, this.width/2);
            this.children[1] = new quadTree (this.center.x, this.center.y, this.width/2);
            this.children[2] = new quadTree (this.bounds.x, this.center.y, this.width/2);
            this.children[3] = new quadTree (this.bounds.x, this.bounds.y, this.width/2);
          };

          this. insert = function(co){
            if(this.boundsCheck(co))
              return false;

            if(this.entities.length < this.maxEntities){
              this.entities.push(co);
              return true;
            }

            if(this.children[0] == null)
              this.split();

            if (this.children[0].insert(co)) return true;
            if (this.children[1].insert(co)) return true;
            if (this.children[2].insert(co)) return true;
            if (this.children[3].insert(co)) return true;
          };

          // ------------------------------------------------
          // getRange takes an optional range and returns an array
          // of all data stored within nodes in that range.
          this. getRange = function(x, y, w){
            var results = [], self = this;
            // IF NO RANGE PARAMETERS, GET EVERYTHING
            if (x == null && y == null && w == null){

              for (var counter = 0; counter < this.entities.length; counter++)
                if(this.entities[counter] != null)
                  results.push(this.entities[counter]);

              for (var counter2 = 0; counter2 < 4; counter2++) // unknown scope error
                if(this.children[counter2] != null){
                  var tmp = this.children[ counter2 ].getRange();
                  for(var counter3 = 0; counter3 < tmp.length; counter3++)
                    if(tmp[counter3])
                      results.push(tmp[counter3]);
                }

              return results;
            }

            // x or y or w aren't null. check for bad input.
            if (x == null || y == null || w == null) return;

            var x2 = x + w, y2 = y + w;
            this.entities.forEach(function(element, index, array){
              if(! self.boundsCheck(element, x, y, w) ) results.push( element );
            });
            // CAN BE OPTIMIZED - CURRENTLY ISN'T!
            this.children.forEach(function(element, index, array){
              if(element){
                var temp = self.children[index].getRange(x, y, w);
                temp.forEach(function(element, index, array){
                  if (element)
                    results.push(element);
                });
              }
            });
            return results;
          };
        }

        quadTree.prototype.update = function(){
          var self = this; // EXTREEEMELY IMPORTANT, forEach overrides "this"
          this.entities.forEach(function (e, i, a){
            self.collision();
            var x = Math.floor(e.speed * e.hor);
            var y = Math.floor(e.speed * e.ver);
            e.x += x > 0 ? x + 1 : x - 1;
            e.y += y > 0 ? y + 1 : y - 1;
            if (e.x > c.width || e.x < 0 || e.y > c.height || e.y < 0)
              a.splice(i, 1);
          });
          for(var counter = 0; counter < this.children.length; counter++){
            if (this.children[counter])
              this.children[counter].update();
          }
        };

        quadTree.prototype.draw = function(){
          for(var counter = 0; counter < 4; counter++)
            if ( this.children[counter] )
              this.children[counter].draw();


          for(var counter2 = 0; counter2 < this.entities.length; counter2++)
            if(this.entities[counter2]){
              ctx.fillStyle = "green";
              ctx.beginPath();
              ctx.arc(this.entities[counter2].x, this.entities[counter2].y, 3, 0, 2 * Math.PI, true);
              ctx.fill();
              ctx.stroke();
            }
          if (this.entities.length){
            ctx.strokeStyle = "black";
            ctx.lineWidth = 1;
            ctx.beginPath();
            ctx.moveTo(this.bounds.x, this.center.y);
            ctx.lineTo(this.bounds.x2, this.center.y);
            ctx.stroke();
            ctx.beginPath();
            ctx.moveTo(this.center.x, this.bounds.y);
            ctx.lineTo(this.center.x, this.bounds.y2);
            ctx.stroke();
          }
        };

        quadTree.prototype.collision = function(){
          if (this.entities.length > 1){
            this.entities.forEach(function(element, index, array){
              for(var counter = 0; counter < array.length; counter++){
                if (counter == index)
                  continue;
                var distance = Math.sqrt((element.x - array[counter].x) * (element.x - array[counter].x) + (element.y - array[counter].y) * (element.y - array[counter].y));
                if(distance < 6){
                  element.hor = Math.cos( Math.random() * 2 * Math.PI );
                  element.ver = Math.sin( Math.random() * 2 * Math.PI );
                  array[counter].hor = element.ver;
                  array[counter].ver = element.hor;
                }
              }
            });
          }
        };

        function entity( x1, y1, speed1, hor1, ver1){
          this.x = x1 || 0;
          this.y = y1 || 0;
          // Extra stuff:
          this.speed = speed1 || 1;
          this.hor = hor1 || 1/2;
          this.ver = ver1 || 1/2;
        }

        var q = new quadTree(0, 0, c.width);

        for(var counter = 0; counter < objects; counter++){
          q.insert(
            new entity(
              Math.floor(c.width/2),//Math.random() * c.width),
              Math.floor(c.height/2),//Math.random() * c.height),
              Math.random() * gravity,
              Math.cos( Math.random() * 2 * Math.PI ),
              Math.sin( Math.random() * 2 * Math.PI )
            )
          );
        }

        function animate(){
          var form = document.getElementById("form");
          objects = form.elements[0].value;
          gravity = form.elements[1].value;
          q.update();
          var newE = q.getRange();
          q = new quadTree(0, 0, c.width);
          document.getElementById("below").innerHTML = "There are " + newE.length + " objects.";
          for(var counter2 = 0; counter2 < objects - newE.length; counter2++){
            q.insert(
              new entity(
                Math.floor(c.width/2),//Math.random() * c.width),
                Math.floor(c.height/2),//Math.random() * c.height),
                Math.random() * gravity,
                Math.cos( Math.random() * 2 * Math.PI ),
                Math.sin( Math.random() * 2 * Math.PI )
              )
            );
          }
          for(var counter = 0; counter < newE.length; counter++){
            q.insert(newE[counter]);
          }
          ctx.fillStyle = "#FFFFFF";
          ctx.fillRect(0, 0, c.width, c.height);
          q.draw();
        }

          function Quad_Tree_Initializer(){
  var quadTreeDIV = document.getElementById("quadTree");
quadTreeDIV.active = false;

  var interv = setInterval(animate, 1000/30);
  window.setTimeout(clearInterval, 1000, interv);

quadTreeDIV.addEventListener('mouseover', function(){
  if(!quadTreeDIV.active)
  quadTreeDIV.interv = setInterval(animate, 1000/30);
  quadTreeDIV.active = true;
});

quadTreeDIV.addEventListener('mouseout', function(){
  clearInterval(quadTreeDIV.interv);
  quadTreeDIV.active = false;
})
}

Quad_Tree_Initializer();