<commit_before><html>
<canvas id ="gameCanvas" width = "800" height = "600"></canvas>

<script type="text/javascript">
"use strict";

var width = window.innerWidth || document.documentElement.clientWidth || document.body.clientWidth,
	height = window.innerHeight || document.documentElement.clientHeight || document.body.clientHeight,

	canvas = document.getElementById('gameCanvas');

var canvasContext,
	objectList;

var objectCount = 25;
var objectMaxDim = 30;
var objectMinDim = 20;

var quadTree;

window.onload = function(){
	canvasContext = canvas.getContext('2d');

	drawBackground();
	canvas.addEventListener("click", handleClick, false);
}

function createObjects(){
	quadTree = new QuadTree(0, canvas.width, 0, canvas.height, 3, 5, -1);

	for(var i = 0; i < objectCount; i++){
		var w = getRandomIntInRange(objectMinDim, objectMaxDim);
		var h = getRandomIntInRange(objectMinDim, objectMaxDim);
		var x = getRandomIntInRange(0, canvas.width);
		var y = getRandomIntInRange(0, canvas.height);

		var obj = new GameObject(x, y, w, h);
		objectList.push(obj);
		obj.draw();
	}
	console.log(quadTree);
}

function sortObjects(){
	quadTree.clear();
	for (var i = 0; i < objectList.length; i++){
			quadTree.insert(objectList[i]);
	}
	quadTree.draw();
}
function drawBackground(){
	canvasContext.fillStyle = 'black';
	canvasContext.fillRect(0,0,canvas.width,canvas.height);
}

function handleClick(evt){

	//empty object list, refresh screen
	objectList = [];
	drawBackground();

	//spawn new set of objects, draw.
	createObjects();

	//sort objects into quad tree.
	sortObjects();

}

class GameObject {
	constructor(x, y, width, height, color){
		this.x = x;
		this.y = y;
		this.width = width;
		this.height = height;
	}

	draw(){
		canvasContext.save();
		canvasContext.translate(this.x, this.y);
		canvasContext.fillStyle = 'red';
		canvasContext.fillRect(0, 0, this.width, this.height);
		canvasContext.restore();
	}
}

class QuadTree {
	constructor(minX, maxX, minY, maxY, maxDepth, maxChildren, level){
		this.maxDepth = maxDepth;
		this.maxChildren = maxChildren;
		this.minX    = minX;
		this.maxX    = maxX;
		this.minY    = minY;
		this.maxY    = maxY;
		this.width   = maxX - minX;
		this.height  = maxY - minY;
		this.level   = level;
		this.nodes   = [];
		this.objects = [];

	}
	clear(){
		this.objects = [];

		for (var i = 0; i < this.nodes.length; i++){
			if (this.nodes[i] != null){
				this.nodes[i].clear();
				this.nodes[i] = null;
			}
		}
	}
	draw(){
		canvasContext.save();
		canvasContext.translate(this.minX, this.minY);
		canvasContext.beginPath();
		canvasContext.lineWidth = "6";
		canvasContext.strokeStyle = "blue";
		canvasContext.rect(0, 0, this.width, this.height);
		canvasContext.stroke();
		canvasContext.restore();

		for (var i = 0; i < this.nodes.length; i++){
			if (this.nodes[i] != null){
				this.nodes[i].draw();
			}
		}
	}
	splitNode(){
		var subWidth  = Math.floor((this.width)/2);
		var subHeight = Math.floor((this.height)/2);

		this.nodes.push(new QuadTree(this.minX, this.minX + subWidth, this.minY, this.minY + subHeight, this.maxDepth, this.maxChildren, this.level + 1));
		this.nodes.push(new QuadTree(this.minX + subWidth, this.maxX, this.minY, this.minY + subHeight, this.maxDepth, this.maxChildren, this.level + 1));
		this.nodes.push(new QuadTree(this.minX, this.minX + subWidth, this.minY + subHeight, this.maxY, this.maxDepth, this.maxChildren, this.level + 1));
		this.nodes.push(new QuadTree(this.minX + subWidth, this.maxX, this.minY + subHeight, this.maxY, this.maxDepth, this.maxChildren, this.level + 1));
	}
	getIndex(obj){
		var index = -1;
		var horizontalMidpoint = this.minX + this.width/2;
		var verticalMidpoint   = this.minY + this.height/2;

		if (obj.x > this.minX && obj.x + obj.width < horizontalMidpoint){
			var leftQuadrant = true;
		}
		if (obj.x + obj.width < this.maxX && obj.x > horizontalMidpoint){
			var rightQuadrant = true;
		}

		if (obj.y > this.minY && obj.y + obj.height < verticalMidpoint){
			if (leftQuadrant){
				index = 0;
			}
			else if (rightQuadrant){
				index = 1;
			}
		}
		else if (obj.y + obj.width < this.maxY && obj.y > verticalMidpoint){
			if (leftQuadrant){
				index = 2;
			}
			else if (rightQuadrant){
				index = 3;
			}
		}
		return index;
	}

	insert(obj){
		if (this.nodes[0] != null){
			var index = this.getIndex(obj);
			if (index != -1){
				this.nodes[index].insert(obj);

				return;
			}
		}

		this.objects.push(obj);

		if (this.objects.length > this.maxChildren && this.level < this.maxDepth){
			if (this.nodes[0] == null){
				this.splitNode();
			}

			var i = 0;
			while(i < this.objects.length){
				var index = this.getIndex(this.objects[i]);
				if (index != -1){
					this.nodes[index].insert(this.objects[i]);
					this.objects.splice(i, 1);
				}
				else{
					i++;
				}
			}
		}
	}
}

//------utils------//
function getRandomIntInRange(min, max){
	return Math.floor(Math.random() * (max-min) + min);
}
</script>
</html><commit_msg>Added the quadtree's retrieve method. Sandbox code allows you to move around an object. on click, retrieves every object that it might possibly collide with.<commit_after><html>
<canvas id ="gameCanvas" width = "800" height = "600"></canvas>

<script type="text/javascript">
"use strict";

var width = window.innerWidth,
	height = window.innerHeight,
	canvas = document.getElementById('gameCanvas');

var canvasContext,
    dynamicObj,
    mouseX,
    mouseY;
var objectList = [];

var objectCount = 25;
var objectMaxDim = 30;
var objectMinDim = 20;

var quadTree;

window.onload = function(){
	canvasContext = canvas.getContext('2d');

	drawBackground();
	canvas.addEventListener("click", handleClick, false);
    canvas.addEventListener("mousemove", calcMousePos, false);
	init();
}

function init(){
    //dynamic object - stuck to mouse
    dynamicObj = new GameObject(0, 0, 20, 20, 'green');


    createObjects();
    setInterval(gameLoop, 1000/30);
}

function gameLoop(){

    dynamicObj.x = mouseX;
	dynamicObj.y = mouseY;
    checkCollisions();
    drawBackground();
    dynamicObj.draw();
	drawStaticObjects();


}

function checkCollisions(){
    quadTree = new QuadTree(0, canvas.width, 0, canvas.height, 4, 6, -1);
    sortObjects();
}

function drawStaticObjects(){
	for (var i = 0; i < objectList.length; i++){
		var obj = objectList[i];
		obj.draw();
	}
    quadTree.draw();
}
function calcMousePos(evt){
	var rect = canvas.getBoundingClientRect(),
        root = document.documentElement;

	mouseX = evt.pageX - rect.left - root.scrollLeft;
	mouseY = evt.pageY - rect.top - root.scrollTop;
}

function createObjects(){
	for(var i = 0; i < objectCount; i++){
		var w = getRandomIntInRange(objectMinDim, objectMaxDim);
		var h = getRandomIntInRange(objectMinDim, objectMaxDim);
		var x = getRandomIntInRange(0, canvas.width);
		var y = getRandomIntInRange(0, canvas.height);

		var obj = new GameObject(x, y, w, h, 'red');
		objectList.push(obj);
	}
}

function sortObjects(){

    quadTree.clear();
    for (var i = 0; i < objectList.length; i++){
        quadTree.insert(objectList[i]);
	}
}
function drawBackground(){
	canvasContext.fillStyle = 'black';
	canvasContext.fillRect(0,0,canvas.width,canvas.height);
}


function handleClick(evt){
    var returnObjects = [];
	returnObjects = quadTree.retrieve(returnObjects, dynamicObj);
    console.log(returnObjects);
}

class GameObject {
	constructor(x, y, width, height, color){
		this.x = x;
		this.y = y;
		this.width = width;
		this.height = height;
        this.color = color;
	}

	draw(){
		canvasContext.save();
		canvasContext.translate(this.x, this.y);
		canvasContext.fillStyle = this.color;
		canvasContext.fillRect(0, 0, this.width, this.height);
		canvasContext.restore();
	}
}

class QuadTree {
	constructor(minX, maxX, minY, maxY, maxDepth, maxChildren, level){
		this.maxDepth = maxDepth;
		this.maxChildren = maxChildren;
		this.minX    = minX;
		this.maxX    = maxX;
		this.minY    = minY;
		this.maxY    = maxY;
		this.width   = maxX - minX;
		this.height  = maxY - minY;
		this.level   = level;
		this.nodes   = [];
		this.objects = [];

	}
	clear(){
		this.objects = [];

		for (var i = 0; i < this.nodes.length; i++){
			if (this.nodes[i] != null){
				this.nodes[i].clear();
				this.nodes[i] = null;
			}
		}
	}
	draw(){
		canvasContext.save();
		canvasContext.translate(this.minX, this.minY);
		canvasContext.beginPath();
		canvasContext.lineWidth = "6";
		canvasContext.strokeStyle = "blue";
		canvasContext.rect(0, 0, this.width, this.height);
		canvasContext.stroke();
		canvasContext.restore();

		for (var i = 0; i < this.nodes.length; i++){
			if (this.nodes[i] != null){
				this.nodes[i].draw();
			}
		}
	}
	splitNode(){
		var subWidth  = Math.floor((this.width)/2);
		var subHeight = Math.floor((this.height)/2);

		this.nodes.push(new QuadTree(this.minX, this.minX + subWidth, this.minY, this.minY + subHeight, this.maxDepth, this.maxChildren, this.level + 1));
		this.nodes.push(new QuadTree(this.minX + subWidth, this.maxX, this.minY, this.minY + subHeight, this.maxDepth, this.maxChildren, this.level + 1));
		this.nodes.push(new QuadTree(this.minX, this.minX + subWidth, this.minY + subHeight, this.maxY, this.maxDepth, this.maxChildren, this.level + 1));
		this.nodes.push(new QuadTree(this.minX + subWidth, this.maxX, this.minY + subHeight, this.maxY, this.maxDepth, this.maxChildren, this.level + 1));
	}
	getIndex(obj){
		var index = -1;
		var horizontalMidpoint = this.minX + this.width/2;
		var verticalMidpoint   = this.minY + this.height/2;

		if (obj.x > this.minX && obj.x + obj.width < horizontalMidpoint){
			var leftQuadrant = true;
		}
		if (obj.x + obj.width < this.maxX && obj.x > horizontalMidpoint){
			var rightQuadrant = true;
		}

		if (obj.y > this.minY && obj.y + obj.height < verticalMidpoint){
			if (leftQuadrant){
				index = 0;
			}
			else if (rightQuadrant){
				index = 1;
			}
		}
		else if (obj.y + obj.width < this.maxY && obj.y > verticalMidpoint){
			if (leftQuadrant){
				index = 2;
			}
			else if (rightQuadrant){
				index = 3;
			}
		}
		return index;
	}

	insert(obj){
		if (this.nodes[0] != null){
			var index = this.getIndex(obj);
			if (index != -1){
				this.nodes[index].insert(obj);

				return;
			}
		}
		this.objects.push(obj);

		if (this.objects.length > this.maxChildren && this.level < this.maxDepth){
			if (this.nodes[0] == null){
				this.splitNode();
			}

			var i = 0;
			while(i < this.objects.length){
				var index = this.getIndex(this.objects[i]);
				if (index != -1){
					this.nodes[index].insert(this.objects[i]);
					this.objects.splice(i, 1);
				}
				else{
					i++;
				}
			}
		}
	}
	retrieve(returnObjects, obj){
		var index = this.getIndex(obj);
        //console.log(this.nodes[0]);

		if (index != -1 && this.nodes[0] != null){
			this.nodes[index].retrieve(returnObjects, obj);
		}
        returnObjects.push.apply(returnObjects, this.objects);
		return returnObjects;
	}
}

//------utils------//
function getRandomIntInRange(min, max){
	return Math.floor(Math.random() * (max-min) + min);
}
</script>
</html>
{'fraction_non_alphanumeric': 0.16041478809738502, 'fraction_numerical': 0.010459873760144274, 'mean_word_length': 3.4848362312980186, 'pattern_counts': {'":': 0, '<': 36, '<?xml version=': 0, '>': 25, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '67502', 'n_tokens_mistral': 4393, 'n_tokens_neox': 3928, 'n_words': 863}