# silly AABB - AABB collision response problem

This topic is 3499 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

This problem is driving me absolutely insane. I'm sure i'm just being stupid. The screenshot demonstrates some examples http://img299.imageshack.us/my.php?image=examplecollisions.jpg This is for a top down 2d space game. I don't want to do anything complex, there is NO rotation. i just want the player to bounce off the tiles, but i can't seem to work out the code to do it. I can detect the collisions and get a list of all the tiles the player has collided with. I just can't work out how to provide the correct response vector If anyone got any resources you could recommend to look, or help to share, i've tried google and found nothing covering AABB-AABB collision response.

##### Share on other sites
The basic algorithm would be to test each tile against the player, one by one, and move the player away from intersecting tiles by the amount of intersection.

However, in example 1 and 3 and 4, you would have multiple contacts, and that would not give you clean response if you try to do it the straight forward way.

If you take example 3, where the player is resting on a bunch of horizontal tiles, you know that the only way for the player is going up. For each tile intersected, the left and right sides are occupied by another tile, therefore those sides should be ignored for response. Only up and down can give you a valid response plane.

a concrete example.

#include <windows.h>#include <gl\glut.h>#include <math.h>#include <stdio.h>#include <stdlib.h>#pragma comment (lib, "opengl32.lib")#pragma comment (lib, "glu32.lib")#pragma comment (lib, "glut32.lib")float sign(float a)								{ return (a>0)? 1.0f : -1.0f; }float clamp(float x, float min, float max)		{ return (x < min)? min : (x > max)? max : x; }float frand(float x)							{ return (rand() / (float) RAND_MAX) * x; }float Pi()										{ static const float _Pi = (float)atan(1.0f) * 4.0; return _Pi; }struct Vector{	float x, y;	Vector()	{}	Vector(float _x, float _y)	: x(_x)	, y(_y)	{}	Vector& operator +=(const Vector& V) { x += V.x;  y += V.y; return *this; }	Vector& operator -=(const Vector& V) { x -= V.x;  y -= V.y; return *this; }	Vector& operator *=(float k)         { x *= k  ;  y *= k  ; return *this; }	Vector& operator /=(float k)         { x /= k  ;  y /= k  ; return *this; }			Vector operator + (const Vector& V) const { return Vector(x + V.x, y + V.y); }	Vector operator - (const Vector& V) const { return Vector(x - V.x, y - V.y); }	Vector operator * (float k)         const { return Vector(x * k, y * k); }	Vector operator / (float k)         const { return Vector(x / k, y / k); }		float  operator * (const Vector& V) const { return x * V.x + y * V.y; }	float  operator ^ (const Vector& V) const { return x * V.y - y * V.x; }	float	length() const { return (float)sqrt(x*x + y*y); }	float	normalise()    { float l = length(); if( l >0.0000001f) { x /= l; y /= l; } return l; }	Vector  normalised() const { Vector temp = *this; temp.normalise(); return temp; }		float   dotProduct	(const Vector& V) const { return (*this) * V; }	Vector  scale		(const Vector& xScale) const { return Vector(x * xScale.x,  y * xScale.y); }	Vector  invScale	(const Vector& xScale) const { return Vector(x / xScale.x,  y / xScale.y); }	Vector rotate(const Vector& C, float a) const	{		float px = (x - C.x) * (float)cos(a) - (y - C.y) * (float)sin(a) + C.x;		float py = (x - C.x) * (float)sin(a) + (y - C.y) * (float)cos(a) + C.y;		return Vector(px, py);	}	Vector& randomise(const Vector& Min, const Vector& Max)	{		x = Min.x + frand(Max.x - Min.x);		y = Min.y + frand(Max.y - Min.y);		return *this;	}};struct Colour{	float r;	float g;	float b;	float a;	Colour(float R, float G, float B, float A)	{		r = R;		g = G;		b = B;		a = A;	}	void render() const	{		glColor4f(r, g, b, a);	}};void renderPoint(const Vector& P, Colour col, float radius){	col.render();	glBegin(GL_POINTS);	glPointSize(radius);	glVertex2f(P.x, P.y);	glEnd();}void renderRectangle(const Vector& P, const Vector& H, Colour col, float radius){	col.render();	glBegin(GL_LINE_LOOP);	glLineWidth(radius);	glVertex2f(P.x - H.x, P.y - H.y);	glVertex2f(P.x + H.x, P.y - H.y);	glVertex2f(P.x + H.x, P.y + H.y);	glVertex2f(P.x - H.x, P.y + H.y);	glEnd();}void renderArrow(const Vector& P, const Vector& D, Colour col, float radius){	col.render();	glLineWidth(radius);		float angle = atan2(D.y, D.x);	glPushMatrix();	glTranslatef(P.x, P.y, 0.0f);	glScalef(D.length(), D.length(), 1.0f);	glRotatef(angle * 180.0f / Pi(), 0, 0, 1);	glBegin(GL_LINES);	glVertex2f(0, 0);	glVertex2f(1, 0);	glVertex2f(1, 0);	glVertex2f(0.9, -0.05);	glVertex2f(1, 0);	glVertex2f(0.9, +0.05);	glEnd();	glPopMatrix();}void renderCircle(const Vector& P, float r, Colour col, float radius){	col.render();	glLineWidth(radius);		glBegin(GL_LINE_LOOP);	int steps = 16;	float angle = 0.0;	for(int i = 0; i < steps; i ++, angle += (2.0 * Pi()) / (float) steps)	{		Vector D(cos(angle) * r, sin(angle) * r);		glVertex2f(P.x + D.x, P.y + D.y);	}	glVertex2f(P.x + r, P.y);		glEnd();}void update(float dt, Vector& velocity, Vector& position, const Vector& screenSize){	position += velocity * dt;	velocity *= 0.999f;	if(position.x < 0)		position.x = screenSize.x;	if(position.y < 0)		position.y = screenSize.y;	if(position.x > screenSize.x)		position.x = 0;	if(position.y > screenSize.y)		position.y = 0;}Vector closestPointOnRectangle(const Vector& point, const Vector& centre, const Vector& halfSize){    // relative position of sphere centre from the rectangle centre    Vector d = (point - centre);    // rectangle half-size    Vector h = halfSize;    // special case when the sphere centre is inside the rectangle    if(fabs(d.x) < h.x && fabs(d.y) < h.y)     {        // use left or right side of the rectangle boundary        // as it is the closest        if((h.x - fabs(d.x)) < (h.y - fabs(d.y)))        {             d.y = 0.0f;             d.x = h.x * sign(d.x);        }        // use top or bottom side of the rectangle boundary        // as it is the closest        else        {             d.x = 0.0f;             d.y = h.y * sign(d.y);        }    }    else    {        // clamp to rectangle boundary        if(fabs(d.x) > h.x) d.x = h.x * sign(d.x);        if(fabs(d.y) > h.y) d.y = h.y * sign(d.y);    }    // the closest point on rectangle from p    Vector c = centre + d;    return c;}bool rectangleRectangleColliding(const Vector& rect1Pos, const Vector& rect1HalfSize, const Vector& rect2Pos, const Vector& rect2HalfSize, Vector& mtd){	Vector min1 = rect1Pos - rect1HalfSize;	Vector max1 = rect1Pos + rect1HalfSize;	Vector min2 = rect2Pos - rect2HalfSize;	Vector max2 = rect2Pos + rect2HalfSize;	float dx0 = (max2.x - min1.x);	if(dx0 < 0) return false;	float dx1 = (max1.x - min2.x);	if(dx1 < 0) return false;	float dy0 = (max2.y - min1.y);	if(dy0 < 0) return false;	float dy1 = (max1.y - min2.y);	if(dy1 < 0) return false;	mtd = Vector(0, 0);	mtd.x = (dx0 < dx1)? dx0 : -dx1;	mtd.y = (dy0 < dy1)? dy0 : -dy1;	if(fabs(mtd.x) < fabs(mtd.y)) 		mtd.y = 0;	else		mtd.x = 0;	return true;}bool circleRectangleColliding(const Vector& sphereCentre, const float sphereRadius, const Vector& rectPos, const Vector& rectHalfSize, Vector& mtd){	Vector pointOnRectangle = closestPointOnRectangle(sphereCentre, rectPos, rectHalfSize);	Vector delta = (sphereCentre - pointOnRectangle);	float distanceSquared = (delta.dotProduct(delta));	if(distanceSquared > sphereRadius * sphereRadius)		return false;	Vector normal = delta / sqrt(distanceSquared);	Vector pointOnSphere = sphereCentre - normal * sphereRadius;		mtd = (pointOnRectangle - pointOnSphere);	renderPoint(pointOnRectangle, Colour(0, 1, 0, 1), 2);	renderPoint(pointOnSphere, Colour(0, 1, 0, 1), 2);	return true;}void intersectionResponse(Vector& pa, float ima, 						  Vector& pb, float imb, 						  const Vector& intersectionVector){	// separate the objects so they just touch each other    const float relaxation = 0.8f; // relaxation coefficient, arbitrary value in range [0, 1].    pa += intersectionVector * (ima / (ima + imb)) * relaxation;    pb -= intersectionVector * (imb / (ima + imb)) * relaxation;}void collisionResponse(Vector& va, float ima, 					   Vector& vb, float imb, 					   Vector& n){	// inverse masses (for static objects, inversemass = 0).    float im  = ima + imb;        // impact velocity along normal of collision 'n'    Vector v = (va - vb);    float vn = v.dotProduct(n);    // objects already separating, no reflection    if (vn > 0.0f) return;    const float cor = 0.7f; // coefficient of restitution. Arbitrary value, in range [0, 1].      // relative collision impulse    float j = -(1.0f + cor) * vn / (im);      // apply collision impulse to the two objects    va += n * (j * ima);    vb -= n * (j * imb);}int screen_width  = 640;int screen_height = 480;float framerate = 30.0f;struct Sphere{	Vector P;	Vector V;	float  r;	float  m;};struct Rect{	Vector P;	Vector H;	Vector V;	float  m;};// the rectangle (two vectors per rectangle, position, and halfsize).enum { MAX_RECTANGLES = 100 };int rectangleCount = 0;Rect rectangles[MAX_RECTANGLES];Sphere sphere;Vector mousePos(0, 0);//-------------------------------------------------------------------------------------------------////    OPENGL Functions////-------------------------------------------------------------------------------------------------void init(){	sphere.P.randomise(Vector(0, 0), Vector(screen_width, screen_height));	sphere.V = Vector(0, 0);	sphere.m = frand(30) + 10;	sphere.r = frand(20) + 10;		rectangleCount = rand() % 10 + 10;	for(int i = 0; i < rectangleCount; i ++)	{		rectangles.P.randomise(Vector(0, 0), Vector(screen_width, screen_height));		rectangles.H.randomise(Vector(screen_width / 100, screen_height / 100), Vector(screen_width / 20, screen_height / 20));		rectangles.V = Vector(0, 0);		rectangles.m = frand(30) + 10;	}}void display(void){	glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT);	glViewport(	0,  0, screen_width, screen_height);	glMatrixMode(GL_PROJECTION);	glLoadIdentity();	gluOrtho2D(0, screen_width, screen_height, 0);	glMatrixMode(GL_MODELVIEW);	glLoadIdentity();	// move spehre towards the mouse	Vector disp = mousePos - sphere.P;	float d = disp.length();	if(d > 5.0) disp *= 5.0f / d;	sphere.V += disp;	float dt = 1.0f / framerate;	// update sphere	update(dt, sphere.V, sphere.P, Vector(screen_width, screen_height));	// update rectangles		for(int i = 0; i < rectangleCount; i ++)	{		update(dt, rectangles.V, rectangles.P, Vector(screen_width, screen_height));	}	// collide sphere with rectangles	for(int i = 0; i < rectangleCount; i ++)	{		Vector mtd;		if(circleRectangleColliding(sphere.P, sphere.r, rectangles.P, rectangles.H, mtd))		{			intersectionResponse(sphere.P, 1.0f / sphere.m, rectangles.P, 1.0f / rectangles.m, mtd);			collisionResponse(sphere.V, 1.0f / sphere.m, rectangles.V, 1.0f / rectangles.m, mtd.normalised());		}	}	// collide rectangles against each other	for(int i = 0; i < rectangleCount; i ++)	{		for(int j = i+1; j < rectangleCount; j ++)		{						Vector mtd;			if(rectangleRectangleColliding(rectangles.P, rectangles.H, rectangles[j].P, rectangles[j].H, mtd))			{				intersectionResponse(rectangles.P, 1.0f / rectangles.m, rectangles[j].P, 1.0f / rectangles[j].m, mtd);				collisionResponse(rectangles.V, 1.0f / rectangles.m, rectangles[j].V, 1.0f / rectangles[j].m, mtd.normalised());			}		}	}	// render sphere	renderPoint(sphere.P, Colour(1, 0, 0, 1), 5);	renderPoint(mousePos, Colour(1, 0, 0, 1), 5);	renderCircle(sphere.P, sphere.r, Colour(1, 1.0, 1.0, 1), 2);	renderArrow(sphere.P, mousePos-sphere.P, Colour(1, 0.2, 0.2, 1), 1);		// render rectangles	for(int i = 0; i < rectangleCount; i ++)	{		renderPoint(rectangles.P, Colour(1, 0, 0, 1), 5);		renderRectangle(rectangles.P, rectangles.H, Colour(1, 1.0, 0.5, 1), 3);	}	glutSwapBuffers();}void reshape(int w,int h){	screen_width = w;	screen_height = h;}void ticker(int i){	display();	glutTimerFunc((int) (1000.0f / framerate), ticker, 0);}void keyboard(unsigned char key, int x, int y){	if(key == 27)	{		exit(0);	}	if(key == ' ')	{		init();	}}void mouse(int x, int y){	mousePos.x = x;	mousePos.y = y;}int main(int argc,char **argv){	glutInit(&argc,argv);	glutInitDisplayMode(GLUT_DOUBLE|GLUT_RGBA|GLUT_DEPTH);	glutInitWindowSize(screen_width, screen_height);	glutInitWindowPosition(100,100);	glutCreateWindow("verlet");	glutDisplayFunc(display);	glutReshapeFunc(reshape);	glutPassiveMotionFunc(mouse);	glutKeyboardFunc(keyboard);	glutTimerFunc((int) (1000.0f / framerate), ticker, 0);		glClearColor(0.0f,0.0f,0.3f,0.1f);	glPointSize(8);	glEnable(GL_POINT_SMOOTH);	glEnable(GL_LINE_SMOOTH);		glBlendFunc(GL_SRC_ALPHA,GL_ONE_MINUS_SRC_ALPHA);	glEnable(GL_BLEND);	init();	glutMainLoop();	return 0;}

in the code, the 'mtd' (minimum translation distance) is the vector of intersection between two boxes (and for box vs sphere). In general, the mtd provides you with the direction and amount of intersection occuring, and you can push your player by that vector to stop him intersecting with a tile.

however, for tiles with 'blocked' sides, this whole block and logic.

		mtd = Vector(0, 0);	mtd.x = (dx0 < dx1)? dx0 : -dx1;	mtd.y = (dy0 < dy1)? dy0 : -dy1;	if(fabs(mtd.x) < fabs(mtd.y)) 		mtd.y = 0;	else		mtd.x = 0;

would need to be changed slightly to ignore sides that cannot be used for response. But in general, the same principle should be valid for your purpose, and the player should be moved out of the intersections nice and smooth.

##### Share on other sites
a simpler example I cooked up over lunchtime...

//===========================================================================//// INCLUDES////===========================================================================#include <stdio.h>#include <stdlib.h>#include <stdarg.h>#include <math.h>#include <gl/glut.h>//===========================================================================//// DECLARE////===========================================================================typedef unsigned char   u_char;typedef unsigned short  u_short;typedef unsigned int    u_int;typedef unsigned long   u_long;float mouse_x	= 0.0f;float mouse_y	= 0.0f;int   mouse_b	= 0;float width		= 640;float height	= 480;class Vector;void printString		(int x, int y, bool pixelcoords, unsigned int rgba, const char* str, ...);void renderSegment		(const Vector& A, const Vector& B, u_int uARGBLine, u_short uStipple=0xFF);void renderBox			(const Vector& Min, const Vector& Max, u_int uARGBFill, u_int uARGBLine);void renderBox			(const Vector& Pos, const Vector& Ext, float orient, u_int uARGBFill, u_int uARGBLine);void renderArrow		(const Vector& P, const Vector& D, float length, u_int uARGB);void renderDisk			(const Vector& xPos, float fRad, u_int uARGBFill, u_int uARGBLine);void renderPoint		(const Vector& xPos, float fRad, u_int uARGB);void renderPolygon		(const Vector& xPos, const Vector* Verts, int numverts, u_int uARGBFill, u_int uARGBLine);	//===========================================================================//// MATHS////===========================================================================inline float sign(float x){	return (x < 0.0f)? -1.0f : 1.0f;}inline float frand(float x=1.0f){	return (rand() / (float) RAND_MAX) * x;}inline float frand(float a, float b){	return a + frand(1.0f) * (b - a);}inline void swapf(float& a, float& b){	float c = a;	a = b;	b = c;}inline float pi(){    static const float s_pi = atan(1.0f) * 4.0f;	return s_pi;}inline float twopi(){	static const float s_twopi = 2.0f * pi();	return s_twopi;}inline float radiansToDegrees(float rad){	static const float k = 180.0f / pi();	return rad * k;}inline float degreesToRadians(float deg){	static const float k = pi() / 180.0f;	return deg * k;}//===========================================================================//// VECTORS////===========================================================================class Vector{public:	float x,y;	static const Vector& zero() { static const Vector v(0, 0); return v; }public:	inline Vector(void)	{}	inline Vector(float inx,float iny)	: x(inx)	, y(iny)	{}	inline Vector &operator /=(const float s)	{ x /= s; y /= s; return *this; }	inline Vector &operator *=(const float s)	{ x *= s; y *= s; return *this; }	inline Vector &operator +=(const Vector &other) { x += other.x;	y += other.y; return *this; }	inline Vector &operator -=(const Vector &other) { x -= other.x;	y -= other.y; return *this;	}	inline Vector operator * (float s) const {	return Vector(x*s, y*s); }	inline Vector operator / (float s) const {	return Vector(x/s, y/s); }	inline Vector operator + (const Vector &other) const {	return Vector(x+other.x, y+other.y); }	inline Vector operator - (const Vector &other) const {	return Vector(x-other.x, y-other.y); }	friend Vector operator * (float k, const Vector& other) { return Vector(other.x*k, other.y*k); }	inline Vector operator -(void) const { return Vector(-x, -y); }	inline float operator ^ (const Vector &other) const { return (x * other.y) - (y * other.x); } // cross product	inline float operator * (const Vector &other) const { return (x * other.x) + (y * other.y); } // dot product		inline float length(void) const { return (float) sqrt(x*x + y*y); }	inline float dotProduct(const Vector& other) const { return (*this) * other; }	inline float crossProduct(const Vector& other) const { return (*this) ^ other; }	Vector& randomPosition(const Vector& min, const Vector& max)	{		x = frand(min.x, max.x);		y = frand(min.y, max.y);		return *this;	}	Vector& randomDirection()	{		float a = frand(twopi());		x = cos(a);		y = sin(a);		return *this;	}	Vector direction(void) const	{		Vector temp(*this);		temp.normalise();		return temp;	}		float normalise(void) 	{			float l = length();					if (l == 0.0f) 			return 0.0f; 				(*this) *= (1.0f / l); 		return l;		}	Vector& minBound(const Vector& a, const Vector& b)	{		x = (a.x < b.x)? a.x : b.x;		y = (a.y < b.y)? a.y : b.y;		return (*this);	}	Vector& maxBound(const Vector& a, const Vector& b)	{		x = (a.x > b.x)? a.x : b.x;		y = (a.y > b.y)? a.y : b.y;		return *this;	}	Vector& rotate(float angle)	{		float tempx = x;		float tempy = y;		float co = (float) cos(angle);		float si = (float) sin(angle);		x = tempx * co - tempy * si;		y = tempx * si + tempy * co;		return *this;	}		Vector& transform(const Vector& position, float orientation)	{		rotate(orientation);		(*this) += position;		return (*this);	}};//===========================================================================//// TOOLS////===========================================================================#define ARGB_A(u) (((u)>>24) & 0x000000FF)#define ARGB_R(u) (((u)>>16) & 0x000000FF)#define ARGB_G(u) (((u)>> 8) & 0x000000FF)#define ARGB_B(u) (((u)>> 0) & 0x000000FF)void renderColour(u_int col){	glColor4ub(ARGB_R(col), ARGB_G(col), ARGB_B(col), ARGB_A(col));}void renderPoint(const Vector& pos, float rad, u_int col){	renderColour(col);	glPointSize(rad);	glBegin(GL_POINTS);	glVertex2f(pos.x, pos.y);	glEnd();}void renderDisk(const Vector& pos, float rad, u_int fill, u_int line){	static int glDiskList = -1;	static int glCircleList = -1;	static int numVerts = 64;	if (!glIsList(glCircleList))	{		glCircleList = glGenLists(1);		glNewList(glCircleList, GL_COMPILE_AND_EXECUTE);		glBegin(GL_LINE_LOOP);		for(int i = 0; i < numVerts + 1; i ++)		{			Vector p(cos(twopi() * (i / (float) numVerts)), sin(twopi() * (i / (float) numVerts)));			glVertex2f(p.x, p.y);		}		glEnd();		glEndList();	}	if (!glIsList(glDiskList))	{		glDiskList = glGenLists(1);		glNewList(glDiskList, GL_COMPILE_AND_EXECUTE);		glBegin(GL_TRIANGLE_FAN);				glVertex2f(0, 0);		for(int i = 0; i < numVerts + 1; i ++)		{			Vector p(cos(twopi() * (i / (float) numVerts)), sin(twopi() * (i / (float) numVerts)));			glVertex2f(p.x, p.y);		}				glEnd();		glEndList();	}	glPushMatrix();	glTranslatef(pos.x, pos.y, 0.0f);	glScalef(rad, rad, rad);		renderColour(fill);	glCallList(glDiskList);		renderColour(line);	glCallList(glCircleList);		glPopMatrix();}void renderPolygon(const Vector& pos, const Vector* verts, int numverts, u_int fill, u_int line){	glPushMatrix();	glTranslatef(pos.x, pos.y, 0.0f);	renderColour(fill);		glBegin(GL_TRIANGLE_FAN);	glVertex2f(0, 0);	for(int i = 0;  i < numverts; i ++)	{		glVertex2f(verts.x, verts.y);	}	glVertex2f(verts[0].x, verts[0].y);	glEnd();	renderColour(line);		glBegin(GL_LINE_LOOP);	for(int i = 0;  i < numverts; i ++)	{		glVertex2f(verts.x, verts.y);	}	glEnd();		glPopMatrix();}void renderArrow(const Vector& pos, const Vector& dir, float length, u_int col){	float angle = atan2(dir.y, dir.x);	glPushMatrix();	glTranslatef(pos.x, pos.y, 0.0f);	glRotatef(radiansToDegrees(angle), 0.0f, 0.0f, 1.0f);	glScalef(length, length, 1.0f);	renderColour(col);	glBegin(GL_LINES);	glVertex2f(0.0f, 0.0f);	glVertex2f(1.0f, 0.0f);	glVertex2f(1.0f, 0.0f);	glVertex2f(0.75f, 0.2f);	glVertex2f(1.0f, 0.0f);	glVertex2f(0.75f,-0.2f);	glEnd();	glPopMatrix();}void renderSegment(const Vector& a, const Vector& b, u_int col, u_short stipple){	renderColour(col);	glEnable(GL_LINE_STIPPLE);	glLineStipple(2, stipple);		glBegin(GL_LINES);	glVertex2f(a.x, a.y);	glVertex2f(b.x, b.y);	glEnd();	glDisable(GL_LINE_STIPPLE);}void renderBox(const Vector& pos, const Vector& halfsize, float orient, u_int fill, u_int line){	glPushMatrix();	glTranslatef(pos.x, pos.y, 0.0f);	glRotatef(orient * 180.0f / pi(), 0, 0, 1);	glScalef(halfsize.x, halfsize.y, 1.0f);		renderColour(fill);	glBegin(GL_QUADS);	glVertex2f(-1, -1);	glVertex2f(-1,  1);	glVertex2f( 1,  1);	glVertex2f( 1, -1);	glEnd();	renderColour(line);	glBegin(GL_LINE_LOOP);	glVertex2f(-1, -1);	glVertex2f(-1,  1);	glVertex2f( 1,  1);	glVertex2f( 1, -1);	glEnd();	glPopMatrix();}void renderBox(const Vector& min, const Vector& max, u_int fill, u_int line){	renderColour(fill);	glBegin(GL_QUADS);	glVertex2f(min.x, min.y);	glVertex2f(max.x, min.y);	glVertex2f(max.x, max.y);	glVertex2f(min.x, max.y);	glEnd();	renderColour(line);	glBegin(GL_LINE_LOOP);	glVertex2f(min.x, min.y);	glVertex2f(max.x, min.y);	glVertex2f(max.x, max.y);	glVertex2f(min.x, max.y);	glEnd();}void printString(int x, int y, bool pixelcoords, unsigned int col, const char* str, ...){	static char buffer[512];	va_list params;	va_start(params, str);	vsprintf_s(buffer, sizeof(buffer), str, params);	va_end(params);	glPushMatrix();	renderColour(col);	float fx = x;	float fy = y;	if (!pixelcoords)	{		x *= 8;		y *= 13;		glRasterPos2f(x, y);	}	else	{		glRasterPos2f(x, y);	}	char* c = buffer;	while(*c)	{		glutBitmapCharacter(GLUT_BITMAP_8_BY_13, *c);		c++;	}	glPopMatrix();}//===========================================================================//// GAME CODE////===========================================================================Vector playerPos(0, 0);Vector targetPos(0, 0);Vector cameraPos(0, 0);const char tileSideLeft = 1;const char tileSideRight = 2;const char tileSideTop = 4;const char tileSideBottom = 8;const int tileHeight = 16;const int tileWidth  = 16;const int playerHeight = 24;const int playerWidth  = 24;enum { WIDTH = 256, HEIGHT = 256 };char tiles[WIDTH][HEIGHT];void computePlayerBox(const Vector& playerPos, Vector& playerMin, Vector& playerMax){	playerMin = playerPos - Vector(playerWidth, playerHeight) / 2;	playerMax = playerPos + Vector(playerWidth, playerHeight) / 2;}void computeTile(int i, int j, Vector& tileMin, Vector& tileMax, char& tileSides){	// tile bounding box	tileMin.x = i * tileWidth;	tileMin.y = j * tileHeight;	tileMax = tileMin + Vector(tileWidth, tileHeight);	tileSides = 0;	// tile not blocked on the left side	if(i >= 0 && tiles[i-1][j] == 0)		tileSides |= tileSideLeft;	// tile not blocked on the right side	if(i <= WIDTH-2 && tiles[i+1][j] == 0)		tileSides |= tileSideRight;	// tile not blocked on the bottom side	if(j >= 0 && tiles[j-1] == 0)		tileSides |= tileSideBottom;	// tile not blocked on the top side	if(j <= HEIGHT-2 && tiles[j+1] == 0)		tileSides |= tileSideTop;}bool collideWithTile(	const Vector& playerMin, const Vector& playerMax, 						const Vector& tileMin, const Vector& tileMax, char tileSides, 						Vector& mtd){	//----------------------------------------------------	// check if boxes are separated from each other	//----------------------------------------------------		float dx0 = (tileMax.x - playerMin.x);	if(dx0 < 0) return false;	float dx1 = (playerMax.x - tileMin.x);	if(dx1 < 0) return false;	float dy0 = (tileMax.y - playerMin.y);	if(dy0 < 0) return false;	float dy1 = (playerMax.y - tileMin.y);	if(dy1 < 0) return false;	//----------------------------------------------------	// find mtd vector to push boxes apart.	//----------------------------------------------------	// init mtd length to impossible value	float mtdlength = -1.0f; 	mtd = Vector(0, 0);		// found right side intersection smaller than previous found mtd	if((mtdlength < 0.0f) || (dx0 <= mtdlength))	{		// if we are on the right side of the tile, 		// and the right side isn't blocked,		// set MTD to right vector.		if((tileSides & tileSideRight) && (dx0 < dx1))		{			mtd = Vector(dx0, 0);			mtdlength = dx0;		}	}		// found left side intersection smaller than previous found mtd	if((mtdlength < 0.0f) || (dx1 <= mtdlength))	{		// if we are on the left side of the tile, 		// and the left side isn't blocked		// set MTD to left vector.		if((dx1 < dx0) && (tileSides & tileSideLeft))		{			mtd = Vector(-dx1, 0);			mtdlength = dx1;		}	}		// found top side intersection smaller than previous found mtd	if((mtdlength < 0.0f) || (dy0 <= mtdlength))	{		// if we are on the top side of the tile, 		// and the top side tile isn't blocked		// set MTD to top vector.		if((dy0 < dy1) && (tileSides & tileSideTop))		{			mtd = Vector(0, dy0);			mtdlength = dy0;		}	}		// found bottom side intersection smaller than previous found mtd	if((mtdlength < 0.0f) || dy1 <= mtdlength)	{		// if we are on the bottom side of the tile, 		// and the bottom side tile isn't blocked		// set MTD to bottom vector.		if((dy1 < dy0) && (tileSides & tileSideBottom))		{			mtd = Vector(0, -dy1);			mtdlength = dy1;		}	}	return true;	}// find patch of tiles intersecting a bounding boxbool findTilePatch(const Vector& min, const Vector& max, int& columnMin, int& columnMax, int& rowMin, int& rowMax){	columnMin = (int)floor(min.x / tileWidth);	rowMin    = (int)floor(min.y / tileHeight);	columnMax = (int)floor(max.x / tileWidth);	rowMax    = (int)floor(max.y / tileHeight);	if(columnMin < 0) columnMin = 0; else if (columnMin >= WIDTH) columnMin = WIDTH-1;	if(columnMax < 0) columnMax = 0; else if (columnMax >= WIDTH) columnMax = WIDTH-1;	if(rowMin < 0) rowMin = 0; else if (rowMin >= HEIGHT) rowMin = HEIGHT-1;	if(rowMax < 0) rowMax = 0; else if (rowMax >= HEIGHT) rowMax = HEIGHT-1;	return true;}// collide player with all nearby tilesbool collideWithTiles(Vector& playerPos){	// area around the player to find what tiles to test	Vector areaMin = playerPos - Vector(playerWidth, playerHeight);	Vector areaMax = playerPos + Vector(playerWidth, playerHeight);	// patch of tiles the player can collide with.	int columnMin;	int rowMin;	int columnMax;	int rowMax;	findTilePatch(areaMin, areaMax, columnMin, columnMax, rowMin, rowMax);	// player bounding box	Vector playerMin;	Vector playerMax;	computePlayerBox(playerPos, playerMin, playerMax);	// test collisions with tiles	for(int i = columnMin; i <= columnMax; i ++)	{		for(int j = rowMin; j <= rowMax; j ++)		{			// tile to test against			Vector	tileMin;			Vector	tileMax;			char	tileSides;			computeTile(i, j, tileMin, tileMax, tileSides);			renderBox(tileMin, tileMax, 0x80008000, 0x4000ff00);				// no tile there. dont test			if(tiles[j] == 0)				continue;						// collision detection			Vector mtd;			if(collideWithTile(	playerMin, playerMax, 								tileMin, tileMax, tileSides, 								mtd))			{				// collision response. move player away from tile.				playerPos += mtd;				// re-compute player bounding box				computePlayerBox(playerPos, playerMin, playerMax);			}		}	}	return true;}//===========================================================================//// MAIN////===========================================================================void init(){	// generate random tiles	for(int i = 0; i < WIDTH; i ++)	{		for(int j = 0; j < HEIGHT; j ++)		{			if(rand() % 100 <= 15 || i == 0 || j == 0 || i == WIDTH-1 || j == HEIGHT-1)			{				tiles[j] = 1;			}			else			{				tiles[j] = 0;			}		}		}	playerPos = Vector((WIDTH /2) * tileWidth, (HEIGHT /2) * tileHeight);	cameraPos = playerPos;	targetPos = playerPos;}void render(){	// area around the player to find what tiles to test	Vector areaMin = cameraPos - Vector(width/2, height/2) - Vector(tileWidth, tileHeight);	Vector areaMax = cameraPos + Vector(width/2, height/2) + Vector(tileWidth, tileHeight);	// patch of tiles visible from the camera	int columnMin;	int rowMin;	int columnMax;	int rowMax;	findTilePatch(areaMin, areaMax, columnMin, columnMax, rowMin, rowMax);	// render tiles	for(int i = columnMin; i < columnMax; i ++)	{		for(int j = rowMin; j < rowMax; j ++)		{			if(tiles[j] == 0)				continue;			// tile to test against			Vector	tileMin;			Vector	tileMax;			char	tileSides;			computeTile(i, j, tileMin, tileMax, tileSides);			renderBox(tileMin, tileMax, 0x80808080, 0x00000000);			if(tileSides & tileSideLeft)				renderSegment(Vector(tileMin.x, tileMin.y), Vector(tileMin.x, tileMax.y), 0xffffffff, 0xFFFF);								if(tileSides & tileSideRight)				renderSegment(Vector(tileMax.x, tileMin.y), Vector(tileMax.x, tileMax.y), 0xffffffff, 0xFFFF);						if(tileSides & tileSideTop)				renderSegment(Vector(tileMin.x, tileMax.y), Vector(tileMax.x, tileMax.y), 0xffffffff, 0xFFFF);						if(tileSides & tileSideBottom)				renderSegment(Vector(tileMin.x, tileMin.y), Vector(tileMax.x, tileMin.y), 0xffffffff, 0xFFFF);		}	}	// player bounding box	Vector playerMin;	Vector playerMax;	computePlayerBox(playerPos, playerMin, playerMax);	renderBox(playerMin, playerMax, 0x80ff8080, 0xff802020);	renderSegment(playerPos, targetPos, 0xffff8080, 0x00ff);}void camera(){		Vector mousePos = Vector(mouse_x, height - mouse_y);	Vector delta = mousePos - Vector(width/2, height/2);	cameraPos += (playerPos - cameraPos) * 0.1f;	targetPos = cameraPos + delta;		glTranslatef(width/2, height/2, 0.0f);	glTranslatef(-cameraPos.x, -cameraPos.y, 0.0f);}void update(){	Vector dir = (targetPos - playerPos);	float dist = dir.length();	if(dist > tileWidth / 4) dist = tileWidth / 4;	dir.normalise();	playerPos += dir * dist;	collideWithTiles(playerPos);}void display(){	//--------------------------------------------------------------------------	// render stuff	//--------------------------------------------------------------------------	glClearColor(0.2f, 0.2f, 0.2f, 0.2f);	glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);		glMatrixMode(GL_PROJECTION);	glLoadIdentity();	gluOrtho2D(0, width, 0, height);	//-----------------------------------------------------------------	// Setup the model view matrix	//-----------------------------------------------------------------	glMatrixMode(GL_MODELVIEW);	glLoadIdentity();	camera();		update();		render();	glutSwapBuffers();}void mouse(int buttons, int state, int x, int y){	mouse_x = x;	mouse_y = y;		if (buttons == GLUT_LEFT_BUTTON)	{		if (state == GLUT_DOWN)			mouse_b |= 1;		else			mouse_b &= ~1;	}	if (buttons == GLUT_RIGHT_BUTTON)	{		if (state == GLUT_DOWN)			mouse_b |= 2;		else			mouse_b &= ~2;	}}void passiveMotion(int x, int y){	mouse_x = x;	mouse_y = y;}void motion(int x, int y){	mouse_x = x;	mouse_y = y;}void timer(int t){	display();	glutTimerFunc(t, timer, (int) 500.0f / 60.0f);}	void reshape(int w, int h){	width  = w;	height = h;	glViewport(0, 0, w, h);}void keyboard(unsigned char key, int x, int y){	if (key == 27)		exit(0);	switch(key)	{	default: break;	case ' ': init(); break;	}}void main(int argc, char** argv){	//--------------------------------------------------------------------------	// OpenGL / GLUT init	//--------------------------------------------------------------------------    glutInit( &argc, argv );	glutInitDisplayMode		(GLUT_DOUBLE | GLUT_RGBA);		glutInitWindowSize		(width, height);	glutInitWindowPosition	(0, 0);	glutCreateWindow		("tile collision");		glPointSize				(3.0f);	glEnable				(GL_BLEND);	glBlendFunc				(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);	glDisable				(GL_CULL_FACE);	glDisable				(GL_LIGHTING);		glutDisplayFunc			(display);	glutReshapeFunc			(reshape);	glutTimerFunc			(0, timer, (int) 100.0f / 60.0f);	glutPassiveMotionFunc	(passiveMotion);	glutMouseFunc			(mouse);	glutMotionFunc			(motion);	glutKeyboardFunc		(keyboard);	init();	glutMainLoop();}

##### Share on other sites
Thank you so much for the examples! They are really helpful! I'm going to have a play and see if I can get them to do what I want. (i want to bounce the player off the tiles)

##### Share on other sites
just to wrap it up, if you want a simple bouncy response, you can do a small modification of the algorithm.

the player would behave more like a rigid body, acting under external forces (gravity and so on), modifying his velocity, and in turn modifying his position in the world.

Quote:
 playerAcceleration = gravity();playerVelocity += playerAcceleration * frame_timestep;playerPosition += playerVelocity * frame_timestep;collide(playerPosition);

if you want to bounce the player against collisions, you will need to affect his velocity (instant change in linear momentum) once collisions are found.

For that effect, the player velocity can simply be 'reflected' against a collision plane.

Quote:
 playerVelocity += ((1.0f + bounceAmount) * playerVelocity.dotProduct(collisionNormal)) * collisionNormal;

bounce amount is a value in range [0, 1].

To find the collision plane, you can use the 'mtd' vector as your plane normal. If you intersect on the left of the tile, the collison plane normal would basically point to the left, same as the mtd vector.

However there is a simpler solution. When you check for intersections and modify the player position, you end up with a final player position that is different from where he would be if there was no collision.

We can use that discrepancy directly as our collision plane.

Quote:
 playerAcceleration = gravity();playerVelocity += playerAcceleration * frame_timestep;playerPosition += playerVelocity * frame_timestep;// where we'd be without collisions.Vector idealplayerPosition = playerPosition;// test collisions, move player outside tiles.collide(playerPosition);// the position discrepancy after collision. Vector delta = (playerPosition - idealplayerPosition);// we've collided with stuff, we are not where // we'd like to beif(delta.length() > 0.0001f) { // bounce of a virtual collison plane. reflectVelocity(delta);}

code
Quote:
 void update(){ // accelerate towards the mouse cursor Vector dir = (targetPos - playerPos); Vector accel = dir.direction() * 0.2f; // integrate velocity, with a maximum speed. playerVel += accel; float speed = playerVel.length(); if(speed > tileWidth / 4) speed = tileWidth / 4; playerVel = playerVel.direction() * speed; // integrate position playerPos += playerVel; // where we would be without collisions. Vector nextPlayerPos = playerPos; // check for collisions. collideWithTiles(playerPos); // bounce player off the collision. Vector ncoll =(playerPos - nextPlayerPos); float dcoll = ncoll.length(); // if we had a collision, // the player position is not where we wanted to be // so bounce against a virtual plane if(dcoll > 1.0f) // arbitrary tolerance, start bouncing if we've been pushed by at least one pixel away. { // normalise collision plane normal ncoll /= dcoll; // reflect velocity off that plane playerVel += -1.5f * (playerVel.dotProduct(ncoll)) * ncoll; }}

1. 1
2. 2
Rutin
19
3. 3
khawk
18
4. 4
5. 5
A4L
11

• 12
• 16
• 26
• 10
• 44
• ### Forum Statistics

• Total Topics
633768
• Total Posts
3013743
×