In response to Loduwijk (#18)
Loduwijk wrote:
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.

I'm pretty sure I have it right. Since x is on the horizontal axis, and y is on the vertical axis.



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.

using the logic i printed checks inside each object, you use a recursive loop to check each object that is collidable against each other object. It can add up to a whole lot of objects real quick, so you gotta keep your collision objects low and only check em if absolutely necessary. You can setup zones to exclude objects.

There's other methods of collision which may be faster.

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.
In response to Loduwijk (#19)
Loduwijk wrote:
Jerico2day wrote:
Has get pixel ever been fast in any language? :D

Yes; see the following.

Perhaps in C++ it's fast depending on how it's setup. In the higher level languages I've used, get pixel (or the equivilent name) has always been really slow.

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.
Page: 1 2