# Problems with collision detection at corners

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

## Recommended Posts

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 on other sites
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 on other sites
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 on other sites
Quote:
 Original post by shmooveTry 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 on other sites
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 on other sites
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 on other sites
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 on other sites
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 on other sites
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 updatesvoid 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 collisionvoid 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 wallsvoid 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 wallvoid 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 wallvoid 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 on other sites
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 on other sites
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