TIGSource Forums

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 image sprite), or a plugin/script for GIMP that can do that?

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

(Hope this makes sense!)

(http://farm4.static.flickr.com/3124/3191689303_a823e53383.jpg)

I made this by gradually evolving a picture using only quads, but it doesn't help you at all  :D

In all seriousness though, your problem may be a variation of the packing problem (http://en.wikipedia.org/wiki/Packing_problem) which is, I think, NP-hard (http://en.wikipedia.org/wiki/NP-hard).

edit: You should probably just try to implement pixel perfect collisions.

It's not exactly what you're after, but I've previously had luck exporting a path from GIMP to svg and using the svg data to build collision geometry.

I actually remember reading about this in another thread and actually went looking for it before posting my original message. :) Looks very nice!

I'm currently trying to make a program to do what I want. The algorithm I'm currently pursuing is dividing the image into a bunch of squares (4x4 pixels, as that's the collision movement resolution I'm using), then mark all squares that only have pixels with alpha > 0.5, and then connecting these marked squares into larger squares. I think this should work in theory, but time will tell.

As to pixel perfect collision: that will be too slow for what I have in mind (I'll have to do a lot of collision checking). My multiple squares approach worked really well in the test I did (where I manually calculated the squares). It's really fast and I actually like it better than pixel perfect collision, as it doesn't always register the hit as soon as the bullet reaches a pixel, but sometimes further "inside" the image -- this almost gives it a 3D effect, as you seem to not just be hitting the edges of the sprite, but stuff on the sprite.


Sounds interesting, but also sounds slower than just checking the bullet X,Y coordinates against 10-12 squares...?

I've managed to make my own program to generate collision boxes. Works pretty well:

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

Hm, would converting to a bunch of circles potentially be more efficient? Not as accurate for squarish shapes I guess, but it could potentially be faster for collisions.

I imagine it would be a lot slower. For squares you just check that the object is within the square. No calculations required, as it's just comparing X and Y coordinates. With a circle, you have to calculate the distance from object to circle center. A lot slower.

Holy crap, that's a good idea! It looks like you might have divided the image into a grid, and if it had more than X number of filled pixels, you treated that square as "filled". From there, you simplified adjacent squares into rectangles. Is this even remotely correct?

Spot-on! ;D