使用最少的位从碰撞对列表创建碰撞位掩码
using minimum amount of bits to create collision bitmask from Collision Pair List
要确定一对对象 - a
和 b
- 是否可以相互碰撞,大多数物理引擎(例如参考 1,2)使用以下公式:-
((a.m1 & b.m2) !=0) && ((a.m2 & b.m1) !=0)
上式中的&
是"and"位掩码运算
如果我有各种类型的实体,为它们创建位掩码的简单方法是定义碰撞对列表。
碰撞对列表的示例:-
player
可以与另一个 player
发生碰撞
tree
可以与 bullet
相撞
tree
可以与另一个 tree
发生碰撞
bullet
可以和另一个bullet
发生碰撞
为了计算 m1
和 m2
,我将 m1
作为 1,2,4,8,...
分配给每种类型的实体。
最后,我对每对执行 "or" 操作(请参阅下面的 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 种类型 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
要确定一对对象 - a
和 b
- 是否可以相互碰撞,大多数物理引擎(例如参考 1,2)使用以下公式:-
((a.m1 & b.m2) !=0) && ((a.m2 & b.m1) !=0)
上式中的&
是"and"位掩码运算
如果我有各种类型的实体,为它们创建位掩码的简单方法是定义碰撞对列表。
碰撞对列表的示例:-
player
可以与另一个player
发生碰撞
tree
可以与bullet
相撞
tree
可以与另一个tree
发生碰撞
bullet
可以和另一个bullet
发生碰撞
为了计算 m1
和 m2
,我将 m1
作为 1,2,4,8,...
分配给每种类型的实体。
最后,我对每对执行 "or" 操作(请参阅下面的 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 种类型 1 位)
如果我有 64++ 类型,那将是有问题的。
问题:
如何从任何通用 碰撞对列表 计算 m1
和 m2
以实现最小位数?
解决方案不需要有完整的代码。
换句话说,粗略的指南可能非常有用。
编辑:(根据 dempzorz 的评论澄清)
上面示例中的一个更好的解决方案可以是:-
air.m1
=0 和air.m2
=0player.m1
=1 和player.m2
=1tree.m1
=2 和tree.m2
=3bullet.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