Commits

Anonymous committed 972e022

replaced collision method (fixes many related bugs)

  • Participants
  • Parent commits 2125664

Comments (0)

Files changed (13)

 
 [Game]
 # intial speed (units/second)
-speed = 60.0
+speed = 100.0
 # gravity (units/second^2)
-gravity = 450.0
+gravity = 650.0
 # jump acceleration (units/second^2)
 jump = 80.0
 # max jump time (seconds)
 jumpTime = 0.3
 # player acceleration (units/second^2)
-acceleration = 2.0
+acceleration = 5.0
 
 [Camera]
 distance = 15

media/leveldata/level.xml

 <leveldata version="1">
     <levelobjects>
-        <object type="CustomAABB" layer="static" x="-1.1468" y="-5" z="175">
+        <object type="CustomAABB" layer="static" x="-1.1468" y="-5.58583" z="175.099">
             <entity name="cube.mesh" />
             <material name="Textures/Rockwall" />
             <scale x="0.1" y="0.01" z="0.1" />
             <orientation w="1" x="0" y="0" z="0" />
-            <AABBextends min_x="-6.1468" min_y="-5.5" min_z="170" max_x="3.8532" max_y="-4.5" max_z="180" />
+            <AABBextends min_x="-6.1468" min_y="-6.08583" min_z="170.099" max_x="3.8532" max_y="-5.08583" max_z="180.099" />
         </object>
-        <object type="CustomAABB" layer="static" x="-1.52796" y="-5" z="195">
+        <object type="CustomAABB" layer="static" x="-1.52796" y="-1.49597" z="195">
             <entity name="cube.mesh" />
             <material name="Textures/Rockwall" />
             <scale x="0.1" y="0.01" z="0.1" />
             <orientation w="1" x="0" y="0" z="0" />
-            <AABBextends min_x="-6.52796" min_y="-5.5" min_z="190" max_x="3.47204" max_y="-4.5" max_z="200" />
+            <AABBextends min_x="-6.52796" min_y="-1.99597" min_z="190" max_x="3.47204" max_y="-0.995967" max_z="200" />
         </object>
-        <object type="CustomAABB" layer="static" x="-1.69739" y="-5" z="215">
+        <object type="CustomAABB" layer="static" x="-1.69739" y="4.01148" z="215">
             <entity name="cube.mesh" />
             <material name="Textures/Rockwall" />
             <scale x="0.1" y="0.01" z="0.1" />
             <orientation w="1" x="0" y="0" z="0" />
-            <AABBextends min_x="-6.69739" min_y="-5.5" min_z="210" max_x="3.30261" max_y="-4.5" max_z="220" />
+            <AABBextends min_x="-6.69739" min_y="3.51148" min_z="210" max_x="3.30261" max_y="4.51148" max_z="220" />
         </object>
-        <object type="CustomAABB" layer="static" x="-2.16621" y="-5" z="235">
+        <object type="CustomAABB" layer="static" x="-2.16621" y="8.54487" z="235">
             <entity name="cube.mesh" />
             <material name="Textures/Rockwall" />
             <scale x="0.1" y="0.01" z="0.1" />
             <orientation w="1" x="0" y="0" z="0" />
-            <AABBextends min_x="-7.16621" min_y="-5.5" min_z="230" max_x="2.83379" max_y="-4.5" max_z="240" />
+            <AABBextends min_x="-7.16621" min_y="8.04487" min_z="230" max_x="2.83379" max_y="9.04487" max_z="240" />
         </object>
         <object type="CustomAABB" layer="static" x="-5" y="-15" z="285">
             <entity name="cube.mesh" />
             <orientation w="1" x="0" y="0" z="0" />
             <AABBextends min_x="-0.250088" min_y="-57.4585" min_z="91.1947" max_x="0.769912" max_y="-6.45849" max_z="142.195" />
         </object>
-        <object type="CustomAABB" layer="static" x="2.10055" y="-5" z="185">
+        <object type="CustomAABB" layer="static" x="2.10055" y="-4.54344" z="185">
             <entity name="cube.mesh" />
             <material name="Textures/Rockwall" />
             <scale x="0.1" y="0.01" z="0.1" />
             <orientation w="1" x="0" y="0" z="0" />
-            <AABBextends min_x="-2.89945" min_y="-5.5" min_z="180" max_x="7.10055" max_y="-4.5" max_z="190" />
+            <AABBextends min_x="-2.89945" min_y="-5.04344" min_z="180" max_x="7.10055" max_y="-4.04344" max_z="190" />
         </object>
-        <object type="CustomAABB" layer="static" x="2.54063" y="-5" z="205">
+        <object type="CustomAABB" layer="static" x="2.54063" y="0.945442" z="205">
             <entity name="cube.mesh" />
             <material name="Textures/Rockwall" />
             <scale x="0.1" y="0.01" z="0.1" />
             <orientation w="1" x="0" y="0" z="0" />
-            <AABBextends min_x="-2.45937" min_y="-5.5" min_z="200" max_x="7.54063" max_y="-4.5" max_z="210" />
+            <AABBextends min_x="-2.45937" min_y="0.445442" min_z="200" max_x="7.54063" max_y="1.44544" max_z="210" />
         </object>
-        <object type="CustomAABB" layer="static" x="1.58107" y="-5" z="225">
+        <object type="CustomAABB" layer="static" x="1.58107" y="6.04307" z="225">
             <entity name="cube.mesh" />
             <material name="Textures/Rockwall" />
             <scale x="0.1" y="0.01" z="0.1" />
             <orientation w="1" x="0" y="0" z="0" />
-            <AABBextends min_x="-3.41893" min_y="-5.5" min_z="220" max_x="6.58107" max_y="-4.5" max_z="230" />
+            <AABBextends min_x="-3.41893" min_y="5.54307" min_z="220" max_x="6.58107" max_y="6.54307" max_z="230" />
         </object>
         <object type="CustomAABB" layer="static" x="-1.09947" y="-25.9962" z="455.415">
             <entity name="cube.mesh" />

src/CMakeLists.txt

 else()
 	ADD_EXECUTABLE(Game ${HDRS} ${SRCS})
 endif()
- 
+
+#ADD_DEFINITIONS(-DTESTING)
+
 SET_TARGET_PROPERTIES(Game PROPERTIES DEBUG_POSTFIX _d)
 TARGET_LINK_LIBRARIES(Game ${OGRE_LIBRARIES} ${OIS_LIBRARIES} ${BOOST_LIBRARIES} ${EXTRA_LIBS})

src/GameObjects/CCharacter.cpp

 }
 
 void CCharacter::Update(float deltaTime) {
-	// avoid floating point precision errors
-	CheckFloatZero(Constraints.top);
-	CheckFloatZero(Constraints.bottom);
-	CheckFloatZero(Constraints.left);
-	CheckFloatZero(Constraints.right);
+	Ogre::Vector2 translation;
 
-	// walk
-	if (Constraints.right < deltaTime*fSpeed) {
-		// collision
-		ogreBodyNode->translate(0, 0, Constraints.right, Ogre::Node::TS_LOCAL);
-	} else {
-		ogreBodyNode->translate(0, 0, deltaTime * fSpeed, Ogre::Node::TS_LOCAL);
+	if (!bJumping)
+		fVerticalVelocity = -fGravity*deltaTime;
+
+	// walk/jump/fall
+	if (goLevel != NULL) {
+		Ogre::Rectangle boundingRect;
+		Ogre::Vector3 position = GetPosition();
+		boundingRect.left = position.z - bounds.left;
+		boundingRect.right = position.z + bounds.right;
+		boundingRect.top = position.y + bounds.top;
+		boundingRect.bottom = position.y - bounds.bottom;
+
+		if (!bJumping) {
+			// EXPERIMENTAL: stairs
+
+			translation = goLevel->ResolveCollision(boundingRect, Ogre::Vector2(0, 4.0f));
+			boundingRect.left += translation.x;
+			boundingRect.right += translation.x;
+			boundingRect.top += translation.y;
+			boundingRect.bottom += translation.y;
+
+			Ogre::Vector2 trans = goLevel->ResolveCollision(boundingRect, Ogre::Vector2(deltaTime*fSpeed, 0));
+			boundingRect.left += trans.x;
+			boundingRect.right += trans.x;
+			boundingRect.top += trans.y;
+			boundingRect.bottom += trans.y;
+			translation = translation+trans;
+
+			trans = goLevel->ResolveCollision(boundingRect, Ogre::Vector2(0, -translation.y + deltaTime*fVerticalVelocity));
+			translation = translation + trans;
+		} else {
+			translation = Ogre::Vector2(deltaTime * fSpeed, deltaTime * fVerticalVelocity);
+			translation = goLevel->ResolveCollision(boundingRect, translation);
+		}
+
+		ogreBodyNode->translate(0.0f, translation.y, translation.x, Ogre::Node::TS_LOCAL);
+		CheckFloatZero(translation.x); CheckFloatZero(translation.y);
+	}
+
+	if (translation.x <= 0) {
+		fSpeed = 80;
 	}
 
 	// fall down
-	if (!bJumping && Constraints.bottom != 0.0) {
+	if (!bJumping && translation.y < 0) {
 		bJumping = true;
 		bJumpAccel = false;
 		SetAnimation(atBase, animJumpLoop, true);
 		SetAnimation(atTop, animNone);
-		fVerticalVelocity = 0;
 	}
 
 	// jump
 	if (bJumping) {
-		if (currentAnimations[atBase] != animJumpStart) {
-			if (bJumpAccel) {
-				fJumpTime += deltaTime;
-				if (fJumpTime >= fMaxJumpTime) {
-					bJumpAccel = false;
-				}
+
+		if (bJumpAccel) {
+			fJumpTime += deltaTime;
+			if (fJumpTime >= fMaxJumpTime) {
+				bJumpAccel = false;
 			}
+		}
 
-			if (Constraints.top < fVerticalVelocity*deltaTime) {
-				// collision top
-				ogreBodyNode->translate(0, Constraints.top, 0, Ogre::Node::TS_LOCAL);
+		if (fVerticalVelocity > 0 && translation.y <= 0) {
+			// collision top
+			//ogreBodyNode->translate(0, Constraints.top, 0, Ogre::Node::TS_LOCAL);
 
-				// finish jump
-				bJumpAccel = false;
-				fVerticalVelocity = 0;
-			} else if (Constraints.bottom > fVerticalVelocity*deltaTime) {
-				// collision bottom
-				ogreBodyNode->translate(0, Constraints.bottom, 0, Ogre::Node::TS_LOCAL);
+			// finish jump
+			bJumpAccel = false;
+			fVerticalVelocity = 0;
+		} else if (fVerticalVelocity < 0 && translation.y >= 0) {
+			// collision bottom
+			//ogreBodyNode->translate(0, Constraints.bottom, 0, Ogre::Node::TS_LOCAL);
 
-				// finish jump
-				SetAnimation(atBase, animJumpEnd, true);
-				fAnimationTimer = 0;
-				bJumping = false;
-			} else {
-				ogreBodyNode->translate(0, fVerticalVelocity * deltaTime, 0, Ogre::Node::TS_LOCAL);
-			}
-
-			if (!bJumpAccel)
-				fVerticalVelocity -= fGravity * deltaTime;
-
-		} else if (!bJumpAccel) {
-			// cancel jump
+			// finish jump
 			SetAnimation(atBase, animJumpEnd, true);
 			fAnimationTimer = 0;
 			bJumping = false;
+		} else {
+			//ogreBodyNode->translate(0, fVerticalVelocity * deltaTime, 0, Ogre::Node::TS_LOCAL);
 		}
+
+		if (!bJumpAccel)
+			fVerticalVelocity -= fGravity * deltaTime;
+
 	} else if (currentAnimations[atBase] != animJumpEnd) {
 		if (fSpeed > 0) {
 			if (currentAnimations[atTop] != animRunTop) {

src/GameObjects/CCharacter.h

 #ifndef CCHARACTER_H_
 #define CCHARACTER_H_
 
+#include "CLevelData.h"
+
 #include "Ogre.h"
 #include <string>
 #include <map>
 	 *  Left and Bottom must be negative; Top and Right must be positive */
 	inline void SetConstraints(const Ogre::Rectangle& constraints) { Constraints = constraints; }
 
+	inline void SetBounds(float left, float top, float right, float bottom) {
+		bounds.left = left; bounds.right = right;
+		bounds.top = top; bounds.bottom = bottom;
+	}
+
+	inline void SetLevel(PLevelData level) { goLevel = level; }
+
 	inline Ogre::SceneNode* GetSceneNode() { return ogreBodyNode; }
 
 	/** Update Character */
 	Ogre::SceneNode* ogreBodyNode;
 	Ogre::Entity* ogreBodyEntity;
 
+	// Collision Data
+	PLevelData goLevel;
+	Ogre::Rectangle bounds;
+
 	// Timer used to see how long Animations have been playing
 	// used for JumpStart, JumpEnd
 	float fAnimationTimer;

src/GameObjects/CLevelData.cpp

 	return node;
 }
 
+Ogre::Rectangle CoordinateTransform(const Ogre::AxisAlignedBox& box) {
+	Ogre::Rectangle result;
+	result.left = box.getMinimum().z;
+	result.right = box.getMaximum().z;
+	result.top = box.getMaximum().y;
+	result.bottom = box.getMinimum().y;
+	return result;
 }
+
+CLevelData::LevelObjectList CLevelData::GetObjectRectangle(const Ogre::Rectangle& rect) {
+	// TODO: use space partitioning here
+	LevelObjectList results;
+	for (LevelObjectListItor it = staticLevelData.begin(); it != staticLevelData.end(); ++it) {
+		const PLevelObject& obj = *it;
+		if (Intersect(CoordinateTransform(obj->GetBoundingBox()), rect) || Contains(rect, CoordinateTransform(obj->GetBoundingBox())))
+			results.push_back(obj);
+	}
+	return results;
 }
+
+std::vector<Ogre::Vector2> MakePolygon(const Ogre::Rectangle& rect) {
+	std::vector<Ogre::Vector2> polygon;
+	polygon.push_back(Ogre::Vector2(rect.left, rect.top));
+	polygon.push_back(Ogre::Vector2(rect.right, rect.top));
+	polygon.push_back(Ogre::Vector2(rect.right, rect.bottom));
+	polygon.push_back(Ogre::Vector2(rect.left, rect.bottom));
+	return polygon;
+}
+
+std::vector<Ogre::Vector2> MakePolygon(const Ogre::Rectangle& rect, const Ogre::Vector2& translation) {
+	std::vector<Ogre::Vector2> polygon;
+	if (translation.x > 0 && translation.y > 0) { // top right
+		polygon.push_back(Ogre::Vector2(rect.left, rect.top));
+		polygon.push_back(Ogre::Vector2(rect.left+translation.x, rect.top+translation.y));
+		polygon.push_back(Ogre::Vector2(rect.right+translation.x, rect.top+translation.y));
+		polygon.push_back(Ogre::Vector2(rect.right+translation.x, rect.bottom+translation.y));
+		polygon.push_back(Ogre::Vector2(rect.right, rect.bottom));
+		polygon.push_back(Ogre::Vector2(rect.left, rect.bottom));
+	} else if (translation.x > 0 && translation.y == 0) { // right
+		polygon.push_back(Ogre::Vector2(rect.left, rect.top));
+		polygon.push_back(Ogre::Vector2(rect.right+translation.x, rect.top));
+		polygon.push_back(Ogre::Vector2(rect.right+translation.x, rect.bottom));
+		polygon.push_back(Ogre::Vector2(rect.left, rect.bottom));
+	} else if (translation.x > 0 && translation.y < 0) { // bottom right
+		polygon.push_back(Ogre::Vector2(rect.left, rect.top));
+		polygon.push_back(Ogre::Vector2(rect.right, rect.top));
+		polygon.push_back(Ogre::Vector2(rect.right+translation.x, rect.top+translation.y));
+		polygon.push_back(Ogre::Vector2(rect.right+translation.x, rect.bottom+translation.y));
+		polygon.push_back(Ogre::Vector2(rect.left+translation.x, rect.bottom+translation.y));
+		polygon.push_back(Ogre::Vector2(rect.left, rect.bottom));
+	} else if (translation.x == 0 && translation.y > 0) { // top
+		polygon.push_back(Ogre::Vector2(rect.left, rect.top + translation.y));
+		polygon.push_back(Ogre::Vector2(rect.right, rect.top + translation.y));
+		polygon.push_back(Ogre::Vector2(rect.right, rect.bottom));
+		polygon.push_back(Ogre::Vector2(rect.left, rect.bottom));
+	} else if (translation.x == 0 && translation.y < 0) { // bottom
+		polygon.push_back(Ogre::Vector2(rect.left, rect.top));
+		polygon.push_back(Ogre::Vector2(rect.right, rect.top));
+		polygon.push_back(Ogre::Vector2(rect.right, rect.bottom + translation.y));
+		polygon.push_back(Ogre::Vector2(rect.left, rect.bottom + translation.y));
+	} else if (translation.x < 0 && translation.y > 0) { // top left
+		polygon.push_back(Ogre::Vector2(rect.left+translation.x, rect.top+translation.y));
+		polygon.push_back(Ogre::Vector2(rect.right+translation.x, rect.top+translation.y));
+		polygon.push_back(Ogre::Vector2(rect.right, rect.top));
+		polygon.push_back(Ogre::Vector2(rect.right, rect.bottom));
+		polygon.push_back(Ogre::Vector2(rect.left, rect.bottom));
+		polygon.push_back(Ogre::Vector2(rect.left+translation.x, rect.bottom+translation.y));
+	} else if (translation.x < 0 && translation.y == 0) { // left
+		polygon.push_back(Ogre::Vector2(rect.left+translation.x, rect.top));
+		polygon.push_back(Ogre::Vector2(rect.right, rect.top));
+		polygon.push_back(Ogre::Vector2(rect.right, rect.bottom));
+		polygon.push_back(Ogre::Vector2(rect.left+translation.x, rect.bottom));
+	} else if (translation.x < 0 && translation.y < 0) { // bottom left
+		polygon.push_back(Ogre::Vector2(rect.left+translation.x, rect.top+translation.y));
+		polygon.push_back(Ogre::Vector2(rect.left, rect.top));
+		polygon.push_back(Ogre::Vector2(rect.right, rect.top));
+		polygon.push_back(Ogre::Vector2(rect.right, rect.bottom));
+		polygon.push_back(Ogre::Vector2(rect.right+translation.x, rect.bottom+translation.y));
+		polygon.push_back(Ogre::Vector2(rect.left+translation.x, rect.bottom+translation.y));
+	}
+	return polygon;
+}
+
+/** Check if axis separates polygon1 and polygon2 */
+bool IsSeparatingAxis(const std::vector<Ogre::Vector2>& polygon1, const std::vector<Ogre::Vector2>& polygon2, const Ogre::Vector2& axis) {
+	// get normal of axis
+	Ogre::Vector2 normal( -axis.y, axis.x);
+	//Ogre::Vector2 normal = axis;
+	normal.normalise();
+
+	// project polygon1
+	float min1, max1; // projected intervall of polygon1
+	float dp;
+	min1 = max1 = (normal.dotProduct(polygon1[0]));
+	for (int i = 1; i < polygon1.size(); i++) {
+		dp = (normal.dotProduct(polygon1[i]));
+		if (dp < min1) min1 = dp;
+		if (dp > max1) max1 = dp;
+	}
+
+	// project polygon2
+	float min2, max2; // projected intervall of polygon2
+	min2 = max2 = (normal.dotProduct(polygon2[0]));
+	for (int i = 1; i < polygon2.size(); i++) {
+		dp = (normal.dotProduct(polygon2[i]));
+		if (dp < min2) min2 = dp;
+		if (dp > max2) max2 = dp;
+	}
+
+#ifdef TESTING
+	std::cout << min1 << ", " << max1 << "; " << min2 << ", " << max2 << std::endl;
+#endif
+
+	// check for overlap
+	//return ( (min1 < min2 && max1 <= min2) || (min1 >= max2 && max1 > max2) );
+	return (min1 - max2 > 0) || (min2 - max1 > 0);
+}
+
+Ogre::Vector2 CLevelData::ResolveCollision(const Ogre::Rectangle& rect, const Ogre::Vector2& translation) {
+	if (translation.x == 0 && translation.y == 0)
+		return translation;
+
+#ifdef TESTING
+	std::cout << "ResolveCollision: (" << rect.left << ", " << rect.top;
+	std::cout << ", " << rect.right << ", " << rect.bottom << ") " << translation << std::endl;
+#endif
+
+	// I. get all objects inside the smallest rectangle containing rect and rect+translation
+	Ogre::Rectangle broadRect( rect );
+	if (translation.x > 0)
+		broadRect.right = rect.right + translation.x;
+	else
+		broadRect.left = rect.left + translation.x;
+	if (translation.y > 0)
+		broadRect.top = rect.top + translation.y;
+	else
+		broadRect.bottom = rect.bottom + translation.y;
+	LevelObjectList objects = GetObjectRectangle(broadRect);
+
+	// if no objects are in range, we will not collide
+	if (objects.empty()) {
+		return translation;
+	}
+
+	// II. get objects which actually intersect with the parallelogram described
+	//     by rect and translation (separating axis test)
+	//	   (also check for collision)
+
+	std::vector<Ogre::Vector2> polygon = MakePolygon(rect, translation);
+	assert(!polygon.empty());
+
+	std::vector<Ogre::Vector2> boundingRectPoly;
+
+	LevelObjectList collisionObjects;
+	LevelObjectList intersectingObjects;
+	Ogre::Rectangle boundingRect;
+	for (LevelObjectListItor it = objects.begin(); it != objects.end(); ++it) {
+		const PLevelObject& obj = *it;
+		boundingRect = CoordinateTransform(obj->GetBoundingBox());
+
+		if (Intersect(rect, boundingRect)) {
+			intersectingObjects.push_back(obj);
+		}
+
+		// skip separating axis test if we already have collision
+		if (!intersectingObjects.empty())
+			continue;
+
+		boundingRectPoly = MakePolygon(boundingRect);
+
+		// test separating axes
+		if (!IsSeparatingAxis(polygon, boundingRectPoly, Ogre::Vector2::UNIT_X)) {
+			if (!IsSeparatingAxis(polygon, boundingRectPoly, Ogre::Vector2::UNIT_Y)) {
+				if (!IsSeparatingAxis(polygon, boundingRectPoly, translation))
+				{
+					collisionObjects.push_back(obj);
+				}
+			}
+		}
+	}
+
+	// in case of collision, resolve
+	if (!intersectingObjects.empty()) {
+#ifdef TESTING
+		std::cout << "COLLISION" << std::endl;
+#endif
+
+		const PLevelObject& obj = intersectingObjects[0];
+		boundingRect = CoordinateTransform(obj->GetBoundingBox());
+		Ogre::Vector2 translationResolve(0,0);
+
+#ifdef TESTING
+		std::cout << "(" << boundingRect.left << ", " << boundingRect.top;
+		std::cout << ", " << boundingRect.right << ", " << boundingRect.bottom << ")" <<  std::endl;
+#endif
+
+		// check if there is a _very_ short way out (aka rounding error)
+		if (fabs(boundingRect.left - rect.right) <= 0.0001f)
+			translationResolve.x = boundingRect.left - rect.right;
+		else if (fabs(boundingRect.right - rect.left) <= 0.0001f)
+			translationResolve.x = boundingRect.right - rect.left;
+		else if (fabs(boundingRect.bottom - rect.top) <= 0.0001f)
+			translationResolve.y = boundingRect.bottom - rect.top;
+		else if (fabs(boundingRect.top - rect.bottom) <= 0.0001f)
+			translationResolve.y = boundingRect.top - rect.bottom;
+		else {
+			// there is no short way out, choose the shortest in opposite translation direction
+			if (translation.x > 0) {
+				translationResolve.x = boundingRect.left - rect.right;
+			} else {
+				translationResolve.x = boundingRect.right - rect.left;
+			}
+
+			if (translation.y > 0) {
+				translationResolve.y = boundingRect.bottom - rect.top;
+			} else {
+				translationResolve.y = boundingRect.top - rect.bottom;
+			}
+
+			if (fabs(translationResolve.x) > fabs(translationResolve.y))
+				translationResolve.x = 0;
+			else
+				translationResolve.y = 0;
+		}
+
+#ifdef TESTING
+		std::cout << translationResolve << std::endl;
+#endif
+
+		// now translationResolve will resolve the collision
+		// perform this and repeat translation
+
+		Ogre::Rectangle transRect;
+		transRect.left = rect.left + translationResolve.x;
+		transRect.right = rect.right + translationResolve.x;
+		transRect.top = rect.top + translationResolve.y;
+		transRect.bottom = rect.bottom + translationResolve.y;
+		return translationResolve + ResolveCollision(transRect, translation);
+	}
+
+	if (collisionObjects.empty()) {
+		return translation; // no collision
+	}
+
+	// III. get maximum translation without collision
+
+	// get faces inside parallelogram
+	Ogre::Vector2 maxTranslation(0,0);
+	//bool bFirst = true;
+	bool bFirstX = true; bool bFirstY = true;
+	std::vector<Ogre::Vector2> face;
+	for (LevelObjectListItor it = collisionObjects.begin(); it != collisionObjects.end(); ++it) {
+		const PLevelObject& obj = *it;
+		boundingRect = CoordinateTransform(obj->GetBoundingBox());
+
+		// get faces in x direction
+		face.clear();
+		if (translation.x > 0) {
+			face.push_back(Ogre::Vector2(boundingRect.left, boundingRect.top));
+			face.push_back(Ogre::Vector2(boundingRect.left, boundingRect.bottom));
+		} else if (translation.x < 0) {
+			face.push_back(Ogre::Vector2(boundingRect.right, boundingRect.top));
+			face.push_back(Ogre::Vector2(boundingRect.right, boundingRect.bottom));
+		}
+		if (!face.empty()) {
+			if (!IsSeparatingAxis(face, polygon, Ogre::Vector2::UNIT_X) &&
+				!IsSeparatingAxis(face, polygon, Ogre::Vector2::UNIT_Y) &&
+				!IsSeparatingAxis(face, polygon, translation))
+			{
+#ifdef TESTING
+				std::cout << "FC_X: " << face[0] << ", " << face[1] << std::endl;
+#endif
+				if (translation.x > 0 && boundingRect.left - rect.right >= 0) {
+					if (bFirstX || maxTranslation.x > boundingRect.left - rect.right) {
+						maxTranslation.x = boundingRect.left - rect.right;
+						bFirstX = false;
+					}
+				} else if (translation.x < 0 && boundingRect.right - rect.left <= 0) {
+					if (bFirstX || maxTranslation.x < boundingRect.right - rect.left) {
+						maxTranslation.x = boundingRect.left - rect.left;
+						bFirstX = false;
+					}
+				}
+			}
+		}
+
+		// get faces in y direction
+		face.clear();
+		if (translation.y > 0) {
+			face.push_back(Ogre::Vector2(boundingRect.left, boundingRect.bottom));
+			face.push_back(Ogre::Vector2(boundingRect.right, boundingRect.bottom));
+		} else if (translation.y < 0) {
+			face.push_back(Ogre::Vector2(boundingRect.left, boundingRect.top));
+			face.push_back(Ogre::Vector2(boundingRect.right, boundingRect.top));
+		}
+		if (!face.empty()) {
+			if (!IsSeparatingAxis(face, polygon, Ogre::Vector2::UNIT_X) &&
+				!IsSeparatingAxis(face, polygon, Ogre::Vector2::UNIT_Y) &&
+				!IsSeparatingAxis(face, polygon, translation))
+			{
+#ifdef TESTING
+				std::cout << "FC_Y: " << face[0] << ", " << face[1] << std::endl;
+#endif
+				if (translation.y > 0 && boundingRect.bottom - rect.top >= 0) {
+					if (bFirstY || maxTranslation.y > boundingRect.bottom - rect.top) {
+						maxTranslation.y = boundingRect.bottom - rect.top;
+						bFirstY = false;
+					}
+				} else if (translation.y < 0 && boundingRect.top - rect.bottom <= 0) {
+					if (bFirstY || maxTranslation.y < boundingRect.top - rect.bottom) {
+						maxTranslation.y = boundingRect.top - rect.bottom;
+						bFirstY = false;
+					}
+				}
+			}
+		}
+	}
+
+#ifdef TESTING
+	std::cout << maxTranslation << "; " << translation << std::endl;
+#endif
+
+	// IV. get maximum translation in a multiple of translation vector without collision
+	float factorX = maxTranslation.x / translation.x;
+	float factorY = maxTranslation.y / translation.y;
+
+	factorX = Ogre::Math::Clamp(factorX, 0.0f, 1.0f);
+	factorY = Ogre::Math::Clamp(factorY, 0.0f, 1.0f);
+
+	Ogre::Vector2 currTranslation;
+	bool bTranslationXDone;
+	if (bFirstX)
+		bTranslationXDone = false;
+	else if (bFirstY)
+		bTranslationXDone = true;
+	else
+		bTranslationXDone = factorX > 0 && factorX < factorY;
+	if (bTranslationXDone)
+		currTranslation = factorX * translation;
+	else
+		currTranslation = factorY * translation;
+
+#ifdef TESTING
+	std::cout << factorX << "/ " << factorY << "; X Done = " << bTranslationXDone;
+	std::cout << " firstX = " << bFirstX << " firstY = " << bFirstY << std::endl;
+#endif
+
+	Ogre::Rectangle tBounds;
+	if (bTranslationXDone) {
+		// find maximum translation in Y direction
+		tBounds.left = rect.left + currTranslation.x;
+		tBounds.right = rect.right + currTranslation.x;
+		if (translation.y > 0) {
+			tBounds.bottom = rect.bottom + currTranslation.y;
+			tBounds.top = rect.top + translation.y;
+		} else {
+			tBounds.top = rect.top + currTranslation.y;
+			tBounds.bottom = rect.bottom + translation.y;
+		}
+	} else {
+		// find maximum translation in X direction
+		tBounds.top = rect.top + currTranslation.y;
+		tBounds.bottom = rect.bottom + currTranslation.y;
+		if (translation.x > 0) {
+			tBounds.left = rect.left + currTranslation.x;
+			tBounds.right = rect.right + translation.x;
+		} else {
+			tBounds.left = rect.left + translation.x;
+			tBounds.right = rect.right + currTranslation.x;
+		}
+	}
+
+#ifdef TESTING
+	std::cout << tBounds.left << ", " << tBounds.top << ", " << tBounds.right << ", " << tBounds.bottom << std::endl;
+#endif
+
+	maxTranslation = Ogre::Vector2::ZERO;
+	bool bFirst = true;
+	boundingRectPoly = MakePolygon(tBounds);
+	for (LevelObjectListItor it = objects.begin(); it != objects.end(); ++it) {
+		const PLevelObject& obj = *it;
+		boundingRect = CoordinateTransform(obj->GetBoundingBox());
+
+		if (Intersect(boundingRect, tBounds)) {
+			face.clear();
+			if (bTranslationXDone) {
+				if (translation.y > 0) {
+					face.push_back(Ogre::Vector2(boundingRect.left, boundingRect.bottom));
+					face.push_back(Ogre::Vector2(boundingRect.right, boundingRect.bottom));
+				} else if (translation.y < 0) {
+					face.push_back(Ogre::Vector2(boundingRect.left, boundingRect.top));
+					face.push_back(Ogre::Vector2(boundingRect.right, boundingRect.top));
+				}
+			} else {
+				if (translation.x > 0) {
+					face.push_back(Ogre::Vector2(boundingRect.left, boundingRect.top));
+					face.push_back(Ogre::Vector2(boundingRect.left, boundingRect.bottom));
+				} else if (translation.x < 0) {
+					face.push_back(Ogre::Vector2(boundingRect.right, boundingRect.top));
+					face.push_back(Ogre::Vector2(boundingRect.right, boundingRect.bottom));
+				}
+			}
+			if (!IsSeparatingAxis(face, boundingRectPoly, Ogre::Vector2::UNIT_X) &&
+				!IsSeparatingAxis(face, boundingRectPoly, Ogre::Vector2::UNIT_Y)) {
+				if (bTranslationXDone) {
+					if (translation.y > 0) {
+						if (bFirst || maxTranslation.y > boundingRect.bottom - rect.top - currTranslation.y) {
+							maxTranslation.y = boundingRect.bottom - rect.top - currTranslation.y;
+							bFirst = false;
+						}
+					} else {
+						if (bFirst || maxTranslation.y > boundingRect.top - rect.bottom - currTranslation.y) {
+							maxTranslation.y = boundingRect.top - rect.bottom - currTranslation.y;
+							bFirst = false;
+						}
+					}
+				} else {
+					if (translation.x > 0) {
+						if (bFirst || maxTranslation.x > boundingRect.left - rect.right - currTranslation.x) {
+							maxTranslation.x = boundingRect.left - rect.right - currTranslation.x;
+							bFirst = false;
+						}
+					} else {
+						if (bFirst || maxTranslation.x > boundingRect.right - rect.left - currTranslation.x) {
+							maxTranslation.x = boundingRect.right - rect.left - currTranslation.x;
+							bFirst = false;
+						}
+					}
+				}
+			}
+		}
+	}
+
+	if (bFirst) {
+		// no faces found
+		if (bTranslationXDone)
+			maxTranslation.y = translation.y - currTranslation.y;
+		else
+			maxTranslation.x = translation.x - currTranslation.x;
+	}
+
+#ifdef TESTING
+	std::cout << maxTranslation << std::endl;
+#endif
+
+	maxTranslation = currTranslation + maxTranslation;
+
+
+#ifdef TESTING
+	std::cout << maxTranslation << std::endl;
+#endif
+
+	return maxTranslation;
+}
+
+}
+}

src/GameObjects/CLevelData.h

 	@param range Maximum distance to check for constraints */
 	Ogre::Rectangle Collision(const Ogre::Rectangle& rect, float range);
 
+	/** Resolve Collision for a Rectangle rect which moves along translation
+	@return Translation vector which avoids collision; returns translation if no collision occurs; a multiple of translation otherwise */
+	Ogre::Vector2 ResolveCollision(const Ogre::Rectangle& rect, const Ogre::Vector2& translation);
+
 	/** Removes all objects */
 	void ClearData();
 
 	typedef std::vector<PLevelObject> LevelObjectList;
 	typedef std::vector<PLevelObject>::iterator LevelObjectListItor;
 
+	LevelObjectList GetObjectRectangle(const Ogre::Rectangle& rect);
+
 	LevelObjectList staticLevelData;
 	LevelObjectList backgroundLevelData;
 	LevelObjectList dynamicLevelData;
 };
 
+std::vector<Ogre::Vector2> MakePolygon(const Ogre::Rectangle& rect, const Ogre::Vector2& translation);
+bool IsSeparatingAxis(const std::vector<Ogre::Vector2>& polygon1, const std::vector<Ogre::Vector2>& polygon2, const Ogre::Vector2& axis);
+
 }
 }
 

src/GameObjects/LevelObjects.cpp

 
 	// check for collision
 	if (Contains(boundingRect, rect) || Intersect(boundingRect, rect)) {
-		// in case of collision, assign a negative value to right
-		// and a positive value to bottom. this will force the character
-		// to always move in that direction
-
-		float intersectX = boundingRect.left - rect.right; // should be negative
-		float intersectY = boundingRect.top - rect.bottom; // should be positive
-
-		// move up and left if distance of X/Y intersection is "almost equal"
-		if (fabs(intersectX - intersectY) < 1.0f) {
-			constraints.right = intersectX;
-			constraints.bottom = intersectY;
-
-		// choose smallest distance
-		} else if (fabs(intersectX) > fabs(intersectY)) {
-			constraints.right = 0;
-			constraints.bottom = intersectY;
-		} else {
-			constraints.right = intersectX;
-			constraints.bottom = 0;
-		}
-
+		// resolve collision in all directions
+		constraints.right = boundingRect.left - rect.right;
+		constraints.bottom = boundingRect.top - rect.bottom;
+		constraints.left = boundingRect.right - rect.left;
+		constraints.top = boundingRect.bottom - rect.top;
+/*
 		constraints.left = -std::numeric_limits<Ogre::Real>::infinity();
+		constraints.bottom = -std::numeric_limits<Ogre::Real>::infinity();
+		constraints.right = std::numeric_limits<Ogre::Real>::infinity();
 		constraints.top = std::numeric_limits<Ogre::Real>::infinity();
-
+*/
 	} else {
 
 		/* How it works:

src/GameObjects/LevelObjects.h

 
 
 bool Intersect(const Ogre::Rectangle& r1, const Ogre::Rectangle& r2);
+bool Contains(const Ogre::Rectangle& r1, const Ogre::Rectangle& r2);
 
 }
 }

src/States/CGameState.cpp

 	light->setShadowFarDistance(500);
 	light->setShadowNearClipDistance(0.1);
 
+/*
+	Ogre::Entity* dragon = ogreScene->createEntity("dragon.mesh" );
+	dragonNode = ogreScene->getRootSceneNode()->createChildSceneNode(Ogre::Vector3(-60,-30, 0));
+	dragonNode->attachObject( dragon );
+	dragonNode->scale(0.5, 0.5, -0.5);
+
+	dragonNode->rotate(Ogre::Vector3::UNIT_X, Ogre::Degree(45), Ogre::Node::TS_LOCAL);
+*/
+
+
+	goLevel = GameObjects::CLevelData::Create();
+
+	GameObjects::PXMLReader xmlReader(new GameObjects::CXMLReader());
+	if (!xmlReader->Read("media/leveldata/level.xml", goLevel))
+		CLog::Get().Write("error loading level data", CLog::logRelease);
+
+	goLevel->Draw(ogreScene);
+
 	goHero = GameObjects::CSindbadCharacter::Create(ogreScene, "SinbadBody");
 	goHero->SetPosition(Ogre::Vector3::UNIT_Y * 5 /*+ Ogre::Vector3::UNIT_Z*(-45)*/);
 	goHero->SetSpeed(CSettingsManager::GetSingleton().get<float>("Game", "speed", 50.0f));
 
 	fAcceleration = CSettingsManager::GetSingleton().get<float>("Game", "acceleration", 1.0f);
 
-/*
-	Ogre::Entity* dragon = ogreScene->createEntity("dragon.mesh" );
-	dragonNode = ogreScene->getRootSceneNode()->createChildSceneNode(Ogre::Vector3(-60,-30, 0));
-	dragonNode->attachObject( dragon );
-	dragonNode->scale(0.5, 0.5, -0.5);
-
-	dragonNode->rotate(Ogre::Vector3::UNIT_X, Ogre::Degree(45), Ogre::Node::TS_LOCAL);
-*/
-
-
-	goLevel = GameObjects::CLevelData::Create();
-
-	GameObjects::PXMLReader xmlReader(new GameObjects::CXMLReader());
-	if (!xmlReader->Read("media/leveldata/level.xml", goLevel))
-		CLog::Get().Write("error loading level data", CLog::logRelease);
-
-	goLevel->Draw(ogreScene);
+	goHero->SetBounds(1.5f, 4.0f, 1.5f, 5.0f);
+	goHero->SetLevel(goLevel);
 
 	goHud = GameObjects::COverlay::Create("Main/HUD", "hud", 100);
 	//goHud->SetValue("Score", 0);
 
 	}
 
+/*
 	Ogre::Rectangle heroRect;
 	heroRect.left = goHero->GetPosition().z - 1.5f;
-	heroRect.right = goHero->GetPosition().z + 1.5f;
+	heroRect.right = goHero->GetPosition().z + 1.5f + CTimerTask::dT * goHero->GetSpeed();
 	heroRect.top = goHero->GetPosition().y + 4.0f;
 	heroRect.bottom = goHero->GetPosition().y - 5.0f;
 
 	goHero->SetConstraints(goLevel->Collision(heroRect, 10.0f));
+*/
 
 	goHero->SetSpeed(goHero->GetSpeed() + CTimerTask::dT * fAcceleration);
 	goHero->Update(CTimerTask::dT);

test/CCustomAABBObjectTest.cpp

 	collider.left = -4; collider.top = 4;
 	collider.right = 0; collider.bottom = 0;
 	constraints = cube->GetConstraints(collider);
-	BOOST_CHECK( constraints.left == -numeric_limits<Real>::infinity() );
-	BOOST_CHECK( constraints.right == -1 );
-	BOOST_CHECK( constraints.top == numeric_limits<Real>::infinity() );
-	BOOST_CHECK( constraints.bottom == 1 );
+	BOOST_CHECK_EQUAL( constraints.left, 5 );
+	BOOST_CHECK_EQUAL( constraints.right, -1 );
+	BOOST_CHECK_EQUAL( constraints.top, -5 );
+	BOOST_CHECK_EQUAL( constraints.bottom, 1 );
 }
 
 BOOST_AUTO_TEST_SUITE_END();

test/CMakeLists.txt

 	TestState.h
 	TestStateFactory.h
 	../src/GameObjects/LevelObjects.h
+	../src/GameObjects/CLevelData.h
 )
 
 SET(TEST_SRCS
 	StateManagerTest.cpp
 	CCustomAABBObjectTest.cpp
 	SettingsManagerTest.cpp
+	CollisionTest.cpp
 	../src/Core/CStateManager.cpp
 	../src/Core/CSettingsManager.cpp	
-	../src/GameObjects/LevelObjects.cpp	
+	../src/GameObjects/LevelObjects.cpp
+	../src/GameObjects/CLevelData.cpp		
 )
  
 if (CMAKE_BUILD_TYPE STREQUAL "Debug")
+	ADD_DEFINITIONS(-DTESTING)
 	ADD_EXECUTABLE(Test_d ${TEST_HDRS} ${TEST_SRCS})		
 	TARGET_LINK_LIBRARIES(Test_d ${OGRE_LIBRARIES} ${OIS_LIBRARIES} ${BOOST_LIBRARIES} ${EXTRA_LIBS})
 endif()

test/CollisionTest.cpp

+/*
+ * CollisionTest.cpp
+ *
+ *  Created on: Sep 4, 2010
+ *      Author: crt
+ */
+#include "../src/GameObjects/CLevelData.h"
+#include "../src/GameObjects/LevelObjects.h"
+#include "Ogre.h"
+#include "boost/test/unit_test.hpp"
+
+using namespace Ogre;
+using namespace Game::GameObjects;
+using namespace std;
+
+BOOST_AUTO_TEST_SUITE(CollisionTest);
+
+BOOST_AUTO_TEST_CASE(separating_axis_test)
+{
+	std::vector<Ogre::Vector2> poly1, poly2;
+	Ogre::Vector2 axis;
+
+	poly1.push_back(Ogre::Vector2(0,0));
+	poly1.push_back(Ogre::Vector2(1,0));
+	poly1.push_back(Ogre::Vector2(1,1));
+	poly1.push_back(Ogre::Vector2(0,1));
+
+	poly2.push_back(Ogre::Vector2(2,0));
+	poly2.push_back(Ogre::Vector2(2,1));
+	poly2.push_back(Ogre::Vector2(3,1));
+	poly2.push_back(Ogre::Vector2(3,0));
+
+	axis = Ogre::Vector2::UNIT_Y;
+	BOOST_CHECK_EQUAL(IsSeparatingAxis(poly1, poly2, axis), true);
+
+	axis = Ogre::Vector2::UNIT_X;
+	BOOST_CHECK_EQUAL(IsSeparatingAxis(poly1, poly2, axis), false);
+
+	axis = Ogre::Vector2(1,1);
+
+	BOOST_CHECK_EQUAL(IsSeparatingAxis(poly1, poly2, axis), false);
+
+	poly2.clear();
+	poly2.push_back(Ogre::Vector2(0.5,0.5));
+	poly2.push_back(Ogre::Vector2(2,0.5));
+	poly2.push_back(Ogre::Vector2(2,2));
+	poly2.push_back(Ogre::Vector2(0.5,2));
+
+	axis = Ogre::Vector2::UNIT_Y;
+	BOOST_CHECK_EQUAL(IsSeparatingAxis(poly1, poly2, axis), false);
+	axis = Ogre::Vector2::UNIT_X;
+	BOOST_CHECK_EQUAL(IsSeparatingAxis(poly1, poly2, axis), false);
+	axis = Ogre::Vector2(1,1);
+	BOOST_CHECK_EQUAL(IsSeparatingAxis(poly1, poly2, axis), false);
+
+	poly1.clear();
+	poly1.push_back(Ogre::Vector2(-1,-1));
+	poly1.push_back(Ogre::Vector2(1,-1));
+	poly1.push_back(Ogre::Vector2(1,1));
+	poly1.push_back(Ogre::Vector2(-1,1));
+
+	poly2.clear();
+	poly2.push_back(Ogre::Vector2(-1,4));
+	poly2.push_back(Ogre::Vector2(1,4));
+	poly2.push_back(Ogre::Vector2(1,0));
+	poly2.push_back(Ogre::Vector2(-1,0));
+
+	axis = Ogre::Vector2::UNIT_Y;
+	BOOST_CHECK_EQUAL(IsSeparatingAxis(poly1, poly2, axis), false);
+	axis = Ogre::Vector2::UNIT_X;
+	BOOST_CHECK_EQUAL(IsSeparatingAxis(poly1, poly2, axis), false);
+	axis = Ogre::Vector2(1,1);
+	BOOST_CHECK_EQUAL(IsSeparatingAxis(poly1, poly2, axis), false);
+}
+
+BOOST_AUTO_TEST_CASE( collision_test )
+{
+	// create 2x2x2 cube with center in origin
+	Vector3 position(0,0,0);
+	Vector3 size(2,2,2);
+
+	PCustomAABBObject cube(new CCustomAABBObject("", position));
+	cube->SetAABBSize(size);
+
+	PLevelData leveldata(new CLevelData());
+	leveldata->InsertObject(cube, CLevelData::otStatic);
+
+	// move 2x2 rectangle downwards
+	Ogre::Rectangle collider;
+	collider.left = -1; collider.right = 1;
+	collider.top = 4; collider.bottom = 2;
+
+	Ogre::Vector2 translation = leveldata->ResolveCollision(collider, Ogre::Vector2::UNIT_Y*(-2.0f));
+	BOOST_CHECK_EQUAL(translation.x, 0.0f);
+	BOOST_CHECK_EQUAL(translation.y, -1.0f);
+
+	// move beyond cube
+	translation = leveldata->ResolveCollision(collider, Ogre::Vector2::UNIT_Y*(-10.0f));
+	BOOST_CHECK_EQUAL(translation.x, 0.0f);
+	BOOST_CHECK_EQUAL(translation.y, -1.0f);
+
+
+	// move down and right
+	translation = leveldata->ResolveCollision(collider, Ogre::Vector2(1.0f, -2.0f));
+	BOOST_CHECK_EQUAL(translation.x, 1.0f);
+	BOOST_CHECK_EQUAL(translation.y, -1.0f);
+
+	collider.left = -2; collider.top = 2;
+	collider.right = 0; collider.bottom = 0;
+	translation = leveldata->ResolveCollision(collider, Ogre::Vector2(1.0f, 0.0f));
+	BOOST_CHECK_EQUAL(translation.x, -1.0f);
+	BOOST_CHECK_EQUAL(translation.y, 0.0f);
+}
+
+BOOST_AUTO_TEST_SUITE_END();