Game Engine Collison Bitmask… Why 0x01 etc?

问题:

Coming across this situation both in Sprite Kit (iOS Development) and in Cocos2d-x (which I know was pretty much the inspiration for Sprite Kit, hence why they use a lot of the same tools), I finally decided to figure out why this happens:

When using a physic engine, I create a sprite, and add a physicsBody to it. For the most part, I understand how to set the category, collision, and contact bitmasks, and how they work. The problem is the actual bitmask number:

SpriteKit:

static const uint32_t missileCategory     =  0x1 << 0;
sprite.physicsBody.categoryBitMask = missileCategory;

Cocos2D-X:

sprite->getPhysicsBody()->setCategoryBitmask(0x01); // 0001

I'm totally confused as to why I would write 0x01 or 0x1 << 0 in either case. I somewhat get that they're using hex, and it has something to do with 32-bit integers. And as far as I've been able to google, 0x01 is 0001 in binary which is 1 in decimal. And 0x02 is 0010 in binary which is 2 in decimal. Okay, so there are these conversions, but why in the world would I use them for something simple like categories?

As far as my logic goes, if I have lets say a player category, an enemy category, a missile category, and a wall category, that's just 4 categories. Why not use strings for the category? Or even just binary numbers that any non-CS person would understand like 0,1,2, and 3?

And finally, I'm confused why there are 32 different categories available? I thought a 32-bit integer had numbers 0-some billion number (unsigned of course). So why do I not have billions of different possible categories?

Is there some sort of optimization I am not understanding? Or this is just an old convention they use, but is not needed? Or is there something going on that someone with only 2 semesters of college course CS training wouldn't understand?

回答1:

The reason for the bitmasks is that it enables you / the program to easily and very quickly compute wether a collision between two objects occurs or does not occur. Therefore: yes it is some sort of optimization.

Assuming we have the three categories

• missile 0x1 << 0
• player 0x1 << 1
• wall 0x1 << 2

Now we have a Player instance, its category is set to player. Its collision bitmask is set to missile | player | wall (+ instead of | works too) since we want to be able to collide with all three types: other players, the level walls and the bullets / missiles flying around.

Now we have a Missile with category set to missile and collision bitmask set to player | wall: it does not collide with other missiles but hits players and walls.

If we now want to evaluate wether two objects can collide with each other we take the category bitmask of the first one and the collision bitmask of the second want and simply & them:

The setup described above looks like the following in code:

let player : UInt8 = 0b1 << 0  // 00000001 = 1
let missile : UInt8 = 0b1 << 1 // 00000010 = 2
let wall : UInt8 = 0b1 << 2    // 00000100 = 4

let playerCollision = player | missile | wall // 00000111 = 7
let missileCollision = player | wall          // 00000101 = 5

The subsequent reasoning is basically:

if player & missileCollision != 0 {
    print("potential collision between player and missile") // prints
}
if missile & missileCollision != 0 {
    print("potential collision between two missiles") // does not print
}

We are using some bit arithmetics here, each bit represents a category. You could simply enumerate the bitmasks 1,2,3,4,5... but then you could not do any math on them. Because you do not know if a 5 as category bitmask is really a category 5 or it was an object of both categories 1 and 4.

However using only bits we can do just that: the only representation in terms of powers of 2 of a 7 is 4 + 2 + 1: therefore whatever object posses collision bitmask 7 collides with category 4, 2 and 1. And the one with bitmask 5 is exactly and only a combination of category 1 and 4 - there is no other way.

Now since we are not enumerating - each category uses one bit and the regular integer has only 32 (or 64) bits we can only have 32 (or 64) categories.

Take a look at the following and a bit more extensive code which demonstrates how the masks are used in a more general term:

let playerCategory : UInt8 = 0b1 << 0
let missileCategory : UInt8 = 0b1 << 1
let wallCategory : UInt8 = 0b1 << 2

struct EntityStruct {
    var categoryBitmask : UInt8
    var collisionBitmask : UInt8
}

let player = EntityStruct(categoryBitmask: playerCategory, collisionBitmask: playerCategory | missileCategory | wallCategory)
let missileOne = EntityStruct(categoryBitmask: missileCategory, collisionBitmask: playerCategory | wallCategory)
let missileTwo = EntityStruct(categoryBitmask: missileCategory, collisionBitmask: playerCategory | wallCategory)
let wall = EntityStruct(categoryBitmask: wallCategory, collisionBitmask: playerCategory | missileCategory | wallCategory)

func canTwoObjectsCollide(first:EntityStruct, _ second:EntityStruct) -> Bool {
    if first.categoryBitmask & second.collisionBitmask != 0 {
        return true
    }
    return false
}

canTwoObjectsCollide(player, missileOne)     // true
canTwoObjectsCollide(player, wall)           // true
canTwoObjectsCollide(wall, missileOne)       // true
canTwoObjectsCollide(missileTwo, missileOne) // false

The important part here is that the method canTwoObjectsCollide does not care about the type of the objects or how many categories there are. As long as you stick with bitmasks that is all you need to determine wether or not two objects can theoretically collide (ignoring their positions, which is a task for another day).

回答2:

luk2302's answer is great, but just to go a bit further and in other directions...

Why hex notation? (0x1 << 2 etc)

Once you know that bit positions are the important part, it is (as mentioned in comments) just a matter of style/readability. You could just as well do:

let catA = 0b0001
let catB = 0b0010
let catC = 0b0100

But binary literals like that are (as far as Apple tools are concerned) new to Swift and not available in ObjC.

You could also do:

static const uint32_t catA =  1 << 0;
static const uint32_t catB =  1 << 1;
static const uint32_t catC =  1 << 2;

or:

static const uint32_t catA =  1;
static const uint32_t catB =  2;
static const uint32_t catC =  4;

But, for historical/cultural reasons, it's become common convention among programmers to use hexadecimal notation as a way of reminding oneself/other readers of your code that a particular integer literal is significant more for its bit pattern than its absolute value. (Also, for the second C example you have to remember which bit has which place value, whereas with << operator or binary literals you can emphasize the position.)

Why bit patterns? Why not ___?

Using bit patterns / bit masks is a performance optimization. To check for collisions, a physics engine must examine every pair of objects in the world. Because it's pairwise, the performance cost is quadratic: if you have 4 objects, you have 4*4 = 16 possible collisions to check... 5 objects is 5*5 = 25 possible conditions, etc. You can cut that list down with some obvious exclusions (no worries about an object colliding with itself, A collides with B is the same as B collides with A, etc), but the growth is still proportional to a quadratic; that is, for n objects, you have O(n²) possible collisions to check. (And remember, we're counting total objects in the scene, not categories.)

Many interesting physics games have a lot more than 5 total objects in the scene, and run at 30 or 60 frames per second (or at least want to). That means the physics engine has to check all those possible collision pairs in 16 milliseconds. Or preferably, much less than 16 ms, because it still has other physics-y stuff to do before/after finding collisions, and the game engine needs time to render, and you probably want time for your game logic in there, too.

Bit mask comparisons are very fast. Something like the mask comparison:

if (bodyA.categoryBitMask & bodyB.collisionBitMask != 0)

...is one of the quickest things you can ask an ALU to do — like one or two clock cycles fast. (Anyone know where to track down actual cycles per instruction figures?)

By contrast, string comparison is an algorithm in itself, requiring a lot more time. (Not to mention some easy way to have those strings express the combinations of categories that should result in collisions.)

A challenge

Since bit masks are a performance optimization, they might as well be a (private) implementation detail. But most physics engines, including SpriteKit's, leave them as part of the API. It'd be nicer to have a way of saying "these are my categories, these are how they should interact" at a high level, and let someone else handle the details of translating that description into bit masks. Apple's DemoBots sample code project appears to have one idea for simplifying such things (see ColliderType in the source)... feel free to use it design your own.

回答3:

To answer your specific question

"why there are 32 different categories available? I thought a 32-bit integer had numbers 0-some billion number (unsigned of course). So why do I not have billions of different possible categories?"

The answer is that the category is always treated as a 32-digit bit mask of which ONLY ONE bit should be set. So these are the valid values:

00000000000000000000000000000001 = 1 = 1 << 0
00000000000000000000000000000010 = 2 = 1 << 1
00000000000000000000000000000100 = 4 = 1 << 2
00000000000000000000000000001000 = 8 = 1 << 3
00000000000000000000000000010000 = 16 = 1 << 4
00000000000000000000000000100000 = 32 = 1 << 5
00000000000000000000000001000000 = 64 = 1 << 6
00000000000000000000000010000000 = 128 = 1 << 7
00000000000000000000000100000000 = 256 = 1 << 8
00000000000000000000001000000000 = 512 = 1 << 9
00000000000000000000010000000000 = 1024 = 1 << 10
00000000000000000000100000000000 = 2048 = 1 << 11
.
.
.
10000000000000000000000000000000 = 2,147,483,648 = 1 << 31

So there are 32 diffeeent categories available. Your categoryBitMask however can have multiple bits sets so can indeed be any number from 1 to whatever the maximum of UInt32 is. for example, in an arcade game you might have categories such as:

00000000000000000000000000000001 = 1 = 1 << 0   //Human
00000000000000000000000000000010 = 2 = 1 << 1   //Alien
00000000000000000000000000000100 = 4 = 1 << 2   //Soldier
00000000000000000000000000001000 = 8 = 1 << 3   //Officer
00000000000000000000000000010000 = 16 = 1 << 4  //Bullet
00000000000000000000000000100000 = 32 = 1 << 5 //laser
00000000000000000000000001000000 = 64 = 1 << 6 //powershot

so a human civilian might have a categoryBitMask of 1, a human soldier 5 (1 + 4), an alien officer 6, a normal bullet 16, a missile 80 (16 + 64), mega-death ray 96 etc etc.