Pixel perfect collision detection or is it needed?

[dunkha]

Hello,

I found from wiki there is implementation for pixel perfect collision detection and I have heard from many sources I should try to avoid it. However, it really looks like I need it. At least in some parts.

I'm working on a cave flying game. My plan is to have different kind of space ships. Because of the nature of the game I think I can't avoid using pixel perfect collision detection. I should know when bullets and missiles hit the ships and also when ships are colliding with the environment. But before I start implementing it I would like to hear opinions about collision detection. So what's your opinion? Does anyone know a good solution for collision other than pixel perfect that could fit my requirements?

I was thinking of forming a ship using multiple rectangles but then I should implement the rectangles for each of the ships because they are different shape and even then it wouldn't be pixel perfect and I think it could really harm the gameplay. And how should I move the rectangles? Should I move and rotate them with the ship? I'm not sure it would work but I could give it a try. Then I could detect if the ship rectangle is colliding with anything and after that go through every inner rectangle and check if any of them collide.

It would be a lot easier if I could just use textures and let one universal implementation take care of the collision detection. If it is just possible and would not slow down the game too much. After all I would like the game run smoothly and be light-weight.

Thanks in advance!

[sjaustirni]

Premature optimization is the root of all evil.

If you are more comfortable with pixel-perfect implementation, but are afraid of its performance, then implement it and go test it. There's no better advice than this.

Having said that, I have never implemented pixel-perfect collision detection. That's because even though it's easy to implement, I never really grokked how pixel-perfect collision resolution was easy to implement. IDK, maybe it's just me, maybe it's because I have stumbled upon SAT in the process.

So, if AABB/oriented AABB and pixel perfect are out of question, I suggest you to have a look at SAT. It works on any convex polygons AND it's really fun to implement. (You will need to decompose your concave polygons into convex ones though).

[dunkha]

Hi,

premature optimization is the root of all evil? Good tip! . But tbh, I really don't have much understanding how heavy task it will be so that's why I was asking for an opinion.

Anyway, thanks for the reply! SAT looks like good option and I'm definitely looking into it. Perhaps best would be to implement both Pixel Perfect and SAT and see how it goes. At least now I think convex polygons are enough for me and I don't need to have concave polygons. So maybe SAT could be better but I just can't figure out it all yet. At least now I have something to start with and I'll see how it goes.

Btw, I don't really understand what you mean by pixel-perfect collision resolution?

[sjaustirni]

I would actually go for AABB/SAT combo. I am pretty confident that based on what collision polygon masks you're going to use, SAT will be unnoticeable compared to pixel-perfect.

Almost every collision system is composed of 2 parts:

• collision detection - finds out which objects collide and what are the collision points
• collision resolution - determines what velocity/acceleration should the colliding objects be given and how should be the objects moved

[dunkha]

Thanks for the reply!

That might work for most of the part. However, I was thinking of using similar environment to Worms games. So that means there will be lots of curvy shapes. As far as I know, SAT is not suitable for curvy shapes.

I was actually trying to explain what I've been thinking here but I found out that it's too difficult without using any demonstration images. Anyway, I was able to implement a semi-pixel-perfect collision detection test and by that I mean I can check if a sprite boundaries is colliding with a pixel of another sprite. So it is like one-way pixel perfect collision detection. I still have some problems and some ideas how to solve them but I'll get back into them after I've drawn some pictures to demonstrate the problems.

[GameBear]

Well, it's a long time since, but what I did when I needed pixel.perfect collision (for a lemmings like game)
Was:
1: spatial partitioning, terrain was decided in 32 by 32 boxes.
2: bounding box collision on anything shown in 1.
3: inner box collision (8 by 8 boxes inside the 32 by 32 boxes of the terrain)
4: pixel perfect collision on anything inside any 8 by 8 box that hit whatever I was testing against.

Why? Because testing 15 figures of 8 by 16 pixels and each weapon/tool effects texture against a map of > 1000 by 1000 pixels was simply to much.
This way it was just any 8 by 8 square close enough against a 8 by 16.
And that was still over 8000 tests...

Just some experience... That said... It was in Java and many years ago..

[sjaustirni]

Thanks for the reply!

That might work for most of the part. However, I was thinking of using similar environment to Worms games. So that means there will be lots of curvy shapes. As far as I know, SAT is not suitable for curvy shapes.

That's true, curvy shapes are a problem for SAT.

I was actually trying to explain what I've been thinking here but I found out that it's too difficult without using any demonstration images. Anyway, I was able to implement a semi-pixel-perfect collision detection test and by that I mean I can check if a sprite boundaries is colliding with a pixel of another sprite. So it is like one-way pixel perfect collision detection. I still have some problems and some ideas how to solve them but I'll get back into them after I've drawn some pictures to demonstrate the problems.

Again, in pixel-perfect, detecting a collision is not the hard part. What you do with it is the hard part.

[dunkha]

Well, it's a long time since, but what I did when I needed pixel.perfect collision (for a lemmings like game)
Was:
1: spatial partitioning, terrain was decided in 32 by 32 boxes.
2: bounding box collision on anything shown in 1.
3: inner box collision (8 by 8 boxes inside the 32 by 32 boxes of the terrain)
4: pixel perfect collision on anything inside any 8 by 8 box that hit whatever I was testing against.

Why? Because testing 15 figures of 8 by 16 pixels and each weapon/tool effects texture against a map of > 1000 by 1000 pixels was simply to much.
This way it was just any 8 by 8 square close enough against a 8 by 16.
And that was still over 8000 tests...

Just some experience... That said... It was in Java and many years ago..

Thank you! This was really helpful and good ideas. It's simple and I like it. I was thinking of dividing the terrain in different sized squares depending on how the terrain is formed but now that I look at into your solution I can see it's just much simpler to divide the terrain in certain amount of squares and those squares in smaller inner squares. So I can use the same logic in every maps.

Again, in pixel-perfect, detecting a collision is not the hard part. What you do with it is the hard part.

It's true that it's surprisingly simple to implement. But taking into account that it's my first time really making any games these things can seem quite complicated to me first. And what was difficult was to optimize it in somehow. I know what you said about premature optimization but this is not really even optimization it's like making it sensible enough that you can run it somehow .

This weekend I got some time and I'm going to implement my first version of collision detection. I'll get back to this next week.

[sjaustirni]

If you're just starting out with collision detection, I would surely go for AABB first, followed by oriented bounding boxes.