A while back, I was throwing around ideas to make my collision detection routines more efficient, especially on the NES, where every cycle counts. I came up with a pretty cool idea that I've never heard before, but I wouldn't be surprised if someone else came up with and implemented this before I did. It just means it's an extra good idea if more than one person came up with it all on their own.
So first and foremost, I'm doing bounding-box collision detection between all of my actors, and I'm iterating through all possible combinations of actors all at once.
If I have actors A, B, C, and D, then I would check AB, AC, AD, BC, BD, CD. It's worthless to check things like AA, BB, etc, and it's redundant to check BA, DB, etc.
Let's say that in my game, there's a player actor, several collectable/powerup actors, and a few enemy actors. Let's also say that enemies don't care about powerups, and enemies don't care about each other (they don't bump into each other).
So maybe in one level, I'll have the player, 10 keys, and 3 enemies. For the player actor, the logical thing would be to check its bounding box with the bounding boxes of each of those 10 keys, and those 3 enemies to see if it's colliding with any of them. No problem!
However, why would I need to check each individual key for collisions against the other keys, and against the enemies, if I've established that they don't do anything when they collide? I'd be performing coordinate transformation calculations for a lot of actors that it doesn't even matter for.
To solve this problem, my system is to assign each type of actor to a team, and have each actor specifiy which teams they collide with. Let's say I have a Player 1 actor, a Key actor, a Health actor, and several different types of enemies.
Each actor has two bytes, which are bitmasks, which determine the team(s) they belong to (the team byte), and which team(s) they collide with (the mask byte). I'll put Player 1 on team 00000001, Key and Health can both go onto team 00000010, and all of the different kinds of enemies can go into team 00000100.
Players need to collide with the collectables and the enemies, so I'll want it to look for collisions with both teams 00000010 and 00000100, so I'll give the player actors a mask byte of 00000110.
Collectables also need to collide with players, since players can collide with collectables, but the collectables don't need to collide with each other, nor the enemies, so I'll give the collectables a mask byte of 00000001. It's important to set both teams up to collide with each other (players collide with collectables and collectables collide with players), otherwise you'll have problems depending on which order you check the actors in.
Enemies also need to collide with players, since players can collide with enemies. They don't need to collide with the collectables, and they don't need to collide with each other, so they get a mask byte of 00000001. Later, if I *do* want the enemies to collide with each other (maybe so they turn around when they bump into each other), I can change their mask byte to 00000101. That way, they'll check for collisions with the players, and members of their own team.
So in summary:
Player1 -> Team 001, Mask 110
Key -> Team 010, Mask 001
Health -> Team 010, Mask 001
EnemyA -> Team 100, Mask 001
EnemyB -> Team 100, Mask 001
EnemyC -> Team 100, Mask 001
So now we're in the level, and the collision routine needs to check each actor combination for collisions. Let's say Actor 1 is a Player1, Actors 2-10 are Keys and Health, Actors 11-14 are various EnemyAs, EnemyBs, and EnemyCs.
The routine first checks (1,2). Actor 1 is a Player1 with a mask 110. Actor 2 is some collectable on team 010.
Mask 110 & Team 010 = nonzero, so this is a valid combination of actors, let's compare 1's collision box with 2's, see if they collide, run the appropriate code if necessary, etc.
Let's say we've done that, and now we check (1,3). Same thing happens, Actor 1 is still Player1 with the same mask 110, Actor 3 is another collectable on team 010. 110 & 010 is nonzero, check these actors for a collision. (There's actually an optimization opportunity here, load actor 1's collision box, transform it, etc, and then just keep that stuff in memory while you compare it with all of the other actors, Until it's time to check Actor 2 against everyone, in which case you forget Actor 1's box, transform Actor 2's box, keep it in memory, etc)
So fast forward a bit, now we're checking (2,3). Actor 2 is a collectable with mask 001. Actor 3 is another collectable on team 010.
Mask 001 & Team 010 = zero, which means we don't even need to bother computing anything else, these two types of actors don't care about colliding with each other.
(2,4) now, same thing, collectable vs. collectable, Mask 001 & Team 010 = zero, so skip and go to the next combination.
So keep going and going until everyone's been checked. The end result is that we've saved ourselves from a lot of worthless computations trying to compare certain combinations of actors who don't care about colliding with each other. Again, on modern hardware, who really cares? However, on a system like the NES, every cycle you save is important.
Now, it's time to touch on something. Remember how it was important to say both that players collide with collectables, and that collectables collide with players?
In the example above, I checked (Player1, Key); Player1's Mask is 110, and Key's Team is 010. 110 & 010 = nonzero.
What if we were checking (Key, Player1)? Maybe in some other situation, Actor 1 was a key, and Actor 2 was a Player1. In this new case, Key's Mask is 001, and Player1's Team is 001. 001 & 001 = nonzero, so the same collision would happen, which is what we want.
If we go back to the enemies, let's say I want them to check each other for collisions, so they can turn around if they bump into each other. I said that I needed to change the masks for the enemies from 001 to 101 to do this.
With this new definition, let's check two random Enemy actors, (EnemyA, EnemyC). EnemyA has a Mask of 101, EnemyC is on Team 100. 101 & 100 = nonzero. So now, everyone on the enemy team will check for collisions with other actors on the enemy team.
This is the method I came up with, and so far, it's worked pretty nicely, and I am at sound mind knowing my code isn't doing stuff it doesn't need to be doing.
So first and foremost, I'm doing bounding-box collision detection between all of my actors, and I'm iterating through all possible combinations of actors all at once.
If I have actors A, B, C, and D, then I would check AB, AC, AD, BC, BD, CD. It's worthless to check things like AA, BB, etc, and it's redundant to check BA, DB, etc.
Let's say that in my game, there's a player actor, several collectable/powerup actors, and a few enemy actors. Let's also say that enemies don't care about powerups, and enemies don't care about each other (they don't bump into each other).
So maybe in one level, I'll have the player, 10 keys, and 3 enemies. For the player actor, the logical thing would be to check its bounding box with the bounding boxes of each of those 10 keys, and those 3 enemies to see if it's colliding with any of them. No problem!
However, why would I need to check each individual key for collisions against the other keys, and against the enemies, if I've established that they don't do anything when they collide? I'd be performing coordinate transformation calculations for a lot of actors that it doesn't even matter for.
To solve this problem, my system is to assign each type of actor to a team, and have each actor specifiy which teams they collide with. Let's say I have a Player 1 actor, a Key actor, a Health actor, and several different types of enemies.
Each actor has two bytes, which are bitmasks, which determine the team(s) they belong to (the team byte), and which team(s) they collide with (the mask byte). I'll put Player 1 on team 00000001, Key and Health can both go onto team 00000010, and all of the different kinds of enemies can go into team 00000100.
Players need to collide with the collectables and the enemies, so I'll want it to look for collisions with both teams 00000010 and 00000100, so I'll give the player actors a mask byte of 00000110.
Collectables also need to collide with players, since players can collide with collectables, but the collectables don't need to collide with each other, nor the enemies, so I'll give the collectables a mask byte of 00000001. It's important to set both teams up to collide with each other (players collide with collectables and collectables collide with players), otherwise you'll have problems depending on which order you check the actors in.
Enemies also need to collide with players, since players can collide with enemies. They don't need to collide with the collectables, and they don't need to collide with each other, so they get a mask byte of 00000001. Later, if I *do* want the enemies to collide with each other (maybe so they turn around when they bump into each other), I can change their mask byte to 00000101. That way, they'll check for collisions with the players, and members of their own team.
So in summary:
Player1 -> Team 001, Mask 110
Key -> Team 010, Mask 001
Health -> Team 010, Mask 001
EnemyA -> Team 100, Mask 001
EnemyB -> Team 100, Mask 001
EnemyC -> Team 100, Mask 001
So now we're in the level, and the collision routine needs to check each actor combination for collisions. Let's say Actor 1 is a Player1, Actors 2-10 are Keys and Health, Actors 11-14 are various EnemyAs, EnemyBs, and EnemyCs.
The routine first checks (1,2). Actor 1 is a Player1 with a mask 110. Actor 2 is some collectable on team 010.
Mask 110 & Team 010 = nonzero, so this is a valid combination of actors, let's compare 1's collision box with 2's, see if they collide, run the appropriate code if necessary, etc.
Let's say we've done that, and now we check (1,3). Same thing happens, Actor 1 is still Player1 with the same mask 110, Actor 3 is another collectable on team 010. 110 & 010 is nonzero, check these actors for a collision. (There's actually an optimization opportunity here, load actor 1's collision box, transform it, etc, and then just keep that stuff in memory while you compare it with all of the other actors, Until it's time to check Actor 2 against everyone, in which case you forget Actor 1's box, transform Actor 2's box, keep it in memory, etc)
So fast forward a bit, now we're checking (2,3). Actor 2 is a collectable with mask 001. Actor 3 is another collectable on team 010.
Mask 001 & Team 010 = zero, which means we don't even need to bother computing anything else, these two types of actors don't care about colliding with each other.
(2,4) now, same thing, collectable vs. collectable, Mask 001 & Team 010 = zero, so skip and go to the next combination.
So keep going and going until everyone's been checked. The end result is that we've saved ourselves from a lot of worthless computations trying to compare certain combinations of actors who don't care about colliding with each other. Again, on modern hardware, who really cares? However, on a system like the NES, every cycle you save is important.
Now, it's time to touch on something. Remember how it was important to say both that players collide with collectables, and that collectables collide with players?
In the example above, I checked (Player1, Key); Player1's Mask is 110, and Key's Team is 010. 110 & 010 = nonzero.
What if we were checking (Key, Player1)? Maybe in some other situation, Actor 1 was a key, and Actor 2 was a Player1. In this new case, Key's Mask is 001, and Player1's Team is 001. 001 & 001 = nonzero, so the same collision would happen, which is what we want.
If we go back to the enemies, let's say I want them to check each other for collisions, so they can turn around if they bump into each other. I said that I needed to change the masks for the enemies from 001 to 101 to do this.
With this new definition, let's check two random Enemy actors, (EnemyA, EnemyC). EnemyA has a Mask of 101, EnemyC is on Team 100. 101 & 100 = nonzero. So now, everyone on the enemy team will check for collisions with other actors on the enemy team.
This is the method I came up with, and so far, it's worked pretty nicely, and I am at sound mind knowing my code isn't doing stuff it doesn't need to be doing.