From 803c3a002550836d5cb35e11099c863e32c1611e Mon Sep 17 00:00:00 2001 From: dsc Date: Mon, 20 Dec 2010 05:26:02 -0800 Subject: [PATCH] Checkpoint on movement refactor to support passable zones. --- src/Y/op.cjs | 2 +- src/Y/types/array.cjs | 12 +- src/Y/types/string.cjs | 5 +- src/Y/utils.cjs | 105 +++++++++--- src/ezl/loc/boundingbox.cjs | 105 ++++++++--- src/ezl/math/index.cjs | 8 +- src/ezl/math/line.cjs | 4 +- src/ezl/math/rect.cjs | 15 ++ src/ezl/math/vec.cjs | 3 +- src/ezl/util/binaryheap.cjs | 31 +++- src/tanks/game.cjs | 2 +- src/tanks/map/index.cjs | 6 +- src/tanks/map/map.cjs | 99 +++++++++++ src/tanks/map/pathmap.cjs | 401 +++++++++++++++++++++++------------------ src/tanks/map/trajectory.cjs | 30 ++-- src/tanks/map/traversal.cjs | 147 +++++++++------- src/tanks/thing/bullet.cjs | 77 ++++++--- src/tanks/thing/item.cjs | 2 +- src/tanks/thing/player.cjs | 2 +- src/tanks/thing/tank.cjs | 45 +++-- src/tanks/thing/thing.cjs | 13 +- src/tanks/ui/configui.cjs | 1 + src/tanks/ui/pathmapui.cjs | 2 +- www/deps.html | 4 +- 24 files changed, 748 insertions(+), 373 deletions(-) create mode 100644 src/tanks/map/map.cjs diff --git a/src/Y/op.cjs b/src/Y/op.cjs index 408e640..7a9e6ca 100644 --- a/src/Y/op.cjs +++ b/src/Y/op.cjs @@ -64,7 +64,7 @@ var core = require('Y/core') var args = slice.call(arguments,1); return function(obj){ if (obj && obj[name]) - return obj[name].apply( obj, args.concat(slice.call(arguments,0)) ); + return obj[name].apply( obj, args.concat(slice.call(arguments,1)) ); else return obj; }; diff --git a/src/Y/types/array.cjs b/src/Y/types/array.cjs index 00c3e13..f4a8733 100644 --- a/src/Y/types/array.cjs +++ b/src/Y/types/array.cjs @@ -19,14 +19,16 @@ YCollection.subclass('YArray', function(YArray){ var newYArray = YArray.instantiate.bind(YArray); - mixin(YArray, { donor:_Array, + mixin({ target:YArray, donor:_Array, context:'_o', names:'indexOf lastIndexOf shift pop join'.split(' ') }); - mixin(YArray, { donor:_Array, chain:true, + mixin({ target:YArray, donor:_Array, context:'_o', chain:true, names:'push unshift sort splice reverse'.split(' ') }); - mixin(YArray, { donor:_Array, fnFirst:true, wrap:newYArray, + mixin({ target:YArray, donor:_Array, context:'_o', fnFirst:true, wrap:newYArray, names:'map forEach filter'.split(' ') }); - mixin(YArray, { donor:_Array, fnFirst:true, names:['reduce', 'some', 'every'] }); - mixin(YArray, { donor:_Array, wrap:newYArray, names:['slice'] }); + mixin({ target:YArray, donor:_Array, context:'_o', fnFirst:true, + names:['reduce', 'some', 'every'] }); + mixin({ target:YArray, donor:_Array, context:'_o', wrap:newYArray, + names:['slice'] }); diff --git a/src/Y/types/string.cjs b/src/Y/types/string.cjs index 993d4c5..8acefdb 100644 --- a/src/Y/types/string.cjs +++ b/src/Y/types/string.cjs @@ -9,9 +9,10 @@ var YCollection = require('Y/types/collection').YCollection exports['YString'] = YCollection.subclass('YString', function(YString){ - mixin(YString, { donor:String, wrap:YString.instantiate.bind(YString), + var newYString = YString.instantiate.bind(YString); + mixin({ target:YString, donor:String, context:'_o', wrap:newYString, names:'slice substr substring concat replace toLowerCase toUpperCase'.split(' ') }); - mixin(YString, { donor:String, + mixin({ target:YString, donor:String, context:'_o', names:'split indexOf lastIndexOf charAt charCodeAt'.split(' ') }); function trim(val){ diff --git a/src/Y/utils.cjs b/src/Y/utils.cjs index 9933e47..b55e8b2 100644 --- a/src/Y/utils.cjs +++ b/src/Y/utils.cjs @@ -1,8 +1,10 @@ var YFunction = require('Y/types/function').YFunction -, isFunction = require('Y/type').isFunction +, type = require('Y/type') , core = require('Y/core') , op = require('Y/op') , slice = core.slice +, isFunction = type.isFunction +, isArray = type.isArray ; @@ -24,35 +26,96 @@ function bindAll(o, names){ } -var defaults = { - 'donor' : null, - 'names' : null, +var +This = mixin['This'] = {}, +Target = mixin['Target'] = {}, +defaults = { + /** + * {Object|Function} target Required. Target object onto which methods will be added. If this a Function, it's prototype will be used. + */ + 'target' : null, + + /** + * {Object|Function} donor Required. Donor object on which to look up names. If this a Function, it's prototype will be used. + */ + 'donor' : null, + + /** + * {Array} names Required. Names to mix into `target`. + */ + 'names' : null, + + /** + * {mixin.This|mixin.Target|String} [context=mixin.This] + * Sets the call context for the function. + * - {mixin.This}: (Default) Use runtime `this` as context. + * - {mixin.Target}: Use `target` as context. + * - {String}: Names a property on `this` to use. If specified and property is false-y, `this` is used. + */ + 'context' : This, + + /** + * {Boolean} [override=true] Whether to override existing methods of the same name. + */ 'override' : true, - 'wrap' : false, - 'chain' : false, - 'fnFirst' : false + + /** + * {Boolean} [chain=false] If true, the method always returns `this`. Supercedes `wrap`. + */ + 'chain' : false, + + /** + * {Function} [wrap] If supplied, this function is called on the result of the delegate-call. The result + * from that call is then returned. This option is superceded by `chain`. + */ + 'wrap' : false, + + /** + * {Boolean} [fnFirst=false] If true, `Function.toFunction()` will be called on the first argument + * received by the method. + */ + 'fnFirst' : false }; -function mixin(o, options){ - var opt = core.extend({}, defaults, options), Donor = opt.donor - , target = ( isFunction(o) ? o.prototype : o ) - , proto = ( isFunction(Donor) ? Donor.prototype : Donor ) - , names = opt.names +function mixin(options){ + var o = core.extend({}, defaults, options) + , target = o.target + , donor = o.donor + , names = o.names + , cxt = o.context ; + // TODO: Throw errors on invalid values + + if (isFunction(target)) target = target.prototype; + if (isFunction(donor)) donor = donor.prototype; + if (!isArray(names)) names = [names]; + // Need a closure to capture the name names.forEach(function(name){ - var fn = proto[name]; - if ( isFunction(fn) && (opt.override || !(name in target)) ) - target[name] = function(){ - var r, A = arguments; - if (opt.fnFirst) A[0] = Function.toFunction(A[0]); - r = fn.apply(this._o || target, A); - return (opt.chain ? this : (opt.wrap ? opt.wrap(r) : r)); - }; + var fn = donor[name]; + if ( !(isFunction(fn) && (o.override || !(name in target))) ) + return; + + target[name] = function(){ + var A = arguments, r, context; + + if (o.fnFirst) + A[0] = Function.toFunction(A[0]); + + if (cxt === This) + context = this; + else if (cxt === Target) + context = target; + else + context = this[cxt] || this; + + r = fn.apply(context, A); + return (o.chain ? this : (o.wrap ? o.wrap(r) : r)); + }; }); return o; } exports['bindAll'] = bindAll; -exports['mixin'] = mixin; +exports['mixin'] = mixin; diff --git a/src/ezl/loc/boundingbox.cjs b/src/ezl/loc/boundingbox.cjs index 973757f..82b39a1 100644 --- a/src/ezl/loc/boundingbox.cjs +++ b/src/ezl/loc/boundingbox.cjs @@ -23,23 +23,82 @@ Rect.subclass('BoundingBox', { }, /** - * Changes origin definition without moving the bounds. + * Changes origin position without moving the bounds. * Use relocate() to change the position by moving the origin. */ - set originX(v){ this._origin.x = v; return v; }, - get originX(){ return this._origin.absolute(this.width,this.height, this.x1,this.y1).x; }, + set origin(o){ this._origin = o; return o; }, + get origin(){ return this._origin; }, - set originY(v){ this._origin.y = v; return v; }, - get originY(){ return this._origin.absolute(this.width,this.height, this.x1,this.y1).y; }, + /** + * Changes origin x-position without moving the bounds. + * Use relocate() to change the position by moving the origin. + */ + set originX(v){ this._origin.x = v - this.x1; return v; }, + get originX(){ return this.absOrigin.x; }, /** - * Accessor for the realized numeric origin. + * Changes origin y-position without moving the bounds. + * Use relocate() to change the position by moving the origin. */ - get absOrigin() { return this._origin.absolute(this.width,this.height, this.x1,this.y1); }, - get relOrigin() { return this._origin.absolute(this.width,this.height); }, + set originY(v){ this._origin.y = v - this.y1; return v; }, + get originY(){ return this.absOrigin.y; }, - get origin(){ return this._origin; }, + // Accessors for the realized numeric origin. + get absOrigin() { return this._origin.absolute(this.width,this.height, this.x1,this.y1); }, // TODO: cache absolute and invalidate + set absOrigin(v) { this._origin.setXY(v.x - this.x1, v.y - this.y1); return this._origin; }, + get relOrigin() { return this._origin.absolute(this.width,this.height); }, // TODO: cache absolute and invalidate + set relOrigin(v) { this._origin.setXY(v.x, v.y); return this._origin; }, + + + // Accessors for distance from origin to requested bound. + get originLeft(){ return this.relOrigin.x; }, + get originTop(){ return this.relOrigin.y; }, + get originRight(){ return this.width - this.relOrigin.x; }, + get originBottom(){ return this.height - this.relOrigin.y; }, + /** + * Calculates realized distance from origin to requested bound. + * @param {String} which Bound to use in calculation: left|right|bottom|top. + * @return {Number} Distance from origin to requested bound. + */ + originDist : function originDist(which){ + switch (which) { + case 'top' : return this.originTop; + case 'bottom' : return this.originBottom; + case 'left' : return this.originLeft; + case 'right' : return this.originRight; + default : throw new Error('WTF kind of side is '+which+'???'); + } + }, + + /** + * Determines the point and line of intersection for the specified bounding boxes + * along the given trajectory. + */ + // collision : function collision(trj, fromBB, toBB){ + // + // if (bb.x2 <= B.x1 && x2 >= B.x1) { + // side = B.leftSide; + // to = trj.pointAtX(B.x1-offX-1); + // + // } else if (bb.x1 >= B.x2 && x1 <= B.x2) { + // side = B.rightSide; + // to = trj.pointAtX(B.x2+ro.x+1); + // + // } else if (bb.y2 <= B.y1 && y2 >= B.y1) { + // side = B.topSide; + // to = trj.pointAtY(B.y1-offY-1); + // + // } else if (bb.y1 >= B.y2 && y1 <= B.y2) { + // side = B.bottomSide; + // to = trj.pointAtY(B.y2+ro.y+1); + // } + // }, + + /** + * Moves absolute location of the origin and retains its relative position of the bounds. + * This is an in-place modification of the BoundingBox. + */ relocate : function relocate(x,y){ if (x instanceof Array) { y=x[1]; x=x[0]; } var _x1 = this[X1], _y1 = this[Y1] @@ -55,10 +114,17 @@ Rect.subclass('BoundingBox', { return this.set4(x1,y1, x2,y2); }, + /** + * As relocate(), but returns a new BoundingBox. + */ relocated : function relocated(x,y){ return this.clone().relocate(x,y); }, + /** + * Resizes bounds to proportionally maintain their distance from the origin. + * This is an in-place modification of the BoundingBox. + */ resize : function resize(w,h){ if (w instanceof Array) { h=w[1]; w=w[0]; } var x1 = this[X1], y1 = this[Y1] @@ -69,7 +135,6 @@ Rect.subclass('BoundingBox', { , xp = o.xPercentage, yp = o.yPercentage ; if ( xp !== null ) { - // diff = w - wOld; abs = x1 + xp*wOld; x1 = abs - xp*w; x2 = abs + (1-xp)*w; @@ -77,7 +142,6 @@ Rect.subclass('BoundingBox', { x2 = x1 + w; if ( yp !== null ) { - // diff = h - hOld; abs = y1 + yp*hOld; y1 = abs - yp*h; y2 = abs + (1-yp)*h; @@ -87,6 +151,9 @@ Rect.subclass('BoundingBox', { return this.set4(x1,y1, x2,y2); }, + /** + * As resize, but returns a new BoundingBox. + */ resized : function resized(w,h){ return this.clone().resize(w,h); }, @@ -94,22 +161,6 @@ Rect.subclass('BoundingBox', { clone : function clone(){ var o = this._origin; return new BoundingBox(this[X1],this[Y1], this[X2],this[Y2], o[X1], o[Y1]); - }, - - - get topSide(){ return new Line(this[X1],this[Y1], this[X2],this[Y1]); }, - get bottomSide(){ return new Line(this[X1],this[Y2], this[X2],this[Y2]); }, - get leftSide(){ return new Line(this[X1],this[Y1], this[X1],this[Y2]); }, - get rightSide(){ return new Line(this[X2],this[Y1], this[X2],this[Y2]); }, - - side : function side(which){ - switch (which) { - case 'top' : return this.topSide; - case 'bottom' : return this.bottomSide; - case 'left' : return this.leftSide; - case 'right' : return this.rightSide; - default : throw new Error('Unknown side: '+which); - } } }); diff --git a/src/ezl/math/index.cjs b/src/ezl/math/index.cjs index 76587b5..57fe480 100644 --- a/src/ezl/math/index.cjs +++ b/src/ezl/math/index.cjs @@ -1,9 +1,9 @@ var Y = require('Y').Y -, Vec = require('ezl/math/vec').Vec +, vec = require('ezl/math/vec') ; Y(exports, { - 'Vec' : Vec, + 'Vec' : vec.Vec, 'Line' : require('ezl/math/line').Line, 'Rect' : require('ezl/math/rect').Rect, @@ -16,8 +16,8 @@ Y(exports, { }, 'reflect' : function reflect(v, line){ - var dot = Vec.dot - , basev = Vec.difference(v, line.p1); + var dot = vec.dot + , basev = vec.difference(v, line.p1); return line.vec() .scale(2 * dot(basev,line) / dot(line,line)) .subtract(basev) diff --git a/src/ezl/math/line.cjs b/src/ezl/math/line.cjs index 1daa9c8..e19ae19 100644 --- a/src/ezl/math/line.cjs +++ b/src/ezl/math/line.cjs @@ -65,8 +65,8 @@ Vec.subclass('Line', { * @return {Float} Elapsed parametric time needed to move the given delta-(x,y). */ timeToMove : function timeToMove(dx,dy){ - // see note at iparametric - return (dx/this.pa + dy/this.pb) * 0.5; + if (dx instanceof Array) { dy=dx[1]; dx=dx[0]; } + return (Math.abs(dx/this.pa) + Math.abs(dy/this.pb)) * 0.5; // see note at iparametric }, parametric : function parametric(t){ diff --git a/src/ezl/math/rect.cjs b/src/ezl/math/rect.cjs index d1b8e85..7cf09e0 100644 --- a/src/ezl/math/rect.cjs +++ b/src/ezl/math/rect.cjs @@ -65,6 +65,21 @@ Y.subclass('Rect', [], { || ( (cy2 = line.calcY(x2)) >= y1 && cy2 <= y2 ) ); }, + get topSide(){ return new Line(this[X1],this[Y1], this[X2],this[Y1]); }, + get bottomSide(){ return new Line(this[X1],this[Y2], this[X2],this[Y2]); }, + get leftSide(){ return new Line(this[X1],this[Y1], this[X1],this[Y2]); }, + get rightSide(){ return new Line(this[X2],this[Y1], this[X2],this[Y2]); }, + + side : function side(which){ + switch (which) { + case 'top' : return this.topSide; + case 'bottom' : return this.bottomSide; + case 'left' : return this.leftSide; + case 'right' : return this.rightSide; + default : throw new Error('WTF kind of side is '+which+'???'); + } + }, + clone : function clone(){ return new this.__class__(this[X1],this[Y1], this[X2],this[Y2]); }, diff --git a/src/ezl/math/vec.cjs b/src/ezl/math/vec.cjs index 1bc3c08..44cdb2a 100644 --- a/src/ezl/math/vec.cjs +++ b/src/ezl/math/vec.cjs @@ -104,9 +104,10 @@ new Y.Class('Vec', [], { }); +// Can't import from math due to deps function lerp(x, a, b) { return a + x*(b - a); } -Y.extend(Vec, { +Y.extend(exports, { sum : function sum(a, b) { return new Vec(a[_X]+b[_X], a[_Y]+b[_Y]); }, diff --git a/src/ezl/util/binaryheap.cjs b/src/ezl/util/binaryheap.cjs index 9ddb155..b813036 100644 --- a/src/ezl/util/binaryheap.cjs +++ b/src/ezl/util/binaryheap.cjs @@ -1,9 +1,20 @@ -function BinaryHeap(score){ +/** + * A Binary Heap. + * @param {String|Function} score Scoring mechanism for contents: + * - {String} Property on values which contains the numeric score + * - {Function} Invoked with the value to get a numeric score + * @param {Array} [vals] Initial values. + */ +function BinaryHeap(score, vals){ if (typeof score === 'string') this.key = score; else this.score = score; + + if (vals) + for (var i=0, L=vals.length; i 0 ) { + if ( this.length ) { this[0] = end; this.heapUp(0); } return result; }, - remove: function(node) { + remove : function remove(node) { var key = this.key , i = this.indexOf(node) @@ -54,7 +65,7 @@ var AP = Array.prototype if ( i !== this.length-1 ) { this[i] = end; - var endScore = (key ? end[key] : this.score(end)) + var endScore = (key ? end[key] : this.score(end)) , nodeScore = (key ? node[key] : this.score(node)) ; if ( endScore < nodeScore ) this.heapDown(i); @@ -64,12 +75,12 @@ var AP = Array.prototype return this; }, - rescore: function(node) { + rescore : function rescore(node) { this.heapDown(this.indexOf(node)); return this; }, - heapDown: function(n) { + heapDown : function heapDown(n) { var key = this.key , el = this[n] , elScore = (key ? el[key] : this.score(el)) @@ -97,7 +108,7 @@ var AP = Array.prototype } }, - heapUp: function(n) { + heapUp : function heapUp(n) { var key = this.key , len = this.length , el = this[n] diff --git a/src/tanks/game.cjs b/src/tanks/game.cjs index 3c5ac9f..3678225 100644 --- a/src/tanks/game.cjs +++ b/src/tanks/game.cjs @@ -93,7 +93,7 @@ Y.subclass('Game', { SQUARETH = REF_SIZE * SECONDTH this.active.invoke('updateCooldowns', ELAPSED, NOW); - this.active.invoke('act'); + this.active.invoke('act', ELAPSED, NOW); this.animations = this.animations.filter(this.tickAnimations, this); this.draw(); diff --git a/src/tanks/map/index.cjs b/src/tanks/map/index.cjs index 7a345f6..a041760 100644 --- a/src/tanks/map/index.cjs +++ b/src/tanks/map/index.cjs @@ -1,8 +1,10 @@ var Y = require('Y').Y; Y.extend(exports, { - 'Level' : require('tanks/map/level').Level, - 'Wall' : require('tanks/map/wall').Wall, + 'Map' : require('tanks/map/map').Map, 'PathMap' : require('tanks/map/pathmap').PathMap, + 'Wall' : require('tanks/map/wall').Wall, + 'Level' : require('tanks/map/level').Level, + 'Traversal' : require('tanks/map/traversal').Traversal, 'Trajectory' : require('tanks/map/trajectory').Trajectory }); diff --git a/src/tanks/map/map.cjs b/src/tanks/map/map.cjs new file mode 100644 index 0000000..939494b --- /dev/null +++ b/src/tanks/map/map.cjs @@ -0,0 +1,99 @@ +// -*- mode: JavaScript; tab-width: 4; indent-tabs-mode: nil; -*- +var Y = require('Y').Y + +, math = require('ezl/math') +, vec = require('ezl/math/vec') +, QuadTree = require('ezl/util/tree/quadtree').QuadTree +, astar = require('ezl/util/astar') + +, config = require('tanks/config').config +, Bullet = require('tanks/thing/bullet').Bullet + +, Vec = vec.Vec +, Line = math.Line +, + + +Map = +exports['Map'] = +QuadTree.subclass('Map', { + + addBlocker : function addBlocker(obj){ + this.removeBlocker(obj); + var bb = obj.boundingBox; + if (obj.blocking && bb) + obj.region = this.set(bb.x1,bb.y1, bb.x2,bb.y2, obj); + return obj; + }, + + removeBlocker : function removeBlocker(obj){ + if (obj.region) { + this.remove(obj.region); + delete obj.region; + } + return obj; + }, + + // moveBlocked : function moveBlocked(agent, trj, to, bb){ + // bb = bb || agent.boundingBox; + // var blockers, blocker, msg + // , side = null + // , tobb = bb.relocated(to.x,to.y) + // , x1 = tobb.x1, y1 = tobb.y1 + // , x2 = tobb.x2, y2 = tobb.y2 + // + // , ro = bb.relOrigin + // , bw = bb.width, bh = bb.height + // , offX = bw - ro.x, offY = bh = ro.y + // + // // , x1 = to.x+offX, y1 = to.y+offY + // // , x2 = x1+bw, y2 = y1+bh + // ; + // + // blockers = this.get(x1,y1, x2,y2).remove(agent).end(); + // blocker = blockers[0]; + // + // // Not blocked + // if (!blocker) return false; + // + // // Literal corner case :P + // // XXX: needs better detection of corner + // if (blockers.length > 1) { + // msg = 'corner of '+blockers.slice(0); + // to = trj.p1; + // + // // Normal reflection against one line + // } else { + // msg = blocker+' on the '; + // + // var B = blocker.boundingBox; + // if (bb.x2 <= B.x1 && x2 >= B.x1) { + // msg += 'left'; + // side = B.leftSide; + // to = trj.pointAtX(B.x1-offX-1); + // + // } else if (bb.x1 >= B.x2 && x1 <= B.x2) { + // msg += 'right'; + // side = B.rightSide; + // to = trj.pointAtX(B.x2+ro.x+1); + // + // } else if (bb.y2 <= B.y1 && y2 >= B.y1) { + // msg += 'top'; + // side = B.topSide; + // to = trj.pointAtY(B.y1-offY-1); + // + // } else if (bb.y1 >= B.y2 && y1 <= B.y2) { + // msg += 'bottom'; + // side = B.bottomSide; + // to = trj.pointAtY(B.y2+ro.y+1); + // } + // + // msg += ' side'; + // } + // + // return { 'msg':msg, 'blockers':blockers, 'side':side, 'to':to }; + // }, + + + +}); diff --git a/src/tanks/map/pathmap.cjs b/src/tanks/map/pathmap.cjs index ac0fb83..14f2ad5 100644 --- a/src/tanks/map/pathmap.cjs +++ b/src/tanks/map/pathmap.cjs @@ -1,44 +1,165 @@ // -*- mode: JavaScript; tab-width: 4; indent-tabs-mode: nil; -*- -var Y = require('Y').Y -, math = require('ezl/math') -, QuadTree = require('ezl/util/tree/quadtree').QuadTree -, astar = require('ezl/util/astar') -, config = require('tanks/config').config -, Bullet = require('tanks/thing/bullet').Bullet -, Vec = math.Vec -, Line = math.Line +var Y = require('Y').Y +, math = require('ezl/math') +, vec = require('ezl/math/vec') +, QuadTree = require('ezl/util/tree/quadtree').QuadTree +, BinaryHeap = require('ezl/util/binaryheap').BinaryHeap + +, config = require('tanks/config').config +, Bullet = require('tanks/thing/bullet').Bullet +, Map = require('tanks/map/map').Map +, Vec = vec.Vec +, Line = math.Line + + +, SQRT_TWO = Math.sqrt(2) , PASSABLE = 1 // Does not obstruct other objects , BLOCKING = 2 // Objstructs other blockers , ZONE = 3 // Does not obstruct other objects, but still collides with them , +// Would be nice if I could make this an inner class (for once) +Square = +exports['Square'] = +Vec.subclass('Square', { + pathId : null, // instance of A* being run, to track when to reset + + // resetable: + dist : 0, // estimated distance + startDist : 0, // distance from start + endDist : 0, // estimated distance to end + visited : false, + closed : false, + prev : null, + + + /** + * @param x Left coord of square. + * @param y Top coord of square. + */ + init : function initSquare(pathmap, x,y){ + Vec.init.call(this, x,y); + this.pathmap = pathmap; + this.reset(); + }, + + reset : function reset(){ + var pathId = this.pathmap._pathId; + if (this.pathId === pathId) + return this; + + this.pathId = pathId; + this._blocked(); + + this.dist = 0; + this.startDist = 0; + this.endDist = 0; + this.visited = false; + this.closed = false; + this.prev = null; + + return this; + }, + + /** + * @private Caches this.blocked value. Should only be called by reset(). + */ + _blocked : function blocked(){ + var pm = this.pathmap + , agent = pm._agent + , bb = agent.boundingBox + + , origin = bb.relOrigin + , left = origin.x, right = bb.width - left + , top = origin.y, bottom = bb.height - top + + , SIZE = pm.gridSquare + , x = Math.floor(this.x) + , y = Math.floor(this.y) + , x1 = x - left, x2 = x + SIZE + right + , y1 = y - top, y2 = y + SIZE + bottom + + , blockers = pm.get(x1,y1, x2,y2) + .remove(agent) + .filter(this._filterBlocked) + ; + + this.blocked = !!blockers.length; + }, + + /** + * @private + */ + _filterBlocked : function filterBlocked(v, r){ + return !(v.isBoundary || v instanceof Bullet); // XXX: use PASSABLE + }, + + getNeighbors : function getNeighbors(){ + var neighbors = [] + , abs = Math.abs + , pm = this.pathmap + , agent = pm._agent + , SIZE = pm.gridSquare + + , x = this.x, y = this.y + , sq, cost, ix, iy + ; + + for (ix=-1; ix<2; ix++) { + for (iy=-1; iy<2; iy++) { + // if (ix === 0 && iy === 0) // skipping diagonals + if ( (ix === 0 && iy === 0) || (abs(ix) === 1 && abs(iy) === 1) ) + continue; + // TODO: handle diagonals: need to ensure we don't try to move through a corner + // cost = ( abs(ix) === 1 && abs(iy) === 1 ) ? SQRT_TWO : 1; + cost = 1; + sq = pm._getSquare(x + ix*SIZE, y + iy*SIZE); + if ( !sq.blocked ) neighbors.push([ sq, cost*SIZE ]); + } + } + + return neighbors; + } + +}) + + + /** * A QuadTree which aids in pathing for AI. - * - QuadTree methods which took rect coords (x1,y1, x2,y2) will accept - * anything Rect-like (having properties x1,y1, x2,y2). - * - Pathing methods will account for the unit's size when calculating paths, - * intersections, blocking, and similar tasks. + * - QuadTree methods which took rect coords (x1,y1, x2,y2) will accept + * anything Rect-like (having properties x1,y1, x2,y2). + * - Pathing methods will account for the unit's size when calculating paths, + * intersections, blocking, and similar tasks. */ PathMap = exports['PathMap'] = -QuadTree.subclass('PathMap', { +Map.subclass('PathMap', { // Config gridSquare : null, gridSquareMid : null, + // State + _squares : null, // Cache of Square objects + _pathId : -1, // Instance of A* being run, to track when to reset Square instances + + init : function init(level, x1,y1, x2,y2, capacity) { x1 -= 1; y1 -= 1; x2 += 1; y2 += 1; QuadTree.init.call(this, x1,y1, x2,y2, capacity); + this.level = level; this.game = level.game; this.walls = level.walls; this.allWalls = level.allWalls; + this._squares = {}; + this.game.addEventListener('ready', this.setup.bind(this, x1,y1, x2,y2)); }, @@ -66,167 +187,107 @@ QuadTree.subclass('PathMap', { }, this); }, - addBlocker : function addBlocker(obj){ - this.removeBlocker(obj); - var bb = obj.boundingBox; - if (obj.blocking && bb) - obj.region = this.set(bb.x1,bb.y1, bb.x2,bb.y2, obj); - return obj; - }, - removeBlocker : function removeBlocker(obj){ - if (obj.region) { - this.remove(obj.region); - delete obj.region; - } - return obj; + /** + * Takes normal (not gridSquare-relative) coordinates. + */ + _getSquare : function getSquare(x,y){ + if (x instanceof Array) { y=x[1]; x=x[0]; } + x = Math.floor(x); y = Math.floor(y); + + var cache = this._squares + , key = x+"_"+y + , sq = cache[key] ; + + if (sq) + sq.reset(); + else + sq = cache[key] = new Square(this, x,y); + + return sq; }, - - - // moveBlocked : function moveBlocked(agent, trj, to, bb){ - // bb = bb || agent.boundingBox; - // var blockers, blocker, msg - // , side = null - // , tobb = bb.relocated(to.x,to.y) - // , x1 = tobb.x1, y1 = tobb.y1 - // , x2 = tobb.x2, y2 = tobb.y2 - // - // , ro = bb.relOrigin - // , bw = bb.width, bh = bb.height - // , offX = bw - ro.x, offY = bh = ro.y - // - // // , x1 = to.x+offX, y1 = to.y+offY - // // , x2 = x1+bw, y2 = y1+bh - // ; - // - // blockers = this.get(x1,y1, x2,y2).remove(agent).end(); - // blocker = blockers[0]; - // - // // Not blocked - // if (!blocker) return false; - // - // // Literal corner case :P - // // XXX: needs better detection of corner - // if (blockers.length > 1) { - // msg = 'corner of '+blockers.slice(0); - // to = trj.p1; - // - // // Normal reflection against one line - // } else { - // msg = blocker+' on the '; - // - // var B = blocker.boundingBox; - // if (bb.x2 <= B.x1 && x2 >= B.x1) { - // msg += 'left'; - // side = B.leftSide; - // to = trj.pointAtX(B.x1-offX-1); - // - // } else if (bb.x1 >= B.x2 && x1 <= B.x2) { - // msg += 'right'; - // side = B.rightSide; - // to = trj.pointAtX(B.x2+ro.x+1); - // - // } else if (bb.y2 <= B.y1 && y2 >= B.y1) { - // msg += 'top'; - // side = B.topSide; - // to = trj.pointAtY(B.y1-offY-1); - // - // } else if (bb.y1 >= B.y2 && y1 <= B.y2) { - // msg += 'bottom'; - // side = B.bottomSide; - // to = trj.pointAtY(B.y2+ro.y+1); - // } - // - // msg += ' side'; - // } - // - // return { 'msg':msg, 'blockers':blockers, 'side':side, 'to':to }; - // }, - - // TODO: Fold A* into this class. - // TODO: Deal with bbox /** - * @protected Creates a pathing grid suitable for A* search. - * @param {Thing|BoundingBox} bbox Denotes the bounds of object under pathing: - * - An object with a `boundingBox` property - * - A BoundingBox-like object (has properties relOrigin, width, height) + * Finds the shortest path to a destination for the given agent. + * @param {Thing} agent Agent whose path is being generated. + * @param {Vec} end End destination. + */ + /** + * Finds the shortest path to a destination for the given agent. + * @param {Thing} agent Agent whose path is being generated. + * @param {Integer} x End destination x-coordinate. + * @param {Integer} y End destination y-coordinate. */ - grid : function grid(bbox){ - if ( !this._grid ) { - var size = this.gridSquare - , floor = Math.floor, ceil = Math.ceil - , cols = ceil((this.width-2) /size) - , rows = ceil((this.height-2)/size) - , grid = new Array(cols); - ; + // * @param {Function} [passable] Function which tests whether a node is passable. + path : function path(agent, x,y){ + ++this._pathId; // Current pathId for Square calculation + this._agent = agent; // Current agent for Square calculation + + var heuristic = vec.manhattan + , start = this._getSquare(agent.loc) + , end = this._getSquare(x,y) + , open = new BinaryHeap('dist') // 'dist' is the scoring key on heap objects + ; + + open.push(start); + while (open.length) { - for (var x=0; x In fact! Weight is determined by Square.getNeighbors() + var startDist = current.startDist + weight; - for (var x=colMin; x 0); - return to; + return this.to; }, - stepTo : function stepTo(t, bb){ - var ng, traj = this.trajectory, og = traj.p2, thing = this.thing - , to = traj.parametric(this.elapsed), _to = to - , test = this.pathmap.moveBlocked(thing, this, to, bb) + /** + * Checks for blockers and moves traversal bounds forward as much as possible. + * @param {Number} t Time units to move this traversal forward. + * @return {Number} Time units consumed by this step. + */ + stepTo : function stepTo(t, tx,ty){ + var blockers, blocker, B + , traj = this.trajectory, thing = this.thing + + , bb = this.bbox + , x1 = bb.x1, y1 = bb.y1 + , x2 = bb.x2, y2 = bb.y2 + , o = bb.absOrigin + + , to = this.to = traj.parametric(this.elapsed+t) ; - // Blocked! Reflect trajectory - if ( test ) { - to = test.to; - this.bounces++; - - var blocker = test.blockers[0]; - thing.fire('collide', blocker); - blocker.fire('collide', thing); - - // Potentially set by responders to collision event - if (this.halt) return to; - - if (!test.side) { - console.error('Null reflection line!', 'to:', to, 'blockers:', test.blockers); - return to; - } + // Don't overshoot the target + if ( tx !== undefined && abs(o.x-to.x) > abs(o.x-tx) ) + to.x = tx; + + if ( ty !== undefined && abs(o.y-to.y) > abs(o.y-ty) ) + to.y = ty; + + // nb: BoundingBox.relocate() is in-place, so this.bbox are updated + bb = bb.relocate(to); + blockers = this.blockers = this.pathmap.get(bb).remove(thing).end(); + + if (!blockers.length) + return t; // All time consumed, yay + + this.isBlocked = true; + + // TODO: Either: this never happens (current belief) OR it needs better corner-detection + // Literal corner case :P + if (blockers.length > 1) { + console.error('Corner! WHO KNEW.', 'to:', to, 'blockers:', blockers); + this.isCorner = true; + // to = trj.p1; // Turn around, go back whence you came + } + + // blocker = traj.closest(blockers) + blocker = this.blocker = blockers[0]; + B = blocker.boundingBox; + + // Figure out which boundary of the blocker we crossed and calculate + // the furthest non-overlapping point. + if (bb.x2 <= B.x1 && x2 >= B.x1) { + this.to = to = trj.pointAtX(B.x1 - 1 - bb.originRight); + this.side = B.leftSide; - if ( test.blockers.length > 1 ) { - to = bb.p1; - ng = this.p1; // XXX: recalculate? - console.log('corner!', this, 'to:',to, 'ng:',ng); - } else { - ng = math.reflect(this.p2, test.side); - } + } else if (bb.x1 >= B.x2 && x1 <= B.x2) { + this.to = to = trj.pointAtX(B.x2 + 1 + bb.originLeft); + this.side = B.rightSide; - this.reset(to.x,to.y, ng.x,ng.y); - thing.render(this.game.level); + } else if (bb.y2 <= B.y1 && y2 >= B.y1) { + this.to = to = trj.pointAtY(B.y1 - 1 - bb.originTop); + this.side = B.topSide; - // console.log([ - // '['+TICKS+' ('+this.depth+')] '+thing+' reflected!', - // ' wanted: '+_to+' x ('+(_to.x+bb.width)+','+(_to.y+bb.height)+')', - // ' blocker: '+test.msg, - // ' old:', - // ' loc: '+bb.p1, - // ' goal: '+og, - // ' new:', - // ' loc: '+to, - // ' goal: '+ng, - // ' --> trajectory: '+this - // ].join('\n')); + } else if (bb.y1 >= B.y2 && y1 <= B.y2) { + this.to = to = trj.pointAtY(B.y2 + 1 + bb.originBottom ); + this.side = B.bottomSide; + } else { + console.error('Null reflection line!', 'to:', to, 'blockers:', blockers); } - return to; - }, - + // Move bounding box to furthest non-overlapping point + bb.relocate(to); + + // Return how much time consumed + return trj.timeToMove(to.x-o.x, to.y-o.y); + } }) diff --git a/src/tanks/thing/bullet.cjs b/src/tanks/thing/bullet.cjs index 8377ef6..08de2ac 100644 --- a/src/tanks/thing/bullet.cjs +++ b/src/tanks/thing/bullet.cjs @@ -7,6 +7,7 @@ var Y = require('Y').Y , thing = require('tanks/thing/thing') , Wall = require('tanks/map/wall').Wall , Trajectory = require('tanks/map/trajectory').Trajectory +, Traversal = require('tanks/map/traversal').Traversal , Explosion = require('tanks/fx/explosion').Explosion , fillStats = thing.fillStats @@ -29,6 +30,18 @@ Thing.subclass('Bullet', { end : 1.5 // ratio of explosion end radius to obj size }, + // Instance + blocking : true, + bounces : 0, + bounceLimit : 1, + + width : 6, + height : 6, + + stats : { + move : 2.0 // move speed (squares/sec) + }, + /** @@ -45,23 +58,11 @@ Thing.subclass('Bullet', { , x1 = loc.x, y1 = loc.y; this.position(x1,y1); - this.trajectory = new Trajectory(this, x1,y1, x2,y2, this.stats.move*REF_SIZE/1000); + this.trajectory = new Trajectory(this, x1,y1, x2,y2, this.movePerMs); this.addEventListener('collide', this.onCollide.bind(this)); }, - - blocking : true, - bounces : 0, - bounceLimit : 1, - - width : 6, - height : 6, - - stats : { - move : 2.0 // move speed (squares/sec) - }, - createStats : function createStats(){ this.stats = Y({}, fillStats(this.owner.stats), fillStats(this.stats) ); }, @@ -82,33 +83,59 @@ Thing.subclass('Bullet', { return this; }, - act : function act(){ - if (!this.dead) this.move(); + act : function act(elapsed, now){ + if (!this.dead) this.move(elapsed, now); return this; }, - move : function move(){ - // We test twice because the process of calculating the trajectory - // could result in a collision, killing the bullet - if (!this.dead) var to = this.trajectory.step( ELAPSED ); - if (!this.dead) this.game.moveThingTo(this, to.x, to.y); + move : function move(elapsed, now){ + if (this.dead) return this; + + var tvsl = new Traversal(this, this.trajectory) + , to = tvsl.step(elapsed) + ; + + if (tvsl.isBlocked && !this.dead) { + tvsl = new Traversal(this, this.trajectory); + to = tvsl.step(tvsl.remaining); + } + + if (!this.dead) + this.game.moveThingTo(this, to.x, to.y); + return this; }, onCollide : function onCollide(evt){ - var unit = evt.trigger + if ( this.dead ) return; + + var ng + , tvsl = evt.target + , traj = this.trajectory + , to = tvsl.to + + , unit = evt.trigger , hitAWall = unit instanceof Wall - , trj = this.trajectory; + ; - if ( this.dead || hitAWall && trj.bounces <= this.bounceLimit ) + // Reflection! + if ( hitAWall && this.bounceLimit >= ++this.bounces ) { + if ( tvsl.isCorner ) { + ng = to; + } else { + if (!tvsl.side) return console.error('Null reflection line!', 'to:', to, 'blockers:', tvsl.blockers); + ng = math.reflect(traj.p2, tvsl.side); + } + traj.reset(to.x,to.y, ng.x,ng.y); + this.render(this.game.level); // to render the new reflection line return; + } unit.dealDamage(this.stats.power, this); this.destroy(); - trj.halt = true; // Trigger explosion - var x, y, loc = this.loc, uloc = unit.loc + var x, y, loc = to, uloc = unit.loc , bsize = Math.max(this.width, this.height) , asize = Math.max(unit.width, unit.height) diff --git a/src/tanks/thing/item.cjs b/src/tanks/thing/item.cjs index ea4b167..7e218ff 100644 --- a/src/tanks/thing/item.cjs +++ b/src/tanks/thing/item.cjs @@ -47,7 +47,7 @@ Thing.subclass('Item', { .origin('50%', '50%') .position(loc.x, loc.y) .fill('#83BB32') - .stroke('#1C625B', 2.0) + .stroke('#1C625B', 3.0) .appendTo( parent ); this.shape.layer.attr('title', ''+loc); diff --git a/src/tanks/thing/player.cjs b/src/tanks/thing/player.cjs index b50713d..8455342 100644 --- a/src/tanks/thing/player.cjs +++ b/src/tanks/thing/player.cjs @@ -55,7 +55,7 @@ Tank.subclass('PlayerTank', { - act : function act(){ + act : function act(elapsed, now){ if (this.dead) return this; diff --git a/src/tanks/thing/tank.cjs b/src/tanks/thing/tank.cjs index 1b33591..40238a5 100644 --- a/src/tanks/thing/tank.cjs +++ b/src/tanks/thing/tank.cjs @@ -1,12 +1,18 @@ var Y = require('Y').Y , op = require('Y/op') + +, vec = require('ezl/math/vec') +, shape = require('ezl/shape') +, Cooldown = require('ezl/loop').Cooldown +, CooldownGauge = require('ezl/widget').CooldownGauge + , Thing = require('tanks/thing/thing').Thing , Bullet = require('tanks/thing/bullet').Bullet , Trajectory = require('tanks/map/trajectory').Trajectory -, Vec = require('ezl/math/vec').Vec -, Cooldown = require('ezl/loop').Cooldown -, CooldownGauge = require('ezl/widget').CooldownGauge -, shape = require('ezl/shape') +, Traversal = require('tanks/map/traversal').Traversal + +, Vec = vec.Vec +, manhattan = vec.manhattan , Rect = shape.Rect , Circle = shape.Circle @@ -63,7 +69,7 @@ Thing.subclass('Tank', function(Tank){ this['init'] = function initTank(align){ Thing.init.call(this, align); - this.coolgauge = new CooldownGauge(this.cooldowns.attack, this.width+1,this.height+1); + this.atkGauge = new CooldownGauge(this.cooldowns.attack, this.width+1,this.height+1); this.onBulletDeath = this.onBulletDeath.bind(this); }; @@ -73,7 +79,7 @@ Thing.subclass('Tank', function(Tank){ this['act'] = - function act(allotment){ + function act(elapsed, now){ var ai = this.ai; // Check to see if we should obey our last decision, and not recalc @@ -190,8 +196,7 @@ Thing.subclass('Tank', function(Tank){ if ( !(agents && agents.size()) ) return null; - var manhattan = Vec.manhattan - , cmp = op.cmp + var cmp = op.cmp , loc = this.loc ; agents.sort(function(a,b){ @@ -284,9 +289,19 @@ Thing.subclass('Tank', function(Tank){ this['move'] = function move(x,y){ if (x instanceof Array) { y=x[_Y]; x=x[_X]; } - var loc = this.loc; - this.trajectory = new Trajectory(this, loc.x,loc.y, x,y, this.stats.move*REF_SIZE/1000); - return this.moveByAngle(this.angleTo(x,y), x,y); + var loc = this.loc + , cur = this.currentMove + ; + + if (cur.x !== x || cur.y !== y) + this.trajectory = new Trajectory(this, loc.x,loc.y, x,y, this.movePerMs); + + var tvsl = new Traversal(this, this.trajectory) + , to = tvsl.step(elapsed, x,y) + ; + + this.game.moveThingTo(this, to.x,to.y); + return this; }; /** @@ -322,8 +337,8 @@ Thing.subclass('Tank', function(Tank){ this['continueMove'] = function continueMove(){ if ( !this.currentMove || this.currentMoveLimit <= NOW ){ - var t = this.findNearEnemies(10000).shift(); - if (t) this.calculatePath(t.midpoint); + var target = this.findNearEnemies(10000).shift(); + if (target) this.calculatePath(target.loc); } var to = this.currentMove; @@ -350,7 +365,7 @@ Thing.subclass('Tank', function(Tank){ var pm = this.game.pathmap , start = this.loc - , path = this.lastPath = pm.path(start, end, this) + , path = this.lastPath = pm.path(this, end) , to = this.currentMove = path.shift() ; }; @@ -407,7 +422,7 @@ Thing.subclass('Tank', function(Tank){ .appendTo( parent ) ; if (this.showAttackCooldown) - this.shape.append(this.coolgauge); + this.shape.append(this.atkGauge); this.turret = new Circle(r) diff --git a/src/tanks/thing/thing.cjs b/src/tanks/thing/thing.cjs index 4eba9dd..4c9b01a 100644 --- a/src/tanks/thing/thing.cjs +++ b/src/tanks/thing/thing.cjs @@ -77,6 +77,8 @@ new evt.Class('Thing', { set : op.set.methodize(), attr : op.attr.methodize(), + get movePerMs(){ return this.stats.move*REF_SIZE/1000; }, + init : function init(align){ @@ -119,10 +121,11 @@ new evt.Class('Thing', { if (x === undefined && y === undefined) return this.loc; - var bb = this.boundingBox.relocate(x,y) - , loc = this.loc = bb.absOrigin; - this.midpoint = bb.midpoint; - if (this.shape) this.shape.position(loc.x,loc.y); // XXX: eh? + var bb = this.boundingBox.relocate(x,y) // in-place + , loc = this.loc = bb.absOrigin + , mid = this.midpoint = bb.midpoint + ; + if (this.shape) this.shape.position(loc.x,loc.y); return this; }, @@ -170,7 +173,7 @@ new evt.Class('Thing', { /** * Determines what the creep should do -- move, attack, etc. */ - act : function act(){ + act : function act(elapsed, now){ return this; }, diff --git a/src/tanks/ui/configui.cjs b/src/tanks/ui/configui.cjs index fcf7d57..838cfc4 100644 --- a/src/tanks/ui/configui.cjs +++ b/src/tanks/ui/configui.cjs @@ -28,6 +28,7 @@ config.addEventListener('set', function(evt){ cookies.remove(d.key); }); +// As EventLoop is in ezl, it should not know about config config.updateOnChange('game.timeDilation', EventLoop.fn); diff --git a/src/tanks/ui/pathmapui.cjs b/src/tanks/ui/pathmapui.cjs index 73323ca..a4c658c 100644 --- a/src/tanks/ui/pathmapui.cjs +++ b/src/tanks/ui/pathmapui.cjs @@ -29,7 +29,7 @@ Rect.subclass('PathMapUI', { Rect.init.call(this, pathmap.width-2, pathmap.height-2); - pathmap.gridPath = this.gridPathWithUI.bind(this); + pathmap._gridPath = this.gridPathWithUI.bind(this); this.cleanUpAgent = this.cleanUpAgent.bind(this); this._drawPathStep = this._drawPathStep.bind(this); }, diff --git a/www/deps.html b/www/deps.html index f00d42a..e7393c6 100644 --- a/www/deps.html +++ b/www/deps.html @@ -48,6 +48,7 @@ + @@ -62,10 +63,11 @@ + - + -- 1.7.0.4