Foomer's Site - How to program a bounding box?

#1 Dec 8 2009, 5:03 pm
Airjoe	Xooxer had a really cool pixel movement / collision system, but I think he pulled it off the hub (still, try taking a quick look for it). I'll see if I still have a copy locally somewhere, but if not, I'll try and write one up some time this week (unless someone beats me, but I may do it anyway just for alternative ideas). Bounding circles are much much easier to do, by the way.

#2 Dec 8 2009, 5:08 pm In response to Airjoe (#1)
Foomer	Airjoe wrote: Bounding circles are much much easier to do, by the way. Bounding circles don't work quite as well on a grid, I suspect. Actually I already know how to do circles, but I want to know how to do squares.

#3 Dec 8 2009, 7:01 pm

Jerico2day

Foomer wrote:

Could someone create a tutorial on how to properly program bounding boxes and detect when two bounding boxes are colliding? Seems like it should be simple thing to do, but I don't know how its supposed to be done.

Bounding boxes? Super easy. In Pseudo BASIC:

<code> x1 = top horizontal y1 = left vertical x2 = bottom horizontal y2 = right vertical point1X = horizontal 2d position point1Y = vertical 2d position if point1X => x1 AND point1X =< x2 if point1Y => y1 AND point 1Y =< y2 'collision! endif endif </code>

For 2 bounding boxes:
<code> obj1.x1 = top horizontal obj1.y1 = left vertical obj1.x2 = bottom horizontal obj1.y2 = right vertical obj2.x1 = top horizontal obj2.y1 = left vertical obj2.x2 = bottom horizontal obj2.y2 = right vertical 'check each object against each other object, usually in while/endwhile loop or similar if obj1.x1 => obj2.x1 AND obj1.x1 =< obj2.x2 if obj1.y1 => obj2.y1 AND point obj1.y2 =< obj2.y2 'collision! endif endif </code>

This is all off the top of my head, so the logic may need adjustment, but this is how it's done.

Now, if the object is moving faster than it's size (example, a 10 pixel width object moving at 30 pixels at a time), well, it'll pass right through small objects. In these cases you need to use other logic, either checking movement at each pixel or some other technique.

#4 Dec 9 2009, 10:26 am
KodeNerd	http://www.gamedev.net/reference/articles/article735.asp George Gough

#5 Dec 9 2009, 1:05 pm In response to KodeNerd (#4)
Jeff8500	This. Usually, in my pixel movement projects, I just copy and paste the snippet there, then rewrite it in DM.

#6 Dec 9 2009, 2:00 pm

In response to Jerico2day (#3)

Garthor

Jerico2day wrote:

Now, if the object is moving faster than it's size (example, a 10 pixel width object moving at 30 pixels at a time), well, it'll pass right through small objects. In these cases you need to use other logic, either checking movement at each pixel or some other technique.

Treat time as an additional dimension. You can now generate simple 3d shapes out of our 2d shapes assuming there is no acceleration during a single frame. Now we can check for a collision between the parallelepiped representations of our moving 2d shapes, and the problem is relatively straightforward, though obviously slightly more difficult than axis-aligned bounding boxes.

Obviously, the similar method for 3d collision detection involves words that are much more fun.

NOTE: this is just a crazy idea that popped into my head and should not be taken as real advice.

#7 Dec 9 2009, 8:19 pm

In response to Garthor (#6)

Jerico2day

Garthor wrote:

Jerico2day wrote:

Now, if the object is moving faster than it's size (example, a 10 pixel width object moving at 30 pixels at a time), well, it'll pass right through small objects. In these cases you need to use other logic, either checking movement at each pixel or some other technique.

Treat time as an additional dimension. You can now generate simple 3d shapes out of our 2d shapes assuming there is no acceleration during a single frame. Now we can check for a collision between the parallelepiped representations of our moving 2d shapes, and the problem is relatively straightforward, though obviously slightly more difficult than axis-aligned bounding boxes.

Obviously, the similar method for 3d collision detection involves words that are much more fun.

NOTE: this is just a crazy idea that popped into my head and should not be taken as real advice.

Yes, that is one technique, to stretch the bouding box along the path it's passed through. Another, simpler technique is to check for collision every few pixels. Of course, the tradeoff is computing speed.

#8 Dec 9 2009, 9:50 pm
Kuraudo	I figured there were already demos available on this, but I guess not. Given the relative usefulness such info could have for certain games, I'll try to make a DM-based demo either tonight or tomorrow.

#9 Dec 9 2009, 10:37 pm In response to Jerico2day (#7)
Garthor	You are misinterpreting what I've said.

#10 Dec 10 2009, 4:39 am (Edited on Dec 10 2009, 4:54 am) In response to Kuraudo (#8)
Kaioken	If you're going to try and make it easier for others, you could go ahead and make a demo for a harder method instead, since boxes are relatively simple to do and tend to be pretty inaccurate. Although DM has `GetPixel()`, I dunno if it's really fast enough for pixel collision.

#11 Dec 10 2009, 7:49 am In response to Garthor (#9)
Jerico2day	Garthor wrote: You are misinterpreting what I've said. Could be, your post was really wordy!

#12 Dec 10 2009, 10:30 am In response to Jerico2day (#11)
Garthor	That's because I wanted to say "parallelepiped".

#13 Dec 10 2009, 3:16 pm

In response to Kaioken (#10)

Kuraudo

Kaioken wrote:

If you're going to try and make it easier for others, you could go ahead and make a demo for a harder method instead

I might try to write up something for polygon collision involving the separation axis method.

since boxes are relatively simple to do and tend to be pretty inaccurate.

Granted, if they were too simple there wouldn't be this thread.

Although DM has GetPixel(), I dunno if it's really fast enough for pixel collision.

Unless much has changed with it, very doubtful.

#14 Dec 11 2009, 7:36 am In response to Kuraudo (#13)
Jerico2day	Has get pixel ever been fast in any language? :D You can store the pixel data in an array and then it would be fast enough:)

#15 Dec 11 2009, 12:40 pm In response to Garthor (#12)
Hobnob	If you had followed-through with the 4D (3D + time) case, you would have been able to use "hyperparallelepiped".

#16 Dec 11 2009, 12:43 pm In response to Hobnob (#15)
Stephen001	Which we do at work, unfortunately. We just call it "Long winded" instead.

#17 Dec 11 2009, 1:06 pm

In response to Kaioken (#10)

D4RK3 54B3R

Kaioken wrote:

Although DM has GetPixel(), I dunno if it's really fast enough for pixel collision.

Well, to really make good use of GetPixel(), you need to do up to 1024 iterations per tile.
I don't think GetPixel() is actually particularly slow, but doing anything for 1024 iterations through a VM like BYOND is going to be slow.

There are probably some more clever uses of GetPixel(). Something like only making less than 10 iterations per tile to generate a bounding box for that tile based upon the graphic, but I'm not sure how fast that is.

#18 Dec 13 2009, 11:14 am

In response to Jerico2day (#3)

Loduwijk

Jerico2day wrote:

Bounding boxes? Super easy. In Pseudo BASIC:

<code> > x1 = top horizontal > y1 = left vertical > x2 = bottom horizontal > y2 = right vertical > ... > </code>

I think you have your terms backward there. x1/x2 should be the left/right verticals, y1/y2 should be the top/bottom horizontals.

For 2 bounding boxes:
<code> > ... > > 'check each object against each other object, usually in while/endwhile loop or similar > > ... > </code>

By "check each object against each other object" do you mean check each point in obj1 to see if it's in obj2, and check each point in obj2 to see if it's in obj1? If so, then good.

Another point to bring up concerns if you are using non-square rectangles. They weren't specifically mentioned, but it's a good thing to keep in mind since bounding boxes often end up being non-square. In this case, you can have a collision without having any of the points of one rectangle inside the other rectangle. For example, if obj1.x1<obj2.x1, obj1.x2>obj2.x2, and obj2.y1<obj1.y1<obj1.y2<obj2.y2. In this case the rectangles would be overlapping like a plus sign.

Now, if the object is moving faster than it's size (example, a 10 pixel width object moving at 30 pixels at a time), well, it'll pass right through small objects. In these cases you need to use other logic, either checking movement at each pixel or some other technique.

If you wanted to implement a collision system for non-rectangular polygons, you could create a shape that starts with the initial bounding box, add to it the translated bounding box (the one for after the move), then loop through all of the points in the bounding box such as for(point/p in boundingBox) and connect the initial bounding box's p to the translated bounding box's p with a line. Anything inside this temporary shape would be inside the path of motion of the object and would therefor be a collision.

Now, if you wanted to take into account the fact that two objects could have moved during the same frame, then you have to create one of these temporary shapes for the motion of both objects during the frame and see if the shapes overlap at all. If they do, then they collide during motion.

Algorithms to handle the question "Is this inside of that thing which could be of any shape?" are more difficult to make, but doing this has the added benefit of perfect accuracy. And it's probably more efficient than checking the box at every pixel, or even every few pixels, of movement.

#19 Dec 13 2009, 11:40 am

In response to Jerico2day (#14)

Loduwijk

Jerico2day wrote:

Has get pixel ever been fast in any language? :D

Yes; see the following.

You can store the pixel data in an array and then it would be fast enough:)

If you're working lower-level, such as in C or C++, you often do have pixel data in an array. Remember, that's how the computer keeps track of it behind the scenes anyway. In lower level languages, you often have direct access to that.

For example, for textures in OpenGL, when you put your graphic data into an array and feed that to OpenGL to tell it what an image looks like, there's nothing stopping you from doing anything else with your array of pixel data you've created. In fact, 24-bit bitmap file format is so simple that I just created my own function for loading bitmap data into an array and one for saving it back to a bitmap.

If you wanted to have access to something like this in Byond, remember that you can do DLL stuff server-side now. You could create a function that takes a dmi file's filename and returns an array of pixel data. Even though it has to be in string format on Byond's side, you could still have the C function make a byte array and return it as a character string, and on Byond's side you could use text2ascii() to get the byte values from the string.

The following example is going to assume that the C function prefixes the return value with 2 extra bytes, the first being the width of the icon in pixels and the second being its height in pixels. Also, this assumes that the dmi has only 1 icon state to search for, otherwise you have to do more stuff, though the more stuff could still be mostly on C's side.

proc/dmi2array(filename)
    var/returnString = call("myLib.dll","dmi2array")(filename)
    var
        width = text2ascii(returnString,1)
        height = text2ascii(returnString,2)
    var/list/imageData[width][height]

    for(var/indexy = 1 to height)
        for(var/indexx = 1 to width)
            imageData[indexx][indexy] = text2ascii(returnString, 2 + indexx + (indexy-1)*width)

    return imageData

And you could set up the C function to handle more than just dmi as well, obviously, since you could handle it however you wanted.

Not only that, but if you make a dll with a function to load up image data, you might as well make one right in there that returns a bit map of which pixels are opaque to make a sprite for collision detection out of. So you could also have a proc/getCollisionArray(filename)

It would be interesting to see the speed advantage of doing it this way.