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 )

	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.

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).

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.

http://www.gamedev.net/blog/1729/entry-2260768-simple-sliding-collisions/