Sign in to follow this  
clum

Problems with collision detection at corners

Recommended Posts

clum    217
I'm having a weird problem with my collision detection (code pasted below). It works fine, until you walk into a corner. Particularly, a corner which opens away from you. If you walk in at the right angle, it can get very confused. It collides with one wall, but ignores the other until a certain point at which it suddenly "realises" that it collided and jumps back to where its supposed to be. I can't figure out what I'm doing wrong. He're some code. It's a bit complicated, but the general idea is pretty simple:
// Test a moving object for collision against a wall
void Walls::testCollision(Actor *actor) {
    profiler->startSection("Colliding with walls");
    for (vector<Wall>::iterator p = walls.begin(); p != walls.end(); p++)
	p->testCollision(actor);
 
    /* I can understand why it needs to be called twice - because sometimes the
       player is facing a direction which shouldn't intersect with a wall, but, due 
       to intersection with another wall is shifted into that direction, causing a
       belated intersection. However, this only takes care of the convex wall
       intersections. A similar problem was happenning with concave ones (for
       unknown reasons and the extra call didn't solve the problem */       
    for (vector<Wall>::iterator p = walls.begin(); p != walls.end(); p++)
	  p->testCollision(actor);
    profiler->finishSection("Colliding with walls");
}
 
// Test for the collision of a moving body into the wall
// Uses a simple line cross test for the perpendicular walls
// Note that wall has to member variables - a and b, which
// represent the two extreme corners of the wall
void Wall::testCollision(Actor *actor) {
    bool collided=false;			  // Has a collision been found?
 
    Coordinate current = actor->position;	  // A placeholder to keep track of the closest collision
 
    if (current.x < actor->oldPosition.x) { 	  // We're moving to the left
	if (current.x - KEEPAWAY < b.x) {	  // So test against the rightmost wall
	    if (actor->oldPosition.x > b.x) {  // We've crossed the rightmost wall's plane
 
		// Find the z intersection with the wall's plane
		double intersectionZ = actor->oldPosition.z -
		    (actor->oldPosition.z - current.z)*(actor->oldPosition.x - b.x)/
		    (actor->oldPosition.x - current.x);
 
		// Test if the intersection is on (or near) the wall
		if (intersectionZ + KEEPAWAY > a.z && intersectionZ - KEEPAWAY < b.z) {
		    collided=true;
		    current.x = b.x + KEEPAWAY + .011;
		}
	    }
	}
    } else {					  // We're moving right (or straight)
	if (current.x + KEEPAWAY > a.x) {	  // So test against the leftmost wall
	    if (actor->oldPosition.x < a.x) {	  // We've crossed the leftmost wall's plane
		// Find the z intersection with the wall's plane
		double intersectionZ = actor->oldPosition.z -
		    (actor->oldPosition.z - current.z)*(actor->oldPosition.x - a.x)/
		    (actor->oldPosition.x - current.x);
 
		// Test if the intersection is on (or near) the wall
		if (intersectionZ + KEEPAWAY > a.z && intersectionZ - KEEPAWAY < b.z) {
		    collided=true;
		    current.x = a.x - KEEPAWAY - .011;
		}
	    }
	}
    }
 
    if (current.z < actor->oldPosition.z) {       // We're moving forwards
	if (current.z - KEEPAWAY < b.z) {	  // So test against the closest wall
	    if (actor->oldPosition.z > b.z) {	  // We've crossed the closest wall's plane
		// Find the x intersection with the wall's plane
		double intersectionX = actor->oldPosition.x -
		    (actor->oldPosition.x - current.x)*(actor->oldPosition.z - b.z)/
		    (actor->oldPosition.z - current.z);
 
		// Test if the intersection is on (or near) the wall
		if (intersectionX + KEEPAWAY > a.x && intersectionX - KEEPAWAY < b.x) {
		    collided=true;
		    current.z = b.z + KEEPAWAY + .011;
		}
	    }
	}
    } else {					  // We're moving backwards
	if (current.z + KEEPAWAY > a.z) {	  // So test against the furthest wall
	    if (actor->oldPosition.z < a.z) {	  // We've crossed the furthest wall's plane
		// Find the x intersection with the wall's plane
		double intersectionX = actor->oldPosition.x -
		    (actor->oldPosition.x - current.x)*(actor->oldPosition.z - a.z)/
		    (actor->oldPosition.z - current.z);
 
		// Test if the intersection is on (or near) the wall
		if (intersectionX + KEEPAWAY > a.x && intersectionX - KEEPAWAY < b.x) {
		    collided=true;
		    current.z = a.z - KEEPAWAY - .011;
		}
	    }
	}
    }
    if (collided) actor->collided(this, current);
}

Share this post


Link to post
Share on other sites
Illumini    205
I actually have a similar problem with my collsion.. havn't been able to track it down yet... if i do I'll be sure and tell you in case we both having something conceptually wrong.

Share this post


Link to post
Share on other sites
shmoove    821
Try separating the collision testing from the collision response. First test for collisions against all walls and add those walls to a list (without altering the actors state within the tests). Then after you're done with the testing, make a collision response routine that receives the list of walls you found and properly handles every case.

shmoove

Share this post


Link to post
Share on other sites
clum    217
Quote:
Original post by shmoove
Try separating the collision testing from the collision response. First test for collisions against all walls and add those walls to a list (without altering the actors state within the tests). Then after you're done with the testing, make a collision response routine that receives the list of walls you found and properly handles every case.

shmoove
You know, I don't see why that should help, but (as I mentioned in a comment in a code) I had a similar problem with convex walls which I solved by doing the entire collision detection twice, and that problem would be solved by doing what you said, so its worth a try.

Share this post


Link to post
Share on other sites
shmoove    821
It would help because you could make sure that the collision response you're doing takes into account all the walls your actor is currently in contact with, and doesn't just move the actor into a collision with another wall. You could make a special case in the collision response to handle corners properly. Otherwise, by just repeating the whole collision testing loop, the collision responses could be "undoing" each other.

I guess with the convex corners, you were just lucky that the second pass of the collision testing wasn't "undoing" the first pass, but with the concave corners this doesn't seem to be the case.

shmoove

Share this post


Link to post
Share on other sites
clum    217
Well, I tried it, and it still doesn't work, but it does something different than it used to. I haven't thought about it too much yet, but I suspect that I'll figure out what's wrong based on its surprising new behaviour. First of all (as expected), there was no longer any need for checking for collisions twice for convex corners, and those work fine. However, in concave ones, it no longer jitters in a weird way, but it is possible to go through walls at the corners by pressing against one wall, and not being directly in the path of the other, and then to go through that other wall. Edit: I take that back - the new problem occurs at both concave and convex corners.

Share this post


Link to post
Share on other sites
shmoove    821
That sounds like a problem with the way you handle the response with corners.
Maybe it's time to post some more code snippets....

shmoove

Share this post


Link to post
Share on other sites
vnillabrent    122
It sounds to me like you need to analyze your initial algorithm and look for loopholes. You could continue to find temporary solutions but it will make your code messy and you're not guarenteed to fix all problems. Good luck.

Share this post


Link to post
Share on other sites
clum    217
I put my game on web site so people can see what I'm talking about. I'll post relevant code soon, too, though for the moment you can get the entire source code in the .tar.gz.
EDIT: Here it comes:
player.cc:

// Process the input to perform physical updates
void Player::physics(double timeDelta, KeyState &state, Game *theGame) {
if (state.isForward()) {
oldPosition = position;
position.z += timeDelta * DISTANCE_PER_MILLISECOND * directionVector.z;
position.x += timeDelta * DISTANCE_PER_MILLISECOND * directionVector.x;
theGame->testCollision(this, "Walls");
setClosestCollision();
}
if (state.isLeft() && !state.isRight()) setDirection(direction - timeDelta * RADIANS_PER_MILLISECOND);
if (state.isRight() && !state.isLeft()) setDirection(direction + timeDelta * RADIANS_PER_MILLISECOND);
}

// Sets the player to the closest collision
void Player::setClosestCollision() {
Coordinate closest = position;
for (vector<Coordinate>::iterator p = collisions.begin(); p != collisions.end(); p++) {
if (abs(p->x - oldPosition.x) < abs(position.x - oldPosition.x))
position.x = p->x;
if (abs(p->z - oldPosition.z) < abs(position.z - oldPosition.z))
position.z = p->z;
}
collisions.clear();
}


game.cc:

void Game::testCollision(Actor *actor, string object){
((Walls *)(objects.find(object)->second))->testCollision(actor);
}


walls.cc:

// Add it to the list of walls
void Walls::addHorizontalWall(int x1, int x2, int z) {
Wall newWall(x1*10 - .099, x2*10 + .099, 0.0, 6.0, z*10 - .101, z*10 + .101);
walls.push_back(newWall);
}
void Walls::addVerticalWall(int x, int z1, int z2) {
Wall newWall(x*10 - .101, x*10 + .101, 0.0, 6.01, z1*10 - .099, z2*10 + .099);
walls.push_back(newWall);
}

// Test a moving object for collision against a wall
void Walls::testCollision(Actor *actor) {
profiler->startSection("Colliding with walls");
for (vector<Wall>::iterator p = walls.begin(); p != walls.end(); p++)
p->testCollision(actor);
profiler->finishSection("Colliding with walls");
}

// Test for the collision of a moving body into the wall
void Wall::testCollision(Actor *actor) {
bool collided=false; // Has a collision been found?

Coordinate current = actor->position; // A placeholder to keep track of the closest collision

if (current.x < actor->oldPosition.x) { // We're moving to the left
if (current.x - KEEPAWAY < b.x) { // So test against the rightmost wall
if (actor->oldPosition.x > b.x) { // We've crossed the rightmost wall's plane

// Find the z intersection with the wall's plane
double intersectionZ = actor->oldPosition.z -
(actor->oldPosition.z - current.z)*(actor->oldPosition.x - b.x)/
(actor->oldPosition.x - current.x);

// Test if the intersection is on (or near) the wall
if (intersectionZ + KEEPAWAY > a.z && intersectionZ - KEEPAWAY < b.z) {
collided=true;
current.x = b.x + KEEPAWAY;
}
}
}
} else { // We're moving right (or straight)
if (current.x + KEEPAWAY > a.x) { // So test against the leftmost wall
if (actor->oldPosition.x < a.x) { // We've crossed the leftmost wall's plane
// Find the z intersection with the wall's plane
double intersectionZ = actor->oldPosition.z -
(actor->oldPosition.z - current.z)*(actor->oldPosition.x - a.x)/
(actor->oldPosition.x - current.x);

// Test if the intersection is on (or near) the wall
if (intersectionZ + KEEPAWAY > a.z && intersectionZ - KEEPAWAY < b.z) {
collided=true;
current.x = a.x - KEEPAWAY;
}
}
}
}
if (collided) actor->collided(this, current);

// Reset values
collided=false;
current = actor->position;

if (current.z < actor->oldPosition.z) { // We're moving forwards
if (current.z - KEEPAWAY < b.z) { // So test against the closest wall
if (actor->oldPosition.z > b.z) { // We've crossed the closest wall's plane
// Find the x intersection with the wall's plane
double intersectionX = actor->oldPosition.x -
(actor->oldPosition.x - current.x)*(actor->oldPosition.z - b.z)/
(actor->oldPosition.z - current.z);

// Test if the intersection is on (or near) the wall
if (intersectionX + KEEPAWAY > a.x && intersectionX - KEEPAWAY < b.x) {
collided=true;
current.z = b.z + KEEPAWAY;
}
}
}
} else { // We're moving backwards
if (current.z + KEEPAWAY > a.z) { // So test against the furthest wall
if (actor->oldPosition.z < a.z) { // We've crossed the furthest wall's plane
// Find the x intersection with the wall's plane
double intersectionX = actor->oldPosition.x -
(actor->oldPosition.x - current.x)*(actor->oldPosition.z - a.z)/
(actor->oldPosition.z - current.z);

// Test if the intersection is on (or near) the wall
if (intersectionX + KEEPAWAY > a.x && intersectionX - KEEPAWAY < b.x) {
collided=true;
current.z = a.z - KEEPAWAY;
}
}
}
}
if (collided) actor->collided(this, current);
}
I'm thinking of redoing large parts of the collision detection system...

[Edited by - clum on July 6, 2004 12:06:47 PM]

Share this post


Link to post
Share on other sites
clum    217
I've figured out my problems exactly, I just can't figure out solutions:
1) (I just noticed this problem) I had to make one type of wall stick out slightly more than the other kind in order so that I wouldn't get artifacts typical of having to polygons coincide. Unfortunately, if someone walks flush right against, the wall, then he'll get stuck by this little protrusion. (I can find a solution for this myself, but I wouldn't mind suggestions).

2) If the player is at a corner which looks like this:

____
|P
|

and the player is facing up but slightly to the left, then the player will be able to go through the left wall! Because the direction vector is facing mostly up, if not for the wall on top, the player would not intersection with the left wall this frame (the player's path would intersect with the left walls plane past the end of the left wall). However, because the top wall is in the way, the left wall will be hit, but the program doesn't notice it. I can't think of a solution for this without totally redoing the whole collision detection system, and even then I'm not 100% sure how to eleviate this problem.

Share this post


Link to post
Share on other sites
shmoove    821
Quote:

is facing up but slightly to the left, then the player will be able to go through the left wall! Because the direction vector is facing mostly up, if not for the wall on top, the player would not intersection with the left wall this frame (the player's path would intersect with the left walls plane past the end of the left wall). However, because the top wall is in the way, the left wall will be hit, but the program doesn't notice it

Well, you would have to rework the collision response. The bolded parts are problematic. Even if the player hits the north wall, he still shouldn't be hitting the left wall. You will need to trace the trajectory the player is moving along, find the intersection with the north wall, and stop him there, for the present frame. Don't slide him along the wall to the left. If you want to create a sliding effect, then his velocity vector should be changed so that it moves to the left (a dot product will do), but the position shouldn't be crossing the left wall. In the next frame he will be moving left which means the collision with the left wall will be detected and the player will stop in the corner.

I hope I'm making myself clear.

shmoove

Share this post


Link to post
Share on other sites
clum    217
Hmm. That's really a good idea. I did want the sliding effect, but you are right about that better way of doing it.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this