Anyone know how to check LARGE numbers of collisions quickly?

The Partridge Family were neither partridges nor a family. Discuss.
Post Reply
John73 John
Posts: 14
Joined: August 6th, 2020, 7:16 pm

Anyone know how to check LARGE numbers of collisions quickly?

Post by John73 John » August 6th, 2020, 7:50 pm

Hello everyone, new member here.

I'm currently partway through the advanced 3D tutorial, but I've been playing around with making some simple games.

In one of my projects, the player runs around on a large map with a bunch of trees and stuff on it.

This is how I'm currently checking for tree collision:

Code: Select all

vec2 intended_position = player.GetPos() + movement_from_keyboard;

bool can_move = true;
for (int i = 0; i < all_the_trees.size(); i++)
{
	if (all_the_trees[i].CollidesWith(intended_position))
	{
		can_move = false;
		// if one collision is found, no point in continuing to check the rest
		break;
	}
}

if (can_move)
{
	player.MoveTo(intended_position);
}
This all works absolutely fine, but it has a significant performance drop if the map is large (say 10,000+ trees).

I've seen lots of games like Factorio where there's a huge map with potentially millions of trees and other collision-causing objects, so I know it's possible... how do they do it? My friend (who knows nothing about programming) suggested "well only check the trees that are near you." as if that were obvious. Thing is, I don't know how I'd filter out "just the ones near me" without looping through all of them to do a distance comparison.

So is there some obvious trick that I'm missing?

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Anyone know how to check LARGE numbers of collisions quickly?

Post by albinopapa » August 7th, 2020, 5:45 am

So is there some obvious trick that I'm missing?
Yes there are a few tricks, but I guess not so obvious unless you know about them.

Something you might look up is spatial partitioning. If the player can only move in X/Z or X/Y axes, then you can use a data structure called a quadtree. If you need to check X/Y and Z axes, then you could use an octree.

If the objects are pretty evenly space, you can even split the scene into a 2D or 3D grid of squares or cubes. Place the objects in each "cell" based on position. This way you only check the "cell" of objects that surround the player or other moving objects.

There is also Kd-trees. I think think this one works best for non-moving objects if I recall correctly.

BVH ( bounding Volume Hierarchy )

Sweep and Prune

I'm sure there are other methods, but can't remember them off the top of my head.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

John73 John
Posts: 14
Joined: August 6th, 2020, 7:16 pm

Re: Anyone know how to check LARGE numbers of collisions quickly?

Post by John73 John » August 7th, 2020, 6:04 am

Thanks, I'll go Google those words to see what they mean ;)

What I was messing around with today was a scheme like this:

1. Maintain a std::vector<Tree&> of the trees near the player
2. Cycle through the trees on a rotating schedule:
Frame 1: trees 0, 10, 20, 30, etc.
Frame 2: trees 1, 11, 21, 31, etc.
...and so on. Test them for distance to the player, and push them to the "near" vector. Also pop any trees from the vector that are no longer close to the player.
3. Check collisions every frame with the trees in the near vector.

It improved performance somewhat, but it's still noticeably slowing down -- I might do better by changing the number of trees scanned per frame, but I'm tired of it right now.
albinopapa wrote:
August 7th, 2020, 5:45 am
If the objects are pretty evenly space, you can even split the scene into a 2D or 3D grid of squares or cubes. Place the objects in each "cell" based on position. This way you only check the "cell" of objects that surround the player or other moving objects.
That's interesting. Let me make sure I understand right. I could divide the map into a bunch of squares, let's say each one has 20-50 trees. So instead of one massive vector of trees I have a vector of cells, and each cell is an object with its own small vector of trees? Based on player (x,y) I know which cell I'm on, so I only check the trees in that cell. Maybe also check adjacent cells if I'm close to the border, since a tree right near the border could have its collision box hang over.

I'll give that a try tomorrow and let you know how it works, and I'll also look into the other schemes you mentioned.

Thank you for the help.

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Anyone know how to check LARGE numbers of collisions quickly?

Post by albinopapa » August 7th, 2020, 9:40 am

I could divide the map into a bunch of squares, let's say each one has 20-50 trees.
You wouldn't base the grid on tree count, but instead evenly divide the map into cells. Some cells might be empty while some would have however many objects fit into the cell.

Let's say your map is 10,000x10,000 and each tree takes up 20x20. You might make each cell 100x100 which would hold a maximum of 25 trees in each cell if the cell was completely filled.

Also, the way you have things setup judging by the code you posted, you aren't really concerned with much more than "can I move into these coordinates?" so it's also possible that each cell could be checked for object density ( number of trees in cell ) and if a thresh hold is reached, it's not possible to move into the boundaries of said cell.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

John73 John
Posts: 14
Joined: August 6th, 2020, 7:16 pm

Re: Anyone know how to check LARGE numbers of collisions quickly?

Post by John73 John » August 7th, 2020, 3:55 pm

albinopapa wrote:
August 7th, 2020, 9:40 am
I could divide the map into a bunch of squares, let's say each one has 20-50 trees.
You wouldn't base the grid on tree count, but instead evenly divide the map into cells. Some cells might be empty while some would have however many objects fit into the cell.
That's kind of what I meant. Trees are placed at random (x, y) at load time with a check to keep them from overlapping. This takes some time for large maps since it's a O(n^2) task, but it's not too much of an issue so far.
albinopapa wrote:
August 7th, 2020, 9:40 am
Let's say your map is 10,000x10,000 and each tree takes up 20x20. You might make each cell 100x100 which would hold a maximum of 25 trees in each cell if the cell was completely filled.

Also, the way you have things setup judging by the code you posted, you aren't really concerned with much more than "can I move into these coordinates?" so it's also possible that each cell could be checked for object density ( number of trees in cell ) and if a thresh hold is reached, it's not possible to move into the boundaries of said cell.
I'd like to avoid it being an obvious "grid-based" game -- the random (x, y) of tree placement is in pixels, so trees can be just 1 or 2 pixels apart. Sometimes you'll find trees with just enough of a gap to move between them, but some trees will be just close enough that you can't quite squeeze through.

Post Reply