# [Tut] 2D Grid collision detection

#### [Tut] 2D Grid collision detection

Aidiakapi #1
26 Aug 2012 - 17:04
2D Grid collision detection

Collision detection is the algorithms that allow you to calculate whether a collision has occurred between two or more entities in a game. Choosing between different kind of algorithms will have a major impact on your game's performance and gameplay, and should therefore be chosen carefully.

In this tutorial I'll be focusing on collision detection inside of a 2D grid.

Finally a new signature.
Aidiakapi #2
27 Aug 2012 - 08:11
1. Steps of collision detection
Collision detection consists out of two main phases:
1. Map search
2. Collision checks

The first phase narrows down the amount of collision checks it has to perform. In this tutorial this'll be done by a 2D grid. We'll be focusing less on the second step, which is the actual checks to see if there's a collision.
There's one general rule to keep in mind: The more expensive your collision checks are (ex. pixel precise collision checks), the more effort you should put in optimizing the map search.
Finally a new signature.
Aidiakapi #3
27 Aug 2012 - 08:11
2. Map search theory
The technique in this tutorial, the 2D grid, is a very simple way to check if an object might possibly collide.

Here's an image of a 2D grid:

This resembles a game board, some solids (gray), and a player (orange). In this case there is absolutely no collision. However, imagine this as a platform game, there's gravity, and it's applied. Imagine that the gravity would be 4 pixels per update.

As a result the player's new position would be:

At this point, the game should check if the new position is valid (which it isn't).

To check for collisions it keeps a map in-memory that 'tracks' which cell(s) objects are in.
These are the steps it then has to take:
1. It has to calculate which cells the object itself occupies.
2. It has to transverse the list of of cells, and retrieve their objects.
3. It has to do the actual collision checking.

The new position of the player makes it collide with cells, which are: (4, 4), (4, 5) and (4, 6).
All that's left is to check for a collision with all the objects inside of those cells, and we know if it's a valid position.
Finally a new signature.
Aidiakapi #4
27 Aug 2012 - 08:11
3. Map search implementation
Now that you know what the process is going to be like, let's look at implementation. It can be divided into these steps:
1. Data structure
2. Filling the map
3. Keeping the map up-to-date

Note: Throughout the entire tutorial I'll be assuming a 32x32 grid. However in your case this could be anything (it doesn't even have to be a square, 48x16 would be fine too).

1. Data structure
The way I'm going to store the data is in a 2D array of linked lists. I'm quite sure you all know what a 2D array is, but let me briefly explain a linked list.

A linked list is a highly effective data structure that has almost no overhead, always adds items at O(1), and is quick and easy to transverse. This does come with a downside, which is that indexing is O(n).

It works by making every entry in the list 'link' to the next entry in the list. This is what an entry of a linked list would look like:
Code:
``````// C#:
class Entry<T>
{
public T Value;
public Entry<T> Next;
}

// C++:
template <typename T>
struct entry {
T value;
struct entry *next;
};``````

So every entry links itself to the next entry. I hope you get the basic idea behind a linked list. For more details about a linked list see Wikipedia.

This is the signature of the variables I'll be using in the tutorial in C#:
Code:
``````private readonly Rectangle[] _solids;
Note: You could use a rectangular array for this, but I prefer jagged arrays due to .Net's performance optimization for them.

2. Filling the map
Before filling the map, let's take the solids from our example and fill the solids array with them:
Code:
``````_solids = new[]
{
new Rectangle(192, 128, 32, 32),
new Rectangle(192, 160, 32, 32),
new Rectangle(32, 192, 32, 32),
new Rectangle(64, 192, 32, 32),
new Rectangle(96, 192, 32, 32),
new Rectangle(128, 192, 32, 32),
new Rectangle(160, 192, 32, 32),
new Rectangle(192, 192, 32, 32)
};``````

Now let's look at the code to initialize the map's data structure:
Code:
``````const int MAP_WIDTH = 16, MAP_HEIGHT = 16;

// Initialize the 2D array
_collisionMap = new Entry<Rectangle>[MAP_WIDTH][];
for (int x = 0; x < MAP_WIDTH; x++)
_collisionMap[x] = new Entry<Rectangle>[MAP_HEIGHT];``````

Now that we've got it all set-up, it's time to look at how you can fill the map, based on the solids.

In order to do this, we'll have to calculate which cells are overlapped by the object, this can easily be done by calculating the top-left and bottom-right cell position:

The calculation behind this is all very easy:
Code:
``````Rectangle rect;
int topLeftX = rect.X / 32,
topLeftY = rect.Y / 32,
bottomRightX = (rect.X + rect.Width - 1) / 32,
bottomRightY = (rect.Y + rect.Height - 1) / 32;``````

This code is pretty self-explanatory but I think you require some justification on the - 1.
If a rectangle is 32x32, with position (0, 0). Then obviously the space it consumes goes from 0 to 31 pixels on both axes (not those things you chop wood with ). Nevertheless the right coord results in 0 + 32 = 32. And that's why you need to do - 1, because the 32nd pixel isn't inside of the rectangle.

So now that you know which cells are overlapped by the object, all you have to do is add it to the linked list, like so:
Code:
``````for (int x = topLeftX; x <= bottomRightX; x++)
for (int y = topLeftY; y <= bottomRightY; y++)
{
}``````

Note: I updated the Entry<T> class a bit to support initialization from the constructor, this is the new version:
Code:
``````private sealed class Entry<T>
{
public T Value { get; set; }
public Entry<T> Next { get; set; }

public Entry(T value, Entry<T> next)
{
Value = value;
Next = next;
}
}``````

3. Keeping the map up-to-date
The final step of our implementation is actually only applicable to moving objects. I'm not going to go in-depth on this, because this is just a basic tutorial.

When an object is moving, it'll sometimes enter or exit cells of the grid. To keep collision detection accurate, the map must be updated.

When for example, an object 32x32 in size would for example be in (1, 1) and would move 16 pixels to the right, it'd be required to add it to (2, 1). If it'd another 16 pixels to the right, it'd have to be removed from (1, 1).

This is how that'd work:
Code:
``````// NOTE: This code is not completely correct. So do not use this as-is. You can do something similar.
int oldTopLeftX = oldRect.X / 32,
oldTopLeftY = oldRect.Y / 32,
oldBottomRightX = (oldRect.X + oldRect.Width - 1) / 32,
oldBottomRightY = (oldRect.Y + oldRect.Height - 1) / 32,
newTopLeftX = newRect.X / 32,
newTopLeftY = newRect.Y / 32,
newBottomRightX = (newRect.X + newRect.Width - 1) / 32,
newBottomRightY = (newRect.Y + newRect.Height - 1) / 32;

// Removing
for (int x = oldTopLeftX; x < newTopLeftX; x++)
{
for (int y = oldTopLeftY; y < newTopLeftY; y++) Remove(x, y, oldRect);
for (int y = oldBottomRightY; y > newBottomRightY; y--) Remove(x, y, oldRect);
}
for (int x = oldBottomRightX; x > newBottomRightX; x--)
{
for (int y = oldTopLeftY; y < newTopLeftY; y++) Remove(x, y, oldRect);
for (int y = oldBottomRightY; y > newBottomRightY; y--) Remove(x, y, oldRect);
}

for (int x = newTopLeftX; x < oldTopLeftX; x++)
{
for (int y = newTopLeftY; y < oldTopLeftY; y++) Add(x, y, newRect);
for (int y = newBottomRightY; y > oldBottomRightY; y--) Add(x, y, newRect);
}
for (int x = newBottomRightX; x > oldBottomRightX; x--)
{
for (int y = newTopLeftY; y < oldTopLeftY; y++) Add(x, y, newRect);
for (int y = newBottomRightY; y > oldBottomRightY; y--) Add(x, y, newRect);
}``````

The problem is that with our current implementation we just store a Rectangle as collision box, without any metadata, so therefore there's no way to securely handle moving hitboxes (without completely regenerating the map).

If you're dealing with a lot of moving objects, and therefore often have to incrementally update the map, it's most likely more effective to use a doubly linked list. It costs a little bit extra memory, but allows you to easily remove an entry, by keeping track of it in the metadata, it'd become an O(1) operation.
Post last edited by : 06 Mar 2013 - 12:55
Finally a new signature.
Aidiakapi #5
27 Aug 2012 - 08:12
4. Collision detection
What we've done so far is all the infrastructure for fast and accurate collision detection, now there's one more important step we need to do; the collision detection itself.

This time I'm giving you the final code beforehand:
Code:
``````bool collision = false;
Entry<Rectangle> current = _collisionMap[ms.X / 32][ms.Y / 32]; // ms.X and ms.Y are the coords of the point
while (current != null)
{
if (current.Value.Contains(ms.X, ms.Y))
{
collision = true;
break;
}
current = current.Next;
}

// Handle the collision here``````

As you can see in the code, the only steps that are required are finding the cell on the map (which is a linked list), traversing it, check for a collision for each entry. If a collision is found, flag it, and there's no need to check the rest of the list for collisions. Then handle the collision.

And that's it!
Finally a new signature.
Aidiakapi #6
27 Aug 2012 - 08:12
5. Summary
To finish off the tutorial I'm going to name some pros and cons about this technique, pros:
• It's fast at narrowing down objects
• Making the map is relatively cheap
• It's memory footprint isn't that high
• Moving objects are cheap to handle (if implemented with a doubly linked list and there's metadata)
• It's completely scalable, because every operation runs in O(1). So even if your map is 102400x102400, it'll still run fast.

Cons:
• Because objects are registered in each cell, without further logic a rectangular collision check could cause multiple collision checks with the same object.
• If for example in a 32x32 grid, an object is 34x34 pixels, it could be registered in 9 cells, which causes it to perform collision checking more often.

This is as much as I can think of right now.
Post last edited by : 27 Aug 2012 - 08:17
Finally a new signature.
Aidiakapi #7
27 Aug 2012 - 08:12
6. Playing around
To put the engine to the test, I've first started by simplifying our terrain into two objects:
Code:
``````_solids = new[]
{
new Rectangle(192, 128, 32, 64),
new Rectangle(32, 192, 192, 32)
};``````

This results in:

(The colors are something I added to visualize different objects.)

To do some testing, I used this terrain:
Code:
``````_solids = new[]
{
new Rectangle(192, 128, 32, 64),
new Rectangle(32, 192, 192, 32),
new Rectangle(72, 200, 16, 16),
new Rectangle(130, 136, 24, 112),
new Rectangle(120, 140, 64, 32),
new Rectangle(100, 144, 128, 1),
new Rectangle(100, 144, 1, 128),
new Rectangle(48, 48, 16, 16),
new Rectangle(72, 40, 16, 8)
};``````

Result:
Finally a new signature.
Aidiakapi #8
27 Aug 2012 - 08:12
(P.S. This was written in XNA 4.0, so you need to install the required software for that.)

Please post what you think below, and the same goes for bugs/suggestions/anything else . Enjoy!

Edit:
Due to writing of this tutorial, I decided to look into collision detection some more, and I found out what kind of a data structure it is I'm describing here. More info on it can be found here.

Edit 2:
I've added an implementation in C++ using SFML for the visual representation. This includes the possibility to move a block. The currently source expect SFML binaries to be installed in D :\SFML. But this should be changed in the project settings to apply to your system. How to do this is explained at: http://www.sfml-dev.org/tutorials/2.0/start-vc.php.

Post last edited by : 06 Nov 2012 - 22:11
Finally a new signature.
Luis #9
14 Sep 2012 - 23:36
This is a great tutorial and will be made a sticky topic once support for it is added. Further, I will most likely move it to a Tutorials forum which I may create later this month.

Thanks again for such a valuable addition and taking the time to write such a great tutorial Aidiakapi!
Nevereal Games Webmaster
Aidiakapi #10
20 Sep 2012 - 21:04
Thanks
Finally a new signature.
Aidiakapi #11
06 Nov 2012 - 22:00
So today I was in the mood to try something new, so I downloaded SFML and made a little mini-project with it. Why I'm posting it here is because the mini-project is a C++ implementation of this.

A little difference between the C++ and the C# implementation is that the C++ version does allow you to remove entries, and also to change them (which is the preferred way to go for moving objects).

As usual I ran a couple of benchmarks and these are the results on my CPU (AMD Phenom(tm) II X4 965 Processor 3.40GHz):
• CollisionMap -> Change (the function to move a region) can be called 64 million times per second.
• CollisionMap -> CheckCollision (the actual check) can be called 236 million times per second without a collision. With a collision this is still 216 million times per second. If the check position is outside of the map, the check can occur 858 million times per second.

The application was compiled with VS2010 and the performance benchmarks were also run using that. The results are conclusive, you don't have to worry about the collision detection freezing up your game.

It's using SFML for it's debug rending and to wrap around it, download of the source and binaries:

The project properties currently match my setup of SFML (installed the binaries in D :\SFML). However you should modify those to match your system. See http://www.sfml-dev.org/tutorials/2.0/start-vc.php for more info on that.
Finally a new signature.
henke96 #12
04 Mar 2013 - 21:34
Nice tutorial!

I ended up doing it a bit differently but this tutorial and the sfml example sure helped
Post last edited by henke96: 04 Mar 2013 - 21:35
Aidiakapi #13
05 Mar 2013 - 16:01
henke96 wrote:
Nice tutorial!

I ended up doing it a bit differently but this tutorial and the sfml example sure helped

Thanks , if you wanna share, how'd you do it ?
Finally a new signature.
henke96 #14
05 Mar 2013 - 21:52
Aidiakapi wrote:
henke96 wrote:
Nice tutorial!

I ended up doing it a bit differently but this tutorial and the sfml example sure helped

Thanks , if you wanna share, how'd you do it ?

Well, it's really similar..

The linked list stuff didn't really make sense to me, so instead of GridNode i just used a vector.
Maybe i should try it though, is it worth it?
Right now i'm using .push_back() to add items and the .erase(std::remove(blah, blah, thingtoremove)) to remove stuff. Not sure how fast those are.

That's the only real difference i guess :p

Anyway, i'm not really trusting your CollisionMap::Change() method in the example. Before even seeing it i tried the same thing myself and failed But i think yours has problems too.

Firstly, you seem to be adding to new cells differently depending on if it's a vertical or horisontal change.(The minX, maxX stuff).
Also, if an object was to (for some reason, maybe lag ) "teleport" to a cell diagonally(up, right) things would break.
Unless i derped: it would be added once to cell at oldX, newY(without ever touching it) and 2 times to cell at newX, newY..

I use delta time so it's not impossible with a lagspike or something
I'l just stick with the "Quick and dirty" way for now

Post last edited by henke96: 05 Mar 2013 - 21:54
Aidiakapi #15
06 Mar 2013 - 13:31

The reason a linked list is better in this example is due to the properties of the data structure. To the collision map the only operations you'll be doing are linear iteration, search and random point removal. Never random access (which is the one thing arrays/vectors are great at ).

Comparing the complexities of dynamic array (vector), hash table and linked lists:
Code:
``````+---------------+---------------+--------+-----------+-----------+---------+
| Type          | Random access | Search | Iteration | Addition  | Removal |
+---------------+---------------+--------+-----------+-----------+---------+
| Dynamic array | O(1)          | O(N)   | O(1)      | O(N)/O(1) | O(N)    |
| Hash table    | O(1)          | O(1)   | O(1)      | O(N)/O(1) | O(1)    |
| Linked list   | O(N)          | O(N)   | O(1)      | O(1)      | O(1)    |
+---------------+---------------+--------+-----------+-----------+---------+``````

As you can see dynamic arrays really suck at modification. Which is what linked lists are great at.
I included a hash table because it has O(1) at searching, which is a pretty sweet property. However, the overhead of a hash table is so big that unless it contains a lot of elements in one cell, it's always slower. Not to mention that insertion in a hash table is an expensive operation, and even hashing itself can be expensive.

The addition in dynamic arrays and hash tables can be O(1) but for dynamic arrays middle point insertions will always be O(N) and for both of them insertion will be O(N) when they have to expand their capacity.

That covers time complexity, which mostly relates to performance. Secondly and probably most important in this case is memory usage. An empty collision map using linked lists will consume x * y * sizeof(void*). However with a vector it'll at least be x * y * (sizeof(void*) + 4), which means double the memory usage in 32-bits systems. Because we're talking about bytes here, this most likely won't change a thing, however, there's a problem of garbage memory involved with vectors.
Imagine that you have a cell, and you place 1000 rectangles in that cell, and then you remove them all. The vector in that cell will still contain the capacity for storing those 1000 rectangles. It will not shrink. This is unused memory and even though still accessible, will most likely never be used again.

Okay, your next point about my Change method. First of all, it makes me kinda happy that somebody noticed that flaw in the tutorial (I was aware of the flaw, just forgot to say that in the post, I added a comment now). However, that flaw doesn't exist in the C++ code.

As you can see in the example in the post, it uses 2 for loops for removal and 2 for addition. The C++ uses 4 for removal and 4 for addition.
This image illustrates how it works with objects moving when 'teleporting':

And this image illustrates how it works with objects moving when they overlap:

It's safe to use the C++'s Change method.

Please don't mind my rough sketches .
Finally a new signature.
henke96 #16
06 Mar 2013 - 14:28
I don't really understand what the sketches mean at all xD

Anyway.. :p I tested the teleport case again and this time everything did what it should.. Magic
I think the minX and maxX stuff confused me last time, i thought maxX was larger than minX..
So, yea. You are right Just me derpin.

I think i might just steal it, but first i'm going to try to understand exactly how it works

Also wouldn't it be smart to do:
if(oleft < nleft) {

} else if(oright > nright) {

} etc.? I think that should save it some if statements in some cases.. but i guess it would break if the method is called after it's collisionbox size is changed..

Finally, i think the linked list stuff sounds good so i'm going to try it. Would you suggest using a doubly linked list which you metioned is faster, a "normal" one?
Post last edited by henke96: 06 Mar 2013 - 14:29
Aidiakapi #17
06 Mar 2013 - 15:03
henke96 wrote:
if(oleft < nleft) {

} else if(oright > nright) {

}

Well if the box used to be 5x5 (in grid size) it's middle point won't change and it's changed to 3x3 then oldLeft < newLeft AND oldRight > newRight.

The current if statements make sure it's only running when it absolutely has to. There's no way to impose stricter conditions that don't result in a bug. I could make a special edge case for if the size stays identical, but the performance gain for that would be almost nil, and I even think the extra condition and code will only be bloat.

Besides, considering you'd have to call it 64 million times per second to consume 100% cpu on a modern PC, I don't think performance is much of an issue here .

This implementation is mainly a benefit when you have rectangle on rectangle checks. Which are generally already a cheap operation, but with the map you just allow it to be scalable to indefinite lengths.

This is a pretty decent implementation (I won't say the best, since I bet you could make the memory allocations better with malloc and some more low level techniques, but not really necessary here, I tried to keep it simple).
Finally a new signature.
henke96 #18
06 Mar 2013 - 18:53
Okay, i spent some time thinking about it, and rewrote my old try at the Change method things.

It works just like yours i'm sure.

I made some silly optimization saving a few if statements..
Though, it made the code big and ugly but i don't really mind that :p
Some variable-names are a bit misleading in the Y part, because instead of having minX and maxX i just changed the value of the oldleft, oldright etc

Anyway, here it is:
Code:
``````unsigned char firstCellX = static_cast<unsigned char>(collisionBoxPosX / gameState->collisionGrid.cellSize);
unsigned char firstCellY = static_cast<unsigned char>(collisionBoxPosY / gameState->collisionGrid.cellSize);
unsigned char lastCellX = static_cast<unsigned char>((collisionBoxPosX + collisionBox->width) / gameState->collisionGrid.cellSize);
unsigned char lastCellY = static_cast<unsigned char>((collisionBoxPosY + collisionBox->height) / gameState->collisionGrid.cellSize);

bool somethingChanged = false;

//X axis
if(firstCellX < prevFirstCellX) { //Expand left
unsigned char x = firstCellX;
unsigned char y;

for(y = firstCellY; y <= lastCellY; ++y) {
}
for(++x; x < prevFirstCellX; ++x) {
for(y = firstCellY; y <= lastCellY; ++y) {
}
}
somethingChanged = true;
}
if(lastCellX > prevLastCellX) { //Expand right
unsigned char x = lastCellX;
unsigned char y;

for(y = firstCellY; y <= lastCellY; ++y) {
}
for(--x; x > prevLastCellX; --x) {
for(y = firstCellY; y <= lastCellY; ++y) {
}
}
somethingChanged = true;
}
if(prevFirstCellX < firstCellX) { //Trim left
unsigned char y;

for(y = prevFirstCellY; y <= prevLastCellY; ++y) {
gameState->collisionGrid.removeFromCell(this, prevFirstCellX, y);
}
for(++prevFirstCellX; prevFirstCellX < firstCellX; ++prevFirstCellX) {
for(y = prevFirstCellY; y <= prevLastCellY; ++y) {
gameState->collisionGrid.removeFromCell(this, prevFirstCellX, y);
}
}
prevFirstCellX = firstCellX;
somethingChanged = true;
}
if(prevLastCellX > lastCellX) { //Trim right
unsigned char y;

for(y = prevFirstCellY; y <= prevLastCellY; ++y) {
gameState->collisionGrid.removeFromCell(this, prevLastCellX, y);
}
for(--prevLastCellX; prevLastCellX > lastCellX; --prevLastCellX) {
for(y = prevFirstCellY; y <= prevLastCellY; ++y) {
gameState->collisionGrid.removeFromCell(this, prevLastCellX, y);
}
}
prevLastCellX = lastCellX;
somethingChanged = true;
}
//Y axis
if(firstCellY < prevFirstCellY) { //Expand top
unsigned char y = firstCellY;
unsigned char x;

for(x = prevFirstCellX; x <= prevLastCellX; ++x) {
}
for(++y; y < prevFirstCellY; ++y) {
for(x = prevFirstCellX; x <= prevLastCellX; ++x) {
}
}
somethingChanged = true;
}
if(lastCellY > prevLastCellY) { //Expand bottom
unsigned char y = lastCellY;
unsigned char x;

for(x = prevFirstCellX; x <= prevLastCellX; ++x) {
}
for(--y; y > prevLastCellX; --y) {
for(x = prevFirstCellX; x <= prevLastCellX; ++x) {
}
}
somethingChanged = true;
}
if(prevFirstCellY < firstCellY) { //Trim top
unsigned char x;

for(x = prevFirstCellX; x <= prevLastCellX; ++x) {
gameState->collisionGrid.removeFromCell(this, x, prevFirstCellY);
}
for(++prevFirstCellY; prevFirstCellY < firstCellY; ++prevFirstCellY) {
for(x = prevFirstCellX; x <= prevLastCellX; ++x) {
gameState->collisionGrid.removeFromCell(this, x, prevFirstCellY);
}
}
somethingChanged = true;
}
if(prevLastCellY > lastCellY) { //Trim bottom
unsigned char x;

for(x = prevFirstCellX; x <= prevLastCellX; ++x) {
gameState->collisionGrid.removeFromCell(this, x, prevLastCellY);
}
for(--prevLastCellY; prevLastCellY > lastCellY; --prevLastCellY) {
for(x = prevFirstCellX; x <= prevLastCellX; ++x) {
gameState->collisionGrid.removeFromCell(this, x, prevLastCellY);
}
}
somethingChanged = true;
}

if(somethingChanged) {
prevFirstCellX = firstCellX;
prevFirstCellY = firstCellY;
prevLastCellX = lastCellX;
prevLastCellY = lastCellY;
}``````

I haven't tested it yet, and might have made a mistake. But i think i should be a tiny bit faster then yours
Edit: ups, got problems, il fix lator :p
Post last edited by henke96: 06 Mar 2013 - 22:35
Aidiakapi #19
07 Mar 2013 - 16:57
Well, since it's not a compatible structure I cannot benchmark it, and without a benchmark you can never be sure.
Finally a new signature.
0 members and 1 guest are browsing this topic