Convert image to a number of squares?

[Christian Knudsen]

I'm working on a 2D game using sprites. Instead of making exact collision masks for each sprite, I just want to assign a number of rectangles to each sprite, so that if the object that I'm checking for collision is within any of these squares, it's colliding with my sprite. I've tried drawing the squares on top of my sprite image manually and then inputing the coordinates of each square into my code, but drawing these squares takes a lot of time, so I was wondering if there's a program that can convert an image into X number of squares (all of them within the edges of the sprite), or a plugin/script for GIMP that can do that?

(Hope this makes sense!)

EDIT: Here's an example:

-->

[noeska]

I dont know if it is worth the trouble.

Alternatively you can look at this:
It is also possible to use the stencil buffer for collision checking:
http://kometbomb.net/2007/07/11/hard...ion-in-opengl/
and
http://kometbomb.net/2008/07/23/coll...queries-redux/

[Christian Knudsen]

The thing is, I can't really use screen drawing functions for my collision detection routine, as a lot of these collisions will happen off-screen. That's why I want to go with the collision boxes idea, as everything needed for checking for collisions will then be hardcoded into the game logic and won't require any screen drawing or checking of textures and sprites. Plus, it'll be a lot faster.

I'll just continue doing the box drawing manually, I guess...

[AthenaOfDelphi]

I would suggest a real good google. I've tried to write a simple progam to do this, but it has some flaws and it certainly won't work properly with concave outlines like the example sprite you provided. Essentially though what I did was calculate the outline of the sprite and then using some very basic statistical analysis to calculate the weight of each column and row, I created a set of quads which contained the sprite (the next stage was to be calculating whether each quad contained some of the sprite.

There are a whole host of articles on the web about bounding boxes and sprite based collision detection. Most of them appear to use a containing bounding box that encompasses the whole sprite and then do pixel based checks if you get a match on bounding boxes. Of course, you could adopt a two stage bounding approach... one box defines definite hits and another defines possible hits.

You've not stated what the underlying API is (or whether you're using some sort of framework) I think, depending on the underlying API, it can also be done by the API and I know it can be done by some of the frameworks.

[Christian Knudsen]

I've already googled this a lot, but wasn't able to find a program or plugin to help me. I know about different methods for collision checking, so I wasn't looking for alternative methods, as the one I've decided on is best suited for my game. Anyway, I did a quick test and discovered that the boxes don't have to be all that precise - the effect is actually best if the boxes don't follow the edges of the image 100%, as this gives the effect of the object being 3D, since all bullets won't impact right on the edge but sometimes further in. It works perfectly. Almost seems to be pixel perfect collision, but a lot faster and not as clinically precise on the edges as pixel perfect collision would be. So, doing the boxes manually won't be quite as big a chore, since they don't need to be all that perfect.

(I'm using SDL and OpenGL, by the way.)

[arthurprs]

why not use polygon collision detection?

but maybe we can come up with an algorithm do do that

[Christian Knudsen]

I've been racking my brain trying to come up with an algorithm to calculate these boxes, but I'm drawing a blank. Any ideas are welcome.

[noeska]

octree's or something like that?
Try to subdevide the boundbox into smaller cubes and check each time if there are pixels inside. After x steps you have some boxes left with either pixels inside and ones without.

[User137]

What if your sprite is triangle shaped?

[Christian Knudsen]

The idea is to calculate the squares that approximate the shape, whatever it is.

Try to subdevide the boundbox into smaller cubes and check each time if there are pixels inside. After x steps you have some boxes left with either pixels inside and ones without.

I'll give this a try. I'll probably try it with all pixels inside the square required to have an alpha value above 0.5, or something similar.