Grid buckets in 2D collision

Game Mechanics
#1

Right now I’m doing collision entirely grid-based, and naturally that presents the occasional problem. Basically, the center of an entity is considered its location in the grid, and only one entity can exist per grid space. This mostly works, but it allows entities to pretty much overlap a lot of the time.

I decided to go with a more conventional radial/bounding-box collision check, but one implementation detail I’m wondering about is buckets.

If I were to just brute force compare every object against every other, that would be mighty slow. What I’d like to do instead is allow more than one object to exist per grid space, and have an object added multiple times (once for each vertex on its bounding box). When performing a collision check, I will therefore only check against objects that have a vertex in the same grid space.

The question here is how can I efficiently create a data structure to store a grid that can have multiple objects in it? I’m very limited on resources, so I don’t just want to make a 3D array or 2D array of lists. I’d some sort of smarter option.

My thoughts were to perhaps have a 2D array of lists (so not too much memory if it’s all null), and adaptively erase or create lists as each bucket is used. To put it in perspective, I probably will have somewhere around a 15x15 array representing the level, and only about 10 entities moving around at the most. So, maintaining 15x15 lists all the time is pretty wasteful. However, I call collision checks pretty frequently (and also test possible collisions that haven’t yet happened), so doing a brute force check or even a cached brute force check doesn’t really make sense.

So, any ideas?

#2

Demonpants, I am currently writing a “tilt the device and move the ball” (oh how original) for Android, and as you know I have very limited processing resources .
My approach was, first, to divide the entire map in a 64x64 grid … why the hell 64x64 ?? well that’s because a long variable holds 64 bits . So My approach is, before each iteration, I calculate which X and Y bucket all entities are . That sums to 2 divisions (on for each coordinate). Then after that I do a bit shift for each coordinate . e.g maskX = 1L<<<shiftX;
with that I have two long variables, each one with just one bit set (the one that represents the coordinate which the entity is currently placed.

Now when I iterate over the instances, I just have to compare if the masks of entities overlap, that is
if (e1.maskX&e2.maskX !=0)
{
// do the heavy calculation .
}

So you’ll only compare things when they’re at the same bucket, and that (for N entities) at cost of N2 divisions, N2 bitshifts and N! bitwise comparation .

That REALLY improved my performance . I get 60 fps with 100 entities (including basic rendering).

There’s another thing I made to further improve performance, but it will only work if you implemented the above method… so if you are intersted I can explain it to you.

I hope I could explain it decently and it can help you.
cheers

#3

That’s a pretty good way of doing it, I would have never thought of using bit shifting to compare. Good idea! But don’t you still need to compare every entity with every other entity if you do this? It’s only a bitwise comparison, but that still seems overly expensive.

#4

Well then comes the other thing :slight_smile:

I separated my entites in two vectors, moveable and fixed.
With the moveables, I can do nothing . Just calculate the mask and compare with each other every iteration .

for the fixed, well I don’t need to compare them with each other, nor I have to calculate the mask each iteration .
So I just have to compare the moveables against the fixed .

Given that, when loading my level, I can sort the fixed entities in the vector using the X position, and then calculate two int vectors : one for the first index in the fixed vector which this bit appears, and another int vector for the last index .

so for each moveable entity you’ll only have to compare from index A to index B of the fixed entities vector, and that almost always results to no comparisions at all :slight_smile:

maybe in code is clearer :



for ( i = firstPositionInVector[movingEntity.bucketLefX] ; i <= lastPositionInVector[movingEntity.bucketRightX]; i++)
{ 
 .....
}

(Okay I oversimplified the bucket calculations, actually you’ll have to set not one bit , but sometimes two . because there’s the entity.x and the (entity.x + entity.width) so maybe the latter will be in the next bucket . That’s why the bucketLefX and bucketRightX) .

Well that’s a bit difficult to explain . I hope you could understand it . The main idea is, if you sort you fixed entities using the X coordinate, you will only need to compare you moveable with the guys that are within his range .

#5

I’ve never tried it myself, but it sounds like you want a quadtree (http://en.wikipedia.org/wiki/Quadtree)

I needed something similar for my line of sight code and just did a 2D list of lists which worked fine, but a quadtree would have been cooler

#6

Yeah, I was thinking about a quad tree, although I thought it was probably a bit too memory-intensive also. It’s definitely worth considering, at least.

Comparing what I think my options are, though, I think I’m going to try just a 2D array of lists first and see how that works. It shouldn’t be too memory intensive, and it will be reasonably fast. A quad tree would be faster but would be a bit more work to implement and would also take up more memory. teletubo’s bit-shifting method would take up the least amount of memory, but would probably be too slow for the number of look-ahead checks I am doing.

#7

Hello

I have a few question :

  1. Does your object have a specific form? Circle, rectangle or random shape?
  2. Does your object have a specific size? Are they all about the same size or some are very small and other very big?

If you answer no to the second question (meaning you have object of random size) you might have a problem – see 3.)

  1. Are your cell size bigger than your object? If not, object could be in every cell size. Then you would just still brute force.

If you answer, yes to 2 and 3 then your idea is very good because an object could only be in 4 cell max. If the answer was no, I would guess that brute force is best.

#8

Am I missing something here? 45 checks doesn’t sound at all bad.

#9

Yes to 2 and 3. I was thinking exactly that - at most we’re looking at 4 bucket searches, which isn’t bad at all.

@pjt33 - Yeah, 45 comparisons is not bad at all, the only problem being that I perform these comparisons very frequently each timestep, so it will end up being say 150 comparisons per entity, on average, so usually around 1,500 per timestep. That’s too many with my limited resources. But you’re right that the situation really could be much much worse in terms of that.

#10

One thing which might help is to just keep them sorted in one axis. It sounds like you’re updating fast enough that you won’t often have to resort, and with a bit of clever coding you could get O(n + number of potential overlaps) - still brute force in the worst case, but I think any algorithm would be (worst case being that everything overlaps!)

#11

Well what I ended up going with and seems to be cheap enough is a 2D array of lists, except for grid spaces that are inaccessible (usually more than half of them), which are null. So I have tons of null pointers hanging around, but it seems to be okay. Another thought I had would be to perhaps use a HashMap to store all the entries, and then use a string like (x + “,” + y) as the key. That doesn’t have a bunch of null pointers hanging around, but constructing strings every time might be a stupid move. Any thoughts on this?

To put things in perspective, level 1 is 15x15 big (225 tiles), and only about 86 tiles can ever be accessed.

#12

I did this once - not quite the same situation, but similar. Rendering a globe, fairly high-detail data, dynamic detail adjustment, so I used keys (level+","+row+","+col) for an in-memory cache. Profiling showed the char[]s thus constructed to be a big waste of memory. If you’re going to map stuff like that, use Integer for your key rather than String. (Or Byte if you prefer - it would be big enough, just).

On the other hand, but the time you take into account 85 Byte objects, each of 17+ bytes, you’re probably better off wasting 140 pointers instead.

#13

Yeah, you’re right, might as well use x * height + y as a byte key. But having all these dangling pointers seems acceptable enough so I’m just sticking with it for now.

#14

Don’t forget that underlying a hashtable is nothing more than a sparsely populated array. Even though it might feel nicer, the “hanging pointers” would all still be there. Also, if you start indexing by x+15y in a hashtable, the only difference from accessing a 225 length array by the same index is lots of method call overhead and the possibility of key collisions between objects at different locations (depending on the size of your hashtable). There’s no benefit whatsoever.

If it were me, I’d use a grid of linked lists (similar to the int-based linked list pool I posted to shared code). Your memory requirements are then just a 225 length int array, plus 10 ints as “next item” pointers for the linked lists. It also avoids method calls, slow removing items from beginning of lists, and new objects at list creation.

My 2c. :slight_smile:

#15

Now here’s something interesting…

Note I’m doing this in Objective-C which has very little profiling information about how well each data structure works, so I’m wondering if that’s skewing the results. But anyway, I noticed after putting in my new collision algorithms, the game would, at a certain point, start grinding to halt (from 40 FPS to 8 or so). Further exploration revealed that my function spaceIsTaken was consuming up to 0.2 seconds every second. Wow. And this is with like 8 entities performing collisions.

So I looked through the function and couldn’t find anything blaringly slow. In fact, I had even avoided a square root call. My next step was to just try out brute force collision (which I should have started with!) and I found that at most I was using 0.02 seconds every second. Wow.

I’m wondering if I did this somehow stupidly or if there is some hidden thing in Objective-C that is very very very slow (like its equivalent of instanceof, perhaps…).

My Objective-C code, translated into Java:


public boolean spaceIsTaken(Vector2 pos, Entity e)
{
	int gridSize = Globals.getGridSize();
	float radius = (e == null) ? gridSize/2 : e.size.x/2;
	
	//Calculate which grid spaces this Entity lies in.
	int minX = (int) ((pos.x - radius) / gridSize);
	int maxX = (int) ((pos.x + radius) / gridSize);
	int minY = (int) ((pos.y - radius) / gridSize);
	int maxY = (int) ((pos.y + radius) / gridSize);
	
	//Now that we know which buckets it exists in, check them for collisions.
	for (int x = (minX < 0 ? 0 : minX); x <= maxX && x < level.midground.arrayWidth; x++)
	{
		for (int y = (minY < 0 ? 0 : minY); y <= maxY && y < level.midground.arrayHeight; y++)
		{
			//collisionList is a subclass of ArrayList that fakes 2D by doing x*height+y for indices.
			Object obj = collisionList.get(x,y);

			if (obj instanceof ArrayList)
			{
				ArrayList bucket = (ArrayList )obj;
				
				for (int i = 0; i < bucket.size(); i++)
				{
					Entity c = bucket.get(i);
					
					if (c != e)
					{
						Vector2 cPos = c.position.getVectorSum(c.size.x/2);
						float x = pos.x - cPos.x;
						float y = pos.y - cPos.y;
						float totalRadius = radius + c.size.x/2;
						
						//If the two circles are within each others' radius, then we have a collision.
						if ((x*x + y*y) <= totalRadius*totalRadius)
						{
							return true;
						}
					}
				}
			}
		}
	}
	return false;
}

At the very very worst case scenario, that function can be called about 40 times per second. Maybe. MAYBE. Perhaps I should profile the average, max, and min times taken each second for the function also.

#16

So, brute force was the best? Lol

#17

Hahaha yeah, it appears so. Sometime in the future I’ll profile the old collision method in more detail in order to see what’s eating up all the processor. I’m suspecting it’s Obj-C’s instanceof equivalent, which would be very good to know because I use it in several locations throughout the code.