Thread: Collision testing and response, for all active objects, in one function

So, I want my Update function in my Physics class to be pretty powerful, perhaps I'm asking too much, but I want it to loop through a box of objects that are currently in play (for instance, a pong ball and two paddles to start). I want it to perform collision checks between all relevant objects, keeping in mind ultimately I plan on having more than just a pong ball and two paddles. It seems overkill for pong, yes this I know, but I'm looking at the future.

Hmmm, I think this is the most I can write before field testing this thing.
I would love if anyone with half an idea of what I'm trying to do could point out any obvious logical errors that I'm missing!


This is the function

Code:

void Physics::Update(std::vector<Renderable_Object*> & Game_Objects)
{		
	for (int i = 0; i++ i < Game_Objects.end())
	{
		if (Game_Objects[i]->isPhysical)
		{
			for (int j = 0; j++; j < Game_Objects.end())
			{
				if (i == j)
				{
					j++; 
				}
				else if (Game_Objects[i]->AABB)
				{
					if (Game_Objects[j]->isPhysical)
					{
						if (Game_Objects[j]->AABB)
						{
							if(collision2d(Game_Objects[i]->getMinimum(), Game_Objects[i]->getMaximum(), 
										Game_Objects[j]->getMinimum(), Game_Objects[j]->getMaximum()))
							{
									//do stuff
							}
							else
							{
								j++;
							}
						}
						else
						{
							if(planeIntersection2d(Game_Objects[j], Game_Objects[i]->getLocation()))
							{
								//do other stuff
							}
							else
							{
								j++;
							}
						}
					}
					else
					{
						j++;
					}
				}
			}
		}
		else
		{
			i++;
		}
	}
}

This is the Renderable_Object class

Code:

class Renderable_Object
{
public:

	Renderable_Object(float minX, float minY, float maxX, float maxY, float posX, float posY, bool visible, bool physical)
	{
		d_min.x = minX;
		d_min.y = minY;
		d_max.x = maxX;
		d_max.y = maxY;
		position.x = posX;
		position.y = posY;
		isVisible = visible;
		isPhysical = physical;
		velocity.x = 0;
		velocity.y = 0;
	}
	Vector2 & getVelocity()
	{
		return velocity;
	}
	void setVelocity(float x, float y)
	{
		velocity.x = x; velocity.y = y;
	}
	Vector2 & getLocation()
	{
		return position;
	}
	Vector2 & getMinimum()
	{
		return d_min;
	}
	Vector2 & getMaximum()
	{
		return d_max;
	}

private:
	Vector2 position;
	Vector2 velocity;
	Vector2 d_min;
	Vector2 d_max;
	bool isPhysical; // does this object use collision at all?
	bool isVisible; // render this object?
	bool AABB; //compatible with AABB collision detection
};

Updated, I think this will suit my needs better, fixed the syntax errors and stupidity levels.

Code:

void Physics::Update(std::vector<Renderable_Object*> & Game_Objects)
{		
	for (int i = 0; i < Game_Objects.size(); i++)
	{
		if (!Game_Objects[i]->isPhysical) continue;
	
		for (int j = i+1; j < Game_Objects.size(); j++)
		{
			if (!Game_Objects[j]->isPhysical) continue;
			
			if(	Game_Objects[i]->AABB && 
				Game_Objects[j]->AABB && 
				collision2d(	Game_Objects[i]->getMinimum(), Game_Objects[i]->getMaximum(), 
								Game_Objects[j]->getMinimum(), Game_Objects[j]->getMaximum()))
			{
				//do stuff
			}

			else if(Game_Objects[i]->Plane && 
					Game_Objects[j]->AABB && 
					planeIntersection2d(Game_Objects[i], Game_Objects[j]->getLocation())
			{
				// do stuff
			}
			else if(Game_Objects[j]->Plane && 
					Game_Objects[i]->AABB && 
					planeIntersection2d(Game_Objects[j], Game_Objects[i]->getLocation())
			{
				//do other stuff
			}
		}
	}
}

Right now I'm using this function in a pong game, how do I make sure I apply the right collision response to the pong ball, and make sure I only apply that specific collision response to the pong ball, or any specific response to any object for that matter?

I have a seemingly complex idea in mind.

Instead of housing the game_objects in a vector, use a map, connected with some kind of other variable, and then I can just update the map, so that some other class, such as logic or whatnot, can determine what to do with the collision event? Or is there some kind of simpler method?

Got it I believe, criticism please!

Code:

void Physics::Update(std::vector<Renderable_Object*> & Game_Objects)
{		
	for (unsigned int i = 0; i < Game_Objects.size(); i++)
	{
		if (!Game_Objects[i]->isPhysical) continue;
	
		for (unsigned int j = i+1; j < Game_Objects.size(); j++)
		{
			if (!Game_Objects[j]->isPhysical) continue;
			
			if(	Game_Objects[i]->AABB && 
				Game_Objects[j]->AABB && 
				collision2d(	Game_Objects[i]->getMinimum(), Game_Objects[i]->getMaximum(), 
								Game_Objects[j]->getMinimum(), Game_Objects[j]->getMaximum()))
			{
				collisionResponse(Game_Objects[i], Game_Objects[j]);
			}

			else if(Game_Objects[i]->Plane && 
					Game_Objects[j]->AABB && 
					planeIntersection2d(Game_Objects[i], Game_Objects[j]->getLocation()))
			{
				collisionResponse(Game_Objects[i], Game_Objects[j]);
			}
			else if(Game_Objects[j]->Plane && 
					Game_Objects[i]->AABB && 
					planeIntersection2d(Game_Objects[j], Game_Objects[i]->getLocation()))
			{
				collisionResponse(Game_Objects[j], Game_Objects[i]);
			}
		}
	}
}

Code:

void Physics::collisionResponse(Renderable_Object * collidedObjectA , Renderable_Object * collidedObjectB)
{
	if (collidedObjectA->defaultCollisionResponse == 1 && collidedObjectB->defaultCollisionResponse == 1)
	{
		if (collidedObjectA->Plane)
		{
			collidedObjectB->getLocation().x = collidedObjectA->getLocation().x;
		}
		if (collidedObjectB->Plane)
		{
			collidedObjectA->getLocation().x = collidedObjectB->getLocation().x;
		}
	}
	if (collidedObjectA->defaultCollisionResponse == 0)
	{
		if (collidedObjectA->getVelocity().x != 0)
		{
			reverse_x_velocity(collidedObjectA->getVelocity());
		}
		if (collidedObjectA->getVelocity().y != 0)
		{
			reverse_y_velocity(collidedObjectA->getVelocity());
		}
	}
	else if (collidedObjectB->defaultCollisionResponse == 0)
	{
		if (collidedObjectB->getVelocity().x != 0)
		{
			reverse_x_velocity(collidedObjectB->getVelocity());
		}
		if (collidedObjectB->getVelocity().y != 0)
		{
			reverse_y_velocity(collidedObjectB->getVelocity());
		}
	}
}

You are using the same "reverse velocity" logic as I am. You realize that will only create a correct reflection if the struck surface lies straight along x or y, right? If the surface is angled, the angle of the reflection must also change.

Here's something I worked out that will work up to 45 degs, and maybe beyond that, I think it will make sense to you:

identify my algorithm, please!

Hey thanks for the linky there! Yeah currently my pong game doesn't support any kind of fancy curved surfaces or anything like that, just perfect squares and such. Right now I'm more focused on determining whether or not what I'm doing is a good way to do what I'm doing.

Originally Posted by Shamino

Hey thanks for the linky there! Yeah currently my pong game doesn't support any kind of fancy curved surfaces or anything like that, just perfect squares and such. Right now I'm more focused on determining whether or not what I'm doing is a good way to do what I'm doing.

The issue is not just curves, it is any plane that doesn't lie straight on x or y. For example, all the boxes on this page do. If a drew a line diagonally across from lower left to upper right, that straight line crosses x and y. You cannot simply reverse the x or the y velocity on that and get a realistic reflection, you have to factor it some how. Or use trigonometry.

As for "determining whether or not what I'm doing is a good way to do what I'm doing" I hope so, that's the system I'm using (just iterating thru all other objects to find collisions). One thing to keep in mind is units per frame; if an object is moving more than 1.0, it could move beyond a collision boundary in the next frame. But I am guessing because maybe ->getMiniumum ->getMaximum deals with that?

If you are testing the collision based on position then it is possible the speed of the ball will be such that the collision parameters can never be satisfied and the ball will appear to pass through the paddle.

In my asteroids clone I'm doing a simple O(n^2) collision test with the following condition: if the distance between the two objects is greater than some maximum the test is not performed.
It performs admirably but it would be better if I used some type of spatial partioning so I would not have to check each object against every other object save for itself.

I've tested it with 2000 asteroids and nearly 40 lasers (usually you cannot get more than 40 lasers on screen at any one time) and it still runs at the refresh of the screen. Of course there are other optimized algorithms under the hood that give me the performance but they do not add to the current discussion.

If I recall the correct way to compute the reflection is to subtract the two positions creating a vector from A to B. Add that vector to the object's velocity vector and normalize. For the other object you would create a vector from B to A (which means you could negate A to B) and do the same operation.

When I'm asking if this is the right way to go about things, I'm focusing more on my collisionResponse function:

Code:

void Physics::collisionResponse(Renderable_Object * collidedObjectA , Renderable_Object * collidedObjectB)
{
	if (collidedObjectA->defaultCollisionResponse == 1 && collidedObjectB->defaultCollisionResponse == 1)
	{
		if (collidedObjectA->Plane)
		{
			collidedObjectB->getLocation().x = collidedObjectA->getLocation().x;
		}
		if (collidedObjectB->Plane)
		{
			collidedObjectA->getLocation().x = collidedObjectB->getLocation().x;
		}
	}
	if (collidedObjectA->defaultCollisionResponse == 0)
	{
		if (collidedObjectA->getVelocity().x != 0)
		{
			reverse_x_velocity(collidedObjectA->getVelocity());
		}
		if (collidedObjectA->getVelocity().y != 0)
		{
			reverse_y_velocity(collidedObjectA->getVelocity());
		}
	}
	else if (collidedObjectB->defaultCollisionResponse == 0)
	{
		if (collidedObjectB->getVelocity().x != 0)
		{
			reverse_x_velocity(collidedObjectB->getVelocity());
		}
		if (collidedObjectB->getVelocity().y != 0)
		{
			reverse_y_velocity(collidedObjectB->getVelocity());
		}
	}
}

It just looks so rigid to me. Like if I ever wanted to use it for anything but what I'm currently doing it wouldn't be viable anymore.

OH EM EFF GEE, IT WORKS!!!

Code:

void Draw (void)
{
	glClear (GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);		// Clear Screen And Depth Buffer
	pong.Update();
	glFlush ();													// Flush The GL Rendering Pipeline
}

Well, at least paddle collision works, here is what I have implemented so far, please ignore the obvious noob mistakes, keeping in mind I've never actually had a program that made it past an experimental stage. I know those pointers and classes that get allocated in the constructor aren't being cleaned up. I probably will not fix it until I'm 100% positive everything else is working.

Code:

#ifndef GAME_H
#define GAME_H
#include "Physics.h"
#include "Renderer.h"
#include "Player.h"
#include <vector>
class Game
{
public:
	Game()
	{
		ball = new Renderable_Object(-1,-1,1,1,0,0,1,0,true,true,true,false,0);
		player1 = new Player(-70,0);
		player2 = new Player(70,0);
		physics = new Physics;
		renderer = new Renderer;
		Game_Objects.push_back(ball);
		Game_Objects.push_back(player1->paddle);
		Game_Objects.push_back(player2->paddle);
	}
	void Update();
private:
	Renderable_Object * ball;
	Player * player1;
	Player * player2;
	Physics * physics;
	Renderer * renderer;
protected:
	std::vector<Renderable_Object*> Game_Objects;
};

#endif

Looooook, it's SIIIIIMMMPPLEEE!!!

Code:

#include "Game.h"

void Game::Update()
{
	renderer->Update(Game_Objects);
	physics->Update(Game_Objects);
}

HAHAHahahAhaheheheHeheHEEHEhe look what I can do:

Code:

		ball = new Renderable_Object(-1,-1,1,1,0,0,.2,0,true,true,true,false,0);
		ball1 = new Renderable_Object(-1,-1,1,1,0,0,-.5,0,true,true,true,false,0);
		ball2 = new Renderable_Object(-1,-1,1,1,0,0,.3,0,true,true,true,false,0);
		ball3 = new Renderable_Object(-1,-1,1,1,0,0,-.4,0,true,true,true,false,0);
		ball4 = new Renderable_Object(-1,-1,1,1,0,0,.5,0,true,true,true,false,0);
		ball5 = new Renderable_Object(-1,-1,1,1,0,0,-.45,0,true,true,true,false,0);
		player1 = new Player(-70,0);
		player2 = new Player(70,0);
		physics = new Physics;
		renderer = new Renderer;
		Game_Objects.push_back(ball);
		Game_Objects.push_back(ball1);
		Game_Objects.push_back(ball2);
		Game_Objects.push_back(ball3);
		Game_Objects.push_back(ball4);
		Game_Objects.push_back(ball5);
		Game_Objects.push_back(player1->paddle);
		Game_Objects.push_back(player2->paddle);

MASS CHAOS ENSUES!!!! Although highly programmed chaos.

I absolutely agree, I thought that the constructor looked waaay too heavy, I'll look into fixing that up.

Originally Posted by Bubba

In my asteroids clone I'm doing a simple O(n^2) collision test with the following condition: if the distance between the two objects is greater than some maximum the test is not performed.

Isn't that basically a collision test all by itself anyway? It seems to me that calculating distance could easily be a more complex calculation than simple x/y/z coordinate tests, since the former involves some trig. So like, the condition is more expensive than the test...