Multiple Enemy Collision Problem

The search term you may want to explore here is “broad-phase collision detection”, which will point you to a set of algorithms that physics engines use for quickly handling large numbers of potential colliding objects.

swiftcoder said:

The search term you may want to explore here is “broad-phase collision detection”, which will point you to a set of algorithms that physics engines use for quickly handling large numbers of potential colliding objects.

Thank you for information i'm searching

@yusufabi Here's an idea:

Use a quadtree (or some other partitioning strategy) to keep track of where things (the player, enemies, obstacles) are. This has the benefit of only having to check for collisions between objects that are close to each other. Have a quadtree node be able to return a list of objects (base objects) that it contains. Then you can do something like this (sloppy pseudo code below) :

For each Node in MyQuadTree

{

std::vector vObjects = Node.GetObjects(); //Get a vector containing all objects in the node

for (int i=0; i< vObjects.size(); i++)

{

for (j=i+1; vObjects.size()-1; j++)

{

if ( Collision(vObjects.at(i), vObjects.(j)) == true)

{

Send a message to vObjects.at(i) that it collided with vObjects.at(j)

Send a message to vObjects.at(j) that it collided with vObjects.at(i)

}

}

}

}

The Collision() routine would be your rect.getGlobalBounds().intersects routine.

Then in the Objects' Update() function, you have them read messages and decide how to respond.

Example:

When a rocket gets a message it hit something, it can explode

When the player's ship gets a message that it hit a rocket, it can subtract 20 from the player's health.

When an enemy gets a message it was hit by a player's rocket, it can subtract 20 health, and then target the player.

I wrote a simple asteroids game using this technique, and it worked out well:

https://www.youtube.com/channel/UCZRzFEjiOyC0cz-ZogE6pqQ/videos​

scott8 said:

@yusufabi Here's an idea:

Use a quadtree (or some other partitioning strategy) to keep track of where things (the player, enemies, obstacles) are. This has the benefit of only having to check for collisions between objects that are close to each other. Have a quadtree node be able to return a list of objects (base objects) that it contains. Then you can do something like this (sloppy pseudo code below) :

For each Node in MyQuadTree

{

std::vector vObjects = Node.GetObjects(); //Get a vector containing all objects in the node

for (int i=0; i< vObjects.size(); i++)

{

for (j=i+1; vObjects.size()-1; j++)

{

if ( Collision(vObjects.at(i), vObjects.(j)) == true)

{

Send a message to vObjects.at(i) that it collided with vObjects.at(j)

Send a message to vObjects.at(j) that it collided with vObjects.at(i)

}

}

}

}

The Collision() routine would be your rect.getGlobalBounds().intersects routine.

Then in the Objects' Update() function, you have them read messages and decide how to respond.

Example:

When a rocket gets a message it hit something, it can explode

When the player's ship gets a message that it hit a rocket, it can subtract 20 from the player's health.

When an enemy gets a message it was hit by a player's rocket, it can subtract 20 health, and then target the player.

I wrote a simple asteroids game using this technique, and it worked out well:

https://www.youtube.com/channel/UCZRzFEjiOyC0cz-ZogE6pqQ/videos​

Thank you for detailed answer and spend your time. İ will try to do but i suppose it looks complicated for me. I ll try or i wont maintain on my project. Because there are no tutorials on the web for beginners. Best regards.

yusufabi said:
İ will try to do but i suppose it looks complicated for me.

My first ‘game’ I created 100 stationary circles on screen and created 10 pong like circles. I set the pong circles in motion and every frame I checked each pong circle with every stationary circle and did a circle to circle collision response for every collision and also did a screen border collision check for each pong circle to keep them on screen.

When you are learning, do things the easiest way possible until that way doesn't work fast enough anymore. Don't worry about broad phase or quadtrees for now. You'll never know what the computer is capable of if you don't push and hit the limit every now and then.

@fleabay i ll keep it in my mind. Thanks

yusufabi said:
Because there are no tutorials on the web for beginners.

Tutorials don't cover everything that is possible, so at some point, you will have to learn how to proceed without someone telling you their solution in full detail. Solutions become more global, often in the form of worked-out ideas how to approach a problem.

For the solution this is better, as it becomes more generally applicable (You can encode an idea in any programming language, rather than only the one that a tutorial happens to use.) For you, it's also a step forward. Programming is about not copy/pasting ready-made solutions from others. (If that was the case, we'd be done by now with programming.) Programming is about inventing solutions for your problems, often by looking at what others have done (reading their ideas), and then cooking something that works good for your specific problem. In other words, this is your first step on a life-long discovery journey. Scary at first, but so much fun to do. Finding answers to problems you thought were impossible, and then someone just shows an idea how to do it. It's awesome!

A quadtree is a good solution, although it may seem strange and complicated at first. Understanding how and why it works takes some effort.

As a first step in that direction, consider what you're doing. Say we have some area with enemies, say 10. How many comparisons are you doing? You test each enemy with all others, so 10 * 9 but that includes testing both (A, B) and (B, A) enemy pairs, so actually you need 10 * 9 / 2 = 45 checks. For 30 enemies, that's 30 * 29 / 2 = 435. For a 1000 enemies, you end up with 1000 * 999 / 2, which is 499500. As you can see the number checks grows very fast.

What you want are the colliding pairs. So everything you check that doesn't collide is a waste of time, right? How many of the checks you're doing give a collision as answer? I don't know your game, but my guess is a handful at most. For 10 enemies you may find 2 collisions. So 43 of the 45 checks you're doing is wasted, about 95%. For more enemies, this 95% waste is going up towards near 99.9%.

So how to improve this? One way to do it is to avoid checking collisions between enemies that are miles apart. If one enemy is at one side of the area and the other is at the other side, no point in ever checking whether they collide eh?

There are lots of ways to do this. A simple one is adding a grid to the area. Conceptually, each enemy is in a cell of the grid. If you make a cell larger than the size of an enemy, then you don't need to compare enemies that are not in neighbouring grid-cells. That should reduce your wasted effort in collision checking!

So collision detection becomes a 2-step process. First assign each enemy to a cell, then compare enemies in a non-empty cell with each other (They are all in the same cell, so likely to collide), and with enemies in directly neighbouring cells. (To understand, imagine an enemy being at the edge of a cell. You assign it to one cell, but since it has a non-zero size, it sticks out into the other cell(s) as well.)

If all is well, this improves the performance, as you have eliminated some of the 95% wasted effort. On the other hand, you added an extra processing step by assigning enemies to cells, which also takes time.

So this is kind of the reasoning process. You find a problem, and think why it happens. Then you invent a way to avoid the problem by changing what you're computing. If you do it right, you reduce the problem (typically it never completely disappear, the best you can hope for is a reduction to make it irrelevant). For complicated problems, you may need to do the above several times.

Solutions like quadtrees are the result of many such improvement cycles. These solutions need time to digest to see why they work, by doing some reasoning like above for yourself. Ask yourself, “what should I do different to make it faster?” Tutorials normally don't even mention down-sides of their solution, you have to learn to see beyond what a tutorial provides.

Lmao, you guys can't tell that this kid is just failing to understand nested loops?

for (int i = 0; i<7; i++)
{
	for (int j = 0; j<7; j++)
	{
		if (enemies[i]->rect.getGlobalBounds().intersects(enemies[j]->rect.getGlobalBounds()))
		{
			// i and j collided
		}
	}
}

Yeah, it's O(n^2), so it'll become quite slow at maybe ~5000 enemies per frame on a modern desktop cpu. That's the point where you would need to employ something like QuadTrees, not on week 1 of learning to program.

for (int i = 0; i<7; i++) { for (int j = 0; j<7; j++)

ugh, then at least optimize to avoid redundant tests:

for (int i = 0; i<7-1; i++)
for (int j = i+1; j<7; j++) {:)}

fleabay said:
Don't worry about broad phase or quadtrees for now. You'll never know what the computer is capable of if you don't push and hit the limit every now and then.

Using brute force algorithms is not pushing computers - it's just wasting power. :D