C++

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

admin
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>
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
}

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).

Answer

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.

Related Posts

C++

Accessing private member from derived class

admin
C++

Calculate total gross pay of 10 employees. (C++ – Array in Struct)

admin
Tutorial Guruji