Jump to content
  • Advertisement
Sign in to follow this  

Collision Filtering (by group?)

This topic is 2563 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey all,

I'm working on a shmup and I'm trying to filter out some collisions. Normally, in my framework, I just brute force through all the entities checking every other entity, but this is the first game I've made that has a whole mess load of entities. In this particular game, there's no reason for the enemy bullets to ever check against anything but the player's ship. A system of filtering seems to be the best / easiest fit but I'm looking to make it as extensible as possible for all future projects.

At first, I thought a simple system of flags would be sufficient, a simple check like:
if(entity1.flag == BULLET && entity2.filters.contains(BULLET) == false) (or something like that)

That still leaves me iterating n^2 times and so that approach was out.

Now I've devised a system of "collision groups" where when an entity is added, it's placed in a certain group. So the player goes in group0 and the bullets go in group1. That's all fine and dandy.

Each group has a defined map of other groups it collides with like so:

group.defineCollisionMap( [ array of other groups it collides with ] );

In my case, group0 has the player and group1 has the bullets, so it's:


The problem, as I'm sure is quickly obvious, is that group0 checks against group1 and group1 checks against group0. That's double the amount of collision checks that's necessary. However, not defining the "collision map" for group1 because I've already defined a relationship in group0 just feels... dirty.

Am I just being ridiculous or is there a smarter way to accomplish this?

Share this post

Link to post
Share on other sites
You could simply give each physical object a int representing a "filter level" and only objects with the same filter level will affect each other. In this case have the Enemy bullets and player ship on one level, and then put the player bullets and enemy ships on a second level.

if(obj1.getCollisionFilterLevel() == obj2.getCollisionFilterLevel())
//preform collision operations

Share this post

Link to post
I've never used collision maps in my games, but I would assume you could give each object type a separate shade of grey and just use the same collision map(Correct me if I'm mistaken). If you know the player doesn't intersect with the bullets there is no point checking a second time to see if the bullets intersect with the player so I don't understand what you're doing there.

if what you're talking about is going through an array of objects and checking as such:
1,2 1,3 1,4 1,5
2,1 2,3 2,4 2,5
3,1 3,2 3,4 3,5

the proper way to check the objects is
1,2 1,3 1,4 1,5 1,6
2,3 2,4 2,5 2,6
3,4 3,5 3,6
4,5 4,6

I'll give a crude example of parsing this way.

Vector vect = new Vector()

//there is probably a prettier way to do this but you useing a nested 4 loop is appropriate and efficient here
for(int i = 0, i<vect size;i++)
for(int b = i+1, b<vect .size; b++)
if(b<vect .size)
if vect.get(i) intersects vect.get(b)
//preform operation

Share this post

Link to post
Share on other sites
Hey GameGeazer,

Thanks for your response -- I guess I wasn't super clear. In this case, defineCollisionMap() takes in an array of other groups that the group should check it's collisions with. Here's a more long winded example:

Say I have four groups: playerGroup, playerProjectileGroup, enemyGroup and enemyProjectileGroup.

I might define the "maps" as:

playerGroup.defineCollisionMap( [ enemyGroup, enemyProjectileGroup ] );
playerProjectileGroup.defineCollisionMap( [ enemyGroup ]);
enemyGroup.defineCollisionMap( [ playerGroup, playerProjectileGroup ] );
enemyProjectileGroup.defineCollisionMap( [ playerGroup ] );

But you can see later on when I call playerGroup.checkCollisions(), it'll loop through and check all the collisions against the enemyGroup. But when I do enemyGroup.checkCollisions(), it'll loop through and check all collisions against the playerGroup TWICE (since the playerGroup already checked those collisions). But if I don't add the playerGroup to the enemyGroup's collision map... it just seems so muddy. Perhaps I'm just over-engineering here.

Share this post

Link to post
Share on other sites
You can try to keep track of the combination of groups you have already check for collision. A simple tuple with both groupId should be enough and not too costly.

Following your exemple, you have :

1) PlayerGroup -> EnemyGroup => new combination, check collision

2) PlayerGroup -> EnemyProjectileGroup => new combination, check collision

3) PlayerProjectileGroup -> EnemyGroup => new combination, check collision

4) EnemyGroup -> PlayerGroup => same combination than step 1, nothing else to do

5) EnemyGroup -> PlayerProjectileGroup => same combination than step 3, nothing else to do

6) EnemyProjectileGroup -> PlayerGroup => same combination than step 2, nothing else to do

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!