|
// TODO: onEnter onLeave sensors? |
|
// Size is considered Radius and origin point xy should be at center. |
|
// An implementation of a range based square QuadTree. |
|
// Which keeps leafs around if they have any nodes in them. |
|
// Child leafs are only removed when empty. |
|
// Querys check position and size nodes to see if they are inside the query radius. |
|
// See my code pen here for more detail: http://codepen.io/LiamKarlMitchell/pen/raxRKq |
|
// The old one. |
|
//http://codepen.io/LiamKarlMitchell/pen/zImip |
|
var QuadTreeConstants = { |
|
useLocal: 0, |
|
useObject: 1, |
|
useObjectLocation: 2, |
|
useObjectPosition: 3, |
|
useParam: 4, |
|
useFunction: 5 |
|
}; |
|
|
|
function AABBCircleIntersect(circle, rectangle) { |
|
// Circle is x,y, radius |
|
// Rectangle is top left bottom right |
|
// We need a copy of the point |
|
var circle_copy = { |
|
x: circle.x, |
|
y: circle.y |
|
}; |
|
// Snap our circle to the rectangle corner/side its nearest |
|
if(circle_copy.x > rectangle.right) { |
|
circle_copy.x = rectangle.right; |
|
} else if(circle_copy.x < rectangle.left) { |
|
circle_copy.x = rectangle.left; |
|
} |
|
if(circle_copy.y > rectangle.bottom) { |
|
circle_copy.y = rectangle.bottom; |
|
} else if(circle_copy.y < rectangle.top) { |
|
circle_copy.y = rectangle.top; |
|
} |
|
var dx = circle_copy.x - circle.x; |
|
var dy = circle_copy.y - circle.y; |
|
var distance = Math.sqrt(Math.abs((dx * dx) + (dy * dy))); |
|
if(distance < circle.radius) return true; |
|
return false; |
|
} |
|
|
|
function QuadTreeNode(opts) { |
|
if(opts === undefined) { |
|
throw new Error('QuadTreeNode requires opts to be defined.'); |
|
} |
|
this.id = undefined; |
|
this.lifetime = 0; |
|
this.x = opts.x || 0; |
|
this.y = opts.y || 0; |
|
this.size = opts.size || 1; |
|
this._valueAccess = QuadTreeConstants.useLocal; |
|
this.object = opts.object || null; |
|
this.type = undefined; |
|
// TODO: Switch to using bitflag? or multi option thing. For example if i want function update but then use object x and y or object.location.x etc |
|
if(this.object !== null) { |
|
if(this.object.x != undefined && this.object.y != undefined) { |
|
this._valueAccess = QuadTreeConstants.useObject; |
|
} else if(this.object.Location !== undefined) { |
|
this._valueAccess = QuadTreeConstants.useObjectLocation; |
|
} else if(this.object.position !== undefined) { |
|
this._valueAccess = QuadTreeConstants.useObjectPosition; |
|
} |
|
this.type = this.object.type || this.object.constructor.name || this.object.__proto__.constructor.name; |
|
} |
|
this.type = opts.type || this.type; |
|
if(opts.getParam) { |
|
this._getParam = opts.getParam; |
|
this._valueAccess = QuadTreeConstants.useParam; |
|
} |
|
|
|
if (typeof(opts.update) === 'function') { |
|
this.UpdateFunction = opts.update; |
|
this._valueAccess = QuadTreeConstants.useFunction; |
|
} else if (opts.useObjectUpdate) { |
|
this.UpdateFunction = this.object.update; |
|
this._valueAccess = QuadTreeConstants.useFunction; |
|
} |
|
this.update(); |
|
} |
|
// Call update to refresh the tree |
|
QuadTreeNode.prototype.update = function(delta) { |
|
if(delta !== undefined) this.lifetime += delta; |
|
switch(this._valueAccess) { |
|
case QuadTreeConstants.useFunction: |
|
var result = this.UpdateFunction.call(this.object,this,delta); |
|
if (result===null) return; |
|
|
|
this.x = result.x; |
|
this.y = result.y; |
|
this.size = result.size || this.size; |
|
break; |
|
case QuadTreeConstants.useLocal: |
|
// Do Nothing |
|
break; |
|
case QuadTreeConstants.useObject: |
|
this.x = this.object.x; |
|
this.y = this.object.y; |
|
this.size = this.object.size || 1; |
|
break; |
|
case QuadTreeConstants.useObjectLocation: |
|
this.x = this.object.Location.X; |
|
this.y = this.object.Location.Y; |
|
this.size = this.object.size || 1; |
|
break; |
|
case QuadTreeConstants.useObjectPosition: |
|
// Check if pixi loaded and if position is of pixi origin. |
|
this.x = this.object.position.x; |
|
this.y = this.object.position.y; |
|
// this.size = this.object.size; TODO: Get size propperly for XYZ |
|
// Maybe getBounds |
|
break; |
|
case QuadTreeConstants.useParam: |
|
this.x = this.object[this._getParam.x]; |
|
this.y = this.object[this._getParam.y]; |
|
this.size = this.object[this._getParam.size] || 1; |
|
break; |
|
default: |
|
throw new Error('Unspecified QuadTreeConstant. (' + this._valueAccess + ')'); |
|
break; |
|
} |
|
} |
|
// Create a tree with options |
|
// {x : 0, y: 0, size: 1000} |
|
|
|
function QuadTree(opts) { |
|
this.leafs = []; |
|
this.nodes = []; |
|
this.nodesHash = {}; |
|
this.topLevel = true; |
|
this.level = opts.level || 0; |
|
if(this.level > 0) { |
|
this.topLevel = false; |
|
} |
|
this.nextNodeID = 1; |
|
QuadTreeNode.call(this, opts); |
|
|
|
// For the root of a QuadTree we can check ignoring size constraint. |
|
if (opts.rootSpansInfinite) { |
|
this.inBounds = function(obj) { |
|
return true; |
|
} |
|
} |
|
|
|
// Set when tree splits remove when unsplit |
|
this.hasChildrenAreas = false; |
|
this.halfSize = this.size / 2; |
|
this.depth = opts.depth || 5; |
|
this.limit = opts.limit || 10; |
|
} |
|
QuadTree.prototype = Object.create(QuadTreeNode.prototype); |
|
QuadTree.prototype.clear = function() { |
|
for(var i = 0; i < this.nodes.length; i++) { |
|
delete this.nodes[i].leaf; |
|
} |
|
this.nodes = []; |
|
this.nodesHash = {}; |
|
this.leafs = []; |
|
this.hasChildrenAreas = false; |
|
this.nextNodeID = 1; |
|
} |
|
QuadTree.prototype.getNodeByID = function(input) { |
|
if (Array.isArray(input)) { |
|
var result = []; |
|
for (var i=0; i < input.length; i++) { |
|
result[i] = this.getNodeByID(input[i]); |
|
} |
|
return result; |
|
} |
|
|
|
var node; |
|
if (this.nodesHash[input]) { |
|
return this.nodesHash[input]; |
|
} |
|
|
|
if (this.hasChildrenAreas) { |
|
node = this.leafs[0].getNodeByID(input); |
|
if (node) return node; |
|
node = this.leafs[1].getNodeByID(input); |
|
if (node) return node; |
|
node = this.leafs[2].getNodeByID(input); |
|
if (node) return node; |
|
node = this.leafs[3].getNodeByID(input); |
|
if (node) return node; |
|
} |
|
|
|
return null; |
|
} |
|
QuadTree.prototype.query = function(query) { |
|
var results = []; |
|
if(query === undefined) { |
|
for(var n = 0; n < this.nodes.length; n++) { |
|
results.push({ |
|
distance: null, |
|
node: this.nodes[n], |
|
object: this.nodes[n].object |
|
}); |
|
} |
|
query = {}; |
|
} else { |
|
if (typeof(query.x) === 'undefined') query.x = 0; |
|
if (typeof(query.y) === 'undefined') query.y = 0; |
|
if(query.position) { |
|
query.x = query.position.x; |
|
query.y = query.position.y; |
|
} |
|
if(query.location) { |
|
query.x = query.location.x; |
|
query.y = query.location.y; |
|
} |
|
if (query.CVec3) { |
|
query.x = query.CVec3.X; |
|
query.y = query.CVec3.Z; |
|
} |
|
if(query.radius === undefined) { |
|
for(var n = 0; n < this.nodes.length; n++) { |
|
var distance = null; |
|
|
|
if (query.x !== undefined && query.y !== undefined) { |
|
var dx = this.nodes[n].x - query.x; |
|
var dy = this.nodes[n].y - query.y; |
|
distance = Math.sqrt(Math.abs((dx * dx) + (dy * dy))) - this.nodes[n].size; |
|
} |
|
|
|
results.push({ |
|
distance: distance, |
|
node: this.nodes[n], |
|
object: this.nodes[n].object |
|
}); |
|
} |
|
} else { |
|
if(this.hasChildrenAreas) { |
|
// Check if circle intersects square for each of these |
|
// If so then query inside |
|
var circle = { |
|
x: query.x, |
|
y: query.y, |
|
radius: query.radius |
|
}; |
|
if(AABBCircleIntersect(circle, this.leafs[0].bounds)) { |
|
results = results.concat(this.leafs[0].query(query)); |
|
} |
|
if(AABBCircleIntersect(circle, this.leafs[1].bounds)) { |
|
results = results.concat(this.leafs[1].query(query)); |
|
} |
|
if(AABBCircleIntersect(circle, this.leafs[2].bounds)) { |
|
results = results.concat(this.leafs[2].query(query)); |
|
} |
|
if(AABBCircleIntersect(circle, this.leafs[3].bounds)) { |
|
results = results.concat(this.leafs[3].query(query)); |
|
} |
|
} |
|
|
|
// Check each of the nodes |
|
for(var n = 0; n < this.nodes.length; n++) { |
|
if(this.nodes[n]) { |
|
// Get distance |
|
var dx = this.nodes[n].x - query.x; |
|
var dy = this.nodes[n].y - query.y; |
|
var distance = Math.sqrt(Math.abs((dx * dx) + (dy * dy))) - this.nodes[n].size; |
|
if(distance <= query.radius) { |
|
results.push({ |
|
distance: distance, |
|
node: this.nodes[n], |
|
object: this.nodes[n].object |
|
}); |
|
} |
|
} |
|
} |
|
|
|
} |
|
} |
|
|
|
if(this.topLevel) { |
|
// Do filter functions |
|
if(query.filter) { |
|
results = results.filter(query.filter); |
|
} |
|
if(query.type) { |
|
if(typeof(query.type) === 'string') { |
|
query.type = query.type.split(/[\s,]+/); |
|
results = results.filter(function(r) { |
|
if(query.type.indexOf(r.node.type) >= 0) { |
|
return true; |
|
} |
|
return false; |
|
}); |
|
} else if(Array.isArray(query.type)) { |
|
results = results.filter(function(r) { |
|
var type; |
|
var typeIsFunction = type instanceof Function; |
|
for (var i=0;i < query.type.length;i++) { |
|
type = query.type[i]; |
|
if (typeIsFunction && r.node.object instanceof type){ |
|
return true; |
|
} else if (type instanceof String && type == r.node.type) { |
|
return true; |
|
} |
|
} |
|
return false; |
|
}); |
|
} |
|
} |
|
// Do sorting |
|
if(query.sort !== undefined) { |
|
if(typeof(query.sort) === 'function') { |
|
results = results.sort(query.sort); |
|
} else { |
|
results = results.sort(function(a, b) { |
|
return a.distance - b.distance; |
|
}); |
|
} |
|
} |
|
} |
|
return results; |
|
} |
|
QuadTree.prototype.update = function update(delta) { |
|
// I am not sure how to handle if quad tree moves? I suppose locaitons of nodes should be relative? |
|
//QuadTreeNode.prototype.update.call(this, delta); |
|
// Should cache old x,y and size compare if different if so recalculate? That would probably be more work than just calculating it. |
|
this.bounds = { |
|
top: this.y, |
|
left: this.x, |
|
bottom: this.y + this.size, |
|
right: this.x + this.size |
|
}; |
|
//if(this.topLevel) { |
|
var i, node, leaf; |
|
for(i = 0; i < this.nodes.length; i++) { |
|
node = this.nodes[i]; |
|
var xold = node.x, yold = node.y, sizeold = node.size; |
|
node.update(delta); |
|
if (node.x == xold && node.y == yold && node.size == sizeold) { |
|
// Node has not moved |
|
continue; |
|
} |
|
leaf = node.leaf; |
|
if(!leaf.inBounds(node)) { |
|
// If node is no longer in parent leaf bounds |
|
leaf.removeNode(node); |
|
var placed = false; |
|
while(leaf.Parent || leaf.topLevel) { |
|
if(leaf.inBounds(node)) { |
|
leaf.addNode(node); |
|
placed = true; |
|
break; |
|
} |
|
if(leaf.topLevel) { |
|
break; |
|
} |
|
leaf = leaf.Parent; |
|
} |
|
if(placed == false) { |
|
console.error('node not in quad tree...'); |
|
} |
|
} else { |
|
// Check if node would fit inside a child leaf |
|
if(this.hasChildrenAreas) { |
|
var placed = false; |
|
if(this.leafs[0].inBounds(node)) { |
|
this.leafs[0].addNode(node); |
|
placed = true; |
|
} else if(this.leafs[1].inBounds(node)) { |
|
this.leafs[1].addNode(node); |
|
placed = true; |
|
} else if(this.leafs[2].inBounds(node)) { |
|
this.leafs[2].addNode(node); |
|
placed = true; |
|
} else if(this.leafs[3].inBounds(node)) { |
|
this.leafs[3].addNode(node); |
|
placed = true; |
|
} |
|
|
|
if (placed) { |
|
var index = this.nodes.indexOf(node); |
|
if(index > -1) { |
|
delete this.nodesHash[node.id]; |
|
this.nodes.splice(index, 1); |
|
} |
|
} |
|
} |
|
|
|
} |
|
} |
|
//} |
|
// If has children |
|
// Update Leafs |
|
if(this.hasChildrenAreas) { |
|
// Unrolled for speed |
|
this.leafs[0].update(delta); |
|
this.leafs[1].update(delta); |
|
this.leafs[2].update(delta); |
|
this.leafs[3].update(delta); |
|
|
|
if (this.topLevel) { |
|
function checkLeafsChildrenEmpty(quadTreeLeaf, maxDepth) { |
|
if (quadTreeLeaf.nodes.length === 0 && (quadTreeLeaf.hasChildrenAreas == false || quadTreeLeaf.level == maxDepth) ) return true; |
|
|
|
if (quadTreeLeaf.hasChildrenAreas) { |
|
var result1 = checkLeafsChildrenEmpty(quadTreeLeaf.leafs[0], maxDepth); |
|
var result2 = checkLeafsChildrenEmpty(quadTreeLeaf.leafs[1], maxDepth); |
|
var result3 = checkLeafsChildrenEmpty(quadTreeLeaf.leafs[2], maxDepth); |
|
var result4 = checkLeafsChildrenEmpty(quadTreeLeaf.leafs[3], maxDepth); |
|
|
|
if (result1 && result2 && result3 && result4) { |
|
quadTreeLeaf.leafs = []; |
|
quadTreeLeaf.hasChildrenAreas = false; |
|
if (quadTreeLeaf.nodes.length === 0) return true; |
|
} |
|
} else { |
|
if (quadTreeLeaf.nodes.length === 0) return true; |
|
} |
|
return false; |
|
} |
|
|
|
checkLeafsChildrenEmpty(this, this.depth); |
|
} |
|
} |
|
} |
|
QuadTree.prototype.inBounds = function(node) { |
|
return (this.x < node.x - node.size && |
|
this.x + this.size > node.x + node.size && |
|
this.y < node.y - node.size && |
|
this.y + this.size > node.y + node.size); |
|
} |
|
// Returns array of unplaced nodes although this should be empty |
|
QuadTree.prototype.putNodesInChildrenLeafs = function() { |
|
if(!this.hasChildrenAreas) { |
|
throw new Error('Cannot use putNodesInChildrenLeafs when there are no children leafs...'); |
|
return; |
|
} |
|
var unplaced = []; |
|
// Place the nodes in the appropriate child leaf |
|
var removed = [], node, i; |
|
for(i = 0; i < this.nodes.length; i++) { |
|
var node = this.nodes[i]; |
|
if(this.leafs[0].inBounds(node)) { |
|
this.leafs[0].addNode(node); |
|
removed.push(node); |
|
} else if(this.leafs[1].inBounds(node)) { |
|
this.leafs[1].addNode(node); |
|
removed.push(node); |
|
} else if(this.leafs[2].inBounds(node)) { |
|
this.leafs[2].addNode(node); |
|
removed.push(node); |
|
} else if(this.leafs[3].inBounds(node)) { |
|
this.leafs[3].addNode(node); |
|
removed.push(node); |
|
} else { |
|
unplaced.push(node); |
|
} |
|
|
|
} |
|
// If the node was placed in a child leaf then remove it from the parents nodes list. |
|
for (i=0;i<removed.length;i++) { |
|
node = removed[i]; |
|
var index = this.nodes.indexOf(node); |
|
if(index > -1) { |
|
delete this.nodesHash[node.id]; |
|
this.nodes.splice(index, 1); |
|
} |
|
} |
|
return unplaced; |
|
} |
|
QuadTree.prototype.removeNode = function(value) { |
|
var node; |
|
if(value instanceof QuadTreeNode) { |
|
node = value; |
|
value = node.id; |
|
} else if(typeof(value) === 'number') { |
|
// Do nothing |
|
} else { |
|
throw new Error('Invalid value passed to QuadTree::removeNode'); |
|
return; |
|
} |
|
if(node === undefined) { |
|
node = this.nodesHash[value]; |
|
} |
|
if(node.leaf !== undefined && node.leaf !== this && this.topLevel) { |
|
node.leaf.removeNode(node); |
|
} |
|
var index = this.nodes.indexOf(node); |
|
if(index > -1) { |
|
delete this.nodesHash[node.id]; |
|
this.nodes.splice(index, 1); |
|
delete node.leaf; |
|
} |
|
} |
|
QuadTree.prototype.addNode = function(node) { |
|
if(this.topLevel) { |
|
if(node instanceof QuadTreeNode === false) { |
|
node = new QuadTreeNode(node); |
|
} |
|
if(node.id === undefined) { |
|
node.id = this.nextNodeID; |
|
this.nextNodeID++; |
|
} |
|
} |
|
node.leaf = this; |
|
// Check any children that exist if we can add it there |
|
if(this.hasChildrenAreas) { |
|
if(this.leafs[0].inBounds(node)) { |
|
this.leafs[0].addNode(node); |
|
} else if(this.leafs[1].inBounds(node)) { |
|
this.leafs[1].addNode(node); |
|
} else if(this.leafs[2].inBounds(node)) { |
|
this.leafs[2].addNode(node); |
|
} else if(this.leafs[3].inBounds(node)) { |
|
this.leafs[3].addNode(node); |
|
} else { |
|
this.nodes.push(node); |
|
this.nodesHash[node.id] = node; |
|
} |
|
// Check if we need to create child areas |
|
} else if(this.depth > 0 && this.nodes.length + 1 > this.limit) { |
|
this.hasChildrenAreas = true; |
|
this.leafs[0] = new QuadTree({ |
|
x: this.x, |
|
y: this.y, |
|
size: this.halfSize, |
|
limit: this.limit, |
|
depth: this.depth - 1, |
|
level: this.level + 1 |
|
}); |
|
this.leafs[1] = new QuadTree({ |
|
x: this.x + this.halfSize, |
|
y: this.y, |
|
size: this.halfSize, |
|
limit: this.limit, |
|
depth: this.depth - 1, |
|
level: this.level + 1 |
|
}); |
|
this.leafs[2] = new QuadTree({ |
|
x: this.x, |
|
y: this.y + this.halfSize, |
|
size: this.halfSize, |
|
limit: this.limit, |
|
depth: this.depth - 1, |
|
level: this.level + 1 |
|
}); |
|
this.leafs[3] = new QuadTree({ |
|
x: this.x + this.halfSize, |
|
y: this.y + this.halfSize, |
|
size: this.halfSize, |
|
limit: this.limit, |
|
depth: this.depth - 1, |
|
level: this.level + 1 |
|
}); |
|
this.leafs[0].Parent = this; |
|
this.leafs[1].Parent = this; |
|
this.leafs[2].Parent = this; |
|
this.leafs[3].Parent = this; |
|
this.nodes.push(node); |
|
this.nodesHash[node.id] = node; |
|
// Reorganize Nodes |
|
this.putNodesInChildrenLeafs(); |
|
}// else if(this.topLevel === false) { |
|
else { |
|
if(this.inBounds(node)) { |
|
this.nodes.push(node); |
|
this.nodesHash[node.id] = node; |
|
node.leaf = this; |
|
} else { |
|
console.error('Node outside Quad Tree bounds ' + this.x + ',' + this.y + ' size ' + this.size); |
|
return null; |
|
} |
|
} |
|
|
|
return node; |
|
} |
|
|
|
QuadTree.QuadTreeConstants = QuadTreeConstants; |
|
QuadTree.AABBCircleIntersect = AABBCircleIntersect; |
|
QuadTree.QuadTreeNode = QuadTreeNode; |
|
|
|
if(typeof module !== "undefined" && module.exports) { |
|
module.exports = QuadTree; |
|
} |
|
if(typeof window !== "undefined") { |
|
window.QuadTree = QuadTree; |
|
} |
|
// END OF QUAD TREE CODE |
|
|
|
// Render stuff / test |
|
QuadTreeNode.prototype.render = function(graphics) { |
|
graphics.lineStyle(3, this.color || 0xFF0000, 1); |
|
graphics.drawCircle(this.x, this.y, this.size); |
|
} |
|
|
|
// Debug only rendering of the tree |
|
QuadTree.prototype.render = function(graphics) { |
|
graphics.lineStyle(1, this.color || 0x333333, 0.75); |
|
//if (this.negative) { |
|
/* graphics.drawRect(this.x-this.halfSize, this.y-this.halfSize, this.size, this.size); |
|
} else {*/ |
|
graphics.drawRect(this.x, this.y, this.size, this.size); |
|
//} |
|
// If has children |
|
if(this.hasChildrenAreas) { |
|
// Unrolled for speed |
|
this.leafs[0].render(graphics); |
|
this.leafs[1].render(graphics); |
|
this.leafs[2].render(graphics); |
|
this.leafs[3].render(graphics); |
|
} |
|
|
|
for(var i = 0; i < this.nodes.length; i++) { |
|
this.nodes[i].render(graphics); |
|
} |
|
} |
|
|
|
|
|
// TODO: Make everything relative to the parent it is in. |
|
//var obj = { x: 100, y: 100, size: 10 }; |
|
var myTree = new QuadTree({ |
|
x: 0, |
|
y: 0, |
|
size: 590, |
|
depth: 5, |
|
limit: 3, |
|
rootSpansInfinite: true |
|
}); |
|
//myTree.addNode(obj); |
|
// create an new instance of a pixi stage |
|
var stage = new PIXI.Stage(0xFFFFFF, true); |
|
var renderer = PIXI.autoDetectRenderer(600, 600, null, false, true); |
|
renderer.view.style.display = "block"; |
|
$('#container').append(renderer.view); |
|
$queryText = $('#queryText'); |
|
|
|
|
|
var graphics = new PIXI.Graphics(); |
|
|
|
graphics.hitArea = new PIXI.Rectangle(myTree.x, myTree.y, myTree.size, myTree.size); |
|
|
|
graphics.setInteractive(true); |
|
graphics.click = function(mouseData) { |
|
var point = mouseData.getLocalPosition(this); |
|
switch(mouseData.originalEvent.button) { |
|
case 0: |
|
// Left Click |
|
var newobj = { |
|
x: point.x, |
|
y: point.y, |
|
size: 5, |
|
type: 'Player' |
|
}; |
|
myTree.addNode(new QuadTreeNode({ |
|
object: newobj |
|
})); |
|
break; |
|
case 1: |
|
// Middle Click |
|
queryOptions.x = Math.floor(point.x); |
|
queryOptions.y = Math.floor(point.y); |
|
break; |
|
case 2: |
|
// Right click |
|
break; |
|
} |
|
|
|
return false; |
|
} |
|
|
|
stage.addChild(graphics); |
|
var queryOptions = { |
|
x: 50, |
|
y: 50, |
|
radius: 100 |
|
}; |
|
|
|
// Rendering part |
|
var speedHack = 1; |
|
var lastTime; |
|
var delta; |
|
var fps = 0; |
|
var $fps = $('#fps'); |
|
|
|
setInterval(function() { |
|
$fps.text("FPS: " + Math.floor(fps)); |
|
}, 250); |
|
|
|
function animate(time) { |
|
if(lastTime === undefined) lastTime = time; |
|
delta = time - lastTime; |
|
graphics.clear(); |
|
|
|
myTree.update(delta * speedHack); |
|
myTree.render(graphics); |
|
|
|
fps = 1000 / delta; |
|
|
|
graphics.lineStyle(1, 0x0000FF, 1); |
|
graphics.drawCircle(queryOptions.x, queryOptions.y, queryOptions.radius); |
|
|
|
var results = myTree.query(queryOptions); |
|
$queryText.text("Result Query " + queryOptions.x + ',' + queryOptions.y + ' radius ' + queryOptions.radius + ': ' + results.length); |
|
|
|
renderer.render(stage); |
|
lastTime = time; |
|
requestAnimFrame(animate); |
|
} |
|
requestAnimFrame(animate); |
|
|
|
function clearTree() { |
|
myTree.clear(); |
|
return false; |
|
} |
|
|
|
function addMovingNode() { |
|
var mySize = 15; |
|
var newobj = { |
|
x: 10, |
|
y: 10, |
|
size: mySize |
|
}; |
|
var AliveTime = 2000 |
|
var node = myTree.addNode(newobj); |
|
|
|
if(!node) { |
|
console.error('Did not insert node into QuadTree.'); |
|
return; |
|
} |
|
|
|
node.render = function(graphics) { |
|
graphics.lineStyle(3, 0xFF0000, 1); /* this.size = ((this.lifetime / AliveTime) * mySize);*/ |
|
|
|
graphics.drawCircle(this.x, this.y, this.size); |
|
}; |
|
|
|
newobj.moveInterval = setInterval(function() { |
|
newobj.x += 1; |
|
newobj.y += 1; |
|
}, 1); |
|
setTimeout(function() { |
|
clearInterval(newobj.moveInterval); |
|
myTree.removeNode(node); |
|
}, AliveTime); |
|
|
|
return false; |
|
} |
|
|
|
$('#btnClear').click(clearTree); |
|
$('#btnAddMoving').click(addMovingNode); |
|
|
|
|
|
/* Attacker Collection is a way to keep track of attackers */ |
|
// attackers should not be touched external to this code |
|
var AttackerCollection = function() { |
|
this.attackers = []; |
|
} |
|
|
|
// Regulate lets us add or update an ID with a set amount of damage. |
|
AttackerCollection.prototype.regulate = function(ID, Damage) { |
|
var attacker = null; |
|
|
|
for(var i in this.attackers) { |
|
if(this.attackers[i].ID == ID) { |
|
attacker = this.attackers[i]; |
|
break; |
|
} |
|
} |
|
|
|
if(attacker) { // Update |
|
attacker.Damage += Damage; |
|
} else { // Add |
|
this.attackers.push({ |
|
ID: ID, |
|
Damage: Damage |
|
}); |
|
} |
|
} |
|
|
|
// If we take references to this collections array and want to clear those to we should set .length = 0 |
|
AttackerCollection.prototype.clear = function() { |
|
this.attackers.length = []; |
|
} |
|
|
|
// Returns the attackers array |
|
AttackerCollection.prototype.sort = function() { |
|
if(this.attackers.length > 1) { |
|
this.attackers = this.attackers.sort(function(a, b) { |
|
return b.Damage - a.Damage; |
|
}); // Sort descending by Damage |
|
} |
|
return this.attackers; |
|
} |
|
|
|
/* Monster Stuff goes here */ |
|
|
|
function Monster(mi) { |
|
this.mi = mi; |
|
this.size = mi.size | 5; |
|
this.updateInterval; |
|
this.action = 'created'; |
|
this.actionTimer = 5000; |
|
this.speed = mi.speed | 5; |
|
this.attackers = new AttackerCollection(); |
|
this.initTemp(); |
|
this.health = 0; |
|
this.target = null; |
|
} |
|
|
|
Monster.prototype.initTemp = function() { |
|
this.temp = { |
|
aggroTimer: 0 |
|
}; |
|
} |
|
|
|
Monster.prototype.sendUpdate = function() { |
|
console.log('Send monster update.'); |
|
clearInterval(this.updateInterval); |
|
this.updateInterval = setInterval(this.sendUpdate, 4000); |
|
} |
|
|
|
Monster.prototype.damage = function(id, damage) { |
|
this.health -= damage; |
|
|
|
this.attackers.regulate(id,damage); |
|
if (this.health < 0) this.health = 0; |
|
console.log(this.id+' hurt by '+(id || 'world')+' for '+damage+' hp is now '+this.health); |
|
|
|
if (this.health === 0) { |
|
if (id) { |
|
// Drop items etc if killed by an ID. |
|
} |
|
|
|
this.action = 'death'; |
|
this.actionTimer = null; |
|
return true; |
|
} |
|
return false |
|
} |
|
|
|
Monster.prototype.heal = function(amount) { |
|
if (amount <= 0) { // If nothing passed for amount or its a negative then heal fully. |
|
amount = this.mi.health || 100; |
|
} |
|
this.health += amount; |
|
if (this.health > this.mi.health || 100) { |
|
this.health = this.mi.health || 100; |
|
} |
|
} |
|
|
|
var radian = Math.PI / 180; |
|
Monster.prototype.update = function monster_update(node, delta) { |
|
var self = this; |
|
if(this.actionTimer > 0) { |
|
this.actionTimer -= delta; |
|
} |
|
|
|
switch(this.action) { |
|
case 'spawn': |
|
if(this.actionTimer <= 0) { |
|
this.attackers.clear(); |
|
this.initTemp(); |
|
this.action = 'idle'; |
|
this.actionTimer = Math.floor((Math.random() * (100 - 50) + 50)) * 10; |
|
this.heal(); |
|
console.log(this.id + ' spawned'); |
|
this.target = null; |
|
} |
|
break; |
|
case 'idle': |
|
if (this.actionTimer === null) { |
|
this.actionTimer = 0; |
|
this.temp.aggroTimer = 0; |
|
} |
|
this.temp.aggroTimer -= delta; |
|
if(this.temp.aggroTimer <= 0) { |
|
|
|
this.temp.aggroTimer = 500; |
|
this.target = null; |
|
|
|
if (this.mi.aggro_range > 0) { |
|
var targets = myTree.query({ x: this.x, y: this.y, radius: this.mi.sight_radius, sort: true, type: Monster, filter: function(r){ return r.object !== self && r.object.health > 0 } }); |
|
if (targets.length > 0) { |
|
this.target = targets[0].object.id; |
|
console.log(this.id + ' aggros '+this.target); |
|
if (targets[0].distance <= this.mi.range) { |
|
this.action = 'attack'; |
|
this.actionTimer = null; |
|
break; |
|
} |
|
this.actionTimer = null; |
|
this.action = 'move'; |
|
break; |
|
} |
|
} |
|
|
|
var attackers = this.attackers.sort(); |
|
if (attackers.length > 0) { |
|
for (var i=0; i<attackers.length; i++) { |
|
var targetNode = myTree.getNodeByID(attackers[i].ID); |
|
if (targetNode === null) { |
|
continue; |
|
} |
|
|
|
// Target is already dead |
|
if (targetNode.object.health <= 0) { |
|
continue; |
|
} |
|
|
|
var dx = targetNode.object.x - this.x; |
|
var dy = targetNode.object.y - this.y; |
|
var distance = Math.sqrt(Math.abs((dx * dx) + (dy * dy))) - (targetNode.object.size + this.size + this.mi.range); |
|
|
|
this.target = attackers[i].ID; |
|
console.log(this.id + ' targets its attacker '+this.target); |
|
if (distance <= this.mi.range) { |
|
this.actionTimer = null; |
|
this.action = 'attack'; |
|
return this; |
|
} |
|
this.actionTimer = null; |
|
this.action = 'move'; |
|
return this; |
|
} |
|
} |
|
} |
|
if(this.actionTimer <= 0) { |
|
if(Math.random() * 100 <= 30) { |
|
this.actionTimer = null; |
|
this.action = 'move'; |
|
break; |
|
} |
|
|
|
this.actionTimer = (Math.floor(2 + (Math.random() * 5))) * 1000; |
|
} |
|
break; |
|
// A Move assumes that the monster is not currently moving and that there is no friction or anything. |
|
// It picks a direction and distance and moves towards it. |
|
// See here for details http://inifintiesky.blogspot.co.nz/2015/01/how-to-make-ai-walk-around-seemingly.html |
|
case 'move': |
|
if(this.actionTimer === null) { |
|
var distance; |
|
|
|
if (this.target !== null) { |
|
var targetNode = myTree.getNodeByID(this.target); |
|
if (targetNode) { |
|
var dx = targetNode.object.x - this.x; |
|
var dy = targetNode.object.y - this.y; |
|
// Distance to be in range |
|
distance = Math.sqrt(Math.abs((dx * dx) + (dy * dy))) - (targetNode.object.size + this.size + this.mi.range); |
|
|
|
if (distance <= this.mi.range) { |
|
this.action = 'attack'; |
|
this.actionTimer = null; |
|
break; |
|
} |
|
|
|
// Multiplying sight radius by 2 as following something should be heightened sense as its focusing on them. |
|
if (distance > this.mi.sight_radius*2) { |
|
this.action = 'idle'; |
|
this.actionTimer = null; |
|
break; |
|
} |
|
|
|
this.newdir = Math.atan2(dy, dx) * (180 / Math.PI); |
|
|
|
} else { |
|
this.action = 'idle'; |
|
this.actionTimer = 3000; |
|
break; |
|
} |
|
} else { |
|
this.newdir = (getWeightedRandomRangeValue(preferedDirectionRanges) + this.direction) % 360; |
|
distance = getWeightedRandomRangeValue(preferedDistanceRanges); |
|
} |
|
this.direction = this.newdir; |
|
|
|
var rad = this.newdir * radian; |
|
this.velocity = { |
|
x: Math.cos(rad), |
|
y: Math.sin(rad) |
|
}; |
|
|
|
this.newx = this.x + (distance * this.velocity.x); |
|
this.newy = this.y + (distance * this.velocity.y); |
|
this.actionTimer = (distance / this.speed) * 1000; |
|
|
|
if (this.target === null) { |
|
// Re-roll to keep inside tree I hope. |
|
if(this.newx < 0) this.actionTimer = null; |
|
if(this.newy < 0) this.actionTimer = null; |
|
if(this.newx > myTree.size) this.actionTimer = null; |
|
if(this.newy > myTree.size) this.actionTimer = null; |
|
} |
|
} else if(this.actionTimer <= 0) { |
|
this.x = this.newx; |
|
this.y = this.newy; |
|
|
|
if (this.target !== null) { |
|
this.action = 'attack'; |
|
this.actionTimer = null; |
|
break; |
|
} |
|
|
|
this.action = 'idle'; |
|
this.actionTimer = Math.floor(300 + (Math.random() * 700)); |
|
} else { |
|
// Could plan for adjustment of movement of object here. |
|
// Plot best intersection point etc if target has movment velocity using lerp? |
|
// Get other direction and speed |
|
// If other direction is different to our direction then recalculate direction to best intersect?? |
|
this.x += (this.velocity.x * this.speed) * (delta / 1000); |
|
this.y += (this.velocity.y * this.speed) * (delta / 1000); |
|
} |
|
break; |
|
case 'attack': |
|
if (this.actionTimer === null) { |
|
this.actionTimer = 0; // Attack now |
|
// Get attack speed * 4 check every 1/4 if target still in range. |
|
} |
|
|
|
if (this.actionTimer <= 0) { |
|
var targetNode = myTree.getNodeByID(this.target); |
|
if (targetNode === null) { |
|
this.actionTimer = null; |
|
this.action = 'idle'; |
|
break; |
|
} |
|
|
|
var dx = targetNode.object.x - this.x; |
|
var dy = targetNode.object.y - this.y; |
|
distance = Math.sqrt(Math.abs((dx * dx) + (dy * dy))) - (targetNode.object.size + this.size + this.mi.range); |
|
|
|
if (distance > this.mi.sight_radius*2) { |
|
this.action = 'idle'; |
|
this.actionTimer = null; |
|
break; |
|
} |
|
|
|
if (distance > this.mi.range) { |
|
this.action = 'move'; |
|
this.actionTimer = null; |
|
break; |
|
} |
|
|
|
// Calculate damage etc |
|
var damage = 10 |
|
|
|
// TOOD: Move doing damage into a monster prototype method |
|
// TODO: Add monster death action/animation and set it if monster is killed |
|
// TODO: Add respawn |
|
var isDead = targetNode.object.damage(this.id, damage); |
|
|
|
if (isDead) { |
|
console.log(this.id+'\'s target is now dead'); |
|
this.actionTimer = null; |
|
this.action = 'idle'; |
|
break; |
|
} |
|
|
|
this.actionTimer = 1000; // set to next attack speed time. |
|
} |
|
break; |
|
case 'death': |
|
if (this.actionTimer === null) { |
|
this.actionTimer = 30000; // How long to keep monster dead? |
|
} |
|
|
|
if (this.actionTimer <= 0) { |
|
this.action = 'spawn'; |
|
} |
|
break; |
|
default: |
|
this.action = 'spawn'; |
|
this.actionTimer = 1000; // We could randomize spawn delay slightly to balance monster AI load on server? |
|
break; |
|
} |
|
|
|
return this; |
|
} |
|
|
|
// Monster Info |
|
var MonsterInfo = [{ |
|
id: 1, |
|
name: 'Basic', |
|
size: 5, |
|
range: 1, |
|
speed: 90, |
|
aggro_range: 0, |
|
sight_radius: 100, |
|
health: 100 |
|
}, // Mele |
|
{ |
|
id: 2, |
|
name: 'Ranged', |
|
size: 5, |
|
range: 20, |
|
speed: 120, |
|
aggro_range: 30, |
|
sight_radius: 100, |
|
health: 150 |
|
}, { |
|
id: 3, |
|
name: 'Boss', |
|
size: 15, |
|
range: 10, |
|
speed: 100, |
|
aggro_range: 15, |
|
sight_radius: 100, |
|
health: 500 |
|
}]; |
|
|
|
// See http://inifintiesky.blogspot.co.nz/2015/01/how-to-make-ai-walk-around-seemingly.html for an example of how these are used. |
|
// Each odd index must be a number that has the total adding to 100. |
|
// Each even index must be an array of low and high values to use for the random range. |
|
var preferedDirectionRanges = [77, [-35, 35], 9, [-45, -35], 9, [35, 45], 5, [90, 270]]; |
|
var preferedDistanceRanges = [ |
|
15, [100, 200], // Lowest chance for Long |
|
20, [30, 60], // Low chance for Short |
|
65, [60, 90] // Higher chance for Medium |
|
]; |
|
|
|
function getWeightedRandomRangeValue(values) { |
|
var total = 0; |
|
var value = Math.random() * 100; |
|
|
|
// Get value pair |
|
for(var i = 0; i < values.length / 2; i += 2) { |
|
total += values[i]; |
|
if(value <= total) { |
|
value = Math.random() * (values[i + 1][1] - values[i + 1][0]) + values[i + 1][0]; |
|
break; |
|
} |
|
} |
|
|
|
return value; |
|
} |
|
|
|
|
|
// Used to create a monster of a certian id will return node or null. |
|
|
|
function CreateMonster(id, x, y) { |
|
var mi = MonsterInfo[id - 1]; |
|
if(!mi) { |
|
console.error('Monster Info for id ' + id + ' does not exist.'); |
|
return null; |
|
} |
|
if(x === undefined) { |
|
x = 0; |
|
} |
|
if(y === undefined) { |
|
y = 0; |
|
} |
|
|
|
var monster = new Monster(mi); |
|
monster.x = x; |
|
monster.y = y; |
|
monster.direction = Math.floor(Math.random() * 360); |
|
|
|
var newobj = { |
|
object: monster, |
|
useObjectUpdate: true |
|
}; |
|
//var AliveTime = -1 |
|
var node = myTree.addNode(newobj); |
|
monster.id = node.id; |
|
|
|
if(!node) { |
|
console.error('Did not insert node into QuadTree.'); |
|
return; |
|
} |
|
|
|
node.render = function(graphics) { |
|
graphics.lineStyle(1, mi.color || 0x00FF00, 1); |
|
|
|
if (this.object.health === 0) { |
|
graphics.beginFill(0xFF0000, 0.5); |
|
} |
|
graphics.drawCircle(this.x, this.y, this.size); |
|
graphics.endFill(); |
|
|
|
if (this.object.health === 0) { |
|
return; |
|
} |
|
|
|
if(this.object.action == 'move') { |
|
graphics.lineStyle(1, 0xFF0000, 1); |
|
|
|
graphics.moveTo(this.object.x, this.object.y); |
|
graphics.lineTo(this.object.newx, this.object.newy); |
|
graphics.drawRect(this.object.newx - 1, this.object.newy - 1, 2, 2); |
|
} |
|
|
|
if (this.object.target) { |
|
var targetNode = myTree.getNodeByID(this.object.target); |
|
if (targetNode) { |
|
graphics.lineStyle(3, 0xFF00FF, 1); |
|
graphics.moveTo(this.object.x, this.object.y); |
|
graphics.lineTo(targetNode.object.x, targetNode.object.y); |
|
} |
|
} |
|
|
|
graphics.lineStyle(1, 0x000000, 1); |
|
graphics.drawCircle(this.x, this.y, (this.size || 5) + (mi.range || 1)); |
|
}; |
|
|
|
newobj.moveInterval = setInterval(function() { |
|
//newobj.x+=1; |
|
//newobj.y+=1; |
|
}, 1000); |
|
|
|
/* setTimeout(function(){ |
|
clearInterval(newobj.moveInterval); |
|
myTree.removeNode(node); |
|
},AliveTime);*/ |
|
|
|
return node; |
|
} |
|
|
|
var Monsters = []; |
|
|
|
Monsters.push(CreateMonster(3, 140, 100)); |
|
|
|
var html = ''; |
|
for(var i = 0; i < MonsterInfo.length; i++) { |
|
html += '<option value="' + MonsterInfo[i].id + '">' + MonsterInfo[i].name + '</option>'; |
|
} |
|
$('#selMonsterType').html(html); |
|
|
|
$('#btnAddMonster').click(function() { |
|
Monsters.push(CreateMonster($('#selMonsterType').val(), queryOptions.x, queryOptions.y)); |
|
}); |
