Jump to content
  • Advertisement
Sign in to follow this  
docflabby

silly AABB - AABB collision response problem

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 box
bool 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 tiles
bool 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 this post


Link to post
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 this post


Link to post
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 be
if(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;
}
}

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!