游戏引擎碰撞位掩码...为什么是0x01等?

11

在Sprite Kit(iOS开发)和Cocos2d-x中都遇到了这种情况(我知道Cocos2d-x基本上是Sprite Kit的灵感来源,因此它们使用了很多相同的工具),最终我决定找出为什么会发生这种情况:

使用物理引擎时,我创建一个精灵,并向其添加physicsBody。 在大多数情况下,我知道如何设置类别、碰撞和接触位掩码以及它们的工作原理。问题在于实际的位掩码数字:

SpriteKit:

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

Cocos2D-X:

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

我完全不明白为什么我要在任何情况下写0x01或0x1 << 0。我有些明白它们正在使用十六进制,与32位整数有关。据我所能通过谷歌搜索得知,0x01在二进制中为0001,相当于十进制的1。而0x02在二进制中为0010,相当于十进制的2。好吧,这些是转换,但为什么我会在简单的类别选择上使用它们呢?

就我的逻辑而言,如果我有玩家类别、敌人类别、导弹类别和墙类别,那只是4个类别。为什么不能为类别使用字符串?或者甚至只使用任何非计算机科学专业人士都能理解的二进制数字,如0、1、2和3?

最后,我不明白为什么有32种不同的类别可用?我以为32位整数具有0到某个十亿数字(当然是无符号的)。那么我为什么没有数十亿个不同的可能类别?

我是否还存在一些优化方面的问题不理解?还是这只是一个旧的惯例,但并不需要使用?还是有一些只接受过2个学期大学计算机科学课程培训的人不理解的事情发生了?


1
你可能想查看苹果关于碰撞位掩码的文档,其中有一个很好的例子。这是他们使用位掩码的部分,向上滚动以获取设置方法的描述。 - Gliderman
使用0x1 << 0风格的表示法基本上归结为使您的代码可读性更强,例如看到0x1 << 0,0x1 << 1更容易理解为零类别,一类别,而不是使用0x2表示一类别,或者如果您正在编写二进制表示法,则使用0b10。 - Knight0fDragon
1
0b10000000000000000000000000000000,2147483648,0x80000000或0x1 << 31?由您决定。 - Epsilon
3个回答

10

位掩码的原因在于它使您/程序能够轻松快速地计算两个对象之间是否发生碰撞。因此:是的,它是某种优化。

假设我们有以下三个类别:

  • 导弹 0x1 << 0
  • 玩家 0x1 << 1
  • 墙壁 0x1 << 2

现在有一个Player实例,其类别设置为player。 它的碰撞位掩码设置为missile | player | wall(也可以使用+而不是|),因为我们希望能够与所有三种类型进行碰撞:其他玩家,关卡墙和正在飞行的子弹/导弹。

现在有一枚类别设置为missile且碰撞位掩码设置为player | wallMissile:它不会与其他导弹发生碰撞,但会击中玩家和墙壁。

现在,如果我们想要评估两个对象是否可以相互碰撞,我们获取第一个对象的类别位掩码和第二个对象的碰撞位掩码,然后简单地将它们进行&运算:

上述设置在代码中的样子如下:

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

后续推理基本上是:

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
}

我们在这里使用一些位运算,每个比特位代表一个类别。 你可以简单地枚举比特掩码1、2、3、4、5……但是那样你就不能对它们进行任何数学运算。因为你不知道一个作为类别比特掩码的5是否真的是一个类别5,还是既包括了类别1又包括了类别4。

然而只使用比特位,我们可以做到这一点:7的唯一表示方式是2的幂次方的和为4+2+1:因此无论什么对象具有碰撞比特掩码7都会与类别4、2和1发生碰撞。而具有比特掩码5的对象恰好且只是类别1和4的组合——没有其他方式。

现在,由于我们不是在枚举,每个类别使用一个比特位,而普通整数只有32(或64)位,所以我们只能有32(或64)个类别。

看一下以下更详细的代码,它演示了如何以更一般的术语使用掩码:

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

这里重要的部分是方法canTwoObjectsCollide并不关心对象的类型或有多少类别。只要你坚持使用位掩码,那么这就是你需要确定两个对象是否可以在理论上发生碰撞的全部内容(忽略它们的位置,这是另一天的任务)。


我无法理解这部分内容:“if missile & missileCollision != 0 {...}”,在我的想法中,missile是00010,而missileCollision是00101,两者都不是0,所以这将会发生...我为什么无法理解这个? - Confused
1
@Confused,这是按位与运算符,按位与的结果将在两个输入都为1的位置上有1,所有其他位都将为0。在您的示例中,00010和00101在任何一个位置上都没有1,因此它们进行AND运算的结果为0。 - luk2302

7

luk2302的答案很好,但是为了更深入地探讨和从其他方向入手...

为什么使用十六进制表示法?(0x1 << 2等)

一旦你知道位 位置 是重要的部分,那么(如评论中所提到的)就只是一种样式/可读性问题。你也可以这样做:

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

但是像这样的二进制字面量在苹果工具中(就Swift而言)是新的,ObjC中不可用。
你也可以这样做:
static const uint32_t catA =  1 << 0;
static const uint32_t catB =  1 << 1;
static const uint32_t catC =  1 << 2;

或者:

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

但是,由于历史和文化原因,程序员之间普遍约定使用十六进制表示法,以提醒自己/其他读者,一个特定的整数字面量更重要的是它的位模式而不是其绝对值。(此外,对于第二个C示例,您必须记住哪个位具有哪个位置值,而使用<<运算符或二进制字面量则可以强调位置。)

为什么要使用位模式?为什么不是___?

使用位模式/位掩码是一种性能优化。为了检查碰撞,物理引擎必须检查世界中每对对象。因为是成对的,性能成本是二次的:如果您有4个对象,则有4*4=16个可能的碰撞要检查... 5个对象是5*5=25个可能的情况等等。您可以通过一些明显的排除方式缩小该列表(不必担心对象与自身发生碰撞,A与B的碰撞与B与A的碰撞相同等等),但增长仍然与二次函数成比例;也就是说,对于n个对象,您有 O(n2) 个可能的碰撞要检查。(还记得,我们在计算场景中的总对象数,而不是类别。)
许多有趣的物理游戏场景中拥有超过5个对象,并以每秒30或60帧的速度运行(或至少希望如此)。这意味着物理引擎必须在16毫秒内检查所有可能的碰撞对。最好是远远少于16毫秒,因为在找到碰撞之前/之后,它仍需要处理其他物理相关的事情,游戏引擎需要时间来渲染,而您可能还想在其中留出一些时间进行游戏逻辑。

比特掩码比较非常快。类似于掩码比较的东西:
if (bodyA.categoryBitMask & bodyB.collisionBitMask != 0)

...是 ALU 可以执行的最快速的操作之一,大约只需要一到两个时钟周期的时间。(有人知道如何获取实际每个指令周期数的数据吗?)

相比之下,字符串比较本身就是一个算法,需要更多的时间。(更不用说要让这些字符串表达应该导致碰撞的类别组合的一些简单方法了。)

一个挑战

由于位掩码是性能优化,它们可能也是(私有)实现细节。但是,包括 SpriteKit 在内的大多数物理引擎将它们作为 API 的一部分。更好的方式是以高层次的方式说出“这些是我的类别,这些是它们应该如何互动”,让其他人处理将该描述转换为位掩码的细节。Apple's DemoBots 示例代码项目似乎有一个简化此类事情的想法(请参见源代码中的 ColliderType)...可以随意使用它来设计自己的方案。


2

回答你的具体问题:

“为什么有32个不同的类别?我以为32位整数有0到几十亿的数字(当然是无符号的)。那么,为什么我没有数十亿种可能的类别?”

答案是类别始终被视为32位二进制掩码,其中只有一个位应该被设置。因此,这些是有效值:

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

因此,共有32个不同的类别可用。但是,您的categoryBitMask可以设置多个位,因此它确实可以是从1到UInt32的最大值之间的任何数字。例如,在街机游戏中,您可能会有以下类别:

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

因此,一个普通人可能具有类别掩码1,一个士兵5(1 + 4),一个外星军官6,一个普通子弹16,一个导弹80(16 + 64),超级死亡射线96等等。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接