# using minimum amount of bits to create collision bitmask from Collision Pair List Code Answer

Hello Developer, Hope you guys are doing great. Today at Tutorial Guruji Official website, we are sharing the answer of using minimum amount of bits to create collision bitmask from Collision Pair List without wasting too much if your time.

The question is published on by Tutorial Guruji team.

To determine whether a pair of object – `a` and `b` – can collide with each other, most physics engine (e.g. reference 1,2) uses the following formula :-

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

The `&` in the above formula is “and” bit mask operation.

If I have various types of entity, an easy way to create bit mask for them is defining Collision Pair List.

An example of Collision Pair List:-

• `player` can collide with another `player`
• `tree` can collide with `bullet`
• `tree` can collide with another `tree`
• `bullet` can collide with another `bullet`

To calculate `m1` and `m2`, I assign `m1` as `1,2,4,8,...` to every type of entity.
Finally, I do the “or” operation for each pair (see `makeItCollide()` below).

Here is the code (coliru demo):-

```#include <iostream>
#include <string>
public: int m1=0;
public: int m2=0;
};
}
int main(){
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
}
```

It works. However, I use bits very wastefully. (1 bit for 1 type)
It would be problematic if I have 64++ types.

Question:
How to calculate `m1` & `m2` from any general Collision Pair List to achieve minimum amount of bits?

A solution doesn’t need to have full code.
In other words, just a rough guide could be very useful.

Edit: (clarify according to dempzorz’s comment)
One of a better solution in the above example can be :-

• `air.m1`=0 , and `air.m2`=0
• `player.m1`=1 , and `player.m2`=1
• `tree.m1`=2 , and `tree.m2`=3
• `bullet.m1`=2 , and `bullet.m2`=3

This solution uses just 2 bits for `m1` and 2 bits for `m2`.
It is also an evidence of how poor my algorithm is (4+4 bits).

You have a (symmetrical) matrix of collision:

Let use `std::vector<std::bitset>` in code for simplification and instead of bitfield:

```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 removedn";
return;
}
++index;
}
std::cout << "No more simplicationsn";
}
```

Let’s test it with your sample:

```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

We are here to answer your question about using minimum amount of bits to create collision bitmask from Collision Pair List - If you find the proper solution, please don't forgot to share this with your team members.