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

This is a discussion on Collision testing and response, for all active objects, in one function within the Game Programming forums, part of the General Programming Boards category; So, I want my Update function in my Physics class to be pretty powerful, perhaps I'm asking too much, but ...

  1. #1
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964

    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
    };
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  2. #2
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964
    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
    			}
    		}
    	}
    }
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  3. #3
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964
    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?
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  4. #4
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964
    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());
    		}
    	}
    }
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  5. #5
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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!
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  6. #6
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964
    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.
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  7. #7
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Shamino View Post
    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?
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  8. #8
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    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.
    Last edited by VirtualAce; 12-02-2009 at 07:58 PM.

  9. #9
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964
    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.
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  10. #10
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964
    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);
    }
    Last edited by Shamino; 12-02-2009 at 10:59 PM.
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  11. #11
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964
    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.
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  12. #12
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    At a glance it looks good save for Renderable_Object's constructor. That is a ton of parameters. Pehaps a two-step construction approach is in order for that object. With that many params there has to be multiple ways that constructor can fail.

  13. #13
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964
    I absolutely agree, I thought that the constructor looked waaay too heavy, I'll look into fixing that up.
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  14. #14
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Bubba View Post
    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...
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  15. #15
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    I thought of that too and you are probably right. But you can always work in terms of the square of the distance, which I do, which eliminates the square root and comes down to a dot product. In fact the function I use is D3DXVec3Dot which returns the result. It is normally used then to do 'dot-producty' things but nothing says you can't use their optimized math to multiply 3 components together.

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21