Which of these examples is better?

[adabo]

which is better?

It seems that this question arises over and over again in my head. It involves handling the collision of entities.

I can think of two ways for handling it.

Option 1: First function to flag colliding entities. Second function to update their stats accordingly
Option 2: One function to check collision and set stats in same loop.

1.

Code: Select all

void Game::UpdateModel()
{
	HandleCollision( entityA, entityB );
	UpdateEntityStats( entityA, entityB );
}

void Game::HandleCollision( std::vector<Entity> &A, std::vector<Entity> &B )
{
	for( A )
	{
		for( B )
		{
			if entity A collides with B;
			{
				A.is_colliding = true;
				A.collides_with = B
				B.is_colliding = true;
				B.collides_with = A;
			}
		}
	}
}

void Game::UpdateEntityStats( std::vector<Entity> &A, std::vector<Entity> &B )
{
	for( A )
	{
		for( B )
		{
			if A.is_colliding
			{
				if A.collides_with == B
				{
					A.hp -= B.damage;
					B.hp -= A.damage;
				}
			}
		}
	}
}

------------------------------
2.

Code: Select all

void Game::UpdateModel()
{
	HandleCollision( entityA, entityB );
}

void Game::HandleCollision( std::vector<Entity> &A, std::vector<Entity> &B )
{
	for( A )
	{
		for( B )
		{
			if entity A collides with B;
			{
				A.hp -= B.damage;
				B.hp -= A.damage;
			}
		}
	}
}

I guess a third and more complicated option would be to have 3 functions. One that returns a bool if colliding. Second that sets the stats. Third that removes the dead entity from the array.

I think the second option is straight forward and fewer lines of code. However, the second option could be useful if perhaps you're concerned with encapsulation.

I figure you experienced programmers can set me straight in this trivial design desision. Thanks!

[MrGodin]

Well sending two vectors of objects to two different functions means you are iterating through the lists twice which is inefficient. You probably only want to go through the lists only once, if you can, and do all appropriate measures as needed.
maybe something like

Code: Select all

void Game::HandleCollision( std::vector<Entity> &A, std::vector<Entity> &B )
{
   for( A )
   {
      for( B )
      {
          if(A.is colliding with B)
           continue;// you already checked this so go to next in loop
       
         if entity A collides with B;
         {
           // here you might do collision correction (if applicable) 
          // remove from list (if applicable)
           // if other words, do as much as you can here in regards to collision
           A.hp -= B.damage;
            B.hp -= A.damage;
         }
      }
   }
}

Something like that I might do. This isn't the most efficient either but i hope you get the idea

[adabo]

I think efficiency comes first, like you said, MrGodin. I think I'm torn because I want my code to be easy to read and maintain. I want it to flow in a logical order and to be predictable to the reader.

Maybe what I could do inside the loop that checks the collision is to call a different function for the different things that happen during collision eg: UpdateHp(), UpdateScore(), UpdateUpgrade(), RemoveDeadEntities(), etc ...

Well that was helpful, because I think I know what I want to do now lol

[albinopapa]

I would as you suggest, do detection and correction in one loop, and once you've determined which entities are dead, then make one more pass to remove them. So two passes, one for collision handling(detection and correction) and one for removal.

The way you are handling the loops going from the end to the beginning you COULD do it all in one loop, but just remember, each time you erase and element that isn't at the end of the loop, all the ones after that have to be shifted down each time so two phases might be more efficient so that you only have to shift once per vector instead of once per dead entity erase.

Oo, just thought of another way.

• Create two copies of each of the vectors named lasers_a, lasers_b, enemies_a and enemies_b
• Create two vector<Entity>*, p_lasers_read, p_lasers_write, p_enemies_read and p_enemies_write
• Point the read vectors to lasers_a and enemies_a and the write vectors to lasers_b and enemies_b
• When loading the lasers or the enemies onto the vectors, use the read vector pointers.
• While you do collision detection and determine which entities are still alive, you copy those over to the write vectors.
• At the end of the before drawing anything clear the read vectors
• Swap the read and write pointers, so that if read was pointing at the A vectors, they now point at the B vectors and write vectors would be the B and A vectors

Only draw from the read vectors after the swap, the write vectors are only there to copy the entities that are still alive.

With a few modifications to this approach, you could go multi threaded having one vector set being updated on one thread and the other being drawn on another thread at the same time before doing the swap.

[adabo]

You have incredible mental visualization skills. It's a little scary. I started losing track by the 2nd bullet point

All we need to do now is to have you put these ideas of yours out on paper, graph, flowchart whatever. This way all us mortals can comprehend what you're telling us

*Edit: I had this idea of something like having two lists. The problem I'm trying to find a solution to isn't just about three entities colliding. I'm thinking of something like hundreds or more. So I had this crazy idea of making a reference & vector that stores every entity with collision boundaries. Some sort of "amalgum" array.

Why? Because what if each entity has a unique interaction with the others? So if there are 5 things on the screen that can collide, but 1 has a different effect on 2. Also a different effect on 3. Also on 4, and so on.

You could just loop from the beginning and compare:

• 1 -> 2, 3, 4, 5
• 2 -> 3, 4, 5
• 3 -> 4, 5
• 4 -> 5

Havn't fully thought it through, but I might be on to something.

[albinopapa]

Yes, you would definitely want to stagger the checks since 1 would run through the complete list, 2 wouldn't need to check 1 or itself, so staggering the loop indices is better than rechecking.

That does bring up an interesting topic though. When you start getting into searching for collisions, you want to find a very efficient way of weeding out as many checks as possible.

One method is creating a grid and unregister and register objects with each cell in the grid as they leave one and enter another. This means you only have to test if there are any collideable objects in that cell with each other and that's it. One object in the cell, no collision checks. The only downside would be if a lot of objects were in the cell, but depending on how you setup your game logic you could say if a cell has 20 objects already, that cell can't be visited and they must go around.

Not sure which is more efficient, calculating the square distance and a comparison or the twelve comparisons for overlapping rectangles, but you could calculate the square distance of each object and if it isn't within a certain range, then no need to do the overlapping rectangle checks. If it is within range, then you would to the overlapping rectangle checks. For instance, the corner of a square is roughly 1.4x the length of a side, so if a side is 20, the corner distance form center would be about 14. 14^2 = 196, so if the square distance from A and B is < 196, do overlapping triangle test. Just don't do sqrt to get the actual distance and don't use the pow() function as it's pretty slow as well.

There are other ways, but I don't think they are easy to explain as I have only used them for other scenarios.

[chili]

I think you need 2 passes. What if you have multiple objects overlapping each other simultaneously and mutually destroying each other?

[reductor]

Alot physics engines are designed around a few phases
* Calculate new positions
* Collision detection (broad and narrow)
* Collision resolution

I'd suggest doing something similar here, detect your collisions then resolve them (take health or prevent)

Code: Select all

void Game::HandleCollision( const std::vector<Entity> &A, const std::vector<Entity> &B )
{
   std::vector<std::pair<Entity&,Entity&> > collisions;
   for( A )
   {
      for( B )
      {
         if entity A collides with B;
         {
            collisions.push_back( { entity A, entity B } );
         }
      }
   }

   for(A, B : collisions)
   {
        // resolve A/B
   }
}

As a further research you could avoid the iterating of all items by using quad trees (or other spatial mapping data types), but that could be unnecessary depending on the number of items. (Only be concerned with performance if you hit an issue)

[adabo]

This is what I love about this forum. The perfect place to get multiple opinions and points of view on any given subject.

@albinopapa, that is a very clever idea. It's definitely going to be part of a future project.
@chili, perfect example of not jumping to conclusions and having another brain in the collective.
@reductor, Could you elaborate a little more on the std::pair suggestion? I don't understand what it does. Btw, I'm stealing those function names: CollisionDetection & CollisionResolution