Sign in to follow this  
cozzie

First person wall sliding, what am I missing?

Recommended Posts

Hi,

I've tried to implement my collision detection so 'it can do wall sliding'.

From the theory I understood it shouldn't be that difficult:

 

- predict collision per axis

- final movement only for axis's which don't collide

 

Here's the code of my old routine and the new one with which I tried to implement it.

Any idea what's I'm overlooking?

 

OLD CODE (working fine btw rolleyes.gif )

	VECTOR3 movement = VECTOR3(0.0f, 0.0f, 0.0f);

	if(mInput.KeyDown(VkKeyScan('w')&0xFF)) movement.z = 1.0f;										// DOWN
	if(mInput.KeyDown(VkKeyScan('s')&0xFF)) movement.z = -1.0f;										// DOWN
	
	if(mInput.KeyDown(VkKeyScan('a')&0xFF)) movement.x = -1.0f;										// DOWN
	if(mInput.KeyDown(VkKeyScan('d')&0xFF)) movement.x = 1.0f;										// DOWN

	movement = mPlayer.NormalizeMovement(movement);

	mSceneManager.GetCurrentD3dcamRef().Move(movement * mTimer.GetDelta());
	mPlayer.SetPosition(mSceneManager.GetCurrentD3dcamRef().GetPositionV3());
	mSceneManager.GetCurrentD3dsceneRef().mMeshInst[mPlayerMeshInstId].SetWorldPos(mSceneManager.GetCurrentD3dcamRef().GetPosition());

	// collision with walls/ maze?
	if(PlayerCollidesWall(mPlayer))							// COLLISION: move back the player
	{
		mSceneManager.GetCurrentD3dcamRef().SetPosition(mSceneManager.GetCurrentD3dcamRef().GetLastPosition());
		mPlayer.SetPosition(mSceneManager.GetCurrentD3dcamRef().GetPositionV3());
		mSceneManager.GetCurrentD3dsceneRef().mMeshInst[mPlayerMeshInstId].SetWorldPos(mSceneManager.GetCurrentD3dcamRef().GetPosition());
	}

NEW ATTEMPT/ CODE (with wall sliding, not working/ same result as old code/approach):

	VECTOR3 movementX = VECTOR3(0.0f, 0.0f, 0.0f);
	VECTOR3 movementZ = VECTOR3(0.0f, 0.0f, 0.0f);

	if(mInput.KeyDown(VkKeyScan('a')&0xFF)) movementX.x = -1.0f;									// DOWN
	if(mInput.KeyDown(VkKeyScan('d')&0xFF)) movementX.x = 1.0f;										// DOWN

	if(mInput.KeyDown(VkKeyScan('w')&0xFF)) movementZ.z = 1.0f;										// DOWN
	if(mInput.KeyDown(VkKeyScan('s')&0xFF)) movementZ.z = -1.0f;									// DOWN
	
	movementX = mPlayer.NormalizeMovement(movementX);
	movementZ = mPlayer.NormalizeMovement(movementZ);

	bool xCollision = false;
	bool zCollision = false;

	// MOVE CAMERA & PLAYER ON X-AXIS
	mSceneManager.GetCurrentD3dcamRef().Move(movementX * mTimer.GetDelta());
	mPlayer.SetPosition(mSceneManager.GetCurrentD3dcamRef().GetPositionV3());

	// CHECK COLLISION X-AXIS
	if(PlayerCollidesWall(mPlayer))	xCollision = true;

	// UNDO MOVEMENT
	mSceneManager.GetCurrentD3dcamRef().SetPosition(mSceneManager.GetCurrentD3dcamRef().GetLastPosition());
	mPlayer.SetPosition(mSceneManager.GetCurrentD3dcamRef().GetPositionV3());

	// MOVE CAMERA & PLAYER ON Z-AXIS
	mSceneManager.GetCurrentD3dcamRef().Move(movementZ * mTimer.GetDelta());
	mPlayer.SetPosition(mSceneManager.GetCurrentD3dcamRef().GetPositionV3());

	// CHECK COLLISION Z-AXIS
	if(PlayerCollidesWall(mPlayer))	zCollision = true;

	// UNDO MOVEMENT
	mSceneManager.GetCurrentD3dcamRef().SetPosition(mSceneManager.GetCurrentD3dcamRef().GetLastPosition());
	mPlayer.SetPosition(mSceneManager.GetCurrentD3dcamRef().GetPositionV3());

	// DETERMINE FINAL MOVEMENT & MOVE CAMERA/PLAYER/MESH
	VECTOR3 finalMovement = VECTOR3(0.0f, 0.0f, 0.0f);
	if(!xCollision) finalMovement.x = movementX.x;
	if(!zCollision) finalMovement.z = movementZ.z;

	if(!xCollision || !zCollision)
	{
		mSceneManager.GetCurrentD3dcamRef().Move(finalMovement * mTimer.GetDelta());
		mPlayer.SetPosition(mSceneManager.GetCurrentD3dcamRef().GetPositionV3());
		mSceneManager.GetCurrentD3dsceneRef().mMeshInst[mPlayerMeshInstId].SetWorldPos(mSceneManager.GetCurrentD3dcamRef().GetPosition());
	}

Any help or hints is appreciated.

Edited by cozzie

Share this post


Link to post
Share on other sites

 The reason something slides when it hits a surface (if it has no elasticity and doesn't bounce) is that it's movement along the normal of the surface is absorbed by the surface. The more an objects movement is aligned with the normal of the surface, the more of its velocity gets absorbed. If the object is moving perpendicular with the surface normal (ie: it is moving along the surface, parallel to it) then none of its velocity will be removed from it.

 

Maybe if you explained what you are experiencing with your new code I could be more specific about what's going on with it.

Share this post


Link to post
Share on other sites
The response of both approaches is now identical.
I think tangletail has explained what I'm trying to achieve, I somehow have to calculate a movement vector to get me sliding. Now I just predict collision on separate axis's, where per axis the look vector is used to calculate the resulting positional change. Maybe I need to use the look vector earlier, to see what movement is possible.

I don't know exactly how to do that though

Share this post


Link to post
Share on other sites

I see that you're working in 2D, so in the following equations I will work in 2D space only (noting axes as X (horizontal) and Y (vertical) as per math convention). This technique can be extended to 3D and work properly.

 

Let us define a scene - we have a moving object (further also player) and a static object (further wall). The player is bounded by circle of radius r and center C. The wall is defined as 2 points (A and B). The player is moved with some speed and under direction defined by vector S (the length of the vector is actual speed value).

 

Let us start by defining a line-circle colision.

 

Given equation of line (note that we first express the direction of line and express line using origin, direction and define range for which the line exists) and circle:

 

$$\textbf{V} = \textbf{B} - \textbf{A}$$

$$\boldsymbol{P_{line}} = \textbf{A} + t\cdot \textbf{V}, t \in [0, 1]$$

$$r^2 = (x - C_x)^2 + (y - C_y)^2$$

 

Given these equations we are searching for set of such t where the equation for line and circle are equal. Note that first equation represents 2 equation (for each axis) ... e.g. in this case we are searching for hit point. These two equations are put together and solved:

 

$$r^2 = ((A_x + t \cdot V_x) - C_x)^2 + ((A_y + t \cdot V_y) - C_y)^2$$

 

Which ultimately goes to quadratic equation returning us true when t (to be precise any of two t values - as each quadratic equation is either insolvable = no intersection, or returns two values ... in the real number domain) is in between 0.0 and 1.0, false otherwise. Note that we're not taking into account situation where our circle is larger than wall and containing it (which can be handled too - as one t would be negative and another one t positive).

 

Of course we can compute how much our circle penetrates the line (actually for testing if there is any collision, this is enough - although you have to compare the distance to radius later) - simply by computing distance between player's center and wall.

 

$$\textbf{F} = \textbf{B} - \textbf{C}$$

$$d = {{|V_x F_y - V_y F_x|}\over{|\textbf{V}|}}$$

 

One could get wrong idea, that by just pushing sphere backwards by this penetration in direction of vector that is orthogonal to line directing towards sphere center we would get perfect sliding. Actually for small penetration values d this should be correct, where:

 

$$d < r$$

 

Assuming our tests have absolute (or at least very good) numeric precision! Which is sadly, not the real case (seriously, we are taking square roots and using divisions - the precision hurts here). What can accidentally happen? Our C would get, in single computation step behind the wall (effectively being pushed in wrong direction), or it can even jump through the wall not detecting any collision at all (this can especially happen when our time step is non-constant!!!).

 

An idea for solution - let us have timestep t, why can't we compute two step functions using half the timestep. This helps, but the problem is still there (it just pushes it a bit further away), okay, so instead of 2 samples, let's do 1000. Yeah, this will be okay for almost all the scenarios (and brutally ineffective), but the problem is still there. To get rid of the problem, we need to do infinite number of samples.

 

First simplification, we treat the sphere as center only, if the distance between this point and line is less than r we have a collision. Right now we just need to do infinite tests of point vs line (simplier, yet still unsolvable).

 

Second simplification, infinite points starting at point C moving under constant direction s form a line segment (further player-line)! So all we need is to test two line segments for distance, if it is less than radius r, then we need to find two closest points, one on line AB and one on players line.  We put another circle C' onto the closest point on line AB and test this circle against player-line. That way we get point X, where circle C intersects line AB.

 

So, how we work from there - we transform our player to the point X where we know it collides with wall. Now we know how much "time in between frames we already used" and we also know "how much time we are left". So we will just move along the wall (in direction orthogonal to wall normal that is continuing the direction of movement, e.g. it doesn't goes opposite to the movement) for the rest of time between frames.

 

Such way is much more precise and properly handles cases where our player would jump through the wall.

 

 

 

Of course this approach can be extended into 3D, as most of the physics engines use such intersection tests so they can properly model a reaction.

 

EDIT: Just a note I needed to add, never undo movement - always use swept tests, they are more precise (especially when using divisions and square roots (or inverse square roots) for calculating distances - and you have to use them).

Edited by Vilem Otte

Share this post


Link to post
Share on other sites

This article is old, but excellent: http://www.peroxide.dk/papers/collision/collision.pdf

Peroxide's article is based on Paul Nettle's collision detection article for which the code is here: http://www.paulnettle.com/pub/FluidStudios/CollisionDetection/Fluid_Studios_Collision_Detection_Demo_and_Source.zip

A sliding vector is what you need to calculate, and apply.

Edited by jacmoe

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