JavaScript collision detection for a rectangle and a set of boundary coordinates?

Question

I've been looking at similar questions posted on Stack Overflow (and elsewhere) but they seem to either only deal with rectangles, which I can handle well at this point, or are more complex than I can currently wrap my head around.

I'm moving a sprite around the screen via mousedown events and want to lock it from moving "out of bounds". The bounds could be something simple like this room:

Where the green is movable space and the red is restricted. Am I better off breaking this down into something like 1 long rectangle and 2 triangles (or groups of squares to represent a triangle with jagged edges) or is there a basic concept that I should look towards to specify the coordinates of the "walkable area" and verify that the user is always "within bounds"?

I'm coding this in JavaScript and am relying heavily on jQuery.

Edit: Considering I'd potentially need to have limitless points (if the room had more than 4 points) would I be better off using something like A* to generate the paths?

Yourpalal · Accepted Answer · 2011-10-18T05:48:17.460

4

Try deconstructing your problem a bit. With this simple shape, you have a rectangle that needs to have x-coordinates between two slopes, and y-coordinates between two flat lines.

Something like this should work nicely:

function outOfBounds(point, boundary) {
    return point.y > boundary.top
        || point.y < boundary.bottom
        || point.x < boundary.getLeftBoundAt(point.y)
        || point.x > boundary.getRightBoundAt(point.y);
}

Recall that sloped lines can be defined as mx + b, but in this case, the x-coordinate of your slopes varies in relation to the y coordinate. Anyway, getLeftBoundAt() will look something like:

function getLeftBoundAt(y) {
    return this.slope * y + this.base;
}

EDIT:

Due to the fact that the height varies along the left and right edges as well, you would need a slightly more complex solution, where boundary.top is replaced with a call to a function like this:

function getTopBoundAt(x) {
    var segment = this.topSegmentAt(x);
    return segment.origin.y + segment.slope * (x - segment.origin.x);
}

edited Oct 18 '11 at 05:48

answered Oct 18 '11 at 04:59

Yourpalal

476
3
11

Thank you, that's very helpful. My only concern is would this kind of logic break when the boundary has more than 4 points? i.e. this: http://oi52.tinypic.com/2u8i0bb.jpg – Charlie Schliesser Oct 18 '11 at 05:15
1

Not necessarily... In the second case you gave you would be fine applying this basic technique. However, instead of boundary.top, you would need a boundary.getTopAt(x) to account for the different heights. Generally, you could extend this technique using getSomeBoundAt(x_or_y_here) for any convex polygon. the various getBound() methods would need to be extended to consider different line segments, for your second image, there are 7 such segments to consider for boundary.getTopBoundAt(). – Yourpalal Oct 18 '11 at 05:43
Upon further reflection, you would need to use getTopBoundAt() even for your first example, since the top y varies along the two edges as well. I'll edit my solution to reflect this. – Yourpalal Oct 18 '11 at 05:43
That is really cool. Thanks for your help. When I get this into my code I'll post it back here. :) – Charlie Schliesser Oct 18 '11 at 14:51

score 1 · Answer 2 · edited May 23 '17 at 12:09

The most common solutions to this are either to deconstruct the parts into triangles and then do overlap testing, or to render it as a pixelated bitmap and do pixel-at-a-time comparisons.

The former is called either Tessellation or Triangulating a Polygon:

http://en.wikipedia.org/wiki/Polygon_triangulation

And has the benefit of being better than O(n^2). There are a number of algorithms to do it, mostly because 3-D engines need to generate lists of triangles to hand to graphics accelerator hardware, which often takes information in triplets of [x,y] coordinates.

The latter is unfortunately O(n^2), but allows you to do things like checking the alpha of a bitmap, so that things that are "clear" in a picture (alpha zero or some cutoff) don't count. Thus, you do interesting things like determine if two overlapping pixels combine to be "solid" enough for a collision, and thus have "fuzzy" partial-alpha bitmaps flying around. This example does not cover alpha, and is for android, but the example holds in general:

https://gamedev.stackexchange.com/questions/23603/how-to-handle-pixel-perfect-collision-detection-with-rotation

Some additional information can be found here:

A simple algorithm for polygon intersection

https://gamedev.stackexchange.com/questions/33553/what-algorithms-exist-for-generating-collision-geometry-from-an-image

Note: If you do want to use rectangles, including bunches of rectangles stacked in approximate shapes, as the boundary for collision, then (full disclosure) I made a jQuery plugin for that. Since you said you rely on jQuery a lot:

https://sourceforge.net/projects/jquerycollision/

Thanks for the detailed info! All of this is helpful reading material. I will play with your jQuery Collision plugin, too. — Charlie Schliesser, Jan 03 '13 at 17:02

score 1 · Answer 3 · answered Oct 18 '11 at 05:52

1

Another possibility for simple-ish, contiguous allowable areas is that you could simply include a low-res map similar to the one provided in your question, and convert x/y coordinates to image coordinates. If the pixel is at the corresponding location point is green, you're good to go. This could potentially be very fast, and also simple to implement.

Is this a bit of a hack? Maybe, yes... but I think it's also a pretty fun solution.

answered Oct 18 '11 at 05:52

Yourpalal

476
3
11

I think this is similar to the method that old point-and-click adventure games implemented. It sounds more like what I had in my head. – Charlie Schliesser Oct 18 '11 at 14:51
So there is something very cool I've stumbled onto with SVGs in this respect. Using pointer-event and an embedded SVG (*not* an SVG via tag) you can check whether coordinates contain a "no no" area. I'll post back when I've got this working, should anyone else stumble on to this. – Charlie Schliesser Oct 27 '11 at 00:47

score 0 · Answer 4 · answered Jan 08 '12 at 17:19

I marked YourPalAl's answer as correct above, but I wanted to leave my final solution as an answer should someone else stumble upon this.

I'm now using jQuery SVG (http://keith-wood.name/svg.html) to insert SVG polygon coordinates as needed which define the boundaries, and checking the objects "next destination" within a 5 pixel tolerance range. If the next destination hits the polygon, I stop the object from moving further.

JavaScript collision detection for a rectangle and a set of boundary coordinates?

4 Answers4

EDIT: