diff options
Diffstat (limited to 'public/assets/javascripts/rectangles/models')
| -rw-r--r-- | public/assets/javascripts/rectangles/models/rect.js | 118 | ||||
| -rw-r--r-- | public/assets/javascripts/rectangles/models/room.js | 49 | ||||
| -rw-r--r-- | public/assets/javascripts/rectangles/models/tree.js | 85 | ||||
| -rw-r--r-- | public/assets/javascripts/rectangles/models/vec2.js | 89 |
4 files changed, 230 insertions, 111 deletions
diff --git a/public/assets/javascripts/rectangles/models/rect.js b/public/assets/javascripts/rectangles/models/rect.js index 315adef..590440a 100644 --- a/public/assets/javascripts/rectangles/models/rect.js +++ b/public/assets/javascripts/rectangles/models/rect.js @@ -1,5 +1,25 @@ (function(){ + var vec2 + if ('window' in this) { + vec2 = window.vec2 + } + else { + vec2 = require('./vec2') + FRONT = 0x1, BACK = 0x2, LEFT = 0x4, RIGHT = 0x8, FLOOR = 0x10, CEILING = 0x20 + TOP = CEILING, BOTTOM = FLOOR + function sidesToString(sides){ + var s = "" + if (sides & FRONT) s += "front " + if (sides & BACK) s += "back " + if (sides & LEFT) s += "left " + if (sides & RIGHT) s += "right " + if (sides & TOP) s += "top " + if (sides & BOTTOM) s += "bottom " + return s + } + } + var Rect = function (x0,y0,x1,y1){ if (x0 instanceof vec2) { this.x = x0 @@ -74,8 +94,18 @@ Rect.prototype.containsDisc = function(x,y,r){ return this.x.containsDisc(x,r) && this.y.containsDisc(y,r) } + Rect.prototype.overlaps = function(rect){ + return this.x.overlaps(rect.x) && this.y.overlaps(rect.y) + } Rect.prototype.intersects = function(r){ - return this.x.intersects(r.x) && this.y.intersects(r.y) + var corner_intersect = (this.x.b === r.x.a && this.y.b === r.y.a) + return this.x.intersects(r.x) && this.y.intersects(r.y) && ! corner_intersect + } + Rect.prototype.adjacent = function(r){ + return this.x.adjacent(r.x) && this.y.adjacent(r.y) + } + Rect.prototype.eq = function(r){ + return this.x.eq(r.x) && this.y.eq(r.y) } Rect.prototype.nearEdge = function (x, y, r) { var edges = 0 @@ -111,79 +141,51 @@ Rect.prototype.split = function(r){ var rz = this var splits = [] - var split_contains = 0 - var x_intervals = [], y_intervals = [] var sides = this.sides - // Split vertically - if (this.x.contains(r.x.a) && r.x.contains(this.x.b)) { - x_intervals.push([ new vec2( this.x.a, r.x.a ), LEFT ]) - x_intervals.push([ new vec2( r.x.a, this.x.b ), RIGHT ]) - split_contains |= RIGHT - } - - else if (r.x.contains(this.x.a) && this.x.contains(r.x.b)) { - x_intervals.push([ new vec2( this.x.a, r.x.b ), LEFT ]) - x_intervals.push([ new vec2( r.x.b, this.x.b ), RIGHT ]) - split_contains |= LEFT - } - - else if (this.x.contains(r.x.a) && this.x.contains(r.x.b)) { - x_intervals.push([ new vec2( this.x.a, r.x.a ), LEFT ]) - x_intervals.push([ new vec2( r.x.a, r.x.b ), 0 ]) - x_intervals.push([ new vec2( r.x.b, this.x.b ), RIGHT ]) - split_contains |= LEFT | RIGHT - } - - else { // if (r.x.contains(this.x.a) && r.x.contains(r.x.b)) { - x_intervals.push([ new vec2( this.x.a, this.x.b ), LEFT | RIGHT ]) - split_contains |= LEFT | RIGHT - } - - // Split horizontally - if (this.y.contains(r.y.a) && r.y.contains(this.y.b)) { - y_intervals.push([ new vec2( this.y.a, r.y.a ), FRONT ]) - y_intervals.push([ new vec2( r.y.a, this.y.b ), BACK ]) - split_contains |= BACK - } - - else if (r.y.contains(this.y.a) && this.y.contains(r.y.b)) { - y_intervals.push([ new vec2( this.y.a, r.y.b ), FRONT ]) - y_intervals.push([ new vec2( r.y.b, this.y.b ), BACK ]) - split_contains |= FRONT - } - - else if (this.y.contains(r.y.a) && this.y.contains(r.y.b)) { - y_intervals.push([ new vec2( this.y.a, r.y.a ), FRONT ]) - y_intervals.push([ new vec2( r.y.a, r.y.b ), 0 ]) - y_intervals.push([ new vec2( r.y.b, this.y.b ), BACK ]) - split_contains |= FRONT | BACK - } - - else { // if (r.y.contains(this.y.a) && this.y.contains(r.y.b)) { - y_intervals.push([ new vec2( this.y.a, this.y.b ), FRONT | BACK ]) - split_contains |= FRONT | BACK - } + // bisect (or trisect) two overlapping rectangles + var x_intervals = this.x.split( r.x, LEFT, RIGHT ) + var y_intervals = this.y.split( r.y, FRONT, BACK ) - x_intervals.forEach(function(x){ - y_intervals.forEach(function(y){ + // generate rectangular regions by crossing the two sets of vectors + x_intervals.forEach(function(x, i){ + y_intervals.forEach(function(y, i){ var rn = new Rect(x[0], y[0]) rn.id = rz.id rn.sides = ((x[1] | y[1]) & sides) - if (r.intersects(rn)) { - rn.sides = 0 - } rn.focused = rz.focused splits.push(rn) + + // cull extra walls from overlapping regions + if (r.x.contains(rn.x.a) && r.x.contains(rn.x.b)) { + if (rz.y.a == rn.y.a && r.y.containsCenter(rn.y.a)) { // top edges + rn.sides &= ~ FRONT + } + if (rz.y.b == rn.y.b && r.y.containsCenter(rn.y.b)) { // bottom edges + rn.sides &= ~ BACK + } + } + + if (r.y.contains(rn.y.a) && r.y.contains(rn.y.b)) { + if (rz.x.a == rn.x.a && r.x.containsCenter(rn.x.a)) { // left edges + rn.sides &= ~ LEFT + } + + if (rz.x.b == rn.x.b && r.x.containsCenter(rn.x.b) ) { // right edges + rn.sides &= ~ RIGHT + } + } + }) }) + return splits } if ('window' in this) { window.Rect = Rect } - else if ('module' in this) { + else { module.exports = Rect } diff --git a/public/assets/javascripts/rectangles/models/room.js b/public/assets/javascripts/rectangles/models/room.js index 61a7447..d19ca2f 100644 --- a/public/assets/javascripts/rectangles/models/room.js +++ b/public/assets/javascripts/rectangles/models/room.js @@ -1,4 +1,32 @@ -window.Room = (function(){ + +(function(){ + var vec2, Rect, sort + if ('window' in this) { + vec2 = window.vec2 + Rect = window.Rect + sort = window.sort + } + else { + vec2 = require('./vec2') + Rect = require('./rect') + UidGenerator = require('../util/uid') + Rooms = { uid: new UidGenerator({}) } + sort = require('../util/sort') + FRONT = 0x1, BACK = 0x2, LEFT = 0x4, RIGHT = 0x8, FLOOR = 0x10, CEILING = 0x20 + TOP = CEILING, BOTTOM = FLOOR + FRONT_BACK = FRONT | BACK + LEFT_RIGHT = LEFT | RIGHT + function sidesToString(sides){ + var s = "" + if (sides & FRONT) s += "front " + if (sides & BACK) s += "back " + if (sides & LEFT) s += "left " + if (sides & RIGHT) s += "right " + if (sides & TOP) s += "top " + if (sides & BOTTOM) s += "bottom " + return s + } + } var Room = function(opt){ this.id = opt.id || Rooms.uid("room_") @@ -81,10 +109,10 @@ window.Room = (function(){ var side = pair[0], els = pair[1] if (side & LEFT_RIGHT) { - els.sort(compare_x) + els.sort(sort.compare_x) } else if (side & FRONT_BACK) { - els.sort(compare_z) + els.sort(sort.compare_z) } // wall holds state for the last wall we created/saw.. @@ -212,17 +240,22 @@ window.Room = (function(){ if (contains_x) { collision |= wall_collision & FRONT_BACK } - else if (contains_y) { + if (contains_y) { collision |= wall_collision & LEFT_RIGHT } - else if (bitcount(wall_collision) > 1) { - collision |= wall_collision - } +// if (bitcount(wall_collision) > 1) { +// collision |= wall_collision +// } }) return collision } - return Room + if ('window' in this) { + window.Room = Room + } + else { + module.exports = Room + } })() diff --git a/public/assets/javascripts/rectangles/models/tree.js b/public/assets/javascripts/rectangles/models/tree.js index 8193988..7c698fe 100644 --- a/public/assets/javascripts/rectangles/models/tree.js +++ b/public/assets/javascripts/rectangles/models/tree.js @@ -1,37 +1,48 @@ -var Tree = function(n, data){ - this.lo = null - this.hi = null - this.value = n - this.data = data -} -Tree.prototype.find = function(n){ - if (n == this.value) return this - if (n < this.value) return this.lo ? this.lo.find(n) : this - if (n > this.value) return this.hi ? this.hi.find(n) : this -} -Tree.prototype.add = function(n, data){ - var closest = this.find(n) - if (n == closest.value) return closest - if (n < closest.value) return closest.lo = new Tree(n, data) - if (n > closest.value) return closest.hi = new Tree(n, data) -} -Tree.prototype.toArray = function(){ - var a = [] - if (this.lo) a = a.concat(this.lo.toArray()) - a.push(this.data) - if (this.hi) a = a.concat(this.hi.toArray()) - return a -} -Tree.prototype.toString = function(){ - var s = ""; - if (this.lo) s += this.lo.toString() - s += this.value + "," - if (this.hi) s += this.hi.toString() - return s -} -Tree.prototype.depth = function(){ - if (this.lo && this.hi) return 1 + max(this.lo.depth(), this.hi.depth()) - else if (this.lo) return 1 + this.lo.depth() - else if (this.hi) return 1 + this.hi.depth() - else return 0 -} +(function(){ + + var Tree = function(n, data){ + this.lo = null + this.hi = null + this.value = n + this.data = data + } + Tree.prototype.find = function(n){ + if (n == this.value) return this + if (n < this.value) return this.lo ? this.lo.find(n) : this + if (n > this.value) return this.hi ? this.hi.find(n) : this + } + Tree.prototype.add = function(n, data){ + var closest = this.find(n) + if (n == closest.value) return closest + if (n < closest.value) return closest.lo = new Tree(n, data) + if (n > closest.value) return closest.hi = new Tree(n, data) + } + Tree.prototype.toArray = function(){ + var a = [] + if (this.lo) a = a.concat(this.lo.toArray()) + a.push(this.data) + if (this.hi) a = a.concat(this.hi.toArray()) + return a + } + Tree.prototype.toString = function(){ + var s = ""; + if (this.lo) s += this.lo.toString() + s += this.value + "," + if (this.hi) s += this.hi.toString() + return s + } + Tree.prototype.depth = function(){ + if (this.lo && this.hi) return 1 + max(this.lo.depth(), this.hi.depth()) + else if (this.lo) return 1 + this.lo.depth() + else if (this.hi) return 1 + this.hi.depth() + else return 0 + } + + if ('window' in this) { + window.Tree = Tree + } + else { + module.exports = Tree + } + +})() diff --git a/public/assets/javascripts/rectangles/models/vec2.js b/public/assets/javascripts/rectangles/models/vec2.js index 9233aec..2bf286b 100644 --- a/public/assets/javascripts/rectangles/models/vec2.js +++ b/public/assets/javascripts/rectangles/models/vec2.js @@ -1,4 +1,6 @@ (function(){ + function clamp(n,a,b){ return n<a?a:n<b?n:b } + var vec2 = function (a,b){ this.a = a this.b = b @@ -7,7 +9,7 @@ return this.b-this.a } vec2.prototype.length = function(){ - return abs(this.b-this.a) + return Math.abs(this.b-this.a) } vec2.prototype.dist = function(){ return dist(0,this.a,0,this.b) @@ -70,6 +72,9 @@ vec2.prototype.contains = function(n){ return this.a <= n && n <= this.b } + vec2.prototype.containsCenter = function(n){ + return this.a < n && n < this.b + } vec2.prototype.containsDisc = function(n,r){ return this.a <= n-r && n+r <= this.b } @@ -80,16 +85,35 @@ return clamp(n, this.a+r, this.b-r) } vec2.prototype.intersects = function(v){ - if (this.a < v.a) { - return (v.a < this.b && this.b <= v.b) || (this.a < v.b && v.b <= this.b) - } - else if (this.a == v.a) { + if (this.a == v.a || this.b == v.b || this.a == v.b || this.b == v.a) { return true } + else if (this.a < v.a) { + return (v.a < this.b && this.b <= v.b) || (this.a < v.b && v.b <= this.b) + } else if (this.a > v.a) { return (this.a < v.b && v.b <= this.b) || (v.a < this.b && this.b <= v.b) } } + vec2.prototype.overlaps = function(v){ + if (this.a == v.a || this.b == v.b) { + return true + } + if (this.a < v.a) { + return (v.a < this.b && this.b < v.b) || (this.a < v.b && v.b < this.b) + } + else if (v.a < this.a) { + return (this.a < v.b && v.b < this.b) || (v.a < this.b && this.b < v.b) + } + } + + + vec2.prototype.adjacent = function(v){ + if (this.a == v.a || this.b == v.b || this.a == v.b || this.b == v.a) { + return true + } + return false + } vec2.prototype.union = function(v){ if (this.intersects(v)) { return new vec2( min(this.a,v.a), max(this.b, v.b) ) @@ -100,6 +124,56 @@ return new vec2( max(this.a,v.a), min(this.b, v.b) ) } } + + // given two vectors, test how they overlap + // return the set of overlapping segments in the initial vector, labelled with sides + vec2.prototype.split = function(v, left, right){ + var intervals = [], _len + + if (this.eq(v)) { + intervals.push([ new vec2( this.a, this.b ), left | right ]) + } + + // a---A===b---B (rightways overlap) + else if (this.contains(v.a) && v.contains(this.b)) { + intervals.push([ new vec2( this.a, v.a ), left ]) + intervals.push([ new vec2( v.a, this.b ), right ]) + } + + // A---a===B---b (leftways overlap) + else if (v.contains(this.a) && this.contains(v.b)) { + intervals.push([ new vec2( this.a, v.b ), left ]) + intervals.push([ new vec2( v.b, this.b ), right ]) + } + + // a---A===B---b (contains v) + else if (this.contains(v.a) && this.contains(v.b)) { + intervals.push([ new vec2( this.a, v.a ), left ]) + intervals.push([ new vec2( v.a, v.b ), 0 ]) + intervals.push([ new vec2( v.b, this.b ), right ]) + } + + // A---a===b---B (contained in v) + else { // if (v.contains(this.a) && v.contains(v.b)) { + intervals.push([ new vec2( this.a, this.b ), left | right ]) + } + + // cull empty vectors + _len = intervals.length + if (_len > 1) { + if (intervals[0][0].magnitude() == 0) { + intervals[1][1] |= intervals[0][1] + intervals.shift() + } + else if (intervals[_len-1][0].magnitude() == 0) { + intervals[_len-2][1] |= intervals[_len-1][1] + intervals.pop() + } + } + + return intervals + } + vec2.prototype.toString = function(){ return "[" + ~~this.a + " " + ~~this.b + "]" } @@ -115,8 +189,7 @@ if ('window' in this) { window.vec2 = vec2 } - else if ('module' in this) { + else { module.exports = vec2 } - -})()
\ No newline at end of file +})() |