C++

Forum

 
Collision detection using bit manipulation

Ch1156 (1999)
So while working on a small game I discovered that the usual if statements for collision detection work fine for single directions, but when I had collision in multiple directions what would happen is say for example collision was detected in front of the player, but if there was a collidable to the right of the player, the player would be allowed to move to the right into the collidable. I discovered using bit manipulation works very effectively for detecting multiple directions. Below is not the code for my game but a very succinct example I made specifically for showcasing this. My question is, is there any drawbacks to this or any thing I should be cautious about when using this for collision detection?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
 
#include <iostream>
#include <vector>
#include <string>
#include <memory>

enum class CollisionDirection
{
    IDLE = 0,
    UP = 1 << 0,
    DOWN = 1 << 1,
    LEFT = 1 << 2,
    RIGHT = 1 << 3
};

int CheckCollision(int& playerY, int& playerX, std::vector<std::vector<char>>& map, char collidable);

int main()
{
    const int mapWidth{ 10 };
    const int mapHeight{ 10 };
    const char mapTile{ '.' };

    const char player{ '*' };
    int playerY{ 2 };
    int playerX{ 2 };

    const char rock{ '&' };

    std::vector<std::vector<char>> map{ mapHeight, std::vector<char>(mapWidth, mapTile) };

    bool gameIsRunning{ true };

    int collisionFlags{};

    while (gameIsRunning)
    {
        map[playerY][playerX] = player;
        map[4][4] = rock;
        map[3][4] = rock;
        map[3][3] = rock;
        map[5][3] = rock;
        map[5][4] = rock;

        collisionFlags = CheckCollision(playerY, playerX, map, rock);

        for (const auto& col : map)
        {
            for (char row : col)
            {
                std::cout << row << ' ';
            }
            std::cout << '\n';
        }

        map[playerY][playerX] = mapTile;

        std::cout << "What direction would you like to go?\n\n";

        std::cout << "Debug - collisionFlags: " << collisionFlags << '\n';

        std::cout << "Player Y: " << playerY << " - Player X: " << playerX << "\n\n";

        std::cout << "W) Up\n";
        std::cout << "S) Down\n";
        std::cout << "A) Left\n";
        std::cout << "D) Right\n";

        char choice{ };

        std::cin >> choice;

        switch (choice)
        {
        case 'W':
        case 'w':
            if (!(collisionFlags & static_cast<int>(CollisionDirection::UP)) && playerY > 0)
            {
                --playerY;
            }
            break;

        case 'S':
        case 's':
            if (!(collisionFlags & static_cast<int>(CollisionDirection::DOWN)) && playerY < mapHeight - 1)
            {
                ++playerY;
            }
            break;

        case 'A':
        case 'a':
            if (!(collisionFlags & static_cast<int>(CollisionDirection::LEFT)) && playerX > 0)
            {
                --playerX;
            }
            break;

        case 'D':
        case 'd':
            if (!(collisionFlags & static_cast<int>(CollisionDirection::RIGHT)) && playerX < mapWidth - 1)
            {
                ++playerX;
            }
            break;
        }
    }
}

int CheckCollision(int& playerY, int& playerX, std::vector<std::vector<char>>& map, char collidable)
{
    int collision = static_cast<int>(CollisionDirection::IDLE);

    // Check collision above the player
    if (playerY > 0 && map[playerY - 1][playerX] == collidable)
    {
        collision |= static_cast<int>(CollisionDirection::UP);
    }

    // Check collision below the player
    if (playerY < map.size() - 1 && map[playerY + 1][playerX] == collidable)
    {
        collision |= static_cast<int>(CollisionDirection::DOWN);
    }

    // Check collision to the left of the player
    if (playerX > 0 && map[playerY][playerX - 1] == collidable)
    {
        collision |= static_cast<int>(CollisionDirection::LEFT);
    }

    // Check collision to the right of the player
    if (playerX < map[0].size() - 1 && map[playerY][playerX + 1] == collidable)
    {
        collision |= static_cast<int>(CollisionDirection::RIGHT);
    }

    return collision;
}
firedraco (6243)
Functionally, it'll work fine. It should be equivalent to returning an object with the 4 directions.

I think it might be easier to check the collision once you know the direction they are headed, that way you only have to check the one direction they are walking to.
Ch1156 (1999)
So it's pretty much exactly the same as if I made a struct of directions and tested against that? Is there any benefits to using bit manipulation for collision as opposed to Boolean values? I'm thinking it would be fine for. Game like Pokemon blue where your constrained to a grid, but a game like Zelda link to he past where you can move freely, I don't know if it would be effective for that, and I don't know how complex either solution would have to be for something like a link to the past.

I was thinking of that as well, testing for only the direction the player is moving in or wants to move in, I'll have to look into that more though.
jonnin (11437)
the computer works on a byte at a time. While bools can be compressed to bits (see, vector bool special case) they are not generally treated as such when doing comparisons and logic.

That means that in some cases, you can have better efficiency with a byte or up to 1 register's worth of bits (32 or 64 bits generally) WHEN THE PROBLEM LENDS ITSELF TO THAT.

So, for example, if you used 9 directions but only allocated space for 4 of them, you can be going north and east at the same time and may want to check 2 bits at once. You can't do that with bools or a struct of directions, but you CAN with an enum that is configured bit-wise for such logic.

I don't see any gains to be had from bits HERE, but maybe I am not thinking through your needs completely. If you can find a way to condense 2 or more comparisons into a single bit operation, and if you do ENOUGH of them in a tight loop or something that this microscopic performance gain has real merits, then you may want to proceed with bits.

If you do not have a LOT of them to do or you have no way to get a lift from using bits, then do not. Bit logic where it is not necessary is just confusing to the reader, as they muddle out what you did and try to fathom WHY you did it when its not necessary. Just don't do it in that case.

Note that fall-through switches can also be more efficient than if/then pairings. Here, its OK to use ... switch statements are not convoluted or difficult to follow so you may as well use them (they CAN be more efficient, but worst case, they are not LESS efficient than the alternatives, so use when you can).


If the other objects are stationary or relatively stationary (consider, planets for example can be treated as stationary over time periods like a couple hours, but in reality, they ARE moving) then you don't need to check for them moving into your path or ramming you from behind, ok, then only check what the object of interest is doing, what will it hit with its movements? In that case there are tons of optimizations you can do if the problem is gigantic (millions of objects or something bizarre, CFD or particle physics or whatnot) along the lines of grouping the objects into sectors by position or whatnot and only checking the ones that are actually potential collisions spatially. But its a lot of nonsense extra work if you are checking to see if your car will hit another car on a 2 lane road. Your common sense should tell you what the problem requires unless you are doing something very scientific. Also, if its just for graphical purposes, you can often fudge the collisions to do them faster without any notable loss to visual representation.
Last edited on
dhayden (5798)
Another way is to just determine the new position and then check both X and Y. I put the mapWidth and mapHeight at global scope so inBounds() can see them. I also set the rocks outside the loop. They don't move. Finally, I changed the player's old position to a mapTile when I figured they were moving rather than every time.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
#include <iostream>
#include <vector>
#include <string>
#include <memory>

const int mapWidth{ 10 };
const int mapHeight{ 10 };


// Are x,y in bounds?
bool inBounds(int x, int y)
{
    return x >= 0 && x < mapWidth && y >= 0 && y < mapHeight;
}

int main()
{
    const char mapTile{ '.' };

    const char player{ '*' };
    int playerY{ 2 };
    int playerX{ 2 };

    const char rock{ '&' };

    std::vector<std::vector<char>> map{ mapHeight, std::vector<char>(mapWidth, mapTile) };

    bool gameIsRunning{ true };

    // Set rocks outside of loop. They don't move
    map[4][4] = rock;
    map[3][4] = rock;
    map[3][3] = rock;
    map[5][3] = rock;
    map[5][4] = rock;


    while (gameIsRunning)
    {
        map[playerY][playerX] = player;
        for (const auto& col : map)
        {
            for (char row : col)
            {
                std::cout << row << ' ';
            }
            std::cout << '\n';
        }

        std::cout << "What direction would you like to go?\n\n";
        std::cout << "Player Y: " << playerY << " - Player X: " << playerX << "\n\n";
        std::cout << "W) Up\n";
        std::cout << "S) Down\n";
        std::cout << "A) Left\n";
        std::cout << "D) Right\n";

        char choice{ };

        std::cin >> choice;

	int newX{playerX}, newY{playerY};
        switch (choice)
        {
        case 'W':
        case 'w':
	    --newY;
            break;
        case 'S':
        case 's':
	    ++newY;
            break;
        case 'A':
        case 'a':
	    --newX;
            break;
        case 'D':
        case 'd':
	    ++newX;
            break;
        }
	if (inBounds(newX,newY) && map[newY][newX] == mapTile) {
	    map[playerY][playerX] = mapTile;
	    playerX = newX;
	    playerY = newY;
	}
		
    }
}

Ch1156 (1999)
Ok so after reading through the responses I decided to try the boolean way. Here is my new interpretation using structs and boolean values to do collision detections, is this good?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
 
#include <iostream>
#include <vector>
#include <string>
#include <memory>

struct Direction
{
    struct Var
    {
        private:
            bool value = false;

        public:
            void Reset()
            {
                value = false;
            }

            bool GetState() const
            {
                return value;
            }

            void Set(bool val)
            {
                value = val;
            }
    };

    Var up;
    Var down;
    Var left;
    Var right;
};

void CheckCollision(int playerY, int playerX, const std::vector<std::vector<char>>& map, char collidable, Direction& directions);

int main() 
{
    const int mapWidth = 10;
    const int mapHeight = 10;

    const char mapTile = '.';
    const char player = '*';

    int playerY = 2;
    int playerX = 2;

    const char rock = '@';

    std::vector<std::vector<char>> map(mapHeight, std::vector<char>(mapWidth, mapTile));

    bool gameIsRunning = true;

    Direction direction{};

    map[4][4] = rock;
    map[3][4] = rock;
    map[3][3] = rock;
    map[5][3] = rock;
    map[5][4] = rock;

    while (gameIsRunning) 
    {
        map[playerY][playerX] = player;

        CheckCollision(playerY, playerX, map, rock, direction);

        for (const auto& col : map) 
        {
            for (char row : col) {
                std::cout << row << ' ';
            }
            std::cout << '\n';
        }

        map[playerY][playerX] = mapTile;

        std::cout << "What direction would you like to go?\n\n";
        std::cout << "Player Y: " << playerY << " - Player X: " << playerX << "\n\n";
        std::cout << "W) Up\n";
        std::cout << "S) Down\n";
        std::cout << "A) Left\n";
        std::cout << "D) Right\n";

        char choice;
        std::cin >> choice;

        switch (choice) 
        {
            case 'W':
            case 'w':
                if (!direction.up.GetState() && playerY > 0)
                {
                    --playerY;
                }
                break;
            case 'S':
            case 's':
                if (!direction.down.GetState() && playerY < mapHeight - 1)
                {
                    ++playerY;
                }
                break;
            case 'A':
            case 'a':
                if (!direction.left.GetState() && playerX > 0)
                {
                    --playerX;
                }
                break;
            case 'D':
            case 'd':
                if (!direction.right.GetState() && playerX < mapWidth - 1)
                {
                    ++playerX;
                }
                break;
        }
    }
}

void CheckCollision(int playerY, int playerX, const std::vector<std::vector<char>>& map, char collidable, Direction& directions) 
{
    directions.up.Reset();
    directions.down.Reset();
    directions.left.Reset();
    directions.right.Reset();

    if (playerY > 0 && map[playerY - 1][playerX] == collidable) 
    {
        directions.up.Set(true);
    }

    if (playerY < map.size() - 1 && map[playerY + 1][playerX] == collidable) 
    {
        directions.down.Set(true);
    }

    if (playerX > 0 && map[playerY][playerX - 1] == collidable) 
    {
        directions.left.Set(true);
    }

    if (playerX < map[0].size() - 1 && map[playerY][playerX + 1] == collidable) 
    {
        directions.right.Set(true);
    }
}
jonnin (11437)
what, exactly, does your struct bring that bool does not?
you can already default construct a bool:
bool foo{false};
set it:
foo = true;
get it:
if(foo)
or
z = foo
or whatever access
reset it:
foo = false
and so on. the OOP is OSO (objects for the sake of objects, basically java code) that brings nothing to the table here... is there something you want to (but have not yet, perhaps) do with that object that justifies its existence?
That is not to mention the questionable name of it (Var? variant? Variable? ). George did a lot of work and using his name for the type is an honor to a founding father of computer science and related mathematics.
Last edited on
Ch1156 (1999)
well i simply just like the way it reads haha. I find it easier to read and decipher code when it reads more like natural language, as for the Var name, I just named it that temporarily and forgot to change it cause i didnt have a better name for it. Its not a struct thats ever meant to be seen by the outside so i figured it didnt matter what its name was. but yeah i mean i technically could just use 4 different bools and not use a struct at all. but i like it when data is grouped under a name as well.
seeplus (6589)
George did a lot of work


That's George Boole (1815 - 1864)
https://en.wikipedia.org/wiki/George_Boole
jonnin (11437)
Ah. You can do whatever when its just you and yourself dealing with the code, but no one is going to accept that sort of thing professionally, because most coders are going to find it harder to memorize and follow a bunch of hand crafted tools whose only purpose is the change the language that they are used to reading into something else that is new and different. Every c++ coder knows what a bool is, but none of them know what you are doing there and have to spend time and energy making sense of it, only to discover... its just a bool. Be prepared for people to dislike that very much if you work on any group projects etc.
Ch1156 (1999)
How would you rewrite the code that I have to just use bools? Like can you show me what specifically you envision it to look like?
Last edited on
mbozzi (3932)
Could be as follows (untested):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
 
#include <iostream>
#include <vector>
#include <string>
#include <memory>

struct Direction { bool up, down, left, right; };

Direction CheckCollision(int playerY, int playerX, const std::vector<std::vector<char>>& map, char collidable);

int main() 
{
    const int mapWidth = 10;
    const int mapHeight = 10;

    const char mapTile = '.';
    const char player = '*';

    int playerY = 2;
    int playerX = 2;

    const char rock = '@';

    std::vector<std::vector<char>> map(mapHeight, std::vector<char>(mapWidth, mapTile));

    bool gameIsRunning = true;


    map[4][4] = rock;
    map[3][4] = rock;
    map[3][3] = rock;
    map[5][3] = rock;
    map[5][4] = rock;

    while (gameIsRunning) 
    {
        map[playerY][playerX] = player;

        Direction direction = CheckCollision(playerY, playerX, map, rock);

        for (const auto& col : map) 
        {
            for (char row : col) {
                std::cout << row << ' ';
            }
            std::cout << '\n';
        }

        map[playerY][playerX] = mapTile;

        std::cout << "What direction would you like to go?\n\n";
        std::cout << "Player Y: " << playerY << " - Player X: " << playerX << "\n\n";
        std::cout << "W) Up\n";
        std::cout << "S) Down\n";
        std::cout << "A) Left\n";
        std::cout << "D) Right\n";

        char choice;
        std::cin >> choice;

        switch (choice) 
        {
            case 'W':
            case 'w':
                if (!direction.up && playerY > 0)
                {
                    --playerY;
                }
                break;
            case 'S':
            case 's':
                if (!direction.down && playerY < mapHeight - 1)
                {
                    ++playerY;
                }
                break;
            case 'A':
            case 'a':
                if (!direction.left && playerX > 0)
                {
                    --playerX;
                }
                break;
            case 'D':
            case 'd':
                if (!direction.right && playerX < mapWidth - 1)
                {
                    ++playerX;
                }
                break;
        }
    }
}

Direction CheckCollision(int playerY, int playerX, const std::vector<std::vector<char>>& map, char collidable) 
{
    Direction d; 
    
    if (playerY > 0 && map[playerY - 1][playerX] == collidable) 
    {
        d.up = true;
    }

    if (playerY < map.size() - 1 && map[playerY + 1][playerX] == collidable) 
    {
        d.down = true;
    }

    if (playerX > 0 && map[playerY][playerX - 1] == collidable) 
    {
        d.left = true;
    }

    if (playerX < map[0].size() - 1 && map[playerY][playerX + 1] == collidable) 
    {
        d.right = true;
    }
    
    return d;
}

Last edited on
seeplus (6589)
Using bool and simplified, consider:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
#include <iostream>
#include <vector>

struct Allowed {
	bool up {}, down {}, left {}, right {};
};

constexpr int mapWidth { 10 };
constexpr int mapHeight { 10 };

constexpr char mapTile { '.' };
constexpr char player { '*' };
constexpr char rock { '@' };

Allowed CheckCollision(int playerY, int playerX, const std::vector<std::vector<char>>& map, char collidable);
void display(const std::vector<std::vector<char>>& map);

int main() {
	std::vector<std::vector<char>> map(mapHeight, std::vector<char>(mapWidth, mapTile));
	int playerY { 2 };
	int playerX { 2 };

	map[4][4] = rock;
	map[3][4] = rock;
	map[3][3] = rock;
	map[5][3] = rock;
	map[5][4] = rock;

	for (bool gameIsRunning { true }; gameIsRunning; ) {
		const auto allow { CheckCollision(playerY, playerX, map, rock) };

		map[playerY][playerX] = player;
		display(map);
		map[playerY][playerX] = mapTile;

		std::cout << "What direction would you like to go?\n\n";
		std::cout << "W) Up\n";
		std::cout << "S) Down\n";
		std::cout << "A) Left\n";
		std::cout << "D) Right\n";

		switch (char choice; std::cin >> choice,  choice) {
			case 'W':
			case 'w':
				playerY -= allow.up;
				break;

			case 'S':
			case 's':
				playerY += allow.down;
				break;

			case 'A':
			case 'a':
				playerX -= allow.left;
				break;

			case 'D':
			case 'd':
				playerX += allow.right;
				break;
		}
	}
}

void display(const std::vector<std::vector<char>>& map) {
	for (const auto& col : map) {
		for (char row : col)
			std::cout << row << ' ';

		std::cout << '\n';
	}
}

Allowed CheckCollision(int playerY, int playerX, const std::vector<std::vector<char>>& map, char collidable) {
	Allowed allow;

	allow.up = playerY > 0 && map[playerY - 1][playerX] != collidable;
	allow.down = playerY < map.size() - 1 && map[playerY + 1][playerX] != collidable;
	allow.left = playerX > 0 && map[playerY][playerX - 1] != collidable;
	allow.right = playerX < map[0].size() - 1 && map[playerY][playerX + 1] != collidable;

	return allow;
}

Last edited on
Topic archived. No new replies allowed.