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:

http://img114.imageshack.us/img114/4894/30301770.png --> http://img372.imageshack.us/img372/3306/28023403.png

[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/hardware-accelerated-2d-collision-detection-in-opengl/
and
http://kometbomb.net/2008/07/23/collision-detection-with-occlusion-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 :yes: ???

[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.

[Christian Knudsen]

Haven't had much time for programming the last two days, but I've managed to throw this together so far:

The sprite:
http://img406.imageshack.us/img406/9356/56436112.png

With 4x4 pixels boxes (can be set to any size):
http://img522.imageshack.us/img522/8059/67067416.jpg

You can click on boxes to remove them in order to "fine tune" the result. Now I just need to join the boxes into larger boxes. I believe a pretty simple algorithm can do this. And then output the coordinates of the boxes to a file I can then copy/paste into my game.

I'm currently having trouble getting the alpha value of pixels, though: http://www.pascalgamedevelopment.com/forum/index.php?topic=5915.msg48074

[arthurprs]

i'm trying to use a convex hull algorithm to generate a collision polygon

it's working fine with your sprite, but i still have to do some more tests

[Pyrogine]

What about this:

Trace around the edge of the image to produce a polygon data structure
First do a simple radius (or square) check to see if your "near", this is your non-precision check.
If you're near, then do a 2D line intersection check along the poly points. This will be the precision check. If you get a intersection you've collided and now have the hit pos that can be used for other things.
Way faster than pixel perfect for example and very accurate as compared to a radius/square check. This turned out to work very well for me.

The algo for tracing the sprite was a mind twist and took a very long time to get working. In the end a guy I met on line from Russia help me to finally get this working and it formed the basis of the PolyPoint collision system in Quantum Engine. There are a few params that allow fine tuning of the algo (alpha threshold, stepback, etc). All in all, the algo can auto trace a very complex shaped image. It's tightly integrated with my engine at this point and pulling it out is not as easy any more without a lot of dependencies.

However, maybe if you make a tool that will allow you to lay down line segments around your mage and save out this data, then you can apply the same steps outline above for collision detection. At least it's another option to explore.

[b]Update: I see arthurprs has a convex hull algo working. There is the polygon data that you can use.

[Andreaz]

In the latest version of my image editor for phoenix there is a Collision drawing tool to create collision shapes for an image and then exporting them to a xml file.

If you feel this could be useful i can wrap up a new version of it tonight.

[Christian Knudsen]

I appreciate all the feedback, but like I said before, I've already decided to use my boxes approach, as it's fast as heck.



In the latest version of my image editor for phoenix there is a Collision drawing tool to create collision shapes for an image and then exporting them to a xml file.

If you feel this could be useful i can wrap up a new version of it tonight.

This sounds very neat, Andreaz, and thanks for the offer, but I'm seeking to automate the box drawing functionality so I don't have to draw the collision boxes manually. My goal is basically to be able to place the program in a folder with the images 1-64.png (for the 64 angles my sprites can point). When the program is run it will load each image one by one, do the automatic collision boxes and export all the data to a text file, so all I have to do is a quick copy/paste.

[Christian Knudsen]

I've got a pretty nice program up and running now:

http://img216.imageshack.us/img216/523/58997671.png

The algorithm to join boxes works pretty well and you can fine tune the settings to make the smallest number of boxes per image.

[arthurprs]

here is the result of my current code ???

http://img2.imageshack.us/img2/5849/clipboard011.png

it used 25 points (blue dots) to cover the sprite

i still have to try some optimizations to reduce the resulting hull connection points