Commits

crt32  committed f0adac3

various fixes (collision, reader/writer)

  • Participants
  • Parent commits 0d79dc7

Comments (0)

Files changed (19)

 zoom = 7.5
 yaw = -100
 speed = 20.0
+
+# syntax: [name] = "[filename]"
+# (path relative to media/leveldata) 
+# optional: [name].displayname = "[displayname]"
+[Levels]
+level1 = "level.xml"
+level1.displayname = "Test Level v1"
+level2 = "obbtest.xml"
+level2.displayname = "OBBTest Area"

File media/main/hud.overlay

 	
 	element TextArea(Score)
 	{
-		top 0.01
-		left 0.01
+		metrics_mode pixels		
+		top 2
+		left 2
         font_name MainMenu/Caption
-        char_height 0.03        
+        char_height 18        
         colour 1 1 1
 		caption Score: 9002
 	}		
+	
+	element TextArea(Infos)
+	{
+		metrics_mode pixels
+		vert_align bottom		
+		top -18
+		left 2
+        font_name MainMenu/Caption
+        char_height 18        
+        colour 1 1 1
+		caption [SPACE] Jump  [ESC]/[RETURN] Exit
+	}	
 }

File media/main/mainmenu.overlay

-template container BorderPanel(MainMenu/Main)
+template container Panel(MainMenu)
 {
-	metrics_mode pixels
-	width 400
-	height 200
-	horz_align center
-	vert_align top
-	left -200
-	top 350
+	metrics_mode relative
+	left 0
+	top 0
+	width 1
+	height 1
 	
-	material MainMenu/Transparent
+	container BorderPanel(Main)
+	{
+		metrics_mode pixels
+		width 400
+		height 200
+		horz_align center
+		vert_align top
+		left -200
+		top 350
 	
-	border_material MainMenu/Black
-	border_size 10 10 10 10			
+		material MainMenu/Transparent
+	
+		border_material MainMenu/Black
+		border_size 10 10 10 10			
 
-	element TextArea(GameTitle)
+		element TextArea(GameTitle)
+		{
+        	metrics_mode pixels
+			top 15
+			left 15
+        	font_name MainMenu/Caption
+        	char_height 45
+        	space_width 20
+        	colour 1 1 1
+			caption [INSERT GAME TITLE]
+			}	
+	
+		element TextArea(NewGame)
+		{
+	        metrics_mode pixels
+			top 75
+			left 15
+	        font_name MainMenu/Caption
+	        char_height 45
+	        space_width 20
+	        colour 1 1 1
+			caption Select Level:
+		}		
+	
+		element TextArea(Level)
+		{
+	        metrics_mode pixels
+			top 135
+			left 15
+	        font_name MainMenu/Caption
+	        char_height 45
+	        space_width 20
+	        colour 1 1 1
+			caption >> level.xml
+		}		
+	}
+	
+	container Panel(Info)
 	{
-        metrics_mode pixels
-		top 15
-		left 15
-        font_name MainMenu/Caption
-        char_height 45
-        space_width 20
-        colour 1 1 1
-		caption [INSERT GAME TITLE]
-	}	
-	
-	element TextArea(NewGame)
-	{
-        metrics_mode pixels
-		top 75
-		left 15
-        font_name MainMenu/Caption
-        char_height 45
-        space_width 20
-        colour 1 1 1
-		caption >> New Game
-	}		
-	
-	element TextArea(Exit)
-	{
-        metrics_mode pixels
-		top 135
-		left 15
-        font_name MainMenu/Caption
-        char_height 45
-        space_width 20
-        colour 1 1 1
-		caption >> Exit
-	}		
+		metrics_mode pixels
+		material MainMenu/Transparent
+		left 0
+		top -28
+		width 430
+		height 28
+		vert_align bottom
+		horz_align left	
+		
+		element TextArea(Desc)
+		{
+			metrics_mode pixels
+			top 5
+			left 3
+        	font_name MainMenu/Caption
+        	char_height 22        
+        	colour 1 1 1
+			caption [Left]/[Right] Change Level [Enter] Start  [E] Editor
+		}		
+	}
 }

File src/CMakeLists.txt

 
 if (CMAKE_BUILD_TYPE STREQUAL "Debug")
 	# uncoment for debug output to console
-	#ADD_DEFINITIONS(-DTESTING)
+	ADD_DEFINITIONS(-DTESTING)
 endif()
 
 SET_TARGET_PROPERTIES(Game PROPERTIES DEBUG_POSTFIX _d)

File src/GameObjects/CCharacter.cpp

 		GameObjects::PLevelObject temp(new GameObjects::CLevelObject(Ogre::Vector2(GetPosition().z, GetPosition().y)));
 		temp->SetBoundingBox(boundingRect);
 
-
+/*
 		if (!bJumping) {
 			// EXPERIMENTAL: stairs
 
 
 			trans = goLevel->ResolveCollision(temp, Ogre::Vector2(0, -translation.y + deltaTime*fVerticalVelocity));
 			translation = translation + trans;
-		} else {
+		} else {*/
 			translation = Ogre::Vector2(deltaTime * fSpeed, deltaTime * fVerticalVelocity);
 			translation = goLevel->ResolveCollision(temp, translation);
-		}
+		//}
 
 		ogreBodyNode->translate(0.0f, translation.y, translation.x, Ogre::Node::TS_LOCAL);
 		CheckFloatZero(translation.x); CheckFloatZero(translation.y);

File src/GameObjects/CLevelData.cpp

 
 	while (!bResolveFinished) {
 
+		// check if we move with zero length
 		if ( (approximatelyEqual(currentTranslation.x, 0.0f) && approximatelyEqual(currentTranslation.y, 0.0f))
 			 || approximatelyEqual(maxLength, 0.0f) || (maxLength <= 0.0f))  {
 			bResolveFinished = true;
 			continue;
 		}
 
-		// make sure not to move too far
+		// limit current translation by maxlength
 		float currentLength = currentTranslation.length();
 		if (currentLength > maxLength) {
 			currentTranslation = (maxLength / currentLength) * currentTranslation;
 		}
 
+		// check again if we are now close to zero
+		if (approximatelyEqual(currentTranslation.x, 0.0f) && approximatelyEqual(currentTranslation.y, 0.0f)) {
+			bResolveFinished = true;
+			continue;
+		}
+
 		TEST_LOG("ResolveCollision: (" << rect << ") " << currentTranslation);
 
 		// I. get all objects inside the smallest rectangle containing rect and rect+translation
+
+		// expand bounding rect by current translation
 		Game::Rectangle broadRect( rect );
 		if (currentTranslation.x > 0)
 			broadRect.SetRight( rect.Right() + currentTranslation.x );
 		else
 			broadRect.SetBottom( rect.Bottom() + currentTranslation.y );
 
-		LevelObjectList objects = GetObjectRectangle(broadRect);
+		LevelObjectList objects = GetObjectRectangle(broadRect); // objects we could collide with
 
 		// if no objects are in range, we will not collide
 		if (objects.empty()) {
 		LevelObjectList collisionObjects; // objects we could collide with
 		LevelObjectList intersectingObjects; // objects we currently are colliding with
 
+		// do more accurate intersection test for objects that are in range
 		for (LevelObjectList::iterator it = objects.begin(); it != objects.end(); ++it) {
 			const PLevelObject& obj = *it;
+			// dont check non-blocking objects twice
 			if (std::find(ignoreObjects.begin(), ignoreObjects.end(), obj) != ignoreObjects.end())
 				continue;
 
 			Game::Rectangle boundingRect = obj->GetBoundingBox();
 			Game::Polygon objPolygon = obj->GetCollisionPolygon();
 
-			// check for intersection
+			// check for intersection with object
 			if (rect.Intersects(boundingRect)) {
 				std::pair<bool, Ogre::Vector2> result = objPolygon.SeparatingAxesTest(objectPolygon);
-				if (!result.first) {
+				if (!result.first && !approximatelyEqual(result.second.length(), 0.0f)) {
 					if (obj->HandleCollision(object, currentTranslation) == CLevelObject::ctBlocking) {
 						intersectingObjects.push_back(obj);
 					} else {
 				}
 			}
 
-			// skip if we already have collision
+			// skip if we already have intersection
 			if (!intersectingObjects.empty())
 				continue;
 
-			// test separating axes
+			// test separating axes with movement parallelogram
 			std::pair<bool, Ogre::Vector2> result = objPolygon.SeparatingAxesTest(movementParallelogram);
-			if (!result.first) {
+			if (!result.first && !approximatelyEqual(result.second.length(), 0.0f)) {
 				collisionObjects.push_back(obj);
 			}
 		}
 
-		// in case of collision, resolve
+		// in case of collision, resolve:
+		/* - Find minimum translation vector
+		 * - translate -> collision is resolved
+		 * - try again to move along translation; this time hopefully without collision
+		 */
 		if (!intersectingObjects.empty()) {
 			TEST_LOG("COLLISION");
 
 
 			// get minimum translation vector
 			std::pair<bool, Ogre::Vector2> SATresult = objectPolygon.SeparatingAxesTest(objPoly);
-			Ogre::Vector2 translationResolve = SATresult.second * (1.0f + TOLERANCE);
+			Ogre::Vector2 translationResolve = SATresult.second;
 
 			float translationLength = translationResolve.length();
 
 			// always use MTV if it is _very_ short (usually a rounding error)
-			if (translationLength > 0.01f) {
+			/*if (translationLength > 0.01f) {
 				// find solution in opposite moving direction
 				Ogre::Vector2 currentTranslationDir = currentTranslation.normalisedCopy();
 				Game::SATResult SATres = objectPolygon.IsSeparatingAxis(objPoly, Ogre::Vector2(currentTranslationDir.y, -currentTranslationDir.x));
 				else
 					translationResolve = SATres.MaximumOverlap * currentTranslationDir;
 				translationLength = translationResolve.length();
+			}*/
+
+			if (approximatelyEqual(translationLength, 0.0f)) {
+				translationResolve.x = copysign(TOLERANCE_ABS, translationResolve.x);
+				translationResolve.y = copysign(TOLERANCE_ABS, translationResolve.y);
 			}
 
+			translationResolve *= (1.0f + TOLERANCE);
+
+
+
 			/*
 			// now translationResolve will resolve the collision
 			// perform and repeat translation
 			*/
 
+			// limit translation by maxLength
 			if (translationLength > maxLength) {
 				translationResolve = (maxLength / translationLength) * translationResolve;
 				maxLength = 0;
 			continue;
 		}
 
-		// no collision
+		// no objects inside parallelogram
 		if (collisionObjects.empty()) {
 			result += currentTranslation;
 			maxLength -= currentTranslation.length();
 		}
 
 		// III. get maximum translation without collision
+		/* - get for each object inside parallelogram maximum translation vector
+		 *   along current translation (vector by which we can translate without collision)
+		 * - perform maximum translation
+		 * - check if collision is blocking; if not ignore object and repeat
+		 */
 
-		Game::Face nearestFace;
-		PLevelObject nearestObj;
-		float nearestFactor;
-		bool bNotFound = true;
+		Game::Face nearestFace; // face we are colliding with
+		PLevelObject nearestObj; // object we are colliding with
+		float nearestFactor; // maximum factor that nearestFactor*currentTranslation can be performed without collision
+		bool bNotFound = true; // no collision found?
 		bool LastCollisionNonBlocking = false;
 
 		do {
 
 			for (LevelObjectList::iterator it = collisionObjects.begin(); it != collisionObjects.end(); ++it) {
 				const PLevelObject& obj = *it;
+				// ignore non-blocking objects we already processed
 				if (std::find(ignoreObjects.begin(), ignoreObjects.end(), obj) != ignoreObjects.end())
 					continue;
 
 					Game::Polygon facePoly(objFaces[i]);
 					std::pair<bool, float> result = objectPolygon.TranslationIntersect(facePoly, currentTranslation);
 					TEST_LOG(result.first << ", " << result.second << " " << objFaces[i]);
-					if (result.first && result.second >= -0.0f) {
+					if (result.first && (approximatelyEqual(result.second, 0.0f) || result.second >= 0.0f)) {
 						 // find nearest collision
 						if (bNotFound || fabs(nearestFactor) > fabs(result.second)) {
 							bNotFound = false;
 				}
 			}
 
+			// an object has been found - perform maximum translation
 			if (!bNotFound) {
-				/*if (approximatelyEqual(nearestFactor, 0.0f)) {
-					// can't move; abort
-					TEST_LOG("nearestFactor = 0");
-					currentTranslation = Ogre::Vector2::ZERO;
-					bResolveFinished = true;
-					break;
-				}*/
-
 				// translate towards nearest object
 				Ogre::Vector2 maxTranslation = nearestFactor*currentTranslation*(1.0f - TOLERANCE);
+
+				// limit by maxLength
+				float maxTranslationLength = maxTranslation.length();
+				if (maxTranslationLength > maxLength) {
+					maxTranslation = (maxLength/maxTranslationLength) * maxTranslation;
+					maxLength = 0.0f;
+				} else {
+					maxLength -= maxTranslationLength;
+				}
+
 				result += maxTranslation;
-				maxLength -= maxTranslation.length();
 				objectPolygon.Translate(maxTranslation);
 				rect.Translate(maxTranslation);
-
 				currentTranslation -= maxTranslation;
 
 				// check if collision is blocking
 					TEST_LOG("non-blocking");
 				}
 			}
-		} while (!currentTranslation.isZeroLength() && LastCollisionNonBlocking);
+		} while (LastCollisionNonBlocking &&
+				 !approximatelyEqual(maxLength, 0.0f) &&
+				 !(approximatelyEqual(currentTranslation.x, 0.0f) && approximatelyEqual(currentTranslation.y, 0.0f)) );
 
-		if (bResolveFinished) continue;
-
-		if (currentTranslation.isZeroLength()) {
+		if (approximatelyEqual(currentTranslation.x, 0.0f) && approximatelyEqual(currentTranslation.y, 0.0f)) {
 			// we have been able to move to our goal; continue
 			currentTranslation = translation - result;
-			TEST_LOG("currentTranslation.isZeroLength()");
+			TEST_LOG("currentTranslation = 0");
+			continue;
+		}
+
+		if (approximatelyEqual(maxLength, 0.0f)) {
+			// dont move any further
+			bResolveFinished = true;
+			TEST_LOG("maxLength = 0");
 			continue;
 		}
 
 
 		// possible separating axes are UNIT_X, UNIT_Y, facedirection
 		std::vector<Ogre::Vector2> separatingAxes;
-		separatingAxes.push_back(Ogre::Vector2::UNIT_X);
-		separatingAxes.push_back(Ogre::Vector2::UNIT_Y);
-
-		// make sure faceDirection is not a mulitple of UNIT_X or UNIT_Y
-		if (!approximatelyEqual(faceDirection.x, 0.0f) && !approximatelyEqual(faceDirection.y, 0.0f))
-			separatingAxes.push_back(faceDirection);
+		separatingAxes.push_back(faceDirection);
+		if (!LinearlyDependent(faceDirection, Ogre::Vector2::UNIT_X))
+			separatingAxes.push_back(Ogre::Vector2::UNIT_X);
+		if (!LinearlyDependent(faceDirection, Ogre::Vector2::UNIT_Y))
+			separatingAxes.push_back(Ogre::Vector2::UNIT_Y);
 
 		// find separating axis
 		Ogre::Vector2 separatingAxis(0.0f, 0.0f);
+
+//		bool knownFace = visitedFaces.find(nearestFace) != visitedFaces.end();
+
+		int separatingAxisIndex = -1;
+		float maxDp = 0.0f;
 		for (int i = 0; i < separatingAxes.size(); i++) {
+			// if we already moved along this face, dont use the same axis twice
+//			if (knownFace && LinearlyDependent(visitedFaces[nearestFace], separatingAxes[i]) )
+//				continue;
+
 			SATResult satResult = objectPolygon.IsSeparatingAxis(facePoly, separatingAxes[i]);
+
+			TEST_LOG("sep axis = " << separatingAxes[i]);
+			TEST_LOG("SAT Result: " << satResult.IsSeparating << "; " << satResult.MinimumOverlap << "; " << satResult.MaximumOverlap);
+
 			if (satResult.IsSeparating || approximatelyEqual(satResult.MinimumOverlap, 0.0f)) {
-				separatingAxis = separatingAxes[i].normalisedCopy();
-				separatingAxes.erase(separatingAxes.begin() + i);
-				TEST_LOG("sep axis = " << separatingAxis);
-				TEST_LOG("SAT Result: " << satResult.IsSeparating << "; " << satResult.MinimumOverlap << "; " << satResult.MaximumOverlap);
-				break;
+				float dp = currentTranslation.dotProduct(separatingAxes[i]);
+				if (fabs(maxDp) < fabs(dp)) {
+					maxDp = dp;
+					separatingAxis = separatingAxes[i].normalisedCopy();
+					TEST_LOG("^ choose");
+					separatingAxisIndex = i;
+				}
 			}
 		}
 
 		TEST_LOG("remaining axes: " << separatingAxes.size());
 
+		// no axis found - cancel
+		if (separatingAxis == Ogre::Vector2::ZERO) {
+			TEST_LOG("sep.axis = 0");
+			bResolveFinished = true;
+			continue;
+		}
+
+		separatingAxes.erase(separatingAxes.begin() + separatingAxisIndex);
+
+		/*if (approximatelyEqual(separatingAxis.dotProduct(currentTranslation), 0.0f)) {
+			TEST_LOG("dotproduct = 0");
+			bResolveFinished = true;
+			continue;
+		}*/
+
 		// make separatingAxis face in same direction as translation
-		if (separatingAxis.dotProduct(translation) < 0.0f)
+		if (separatingAxis.dotProduct(currentTranslation) < 0.0f)
 			separatingAxis = -separatingAxis;
 
+		TEST_LOG("sep.axis = " << separatingAxis);
+
 		// calculate maximum allowed translation along separatingAxis
-		float maxFactor = separatingAxis.dotProduct(currentTranslation);
+		float maxFactor = separatingAxis.dotProduct(translation);
+
+		if (maxFactor < 0.0f || approximatelyEqual(maxFactor, 0.0f)) {
+			TEST_LOG("maxFactor <= 0");
+			bResolveFinished = true;
+			continue;
+		}
+
 
 		// find minimum translation to "create" a new separating axis
 		float minFactor = std::numeric_limits<float>::infinity();
 		for (int i = 0; i < separatingAxes.size(); i++) {
 			SATResult satResult = objectPolygon.IsSeparatingAxis(facePoly, separatingAxes[i]);
-			if (!satResult.IsSeparating) {
+			if (!satResult.IsSeparating && !approximatelyEqual(satResult.MinimumOverlap, 0.0f)) {
 				// get minimum translation vector in direction of currentTranslation
 				Ogre::Vector2 axisNormal = LeftHandNormal(separatingAxes[i]);
 				Ogre::Vector2 MTV = satResult.MinimumOverlap * axisNormal;
-				if (MTV.dotProduct(translation) < 0)
-					MTV = satResult.MaximumOverlap * axisNormal;
+//				if (MTV.dotProduct(translation) < 0)
+//					MTV = satResult.MaximumOverlap * axisNormal;
+
+				MTV *= (1.0f + TOLERANCE);
+
+				TEST_LOG("MTV: "<<MTV);
 
 				float factor;
-				if (approximatelyEqual(separatingAxis.y, 0.0f) || (MTV.x > MTV.y && !approximatelyEqual(separatingAxis.x, 0.0f)))
+				if (approximatelyEqual(separatingAxis.y, 0.0f))
 					factor = MTV.x / separatingAxis.x;
-				else
+				else if (approximatelyEqual(separatingAxis.x, 0.0f))
 					factor = MTV.y / separatingAxis.y;
+				else {
+					if (fabs(MTV.x) > fabs(MTV.y))
+						factor = MTV.x / separatingAxis.x;
+					else
+						factor = MTV.y / separatingAxis.y;
+				}
+
+				if (factor < 0.0f) {
+					MTV = satResult.MaximumOverlap * axisNormal;
+					MTV *= (1.0f + TOLERANCE);
+
+					TEST_LOG("MTV: "<<MTV);
+
+					if (approximatelyEqual(separatingAxis.y, 0.0f))
+						factor = MTV.x / separatingAxis.x;
+					else if (approximatelyEqual(separatingAxis.x, 0.0f))
+						factor = MTV.y / separatingAxis.y;
+					else {
+						if (fabs(MTV.x) > fabs(MTV.y))
+							factor = MTV.x / separatingAxis.x;
+						else
+							factor = MTV.y / separatingAxis.y;
+					}
+				}
+
+				TEST_LOG("->factor="<<factor);
 
 				if (fabs(minFactor) > fabs(factor))
 					minFactor = factor;
 
 		float factor = (fabs(minFactor) < fabs(maxFactor)) ? minFactor : maxFactor;
 
-		currentTranslation = factor*separatingAxis*(1.0f + TOLERANCE);
+		TEST_LOG("minFactor="<<minFactor<<"; maxFactor="<<maxFactor);
+
+		Ogre::Vector2 nextTranslation = factor*separatingAxis;
+		if (approximatelyEqual(nextTranslation.x, currentTranslation.x) && approximatelyEqual(nextTranslation.y, currentTranslation.y)) {
+			TEST_LOG("next=current");
+			bResolveFinished = true;
+			continue;
+		} else {
+			currentTranslation = nextTranslation;
+		}
 
 		// if we already visited that face, we dont want to move in opposite direction
 		if (visitedFaces.find(nearestFace) != visitedFaces.end()) {
 			// check if we are moving backwards
 			float dp = visitedFaces[nearestFace].dotProduct(currentTranslation);
-			if (dp < 0) {
+			if (dp < 0.0f) {
 				// cancel
 				TEST_LOG("dotProduct < 0");
 				bResolveFinished = true;
 			visitedFaces[nearestFace] = currentTranslation;
 		}
 
+
 		TEST_LOG("currentTranslation = " << currentTranslation);
 	}
 
 	TEST_LOG("result=" << result);
+	TEST_LOG("========================"<<std::endl);
 	return result;
 }
 

File src/GameObjects/Geometry.cpp

 	for (int i = 0; i < Points.size(); i++) {
 		Ray ray(Points[i], direction);
 		std::pair<bool, float> intersection = ray.Intersects(polygon);
-		if (intersection.first && intersection.second >= 0.0f && intersection.second <= 1.0f) {
-			bIntersection = true;
-			if (factor > intersection.second) {
-				factor = intersection.second;
+		if (!std::isinf(intersection.second))
+			if (approximatelyEqual(intersection.second, 0.0f) || approximatelyEqual(intersection.second, 1.0f) ||
+					(intersection.second >= 0.0f && intersection.second <= 1.0f)) {
+				bIntersection = true;
+				if (factor > intersection.second) {
+					factor = intersection.second;
+				}
 			}
-		}
 	}
 
 	// check all rays in direction through all points of polygon
 	for (int i = 0; i < polygon.Points.size(); i++) {
 		Ray ray(polygon.Points[i], -direction);
 		std::pair<bool, float> intersection = ray.Intersects(*this);
-		if (intersection.first && intersection.second >= 0.0f && intersection.second <= 1.0f) {
-			bIntersection = true;
-			if (factor > intersection.second) {
-				factor = intersection.second;
+		if (!std::isinf(intersection.second))
+			if (approximatelyEqual(intersection.second, 0.0f) || approximatelyEqual(intersection.second, 1.0f) ||
+					(intersection.second >= 0.0f && intersection.second <= 1.0f)) {
+				bIntersection = true;
+				if (factor > intersection.second) {
+					factor = intersection.second;
+				}
 			}
-		}
 	}
 
 	return std::pair<bool, float>(bIntersection, factor);
 	float det =  -(this->Direction.x * ray.Direction.y) + (this->Direction.y * ray.Direction.x);
 
 	// if det(A) is 0 the rays are parallel
-	if (approximatelyEqual(det, 0.0f))
+	//if (approximatelyEqual(det, 0.0f))
+	if (det == 0.0f)
 		return std::pair<bool, float>(false, 0.0f);
 
 	Ogre::Vector2 y = ray.Origin - this->Origin;
 	// first row of A^-1 is 1/det(A)*(d,-b)
 	float t = (1.0f / det) * ( - ray.Direction.y * y.x  + ray.Direction.x * y.y);
 
-	return std::pair<bool, float>(true, t);
+	if (approximatelyEqual(det, 0.0f))
+		return std::pair<bool, float>(false, t);
+	else
+		return std::pair<bool, float>(true, t);
 }
 
 /** Checks for intersection with given polygon

File src/GameObjects/Geometry.h

 namespace Game {
 
 /** Maximum allowed relative rounding error */
-const float TOLERANCE = 0.001f;
+const float TOLERANCE = 0.005f;
 
 /** Maximum allowed absolute rounding error*/
-const float TOLERANCE_ABS = 0.000001f;
+const float TOLERANCE_ABS = 0.005f;
 
 /** Source of float comparison functions: Knuth, The Art of computer programming Vol 2 */
 
 }
 
 inline bool definitelyGreaterThan(float a, float b) {
+	if (fabs(a-b) <= TOLERANCE_ABS) return false;
     return (a - b) > ( (fabs(a) < fabs(b) ? fabs(b) : fabs(a)) * TOLERANCE);
 }
 
 inline bool LinearlyDependent(const Ogre::Vector2& v, const Ogre::Vector2& w) {
 	// check if a*v + b*w = 0 has a unique solution <=> det(v,w) = 0
 	float det = v.x*w.y - v.y*w.x;
-	return !approximatelyEqual(det, 0.0f);
+	return approximatelyEqual(det, 0.0f);
 }
 
 class Rectangle {

File src/GameObjects/LevelDataReader.cpp

 }
 
 Game::Polygon CXMLReader::ReadPolygon(const ticpp::Element& node) {
-	// TODO
+	Game::Polygon result;
+	// iterate <point../>
+	ticpp::Iterator< ticpp::Element > child("point");
+	for (child = child.begin( &node ); child != child.end(); child++) {
+		result.AddPoint(ReadVector2(*child));
+	}
+	return result;
 }
 
 Ogre::Vector3 CXMLReader::ReadVector(const ticpp::Element& node, const std::string& prefix) {
 	if (orientation) {
 		view->SetOrientation(ReadQuaternion(*orientation));
 	}
+
+	ticpp::Element* collision = node.FirstChildElement("Collision", false);
+	if (collision) {
+		object->SetCollisionPolygon(ReadPolygon(*collision));
+	}
 }
 
 void CXMLReader::ReadTemplate(const ticpp::Element& node, LevelDataReaderListener* listener) {

File src/GameObjects/LevelDataWriter.cpp

 	WriteVector(*element, "scale", view->GetScale());
 	WriteVector(*element, "position", view->GetPositionOffset());
 	WriteQuaternion(*element, "orientation", view->GetOrientation());
-	WriteRectangle(*element, "AABBextends", object->GetBoundingBox());
+	if (object->BoundingBoxCollisionEnabled())
+		WriteRectangle(*element, "AABBextends", object->GetBoundingBox());
+	else
+		WritePolygon(*element, "Collision", object->GetCollisionPolygon());
 
 	levelobjects->LinkEndChild(element);
 }
 	node.LinkEndChild(element);
 }
 
+void CXMLWriter::WriteVector2(Element& node, const string& name, const Ogre::Vector2& vec) {
+	Element* element = new Element(name);
+	element->SetAttribute("x", vec.x);
+	element->SetAttribute("y", vec.y);
+	node.LinkEndChild(element);
+}
+
 void CXMLWriter::WriteAABB(Element& node, const string& name, const Ogre::AxisAlignedBox& box) {
 	Element* element = new Element(name);
 	Ogre::Vector3 vMin = box.getMinimum();
 	node.LinkEndChild(element);
 }
 
+void CXMLWriter::WritePolygon(ticpp::Element& node, const std::string& name, const Game::Polygon& poly) {
+	Element* element = new Element(name);
+	std::vector<Ogre::Vector2> points = poly.GetPoints();
+
+	for (std::vector<Ogre::Vector2>::iterator it = points.begin(); it != points.end(); ++it) {
+		WriteVector2(node, "point", *it);
+	}
+
+	node.LinkEndChild(element);
 }
+
 }
+}

File src/GameObjects/LevelDataWriter.h

 private:
 	void WriteQuaternion(ticpp::Element& node, const std::string& name, const Ogre::Quaternion& quater);
 	void WriteVector(ticpp::Element& node, const std::string& name, const Ogre::Vector3& vec);
+	void WriteVector2(ticpp::Element& node, const std::string& name, const Ogre::Vector2& vec);
 	void WriteAABB(ticpp::Element& node, const std::string& name, const Ogre::AxisAlignedBox& box);
 	void WriteRectangle(ticpp::Element& node, const std::string& name, const Game::Rectangle& rect);
 	void WriteString(ticpp::Element& node, const std::string& name, const std::string& value);
+	void WritePolygon(ticpp::Element& node, const std::string& name, const Game::Polygon& poly);
 
 	ticpp::Document document;
 	ticpp::Element *root, *templates, *levelobjects;

File src/GameObjects/LevelObjects.cpp

 CLevelObject::CLevelObject(const CLevelObject& obj) {
 	// don't copy listeners
 	aabBounds = obj.aabBounds;
+	collisionData = obj.collisionData;
 	vPosition = obj.vPosition;
 	collisionType = obj.collisionType;
 }

File src/States/CEditorState.cpp

 	dynamicLevelData.clear();
 	dynamicViews.clear();
 
-	for (ViewViewMap::iterator it = backupObjects.begin(); it != backupObjects.end(); ++it) {
-		it->second->GetModel()->RemoveListener(it->second);
+	for (ViewObjectViewPairMap::iterator it = backupObjects.begin(); it != backupObjects.end(); ++it) {
+		it->second.first->RemoveListener(it->second.second);
 	}
 	backupObjects.clear();
 
-	for (OgreViewQueue::iterator it = deletedObjects.begin(); it != deletedObjects.end(); ++it) {
-		(*it)->GetModel()->RemoveListener(*it);
+	for (OgreObjectViewPairQueue::iterator it = deletedObjects.begin(); it != deletedObjects.end(); ++it) {
+		it->first->RemoveListener(it->second);
 	}
 	deletedObjects.clear();
 
 	for (OgreViewList::iterator it = staticViews.begin(); it != staticViews.end(); ++it) {
 		GameObjects::PLevelObject modelCopy = (*it)->GetModel()->Copy();
 		GameObjects::POgreEntityView viewCopy = (*it)->Copy(modelCopy);
-		backupObjects[*it] = viewCopy;
+		backupObjects[*it].first = modelCopy;
+		backupObjects[*it].second = viewCopy;
 	}
 	for (OgreViewList::iterator it = backgroundViews.begin(); it != backgroundViews.end(); ++it) {
 		GameObjects::PLevelObject modelCopy = (*it)->GetModel()->Copy();
 		GameObjects::POgreEntityView viewCopy = (*it)->Copy(modelCopy);
-		backupObjects[*it] = viewCopy;
+		backupObjects[*it].first = modelCopy;
+		backupObjects[*it].second = viewCopy;
 	}
 	for (OgreViewList::iterator it = dynamicViews.begin(); it != dynamicViews.end(); ++it) {
 		GameObjects::PLevelObject modelCopy = (*it)->GetModel()->Copy();
 		GameObjects::POgreEntityView viewCopy = (*it)->Copy(modelCopy);
-		backupObjects[*it] = viewCopy;
+		backupObjects[*it].first = modelCopy;
+		backupObjects[*it].second = viewCopy;
 	}
 
 	DrawLevel();
 	// make backup copy
 	GameObjects::PLevelObject modelCopy = objModel->Copy();
 	GameObjects::POgreEntityView viewCopy = objView->Copy(modelCopy);
-	backupObjects[objView] = viewCopy;
+	backupObjects[objView].first = modelCopy;
+	backupObjects[objView].second = viewCopy;
 
 	GetViewContainer(ActiveLayer).push_back(objView);
 	GetContainer(ActiveLayer).push_back(objModel);
 	if (deletedObjects.empty()) return;
 
 	// get newest deleted object and redraw
-	GameObjects::POgreEntityView obj = deletedObjects.back();
-	deletedObjects.pop_back();
+	GameObjects::POgreEntityView obj = deletedObjects.back().second;
 	GetViewContainer(ActiveLayer).push_back(obj);
 	GetContainer(ActiveLayer).push_back(obj->GetModel());
+	deletedObjects.pop_back();
+
 	obj->SetOgreScene(ogreScene, ogreLevelNode);
 	if (bBoundingBoxes) {
 		MakeBoundingBox(obj);
 void CEditorState::DeleteObject() {
 	if (objSelected == NULL) return;
 
-	// find container and remove object
-	LevelObjectList& objContainer = GetContainer(ActiveLayer);
-	LevelObjectList::iterator it = std::find(objContainer.begin(), objContainer.end(), objSelected->GetModel());
-
-	if (it != objContainer.end())
-		objContainer.erase(it);
-
+	// remove object view; (safe to do because we still have a reference from objSelected
 	OgreViewList& container = GetViewContainer(ActiveLayer);
 	OgreViewList::iterator it2 = std::find(container.begin(), container.end(), objSelected);
 
 
 	// limit size of deleted objects queue
 	while (deletedObjects.size() > 10) {
-		backupObjects[deletedObjects.front()]->GetModel()->RemoveListener(backupObjects[deletedObjects.front()]);
-		backupObjects[deletedObjects.front()] = GameObjects::POgreEntityView();
+		GameObjects::POgreEntityView front = deletedObjects.front().second;
+		backupObjects[front].first->RemoveListener(backupObjects[front].second);
+		backupObjects[front].first.reset();
+		backupObjects[front].second.reset();
+		front.reset();
+
+		deletedObjects.front().first->RemoveListener(deletedObjects.front().second);
 		deletedObjects.pop_front();
 	}
 
-	deletedObjects.push_back(objSelected);
+	deletedObjects.push_back(ObjectViewPair(objSelected->GetModel(),objSelected));
 
 	// remove ogre objects
 	DestroySceneNode(objSelected->GetOgreNode());
 		mBoundingBoxes.erase(objSelected);
 	}
 
+	// find container and remove object model
+	LevelObjectList& objContainer = GetContainer(ActiveLayer);
+	LevelObjectList::iterator it = std::find(objContainer.begin(), objContainer.end(), objSelected->GetModel());
+
+	if (it != objContainer.end())
+		objContainer.erase(it);
+
 	objSelected.reset();
 }
 

File src/States/CEditorState.h

 	typedef std::map<GameObjects::POgreEntityView, GameObjects::POgreBoundsView> OgreViewBoundsMap;
 	typedef std::pair<GameObjects::PLevelObject, GameObjects::POgreEntityView> ObjectViewPair;
 	typedef std::map<GameObjects::PLevelData, ObjectViewPair> ObjectPairMap;
-	typedef std::map<GameObjects::POgreEntityView, GameObjects::POgreEntityView> ViewViewMap;
+	typedef std::map<GameObjects::POgreEntityView, ObjectViewPair> ViewObjectViewPairMap;
 	typedef std::map<std::string, ObjectViewPair> StringObjectPairMap;
-	typedef std::deque<GameObjects::POgreEntityView> OgreViewQueue;
+	typedef std::deque<ObjectViewPair> OgreObjectViewPairQueue;
 
 	enum EditorMode { emMove, emScale, emRotate, emSelect };
 	enum Align { alLeft, alTop, alRight, alBottom, alFront, alBack, alCenter };
 	LevelObjectList dynamicLevelData;
 	OgreViewList dynamicViews;
 
-	ViewViewMap backupObjects;
-	OgreViewQueue deletedObjects;
+	ViewObjectViewPairMap backupObjects;
+	OgreObjectViewPairQueue deletedObjects;
 
 	OgreViewBoundsMap mBoundingBoxes;
 

File src/States/CGameState.cpp

 namespace Game {
 
 CGameState::CGameState()
-	: lTimeShift(0), lTimePaused(0), bRotateCamera(false), fSkyRotation(-90), fAcceleration(1.0), bSkipOneFrame(false)
+	: LevelFileName("level.xml"), lTimeShift(0), lTimePaused(0), bRotateCamera(false), fSkyRotation(-90), fAcceleration(1.0), bSkipOneFrame(false)
 {
 }
 
 	goLevel = GameObjects::CLevelData::Create();
 
 	GameObjects::CXMLReader xmlReader;
-	if (!xmlReader.Read("media/leveldata/level.xml", goLevel.get()))
+	if (!xmlReader.Read("media/leveldata/" + LevelFileName, goLevel.get()))
 		CLog::Get().Write("error loading level data", CLog::logRelease);
 
 	goLevel->Draw(ogreScene);
 	if (e.key == OIS::KC_RIGHT || e.key == OIS::KC_D) goHero->SetSpeed(0);
 	else if (e.key == OIS::KC_SPACE) goHero->FinishJump();
 	else if (e.key == OIS::KC_F) bRotateCamera = false;
-	else if (e.key == OIS::KC_ESCAPE) CTaskManager::GetSingleton().KillAll();
+	else if (e.key == OIS::KC_ESCAPE) CStateManager::GetSingleton().ChangeState("MainMenu");
 	else if (e.key == OIS::KC_RETURN) CStateManager::GetSingleton().ChangeState("MainMenu");
 
 
 		return;
 	}
 
+
+	long lastFrameIndex = CTimerTask::lastFrameIndex + lTimeShift;
 	long thisFrameIndex = CTimerTask::thisFrameIndex + lTimeShift;
 
+	// limit dT to 0.1 (=> dont go below 10 FPS)
+	if (thisFrameIndex - lastFrameIndex > 100) {
+		lTimeShift += thisFrameIndex - lastFrameIndex - 100;
+		lastFrameIndex += thisFrameIndex - lastFrameIndex - 100;
+	}
+
+	float deltaTime = ((float)(thisFrameIndex-lastFrameIndex))/1000.0f;
+
 	if (bLightning && lLightningStarted+200 <= thisFrameIndex) {
 		ogreScene->setAmbientLight(Ogre::ColourValue(0.1, 0.1, 0.1));
 		bLightning = false;
 	goHero->SetConstraints(goLevel->Collision(heroRect, 10.0f));
 */
 
-	goHero->SetSpeed(goHero->GetSpeed() + CTimerTask::dT * fAcceleration);
-	goHero->Update(CTimerTask::dT);
+	goHero->SetSpeed(goHero->GetSpeed() + deltaTime * fAcceleration);
+	goHero->Update(deltaTime);
 
 //	dragonNode->translate(0,0,goHero->GetSpeed() * CTimerTask::dT * 1.01f, Ogre::Node::TS_WORLD);
 
 	goCamera->SetPivot(goHero->GetPosition());
-	goCamera->Update(CTimerTask::dT);
+	goCamera->Update(deltaTime);
 
 	goHud->SetValue<float>("Score", CVideoTask::ogreRenderWindow->getAverageFPS());
 

File src/States/CGameState.h

 
 	virtual void mouseMoved( const OIS::MouseEvent &e );
 
+	std::string LevelFileName;
+
 protected:
 	long lTimeShift;
 	long lTimePaused;

File src/States/CMainMenuState.cpp

 
 bool CMainMenuState::Start() {
 	try {
+		// read level config
+		ReadLevelConfig();
+
+
 		// create new ogre scene
 		CVideoTask::ogreRenderWindow->removeAllViewports();
 
 		ogreViewport = CVideoTask::ogreRenderWindow->addViewport(ogreCamera);
 		ogreCamera->setAspectRatio(Ogre::Real(ogreViewport->getActualWidth()) / Ogre::Real(ogreViewport->getActualHeight()));
 
-		ogreViewport->setBackgroundColour(Ogre::ColourValue(1.0f, 1.0f, 1.0f));
+		ogreViewport->setBackgroundColour(Ogre::ColourValue(189.0f/255.0f, 215.0f/255.0f, 225.0f/255.0f));
 
 		ogreScene->setAmbientLight(Ogre::ColourValue(0.3, 0.3, 0.3));
 
 		panel->add2D((Ogre::OverlayContainer*)mElement);
 		panel->show();
 */
-		overlay = GameObjects::COverlay::Create("MainMenu/Main", "mainmenu", 100);
+		overlay = GameObjects::COverlay::Create("MainMenu", "mainmenu", 100);
 		overlay->Show();
+		overlay->SetText("Main/Level", ">> " + Levels[levelSelected]);
 
 	} catch (Ogre::Exception& ex) {
 		CLog::Get().Write("Main Menu Startup Error: " + ex.getFullDescription(), CLog::logDebug);
 		CTaskManager::GetSingletonPtr()->KillAll();
 	else if (e.key == OIS::KC_E)
 		CStateManager::GetSingleton().ChangeState("Editor");
-	else
-		CStateManager::GetSingleton().ChangeState("Game");
+	else if (e.key == OIS::KC_RETURN) {
+		PState state = CStateManager::GetSingleton().CreateState("Game");
+		if (state) {
+			PGameState gameState = boost::static_pointer_cast<CGameState>(state);
+			gameState->LevelFileName = levelSelected;
+		}
+		CStateManager::GetSingleton().ChangeState(state);
+	} else if (e.key == OIS::KC_LEFT) {
+		LevelMap::iterator it = Levels.find(levelSelected);
+		if (it == Levels.begin()) it = Levels.end();
+		it--;
+		levelSelected = it->first;
+		overlay->SetText("Main/Level", ">> " + it->second);
+	}
+	else if (e.key == OIS::KC_RIGHT) {
+		LevelMap::iterator it = Levels.find(levelSelected);
+		it++;
+		if (it == Levels.end()) it = Levels.begin();
+		levelSelected = it->first;
+		overlay->SetText("Main/Level", ">> " + it->second);
+	}
+}
+
+void CMainMenuState::ReadLevelConfig() {
+	CSettingsManager& sm = CSettingsManager::GetSingleton();
+	std::vector<std::string> levelKeys;
+	std::vector<std::string> configKeys = sm.EnumerateSection("Levels");
+
+	if (configKeys.empty()) return;
+
+
+	// remove all keys with dot
+	std::vector<std::string>::iterator it;
+	for (it = configKeys.begin(); it != configKeys.end(); ++it) {
+		if (it->find(".") == std::string::npos && *it != "")
+			levelKeys.push_back(*it);
+	}
+
+	// load settings for each key
+	for (it = levelKeys.begin(); it != levelKeys.end(); ++it) {
+		std::string key = *it;
+		std::string filename = sm.get<std::string>("Levels", key, "");
+
+		if (filename == "") continue;
+
+		std::string displayname = sm.get<std::string>("Levels", key + ".displayname", filename);
+		Levels[filename] = displayname;
+	}
+
+	levelSelected = Levels.begin()->first;
 }
 
 }

File src/States/CMainMenuState.h

 #include "../Core/CLog.h"
 #include "../GameObjects/CSindbadCharacter.h"
 #include "../GameObjects/COverlay.h"
+#include "CGameState.h"
 
 #include "Ogre.h"
 
 #include "boost/shared_ptr.hpp"
+#include <string>
+#include <map>
 
 namespace Game {
 
 	}
 
 private:
+	void ReadLevelConfig();
+	typedef std::map<std::string, std::string> LevelMap;
+	LevelMap Levels;
+	std::string levelSelected;
+	std::string levelDisplay;
+
 	Ogre::SceneManager* ogreScene;
 	Ogre::Viewport* ogreViewport;
 	Ogre::Camera* ogreCamera;
 	GameObjects::PSindbadCharacter character;
 	GameObjects::POverlay overlay;
 
+
+
 	CMainMenuState();
 };
 

File test/CollisionTest.cpp

 	PLevelObject collider(new CLevelObject());
 
 	PLevelData leveldata(new CLevelData());
-	leveldata->InsertObject(cube, CLevelData::otStatic);
+	leveldata->InsertObject(cube, otStatic);
 
 	// move 2x2 rectangle downwards
 	collider->SetPosition(Ogre::Vector2(0.0f, 3.0f));
 	poly.AddPoint(Ogre::Vector2(4.0f, -2.0f));
 	poly.AddPoint(Ogre::Vector2(4.0f,  2.0f));
 	triangle->SetCollisionPolygon(poly);
-	leveldata->InsertObject(triangle, CLevelData::otStatic);
+	leveldata->InsertObject(triangle, otStatic);
 
 	collider->SetPosition(Ogre::Vector2(0.5f, 0.5f));
 	collider->SetAABBSize(Ogre::Vector2(1.0f, 1.0f));
 	cube = PLevelObject(new CLevelObject());
 	cube->SetPosition(Ogre::Vector2(3.5f, 1.5f));
 	cube->SetAABBSize(Ogre::Vector2::UNIT_SCALE);
-	leveldata->InsertObject(cube, CLevelData::otStatic);
+	leveldata->InsertObject(cube, otStatic);
 	translation = leveldata->ResolveCollision(collider, Ogre::Vector2(5.0f, 0.0f));
 	FLOAT_CHECK_EQUAL(translation, Ogre::Vector2(2.0f, 1.0f));