c++ - 使用最少的位数从冲突对列表创建冲突位掩码

为了确定一对对象a和b是否可以相互碰撞，大多数物理引擎(例如引用1，2)使用以下公式:

((a.m1 & b.m2) !=0) && ((a.m2 & b.m1) !=0)

上式中的&是“和” 位掩码操作。

如果我有各种类型的实体，为它们创建位掩码的一种简单方法是定义碰撞对列表。

冲突对列表的示例:-

player可与另一个player碰撞

tree可能与bullet相撞

tree可与另一个tree碰撞

bullet可与另一个bullet碰撞

为了计算m1和m2，我将m1作为1,2,4,8,...分配给每种类型的实体。
最后，我对每对执行“或” 操作(请参见下面的makeItCollide())。

这是代码(coliru demo):-

#include <iostream>
#include <string>
class Mask{
    public: int m1=0;
    public: int m2=0;
};
void makeItCollide(Mask& mask1,Mask& mask2){
    mask1.m2=mask1.m2|mask2.m1;
    mask2.m2=mask2.m2|mask1.m1;
}
int main(){
    Mask player;
    Mask tree  ;
    Mask bullet;
    Mask air   ;
    int run=1;
    player.m1=run;run*=2;   //1
    tree  .m1=run;run*=2;   //2
    bullet.m1=run;run*=2;   //4
    air   .m1=run;run*=2;   //8
    makeItCollide(player,player);
    makeItCollide(tree  ,bullet);
    makeItCollide(tree  ,tree);
    makeItCollide(bullet,bullet);
  //test :
  //(tree.m1 & bullet.m2 != 0) &&  (tree.m2 & bullet.m1 != 0)  --> true
  //(player.m1 & air.m2 != 0) &&  (player.m2 & air.m1 != 0)  --> false
}

有用。
但是，我非常浪费地使用位。 (一种类型为1位)
如果我有64 ++类型，那将是有问题的。

问题:
如何从任何通用冲突对列表计算m1和m2，以实现最小位数？

解决方案不需要完整的代码。
换句话说，只是一个粗略的指导可能会非常有用。

编辑:(根据dempzorz的评论进行澄清)
上述示例中的一种更好的解决方案可以是:

air.m1 = 0，而air.m2 = 0

player.m1 = 1和player.m2 = 1

tree.m1 = 2和tree.m2 = 3

bullet.m1 = 2和bullet.m2 = 3

此解决方案仅将m1使用2位，将m2使用2位。
这也证明了我的算法有多差(4 + 4位)。

最佳答案

您有一个(对称)碰撞矩阵:
让我们在代码中使用std::vector<std::bitset>进行简化，而不是使用位域:

template <std::size_t N>
void Simplify(const std::vector<std::bitset<N>>& m)
{
    int index = 1;
     for (const auto& b : m) {
        std::bitset<4> res;
        for (std::size_t i = 0; i != b.size(); ++i) {
            if (b[b.size() - 1 - i]) {
                res |= m[i];
            }
        }
        if (res == b && b.count() != 1) {
            std::cout << index << "th type can be removed\n";
            return;
        }
        ++index;
    }
    std::cout << "No more simplications\n";
}

让我们用您的样本进行测试:

const std::vector<std::bitset<4>> m4 = {
    std::bitset<4>{"1000"}, // player
    std::bitset<4>{"0110"}, // tree
    std::bitset<4>{"0110"}, // bullet
    std::bitset<4>{"0000"}, // air
};

Simplify(m4); // 2th type can be removed

const std::vector<std::bitset<4>> m3 = {
    std::bitset<4>{"100"}, // player
    std::bitset<4>{"010"}, // tree/bullet
    std::bitset<4>{"000"}, // air
};
Simplify(m3); // 3th type can be removed

const std::vector<std::bitset<4>> m2 = {
    std::bitset<4>{"10"}, // player
    std::bitset<4>{"01"}, // tree/bullet
};
Simplify(m2); // No more simplifications

Demo

关于c++ - 使用最少的位数从冲突对列表创建冲突位掩码，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/49042401/

M1

c++ - 使用最少的位数从冲突对列表创建冲突位掩码