diff options
Diffstat (limited to 'public/assets/javascripts/rectangles/engine/shapes/regionlist.js')
| -rw-r--r-- | public/assets/javascripts/rectangles/engine/shapes/regionlist.js | 83 |
1 files changed, 60 insertions, 23 deletions
diff --git a/public/assets/javascripts/rectangles/engine/shapes/regionlist.js b/public/assets/javascripts/rectangles/engine/shapes/regionlist.js index 71f19d8..663f3fd 100644 --- a/public/assets/javascripts/rectangles/engine/shapes/regionlist.js +++ b/public/assets/javascripts/rectangles/engine/shapes/regionlist.js @@ -1,36 +1,58 @@ +// This algorithm takes the polylines from ShapeList as input and produces +// a set of Rooms which can be used by the existing V1 mover and editor. + +// The algorithm assumes that +// 1) all angles are orthogonal +// 2) all polylines are closed + var RegionList = (function(){ var RegionList = {} var regions = RegionList.regions RegionList.build = function(){ + + // first, get the segments sorted right to left & top to bottom var segments = RegionList.getSortedSegments() var rooms = [] var seen_rooms = {} var open_segments = [] - var closed_segments = [] var segment, open_segment, x_segment, y_segments, overlapped, seen_segments + // first pass: generate rooms from the vertical segments only for (var i = 0; i < segments.length; i++) { segment = segments[i] if (! segment.isVertical()) { continue } + + // check all the "open segments" we know about, i.e. rooms where we've only found + // the right wall. overlapped = false for (var j = 0; j < open_segments.length; j++) { open_segment = open_segments[j] + + // if these two segments overlap each other, then there is a room between them. if (segment.y.overlaps(open_segment.y)) { overlapped = true - closed_segments.push(open_segments[j]) open_segments.splice(j--, 1) + // the X part of the room will be the span between these two vertical segments' + // X components. the Y part of the room is the "split" or subdivision between + // the two horizontal vectors. + + // the split function is non-commutative, + // so we need to call A split B and B split A, + // then dedupe the segments we got back.. x_segment = new vec2( open_segment.x.a, segment.x.b ) y_segments = open_segment.y.split(segment.y, 0, 0) seen_segments = {} + // check each of the splits.. if the two segments overlap, then we definitely + // have a room here. y_segments.forEach(function(seg){ seen_segments[ seg[0]+"" ] = true var room = new Rect( x_segment, seg[0] ) @@ -46,7 +68,8 @@ var RegionList = (function(){ j++ }) - y_segments = segment.y.split(open_segment.y, TOP, BOTTOM) + // splitting the other way.. + y_segments = segment.y.split(open_segment.y, 0, 0) y_segments.forEach(function(seg){ if (seen_segments[ seg[0]+"" ]) return; var new_seg = new Rect( segment.x, seg[0] ) @@ -55,6 +78,9 @@ var RegionList = (function(){ }) } } + + // if we have overlap, then re-sort the open segments Y-wise + // and (again) dedupe.. if (overlapped) { open_segments = open_segments.sort(function(a,b){ if (a.y.a < b.y.a) { return -1 } @@ -74,6 +100,7 @@ var RegionList = (function(){ } } } + // if we don't have any overlap, then this is a new open segment. else { open_segments.push(segment) } @@ -81,11 +108,15 @@ var RegionList = (function(){ var splits, splitter + // second pass: now that we have a bunch of rooms, assign sides to all of them. + // sides are used in the "mover" script to do bounds checking. for (var i = 0; i < segments.length; i++) { segment = segments[i] var horizontal = segment.isHorizontal(), vertical = segment.isVertical() for (var r = 0; r < rooms.length; r++){ room = rooms[r] + + // vertical segments determine the left and right edges of the room, fairly simply. if (vertical) { if (segment.y.containsVec(room.y)) { if (segment.x.a == room.x.a) { @@ -96,6 +127,8 @@ var RegionList = (function(){ } } } + + // horizontal segments determine the front and back edges of the room. if (horizontal) { if (segment.x.containsVec(room.x)) { if (segment.y.a == room.y.a) { @@ -105,28 +138,30 @@ var RegionList = (function(){ room.sides |= BACK } } - - else if (segment.y.a == room.y.a || segment.y.a == room.y.b) { - if (room.x.overlaps(segment.x)) { - splits = room.x.split(segment.x, room.sides & LEFT, room.sides & RIGHT) - rooms.splice(r--, 1) - console.log(splits) - for (var k = 0; k < splits.length; k++) { - splitter = splits[k] - var new_room = new Rect( splitter[0], room.y ) - new_room.sides = 0 - new_room.sides |= splitter[1] | ( room.sides & FRONT_BACK ) - if (segment.x.overlaps( splitter[0] )) { - if (segment.y.a == new_room.y.a) { - new_room.sides |= FRONT - } - if (segment.y.a == new_room.y.b) { - new_room.sides |= BACK - } + + // however, since we did not split on horizontal segments, our rooms may + // only have partial overlap with these segments, in which case we need to + // split the rooms apart. + else if ((segment.y.a == room.y.a || segment.y.a == room.y.b) && room.x.overlaps(segment.x)) { + + // split the room across the segment. preserve whether or not we know the + // room borders a segment on the left or right. + splits = room.x.split(segment.x, room.sides & LEFT, room.sides & RIGHT) + rooms.splice(r--, 1) + for (var k = 0; k < splits.length; k++) { + splitter = splits[k] + var new_room = new Rect( splitter[0], room.y ) + new_room.sides = splitter[1] | ( room.sides & FRONT_BACK ) + if (segment.x.overlaps( splitter[0] )) { + if (segment.y.a == new_room.y.a) { + new_room.sides |= FRONT + } + if (segment.y.a == new_room.y.b) { + new_room.sides |= BACK } - rooms.unshift(new_room) - r++ } + rooms.unshift(new_room) + r++ } } @@ -137,6 +172,8 @@ var RegionList = (function(){ return { rooms: rooms } } + + // Gets a list of polylines from the ShapeList and sorts the segments. RegionList.getSortedSegments = function(){ // get a list of all segments from these polylines var segments = shapes.getAllSegments() |