34 files changed, 1949 insertions, 497 deletions

diff --git a/dep/recastnavigation/Detour/CMakeLists.txt b/dep/recastnavigation/Detour/CMakeLists.txt
index b7c0853efc4..5f3542e96b9 100644
--- a/dep/recastnavigation/Detour/CMakeLists.txt
+++ b/dep/recastnavigation/Detour/CMakeLists.txt
@@ -9,13 +9,14 @@
 # implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 
 set(Detour_STAT_SRCS
-    DetourAlloc.cpp 
-    DetourCommon.cpp 
-    DetourNavMesh.cpp 
-    DetourNavMeshBuilder.cpp 
-    DetourNavMeshQuery.cpp 
-    DetourNode.cpp 
+    Source/DetourAlloc.cpp 
+    Source/DetourCommon.cpp 
+    Source/DetourNavMesh.cpp 
+    Source/DetourNavMeshBuilder.cpp 
+    Source/DetourNavMeshQuery.cpp 
+    Source/DetourNode.cpp 
 )
+include_directories(Include)
 
 if(WIN32)
   include_directories(
diff --git a/dep/recastnavigation/Detour/DetourAlloc.h b/dep/recastnavigation/Detour/Include/DetourAlloc.h
index e814b62a716..e814b62a716 100644
--- a/dep/recastnavigation/Detour/DetourAlloc.h
+++ b/dep/recastnavigation/Detour/Include/DetourAlloc.h
diff --git a/dep/recastnavigation/Detour/DetourAssert.h b/dep/recastnavigation/Detour/Include/DetourAssert.h
index 3cf652288fa..3cf652288fa 100644
--- a/dep/recastnavigation/Detour/DetourAssert.h
+++ b/dep/recastnavigation/Detour/Include/DetourAssert.h
diff --git a/dep/recastnavigation/Detour/DetourCommon.h b/dep/recastnavigation/Detour/Include/DetourCommon.h
index 0888614ea9b..0888614ea9b 100644
--- a/dep/recastnavigation/Detour/DetourCommon.h
+++ b/dep/recastnavigation/Detour/Include/DetourCommon.h
diff --git a/dep/recastnavigation/Detour/DetourNavMesh.h b/dep/recastnavigation/Detour/Include/DetourNavMesh.h
index cdd473f1aff..782ddbc2edd 100644
--- a/dep/recastnavigation/Detour/DetourNavMesh.h
+++ b/dep/recastnavigation/Detour/Include/DetourNavMesh.h
@@ -119,6 +119,25 @@ enum dtStraightPathOptions
 	DT_STRAIGHTPATH_ALL_CROSSINGS = 0x02,	///< Add a vertex at every polygon edge crossing.
 };
 
+
+/// Options for dtNavMeshQuery::findPath
+enum dtFindPathOptions
+{
+	DT_FINDPATH_LOW_QUALITY_FAR = 0x01,		///< [provisional] trade quality for performance far from the origin. The idea is that by then a new query will be issued
+	DT_FINDPATH_ANY_ANGLE	= 0x02,			///< use raycasts during pathfind to "shortcut" (raycast still consider costs)
+};
+
+/// Options for dtNavMeshQuery::raycast
+enum dtRaycastOptions
+{
+	DT_RAYCAST_USE_COSTS = 0x01,		///< Raycast should calculate movement cost along the ray and fill RaycastHit::cost
+};
+
+
+/// Limit raycasting during any angle pahfinding
+/// The limit is given as a multiple of the character radius
+static const float DT_RAY_CAST_LIMIT_PROPORTIONS = 50.0f;
+
 /// Flags representing the type of a navigation mesh polygon.
 enum dtPolyTypes
 {
diff --git a/dep/recastnavigation/Detour/DetourNavMeshBuilder.h b/dep/recastnavigation/Detour/Include/DetourNavMeshBuilder.h
index c80d1717630..c80d1717630 100644
--- a/dep/recastnavigation/Detour/DetourNavMeshBuilder.h
+++ b/dep/recastnavigation/Detour/Include/DetourNavMeshBuilder.h
diff --git a/dep/recastnavigation/Detour/DetourNavMeshQuery.h b/dep/recastnavigation/Detour/Include/DetourNavMeshQuery.h
index 4a5112c9eb9..c7b360dcdc6 100644
--- a/dep/recastnavigation/Detour/DetourNavMeshQuery.h
+++ b/dep/recastnavigation/Detour/Include/DetourNavMeshQuery.h
@@ -41,6 +41,10 @@ class dtQueryFilter
 public:
 	dtQueryFilter();
 	
+#ifdef DT_VIRTUAL_QUERYFILTER
+	virtual ~dtQueryFilter() { }
+#endif
+	
 	/// Returns true if the polygon can be visited.  (I.e. Is traversable.)
 	///  @param[in]		ref		The reference id of the polygon test.
 	///  @param[in]		tile	The tile containing the polygon.
@@ -115,6 +119,34 @@ public:
 
 };
 
+
+
+/// Provides information about raycast hit
+/// filled by dtNavMeshQuery::raycast
+/// @ingroup detour
+struct dtRaycastHit
+{
+	/// The hit parameter. (FLT_MAX if no wall hit.)
+	float t; 
+	
+	/// hitNormal	The normal of the nearest wall hit. [(x, y, z)]
+	float hitNormal[3];
+	
+	/// Pointer to an array of reference ids of the visited polygons. [opt]
+	dtPolyRef* path;
+	
+	/// The number of visited polygons. [opt]
+	int pathCount;
+
+	/// The maximum number of polygons the @p path array can hold.
+	int maxPath;
+
+	///  The cost of the path until hit.
+	float pathCost;
+};
+
+
+
 /// Provides the ability to perform pathfinding related queries against
 /// a navigation mesh.
 /// @ingroup detour
@@ -179,10 +211,11 @@ public:
 	///  @param[in]		startPos	A position within the start polygon. [(x, y, z)]
 	///  @param[in]		endPos		A position within the end polygon. [(x, y, z)]
 	///  @param[in]		filter		The polygon filter to apply to the query.
+	///  @param[in]		options		query options (see: #dtFindPathOptions)
 	/// @returns The status flags for the query.
 	dtStatus initSlicedFindPath(dtPolyRef startRef, dtPolyRef endRef,
 								const float* startPos, const float* endPos,
-								const dtQueryFilter* filter);
+								const dtQueryFilter* filter, const unsigned int options = 0);
 
 	/// Updates an in-progress sliced path query.
 	///  @param[in]		maxIter		The maximum number of iterations to perform.
@@ -308,6 +341,7 @@ public:
 	
 	/// Casts a 'walkability' ray along the surface of the navigation mesh from 
 	/// the start position toward the end position.
+	/// @note A wrapper around raycast(..., RaycastHit*). Retained for backward compatibility.
 	///  @param[in]		startRef	The reference id of the start polygon.
 	///  @param[in]		startPos	A position within the start polygon representing 
 	///  							the start of the ray. [(x, y, z)]
@@ -323,6 +357,22 @@ public:
 					 const dtQueryFilter* filter,
 					 float* t, float* hitNormal, dtPolyRef* path, int* pathCount, const int maxPath) const;
 	
+	/// Casts a 'walkability' ray along the surface of the navigation mesh from 
+	/// the start position toward the end position.
+	///  @param[in]		startRef	The reference id of the start polygon.
+	///  @param[in]		startPos	A position within the start polygon representing 
+	///  							the start of the ray. [(x, y, z)]
+	///  @param[in]		endPos		The position to cast the ray toward. [(x, y, z)]
+	///  @param[in]		filter		The polygon filter to apply to the query.
+	///  @param[in]		flags		govern how the raycast behaves. See dtRaycastOptions
+	///  @param[out]	hit			Pointer to a raycast hit structure which will be filled by the results.
+	///  @param[in]		prevRef		parent of start ref. Used during for cost calculation [opt]
+	/// @returns The status flags for the query.
+	dtStatus raycast(dtPolyRef startRef, const float* startPos, const float* endPos,
+					 const dtQueryFilter* filter, const unsigned int options,
+					 dtRaycastHit* hit, dtPolyRef prevRef = 0) const;
+
+
 	/// Finds the distance from the specified position to the nearest polygon wall.
 	///  @param[in]		startRef		The reference id of the polygon containing @p centerPos.
 	///  @param[in]		centerPos		The center of the search circle. [(x, y, z)]
@@ -463,6 +513,8 @@ private:
 		dtPolyRef startRef, endRef;
 		float startPos[3], endPos[3];
 		const dtQueryFilter* filter;
+		unsigned int options;
+		float raycastLimitSqr;
 	};
 	dtQueryData m_query;				///< Sliced query state.
 
diff --git a/dep/recastnavigation/Detour/DetourNode.h b/dep/recastnavigation/Detour/Include/DetourNode.h
index b68c922d038..6fefdc8e0f3 100644
--- a/dep/recastnavigation/Detour/DetourNode.h
+++ b/dep/recastnavigation/Detour/Include/DetourNode.h
@@ -25,6 +25,7 @@ enum dtNodeFlags
 {
 	DT_NODE_OPEN = 0x01,
 	DT_NODE_CLOSED = 0x02,
+	DT_NODE_PARENT_DETACHED = 0x04, // parent of the node is not adjacent. Found using raycast.
 };
 
 typedef unsigned short dtNodeIndex;
@@ -35,12 +36,17 @@ struct dtNode
 	float pos[3];				///< Position of the node.
 	float cost;					///< Cost from previous node to current node.
 	float total;				///< Cost up to the node.
-	unsigned int pidx : 30;		///< Index to parent node.
-	unsigned int flags : 2;		///< Node flags 0/open/closed.
+	unsigned int pidx : 24;		///< Index to parent node.
+	unsigned int state : 2;		///< extra state information. A polyRef can have multiple nodes with different extra info. see DT_MAX_STATES_PER_NODE
+	unsigned int flags : 3;		///< Node flags. A combination of dtNodeFlags.
 	dtPolyRef id;				///< Polygon ref the node corresponds to.
 };
 
 
+static const int DT_MAX_STATES_PER_NODE = 4;	// number of extra states per node. See dtNode::state
+
+
+
 class dtNodePool
 {
 public:
@@ -48,8 +54,12 @@ public:
 	~dtNodePool();
 	inline void operator=(const dtNodePool&) {}
 	void clear();
-	dtNode* getNode(dtPolyRef id);
-	dtNode* findNode(dtPolyRef id);
+
+	// Get a dtNode by ref and extra state information. If there is none then - allocate
+	// There can be more than one node for the same polyRef but with different extra state information
+	dtNode* getNode(dtPolyRef id, unsigned char state=0);	
+	dtNode* findNode(dtPolyRef id, unsigned char state);
+	unsigned int findNodes(dtPolyRef id, dtNode** nodes, const int maxNodes);
 
 	inline unsigned int getNodeIdx(const dtNode* node) const
 	{
@@ -82,6 +92,7 @@ public:
 	inline int getHashSize() const { return m_hashSize; }
 	inline dtNodeIndex getFirst(int bucket) const { return m_first[bucket]; }
 	inline dtNodeIndex getNext(int i) const { return m_next[i]; }
+	inline int getNodeCount() const { return m_nodeCount; }
 	
 private:
 	
diff --git a/dep/recastnavigation/Detour/DetourStatus.h b/dep/recastnavigation/Detour/Include/DetourStatus.h
index af822c4a92d..af822c4a92d 100644
--- a/dep/recastnavigation/Detour/DetourStatus.h
+++ b/dep/recastnavigation/Detour/Include/DetourStatus.h
diff --git a/dep/recastnavigation/Detour/DetourAlloc.cpp b/dep/recastnavigation/Detour/Source/DetourAlloc.cpp
index 5f671df5bdb..5f671df5bdb 100644
--- a/dep/recastnavigation/Detour/DetourAlloc.cpp
+++ b/dep/recastnavigation/Detour/Source/DetourAlloc.cpp
diff --git a/dep/recastnavigation/Detour/DetourCommon.cpp b/dep/recastnavigation/Detour/Source/DetourCommon.cpp
index b5700f5930b..b5700f5930b 100644
--- a/dep/recastnavigation/Detour/DetourCommon.cpp
+++ b/dep/recastnavigation/Detour/Source/DetourCommon.cpp
diff --git a/dep/recastnavigation/Detour/DetourNavMesh.cpp b/dep/recastnavigation/Detour/Source/DetourNavMesh.cpp
index 51740509950..51740509950 100644
--- a/dep/recastnavigation/Detour/DetourNavMesh.cpp
+++ b/dep/recastnavigation/Detour/Source/DetourNavMesh.cpp
diff --git a/dep/recastnavigation/Detour/DetourNavMeshBuilder.cpp b/dep/recastnavigation/Detour/Source/DetourNavMeshBuilder.cpp
index 9d8471b96a1..9d8471b96a1 100644
--- a/dep/recastnavigation/Detour/DetourNavMeshBuilder.cpp
+++ b/dep/recastnavigation/Detour/Source/DetourNavMeshBuilder.cpp
diff --git a/dep/recastnavigation/Detour/DetourNavMeshQuery.cpp b/dep/recastnavigation/Detour/Source/DetourNavMeshQuery.cpp
index f1709dfd4cf..ec3a2946ea5 100644
--- a/dep/recastnavigation/Detour/DetourNavMeshQuery.cpp
+++ b/dep/recastnavigation/Detour/Source/DetourNavMeshQuery.cpp
@@ -1011,7 +1011,13 @@ dtStatus dtNavMeshQuery::findPath(dtPolyRef startRef, dtPolyRef endRef,
 			if (!filter->passFilter(neighbourRef, neighbourTile, neighbourPoly))
 				continue;
 
-			dtNode* neighbourNode = m_nodePool->getNode(neighbourRef);
+			// deal explicitly with crossing tile boundaries
+			unsigned char crossSide = 0;
+			if (bestTile->links[i].side != 0xff)
+				crossSide = bestTile->links[i].side >> 1;
+
+			// get the node
+			dtNode* neighbourNode = m_nodePool->getNode(neighbourRef, crossSide);
 			if (!neighbourNode)
 			{
 				status |= DT_OUT_OF_NODES;
@@ -1139,7 +1145,7 @@ dtStatus dtNavMeshQuery::findPath(dtPolyRef startRef, dtPolyRef endRef,
 ///
 dtStatus dtNavMeshQuery::initSlicedFindPath(dtPolyRef startRef, dtPolyRef endRef,
 											const float* startPos, const float* endPos,
-											const dtQueryFilter* filter)
+											const dtQueryFilter* filter, const unsigned int options)
 {
 	dtAssert(m_nav);
 	dtAssert(m_nodePool);
@@ -1153,6 +1159,8 @@ dtStatus dtNavMeshQuery::initSlicedFindPath(dtPolyRef startRef, dtPolyRef endRef
 	dtVcopy(m_query.startPos, startPos);
 	dtVcopy(m_query.endPos, endPos);
 	m_query.filter = filter;
+	m_query.options = options;
+	m_query.raycastLimitSqr = FLT_MAX;
 	
 	if (!startRef || !endRef)
 		return DT_FAILURE | DT_INVALID_PARAM;
@@ -1161,6 +1169,16 @@ dtStatus dtNavMeshQuery::initSlicedFindPath(dtPolyRef startRef, dtPolyRef endRef
 	if (!m_nav->isValidPolyRef(startRef) || !m_nav->isValidPolyRef(endRef))
 		return DT_FAILURE | DT_INVALID_PARAM;
 
+	// trade quality with performance?
+	if (options & DT_FINDPATH_ANY_ANGLE)
+	{
+		// limiting to several times the character radius yields nice results. It is not sensitive 
+		// so it is enough to compute it from the first tile.
+		const dtMeshTile* tile = m_nav->getTileByRef(startRef);
+		float agentRadius = tile->header->walkableRadius;
+		m_query.raycastLimitSqr = dtSqr(agentRadius * DT_RAY_CAST_LIMIT_PROPORTIONS);
+	}
+
 	if (startRef == endRef)
 	{
 		m_query.status = DT_SUCCESS;
@@ -1197,6 +1215,9 @@ dtStatus dtNavMeshQuery::updateSlicedFindPath(const int maxIter, int* doneIters)
 		m_query.status = DT_FAILURE;
 		return DT_FAILURE;
 	}
+
+	dtRaycastHit rayHit;
+	rayHit.maxPath = 0;
 		
 	int iter = 0;
 	while (iter < maxIter && !m_openList->empty())
@@ -1233,15 +1254,22 @@ dtStatus dtNavMeshQuery::updateSlicedFindPath(const int maxIter, int* doneIters)
 			return m_query.status;
 		}
 		
-		// Get parent poly and tile.
-		dtPolyRef parentRef = 0;
+		// Get parent and grand parent poly and tile.
+		dtPolyRef parentRef = 0, grandpaRef = 0;
 		const dtMeshTile* parentTile = 0;
 		const dtPoly* parentPoly = 0;
+		dtNode* parentNode = 0;
 		if (bestNode->pidx)
-			parentRef = m_nodePool->getNodeAtIdx(bestNode->pidx)->id;
+		{
+			parentNode = m_nodePool->getNodeAtIdx(bestNode->pidx);
+			parentRef = parentNode->id;
+			if (parentNode->pidx)
+				grandpaRef = m_nodePool->getNodeAtIdx(parentNode->pidx)->id;
+		}
 		if (parentRef)
 		{
-			if (dtStatusFailed(m_nav->getTileAndPolyByRef(parentRef, &parentTile, &parentPoly)))
+			bool invalidParent = dtStatusFailed(m_nav->getTileAndPolyByRef(parentRef, &parentTile, &parentPoly));
+			if (invalidParent || (grandpaRef && !m_nav->isValidPolyRef(grandpaRef)) )
 			{
 				// The polygon has disappeared during the sliced query, fail.
 				m_query.status = DT_FAILURE;
@@ -1250,6 +1278,14 @@ dtStatus dtNavMeshQuery::updateSlicedFindPath(const int maxIter, int* doneIters)
 				return m_query.status;
 			}
 		}
+
+		// decide whether to test raycast to previous nodes
+		bool tryLOS = false;
+		if (m_query.options & DT_FINDPATH_ANY_ANGLE)
+		{
+			if ((parentRef != 0) && (dtVdistSqr(parentNode->pos, bestNode->pos) < m_query.raycastLimitSqr))
+				tryLOS = true;
+		}
 		
 		for (unsigned int i = bestPoly->firstLink; i != DT_NULL_LINK; i = bestTile->links[i].next)
 		{
@@ -1268,13 +1304,22 @@ dtStatus dtNavMeshQuery::updateSlicedFindPath(const int maxIter, int* doneIters)
 			if (!m_query.filter->passFilter(neighbourRef, neighbourTile, neighbourPoly))
 				continue;
 			
-			dtNode* neighbourNode = m_nodePool->getNode(neighbourRef);
+			// deal explicitly with crossing tile boundaries
+			unsigned char crossSide = 0;
+			if (bestTile->links[i].side != 0xff)
+				crossSide = bestTile->links[i].side >> 1;
+
+			dtNode* neighbourNode = m_nodePool->getNode(neighbourRef, crossSide);
 			if (!neighbourNode)
 			{
 				m_query.status |= DT_OUT_OF_NODES;
 				continue;
 			}
 			
+			// do not expand to nodes that were already visited from the same parent
+			if (neighbourNode->pidx != 0 && neighbourNode->pidx == bestNode->pidx)
+				continue;
+
 			// If the node is visited the first time, calculate node position.
 			if (neighbourNode->flags == 0)
 			{
@@ -1287,30 +1332,44 @@ dtStatus dtNavMeshQuery::updateSlicedFindPath(const int maxIter, int* doneIters)
 			float cost = 0;
 			float heuristic = 0;
 			
-			// Special case for last node.
-			if (neighbourRef == m_query.endRef)
+			// raycast parent
+			bool foundShortCut = false;
+			rayHit.pathCost = rayHit.t = 0;
+			if (tryLOS)
 			{
-				// Cost
+				raycast(parentRef, parentNode->pos, neighbourNode->pos, m_query.filter, DT_RAYCAST_USE_COSTS, &rayHit, grandpaRef);
+				foundShortCut = rayHit.t >= 1.0f;
+			}
+
+			// update move cost
+			if (foundShortCut)
+			{
+				// shortcut found using raycast. Using shorter cost instead
+				cost = parentNode->cost + rayHit.pathCost;
+			}
+			else
+			{
+				// No shortcut found.
 				const float curCost = m_query.filter->getCost(bestNode->pos, neighbourNode->pos,
 															  parentRef, parentTile, parentPoly,
-															  bestRef, bestTile, bestPoly,
-															  neighbourRef, neighbourTile, neighbourPoly);
+															bestRef, bestTile, bestPoly,
+															neighbourRef, neighbourTile, neighbourPoly);
+				cost = bestNode->cost + curCost;
+			}
+
+			// Special case for last node.
+			if (neighbourRef == m_query.endRef)
+			{
 				const float endCost = m_query.filter->getCost(neighbourNode->pos, m_query.endPos,
 															  bestRef, bestTile, bestPoly,
 															  neighbourRef, neighbourTile, neighbourPoly,
 															  0, 0, 0);
 				
-				cost = bestNode->cost + curCost + endCost;
+				cost = cost + endCost;
 				heuristic = 0;
 			}
 			else
 			{
-				// Cost
-				const float curCost = m_query.filter->getCost(bestNode->pos, neighbourNode->pos,
-															  parentRef, parentTile, parentPoly,
-															  bestRef, bestTile, bestPoly,
-															  neighbourRef, neighbourTile, neighbourPoly);
-				cost = bestNode->cost + curCost;
 				heuristic = dtVdist(neighbourNode->pos, m_query.endPos)*H_SCALE;
 			}
 			
@@ -1324,11 +1383,13 @@ dtStatus dtNavMeshQuery::updateSlicedFindPath(const int maxIter, int* doneIters)
 				continue;
 			
 			// Add or update the node.
-			neighbourNode->pidx = m_nodePool->getNodeIdx(bestNode);
+			neighbourNode->pidx = foundShortCut ? bestNode->pidx : m_nodePool->getNodeIdx(bestNode);
 			neighbourNode->id = neighbourRef;
-			neighbourNode->flags = (neighbourNode->flags & ~DT_NODE_CLOSED);
+			neighbourNode->flags = (neighbourNode->flags & ~(DT_NODE_CLOSED | DT_NODE_PARENT_DETACHED));
 			neighbourNode->cost = cost;
 			neighbourNode->total = total;
+			if (foundShortCut)
+				neighbourNode->flags = (neighbourNode->flags | DT_NODE_PARENT_DETACHED);
 			
 			if (neighbourNode->flags & DT_NODE_OPEN)
 			{
@@ -1392,11 +1453,15 @@ dtStatus dtNavMeshQuery::finalizeSlicedFindPath(dtPolyRef* path, int* pathCount,
 		
 		dtNode* prev = 0;
 		dtNode* node = m_query.lastBestNode;
+		int prevRay = 0;
 		do
 		{
 			dtNode* next = m_nodePool->getNodeAtIdx(node->pidx);
 			node->pidx = m_nodePool->getNodeIdx(prev);
 			prev = node;
+			int nextRay = node->flags & DT_NODE_PARENT_DETACHED; // keep track of whether parent is not adjacent (i.e. due to raycast shortcut)
+			node->flags = (node->flags & ~DT_NODE_PARENT_DETACHED) | prevRay; // and store it in the reversed path's node
+			prevRay = nextRay;
 			node = next;
 		}
 		while (node);
@@ -1405,13 +1470,31 @@ dtStatus dtNavMeshQuery::finalizeSlicedFindPath(dtPolyRef* path, int* pathCount,
 		node = prev;
 		do
 		{
-			path[n++] = node->id;
-			if (n >= maxPath)
+			dtNode* next = m_nodePool->getNodeAtIdx(node->pidx);
+			dtStatus status = 0;
+			if (node->flags & DT_NODE_PARENT_DETACHED)
 			{
-				m_query.status |= DT_BUFFER_TOO_SMALL;
+				float t, normal[3];
+				int m;
+				status = raycast(node->id, node->pos, next->pos, m_query.filter, &t, normal, path+n, &m, maxPath-n);
+				n += m;
+				// raycast ends on poly boundary and the path might include the next poly boundary.
+				if (path[n-1] == next->id)
+					n--; // remove to avoid duplicates
+			}
+			else
+			{
+				path[n++] = node->id;
+				if (n >= maxPath)
+					status = DT_BUFFER_TOO_SMALL;
+			}
+
+			if (status & DT_STATUS_DETAIL_MASK)
+			{
+				m_query.status |= status & DT_STATUS_DETAIL_MASK;
 				break;
 			}
-			node = m_nodePool->getNodeAtIdx(node->pidx);
+			node = next;
 		}
 		while (node);
 	}
@@ -1457,7 +1540,7 @@ dtStatus dtNavMeshQuery::finalizeSlicedFindPathPartial(const dtPolyRef* existing
 		dtNode* node = 0;
 		for (int i = existingSize-1; i >= 0; --i)
 		{
-			node = m_nodePool->findNode(existing[i]);
+			m_nodePool->findNodes(existing[i], &node, 1);
 			if (node)
 				break;
 		}
@@ -1470,11 +1553,15 @@ dtStatus dtNavMeshQuery::finalizeSlicedFindPathPartial(const dtPolyRef* existing
 		}
 		
 		// Reverse the path.
+		int prevRay = 0;
 		do
 		{
 			dtNode* next = m_nodePool->getNodeAtIdx(node->pidx);
 			node->pidx = m_nodePool->getNodeIdx(prev);
 			prev = node;
+			int nextRay = node->flags & DT_NODE_PARENT_DETACHED; // keep track of whether parent is not adjacent (i.e. due to raycast shortcut)
+			node->flags = (node->flags & ~DT_NODE_PARENT_DETACHED) | prevRay; // and store it in the reversed path's node
+			prevRay = nextRay;
 			node = next;
 		}
 		while (node);
@@ -1483,13 +1570,31 @@ dtStatus dtNavMeshQuery::finalizeSlicedFindPathPartial(const dtPolyRef* existing
 		node = prev;
 		do
 		{
-			path[n++] = node->id;
-			if (n >= maxPath)
+			dtNode* next = m_nodePool->getNodeAtIdx(node->pidx);
+			dtStatus status = 0;
+			if (node->flags & DT_NODE_PARENT_DETACHED)
+			{
+				float t, normal[3];
+				int m;
+				status = raycast(node->id, node->pos, next->pos, m_query.filter, &t, normal, path+n, &m, maxPath-n);
+				n += m;
+				// raycast ends on poly boundary and the path might include the next poly boundary.
+				if (path[n-1] == next->id)
+					n--; // remove to avoid duplicates
+			}
+			else
+			{
+				path[n++] = node->id;
+				if (n >= maxPath)
+					status = DT_BUFFER_TOO_SMALL;
+			}
+
+			if (status & DT_STATUS_DETAIL_MASK)
 			{
-				m_query.status |= DT_BUFFER_TOO_SMALL;
+				m_query.status |= status & DT_STATUS_DETAIL_MASK;
 				break;
 			}
-			node = m_nodePool->getNodeAtIdx(node->pidx);
+			node = next;
 		}
 		while (node);
 	}
@@ -2161,6 +2266,8 @@ dtStatus dtNavMeshQuery::getEdgeMidPoint(dtPolyRef from, const dtPoly* fromPoly,
 	return DT_SUCCESS;
 }
 
+
+
 /// @par
 ///
 /// This method is meant to be used for quick, short distance checks.
@@ -2203,73 +2310,144 @@ dtStatus dtNavMeshQuery::raycast(dtPolyRef startRef, const float* startPos, cons
 								 const dtQueryFilter* filter,
 								 float* t, float* hitNormal, dtPolyRef* path, int* pathCount, const int maxPath) const
 {
-	dtAssert(m_nav);
+	dtRaycastHit hit;
+	hit.path = path;
+	hit.maxPath = maxPath;
+
+	dtStatus status = raycast(startRef, startPos, endPos, filter, 0, &hit);
 	
-	*t = 0;
+	*t = hit.t;
+	if (hitNormal)
+		dtVcopy(hitNormal, hit.hitNormal);
 	if (pathCount)
-		*pathCount = 0;
+		*pathCount = hit.pathCount;
+
+	return status;
+}
+
+
+/// @par
+///
+/// This method is meant to be used for quick, short distance checks.
+///
+/// If the path array is too small to hold the result, it will be filled as 
+/// far as possible from the start postion toward the end position.
+///
+/// <b>Using the Hit Parameter t of RaycastHit</b>
+/// 
+/// If the hit parameter is a very high value (FLT_MAX), then the ray has hit 
+/// the end position. In this case the path represents a valid corridor to the 
+/// end position and the value of @p hitNormal is undefined.
+///
+/// If the hit parameter is zero, then the start position is on the wall that 
+/// was hit and the value of @p hitNormal is undefined.
+///
+/// If 0 < t < 1.0 then the following applies:
+///
+/// @code
+/// distanceToHitBorder = distanceToEndPosition * t
+/// hitPoint = startPos + (endPos - startPos) * t
+/// @endcode
+///
+/// <b>Use Case Restriction</b>
+///
+/// The raycast ignores the y-value of the end position. (2D check.) This 
+/// places significant limits on how it can be used. For example:
+///
+/// Consider a scene where there is a main floor with a second floor balcony 
+/// that hangs over the main floor. So the first floor mesh extends below the 
+/// balcony mesh. The start position is somewhere on the first floor. The end 
+/// position is on the balcony.
+///
+/// The raycast will search toward the end position along the first floor mesh. 
+/// If it reaches the end position's xz-coordinates it will indicate FLT_MAX
+/// (no wall hit), meaning it reached the end position. This is one example of why
+/// this method is meant for short distance checks.
+///
+dtStatus dtNavMeshQuery::raycast(dtPolyRef startRef, const float* startPos, const float* endPos,
+								 const dtQueryFilter* filter, const unsigned int options,
+								 dtRaycastHit* hit, dtPolyRef prevRef) const
+{
+	dtAssert(m_nav);
 	
+	hit->t = 0;
+	hit->pathCount = 0;
+	hit->pathCost = 0;
+
 	// Validate input
 	if (!startRef || !m_nav->isValidPolyRef(startRef))
 		return DT_FAILURE | DT_INVALID_PARAM;
+	if (prevRef && !m_nav->isValidPolyRef(prevRef))
+		return DT_FAILURE | DT_INVALID_PARAM;
 	
-	dtPolyRef curRef = startRef;
-	float verts[DT_VERTS_PER_POLYGON*3];	
+	float dir[3], curPos[3], lastPos[3];
+	float verts[DT_VERTS_PER_POLYGON*3+3];	
 	int n = 0;
-	
-	hitNormal[0] = 0;
-	hitNormal[1] = 0;
-	hitNormal[2] = 0;
-	
+
+	dtVcopy(curPos, startPos);
+	dtVsub(dir, endPos, startPos);
+	dtVset(hit->hitNormal, 0, 0, 0);
+
 	dtStatus status = DT_SUCCESS;
-	
+
+	const dtMeshTile* prevTile, *tile, *nextTile;
+	const dtPoly* prevPoly, *poly, *nextPoly;
+	dtPolyRef curRef, nextRef;
+
+	// The API input has been checked already, skip checking internal data.
+	nextRef = curRef = startRef;
+	tile = 0;
+	poly = 0;
+	m_nav->getTileAndPolyByRefUnsafe(curRef, &tile, &poly);
+	nextTile = prevTile = tile;
+	nextPoly = prevPoly = poly;
+	if (prevRef)
+		m_nav->getTileAndPolyByRefUnsafe(prevRef, &prevTile, &prevPoly);
+
 	while (curRef)
 	{
 		// Cast ray against current polygon.
 		
-		// The API input has been cheked already, skip checking internal data.
-		const dtMeshTile* tile = 0;
-		const dtPoly* poly = 0;
-		m_nav->getTileAndPolyByRefUnsafe(curRef, &tile, &poly);
-		
 		// Collect vertices.
 		int nv = 0;
 		for (int i = 0; i < (int)poly->vertCount; ++i)
 		{
 			dtVcopy(&verts[nv*3], &tile->verts[poly->verts[i]*3]);
 			nv++;
-		}		
+		}
 		
 		float tmin, tmax;
 		int segMin, segMax;
 		if (!dtIntersectSegmentPoly2D(startPos, endPos, verts, nv, tmin, tmax, segMin, segMax))
 		{
 			// Could not hit the polygon, keep the old t and report hit.
-			if (pathCount)
-				*pathCount = n;
+			hit->pathCount = n;
 			return status;
 		}
 		// Keep track of furthest t so far.
-		if (tmax > *t)
-			*t = tmax;
+		if (tmax > hit->t)
+			hit->t = tmax;
 		
 		// Store visited polygons.
-		if (n < maxPath)
-			path[n++] = curRef;
+		if (n < hit->maxPath)
+			hit->path[n++] = curRef;
 		else
 			status |= DT_BUFFER_TOO_SMALL;
-		
+
 		// Ray end is completely inside the polygon.
 		if (segMax == -1)
 		{
-			*t = FLT_MAX;
-			if (pathCount)
-				*pathCount = n;
+			hit->t = FLT_MAX;
+			hit->pathCount = n;
+			
+			// add the cost
+			if (options & DT_RAYCAST_USE_COSTS)
+				hit->pathCost += filter->getCost(curPos, endPos, prevRef, prevTile, prevPoly, curRef, tile, poly, curRef, tile, poly);
 			return status;
 		}
-		
+
 		// Follow neighbours.
-		dtPolyRef nextRef = 0;
+		nextRef = 0;
 		
 		for (unsigned int i = poly->firstLink; i != DT_NULL_LINK; i = tile->links[i].next)
 		{
@@ -2280,8 +2458,8 @@ dtStatus dtNavMeshQuery::raycast(dtPolyRef startRef, const float* startPos, cons
 				continue;
 			
 			// Get pointer to the next polygon.
-			const dtMeshTile* nextTile = 0;
-			const dtPoly* nextPoly = 0;
+			nextTile = 0;
+			nextPoly = 0;
 			m_nav->getTileAndPolyByRefUnsafe(link->ref, &nextTile, &nextPoly);
 			
 			// Skip off-mesh connections.
@@ -2349,6 +2527,24 @@ dtStatus dtNavMeshQuery::raycast(dtPolyRef startRef, const float* startPos, cons
 			}
 		}
 		
+		// add the cost
+		if (options & DT_RAYCAST_USE_COSTS)
+		{
+			// compute the intersection point at the furthest end of the polygon
+			// and correct the height (since the raycast moves in 2d)
+			dtVcopy(lastPos, curPos);
+			dtVmad(curPos, startPos, dir, hit->t);
+			float* e1 = &verts[segMax*3];
+			float* e2 = &verts[((segMax+1)%nv)*3];
+			float eDir[3], diff[3];
+			dtVsub(eDir, e2, e1);
+			dtVsub(diff, curPos, e1);
+			float s = dtSqr(eDir[0]) > dtSqr(eDir[2]) ? diff[0] / eDir[0] : diff[2] / eDir[2];
+			curPos[1] = e1[1] + eDir[1] * s;
+
+			hit->pathCost += filter->getCost(lastPos, curPos, prevRef, prevTile, prevPoly, curRef, tile, poly, nextRef, nextTile, nextPoly);
+		}
+
 		if (!nextRef)
 		{
 			// No neighbour, we hit a wall.
@@ -2360,22 +2556,25 @@ dtStatus dtNavMeshQuery::raycast(dtPolyRef startRef, const float* startPos, cons
 			const float* vb = &verts[b*3];
 			const float dx = vb[0] - va[0];
 			const float dz = vb[2] - va[2];
-			hitNormal[0] = dz;
-			hitNormal[1] = 0;
-			hitNormal[2] = -dx;
-			dtVnormalize(hitNormal);
+			hit->hitNormal[0] = dz;
+			hit->hitNormal[1] = 0;
+			hit->hitNormal[2] = -dx;
+			dtVnormalize(hit->hitNormal);
 			
-			if (pathCount)
-				*pathCount = n;
+			hit->pathCount = n;
 			return status;
 		}
-		
+
 		// No hit, advance to neighbour polygon.
+		prevRef = curRef;
 		curRef = nextRef;
+		prevTile = tile;
+		tile = nextTile;
+		prevPoly = poly;
+		poly = nextPoly;
 	}
 	
-	if (pathCount)
-		*pathCount = n;
+	hit->pathCount = n;
 	
 	return status;
 }
@@ -3333,6 +3532,15 @@ bool dtNavMeshQuery::isValidPolyRef(dtPolyRef ref, const dtQueryFilter* filter)
 bool dtNavMeshQuery::isInClosedList(dtPolyRef ref) const
 {
 	if (!m_nodePool) return false;
-	const dtNode* node = m_nodePool->findNode(ref);
-	return node && node->flags & DT_NODE_CLOSED;
+	
+	dtNode* nodes[DT_MAX_STATES_PER_NODE];
+	int n= m_nodePool->findNodes(ref, nodes, DT_MAX_STATES_PER_NODE);
+
+	for (int i=0; i<n; i++)
+	{
+		if (nodes[i]->flags & DT_NODE_CLOSED)
+			return true;
+	}		
+
+	return false;
 }
diff --git a/dep/recastnavigation/Detour/DetourNode.cpp b/dep/recastnavigation/Detour/Source/DetourNode.cpp
index 4c8215e20d0..1d1897708f4 100644
--- a/dep/recastnavigation/Detour/DetourNode.cpp
+++ b/dep/recastnavigation/Detour/Source/DetourNode.cpp
@@ -71,27 +71,46 @@ void dtNodePool::clear()
 	m_nodeCount = 0;
 }
 
-dtNode* dtNodePool::findNode(dtPolyRef id)
+unsigned int dtNodePool::findNodes(dtPolyRef id, dtNode** nodes, const int maxNodes)
 {
+	int n = 0;
 	unsigned int bucket = dtHashRef(id) & (m_hashSize-1);
 	dtNodeIndex i = m_first[bucket];
 	while (i != DT_NULL_IDX)
 	{
 		if (m_nodes[i].id == id)
+		{
+			if (n >= maxNodes)
+				return n;
+			nodes[n++] = &m_nodes[i];
+		}
+		i = m_next[i];
+	}
+
+	return n;
+}
+
+dtNode* dtNodePool::findNode(dtPolyRef id, unsigned char state)
+{
+	unsigned int bucket = dtHashRef(id) & (m_hashSize-1);
+	dtNodeIndex i = m_first[bucket];
+	while (i != DT_NULL_IDX)
+	{
+		if (m_nodes[i].id == id && m_nodes[i].state == state)
 			return &m_nodes[i];
 		i = m_next[i];
 	}
 	return 0;
 }
 
-dtNode* dtNodePool::getNode(dtPolyRef id)
+dtNode* dtNodePool::getNode(dtPolyRef id, unsigned char state)
 {
 	unsigned int bucket = dtHashRef(id) & (m_hashSize-1);
 	dtNodeIndex i = m_first[bucket];
 	dtNode* node = 0;
 	while (i != DT_NULL_IDX)
 	{
-		if (m_nodes[i].id == id)
+		if (m_nodes[i].id == id && m_nodes[i].state == state)
 			return &m_nodes[i];
 		i = m_next[i];
 	}
@@ -108,6 +127,7 @@ dtNode* dtNodePool::getNode(dtPolyRef id)
 	node->cost = 0;
 	node->total = 0;
 	node->id = id;
+	node->state = state;
 	node->flags = 0;
 	
 	m_next[i] = m_first[bucket];
diff --git a/dep/recastnavigation/Readme.txt b/dep/recastnavigation/Readme.txt
index 0c2f7b1675f..1383b01d582 100644
--- a/dep/recastnavigation/Readme.txt
+++ b/dep/recastnavigation/Readme.txt
@@ -32,9 +32,6 @@ the regions as simple polygons.
 The toolset code is located in the Recast folder and demo application using the Recast
 toolset is located in the RecastDemo folder.
 
-The project files with this distribution can be compiled with Microsoft Visual C++ 2008
-(you can download it for free) and XCode 3.1.
-
 
 Detour
 
@@ -43,78 +40,7 @@ Recast is accompanied with Detour, path-finding and spatial reasoning toolkit. Y
 Detour offers simple static navigation mesh which is suitable for many simple cases, as well as tiled navigation mesh which allows you to plug in and out pieces of the mesh. The tiled mesh allows to create systems where you stream new navigation data in and out as the player progresses the level, or you may regenerate tiles as the world changes. 
 
 
-Latest code available at http://code.google.com/p/recastnavigation/
-
-
---
-
-Release Notes
-
-----------------
-* Recast 1.4
-  Released August 24th, 2009
-
-- Added detail height mesh generation (RecastDetailMesh.cpp) for single,
-  tiled statmeshes as well as tilemesh.
-- Added feature to contour tracing which detects extra vertices along
-  tile edges which should be removed later.
-- Changed the tiled stat mesh preprocess, so that it first generated
-  polymeshes per tile and finally combines them.
-- Fixed bug in the GUI code where invisible buttons could be pressed.
-
-----------------
-* Recast 1.31
-  Released July 24th, 2009
-
-- Better cost and heuristic functions.
-- Fixed tile navmesh raycast on tile borders.
-
-----------------
-* Recast 1.3
-  Released July 14th, 2009
-
-- Added dtTileNavMesh which allows to dynamically add and remove navmesh pieces at runtime.
-- Renamed stat navmesh types to dtStat* (i.e. dtPoly is now dtStatPoly).
-- Moved common code used by tile and stat navmesh to DetourNode.h/cpp and DetourCommon.h/cpp.
-- Refactores the demo code.
-
-----------------
-* Recast 1.2
-  Released June 17th, 2009
-
-- Added tiled mesh generation. The tiled generation allows to generate navigation for
-  much larger worlds, it removes some of the artifacts that comes from distance fields
-  in open areas, and allows later streaming and dynamic runtime generation
-- Improved and added some debug draw modes
-- API change: The helper function rcBuildNavMesh does not exists anymore,
-  had to change few internal things to cope with the tiled processing,
-  similar API functionality will be added later once the tiled process matures
-- The demo is getting way too complicated, need to split demos
-- Fixed several filtering functions so that the mesh is tighter to the geometry,
-  sometimes there could be up error up to tow voxel units close to walls,
-  now it should be just one.
-
-----------------
-* Recast 1.1
-  Released April 11th, 2009
-
-This is the first release of Detour.
-
-----------------
-* Recast 1.0
-  Released March 29th, 2009
-
-This is the first release of Recast.
-
-The process is not always as robust as I would wish. The watershed phase sometimes swallows tiny islands
-which are close to edges. These droppings are handled in rcBuildContours, but the code is not
-particularly robust either.
-
-Another non-robust case is when portal contours (contours shared between two regions) are always
-assumed to be straight. That can lead to overlapping contours specially when the level has
-large open areas.
-
-
+Latest code available at https://github.com/memononen/recastnavigation
 
 Mikko Mononen
 memon@inside.org
diff --git a/dep/recastnavigation/Recast/CMakeLists.txt b/dep/recastnavigation/Recast/CMakeLists.txt
index 10028f8535f..f4869bf8773 100644
--- a/dep/recastnavigation/Recast/CMakeLists.txt
+++ b/dep/recastnavigation/Recast/CMakeLists.txt
@@ -9,18 +9,20 @@
 # implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 
 set(Recast_STAT_SRCS
-    Recast.cpp 
-    RecastAlloc.cpp 
-    RecastArea.cpp 
-    RecastContour.cpp 
-    RecastFilter.cpp 
-	RecastLayers.cpp
-    RecastMesh.cpp 
-    RecastMeshDetail.cpp 
-    RecastRasterization.cpp 
-    RecastRegion.cpp 
+    Source/Recast.cpp 
+    Source/RecastAlloc.cpp 
+    Source/RecastArea.cpp 
+    Source/RecastContour.cpp 
+    Source/RecastFilter.cpp 
+	Source/RecastLayers.cpp
+    Source/RecastMesh.cpp 
+    Source/RecastMeshDetail.cpp 
+    Source/RecastRasterization.cpp 
+    Source/RecastRegion.cpp 
 )
 
+include_directories(Include)
+
 if(WIN32)
   include_directories(
     ${CMAKE_SOURCE_DIR}/dep/zlib
diff --git a/dep/recastnavigation/Recast/Recast.h b/dep/recastnavigation/Recast/Include/Recast.h
index 3f4ae96d1c9..66974cdbcc3 100644
--- a/dep/recastnavigation/Recast/Recast.h
+++ b/dep/recastnavigation/Recast/Include/Recast.h
@@ -338,7 +338,7 @@ struct rcHeightfieldLayer
 	int maxy;					///< The maximum y-bounds of usable data. (Along the z-axis.)
 	int hmin;					///< The minimum height bounds of usable data. (Along the y-axis.)
 	int hmax;					///< The maximum height bounds of usable data. (Along the y-axis.)
-	unsigned char* heights;		///< The heightfield. [Size: (width - borderSize*2) * (h - borderSize*2)]
+	unsigned char* heights;		///< The heightfield. [Size: width * height]
 	unsigned char* areas;		///< Area ids. [Size: Same as #heights]
 	unsigned char* cons;		///< Packed neighbor connection information. [Size: Same as #heights]
 };
@@ -969,7 +969,7 @@ void rcMarkCylinderArea(rcContext* ctx, const float* pos,
 ///  @returns True if the operation completed successfully.
 bool rcBuildDistanceField(rcContext* ctx, rcCompactHeightfield& chf);
 
-/// Builds region data for the heightfield using watershed partitioning. 
+/// Builds region data for the heightfield using watershed partitioning.
 ///  @ingroup recast
 ///  @param[in,out]	ctx				The build context to use during the operation.
 ///  @param[in,out]	chf				A populated compact heightfield.
@@ -983,6 +983,18 @@ bool rcBuildDistanceField(rcContext* ctx, rcCompactHeightfield& chf);
 bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf,
 					const int borderSize, const int minRegionArea, const int mergeRegionArea);
 
+/// Builds region data for the heightfield by partitioning the heightfield in non-overlapping layers.
+///  @ingroup recast
+///  @param[in,out]	ctx				The build context to use during the operation.
+///  @param[in,out]	chf				A populated compact heightfield.
+///  @param[in]		borderSize		The size of the non-navigable border around the heightfield.
+///  								[Limit: >=0] [Units: vx]
+///  @param[in]		minRegionArea	The minimum number of cells allowed to form isolated island areas.
+///  								[Limit: >=0] [Units: vx].
+///  @returns True if the operation completed successfully.
+bool rcBuildLayerRegions(rcContext* ctx, rcCompactHeightfield& chf,
+						 const int borderSize, const int minRegionArea);
+
 /// Builds region data for the heightfield using simple monotone partitioning.
 ///  @ingroup recast 
 ///  @param[in,out]	ctx				The build context to use during the operation.
@@ -997,7 +1009,6 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf,
 bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf,
 							const int borderSize, const int minRegionArea, const int mergeRegionArea);
 
-
 /// Sets the neighbor connection data for the specified direction.
 ///  @param[in]		s		The span to update.
 ///  @param[in]		dir		The direction to set. [Limits: 0 <= value < 4]
diff --git a/dep/recastnavigation/Recast/RecastAlloc.h b/dep/recastnavigation/Recast/Include/RecastAlloc.h
index 438be9ea56b..438be9ea56b 100644
--- a/dep/recastnavigation/Recast/RecastAlloc.h
+++ b/dep/recastnavigation/Recast/Include/RecastAlloc.h
diff --git a/dep/recastnavigation/Recast/RecastAssert.h b/dep/recastnavigation/Recast/Include/RecastAssert.h
index 2aca0d9a14f..2aca0d9a14f 100644
--- a/dep/recastnavigation/Recast/RecastAssert.h
+++ b/dep/recastnavigation/Recast/Include/RecastAssert.h
diff --git a/dep/recastnavigation/Recast/Recast.cpp b/dep/recastnavigation/Recast/Source/Recast.cpp
index b9d86036c3f..b9d86036c3f 100644
--- a/dep/recastnavigation/Recast/Recast.cpp
+++ b/dep/recastnavigation/Recast/Source/Recast.cpp
diff --git a/dep/recastnavigation/Recast/RecastAlloc.cpp b/dep/recastnavigation/Recast/Source/RecastAlloc.cpp
index b5ec1516146..b5ec1516146 100644
--- a/dep/recastnavigation/Recast/RecastAlloc.cpp
+++ b/dep/recastnavigation/Recast/Source/RecastAlloc.cpp
diff --git a/dep/recastnavigation/Recast/RecastArea.cpp b/dep/recastnavigation/Recast/Source/RecastArea.cpp
index 1a338cd9b8c..1a338cd9b8c 100644
--- a/dep/recastnavigation/Recast/RecastArea.cpp
+++ b/dep/recastnavigation/Recast/Source/RecastArea.cpp
diff --git a/dep/recastnavigation/Recast/RecastContour.cpp b/dep/recastnavigation/Recast/Source/RecastContour.cpp
index 5c324bcedfe..8aa9d1d92a1 100644
--- a/dep/recastnavigation/Recast/RecastContour.cpp
+++ b/dep/recastnavigation/Recast/Source/RecastContour.cpp
@@ -20,6 +20,7 @@
 #include <math.h>
 #include <string.h>
 #include <stdio.h>
+#include <stdlib.h>
 #include "Recast.h"
 #include "RecastAlloc.h"
 #include "RecastAssert.h"
@@ -36,7 +37,7 @@ static int getCornerHeight(int x, int y, int i, int dir,
 	unsigned int regs[4] = {0,0,0,0};
 	
 	// Combine region and area codes in order to prevent
-	// border vertices which are in between two areas to be removed. 
+	// border vertices which are in between two areas to be removed.
 	regs[0] = chf.spans[i].reg | (chf.areas[i] << 16);
 	
 	if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
@@ -187,27 +188,6 @@ static float distancePtSeg(const int x, const int z,
 						   const int px, const int pz,
 						   const int qx, const int qz)
 {
-/*	float pqx = (float)(qx - px);
-	float pqy = (float)(qy - py);
-	float pqz = (float)(qz - pz);
-	float dx = (float)(x - px);
-	float dy = (float)(y - py);
-	float dz = (float)(z - pz);
-	float d = pqx*pqx + pqy*pqy + pqz*pqz;
-	float t = pqx*dx + pqy*dy + pqz*dz;
-	if (d > 0)
-		t /= d;
-	if (t < 0)
-		t = 0;
-	else if (t > 1)
-		t = 1;
-	
-	dx = px + t*pqx - x;
-	dy = py + t*pqy - y;
-	dz = pz + t*pqz - z;
-	
-	return dx*dx + dy*dy + dz*dz;*/
-
 	float pqx = (float)(qx - px);
 	float pqz = (float)(qz - pz);
 	float dx = (float)(x - px);
@@ -257,13 +237,13 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified,
 				simplified.push(points[i*4+2]);
 				simplified.push(i);
 			}
-		}       
+		}
 	}
 	
 	if (simplified.size() == 0)
 	{
 		// If there is no connections at all,
-		// create some initial points for the simplification process. 
+		// create some initial points for the simplification process.
 		// Find lower-left and upper-right vertices of the contour.
 		int llx = points[0];
 		int lly = points[1];
@@ -311,19 +291,19 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified,
 	{
 		int ii = (i+1) % (simplified.size()/4);
 		
-		const int ax = simplified[i*4+0];
-		const int az = simplified[i*4+2];
-		const int ai = simplified[i*4+3];
-		
-		const int bx = simplified[ii*4+0];
-		const int bz = simplified[ii*4+2];
-		const int bi = simplified[ii*4+3];
+		int ax = simplified[i*4+0];
+		int az = simplified[i*4+2];
+		int ai = simplified[i*4+3];
+
+		int bx = simplified[ii*4+0];
+		int bz = simplified[ii*4+2];
+		int bi = simplified[ii*4+3];
 
 		// Find maximum deviation from the segment.
 		float maxd = 0;
 		int maxi = -1;
 		int ci, cinc, endi;
-		
+
 		// Traverse the segment in lexilogical order so that the
 		// max deviation is calculated similarly when traversing
 		// opposite segments.
@@ -338,6 +318,8 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified,
 			cinc = pn-1;
 			ci = (bi+cinc) % pn;
 			endi = ai;
+			rcSwap(ax, bx);
+			rcSwap(az, bz);
 		}
 		
 		// Tessellate only outer edges or edges between areas.
@@ -397,11 +379,11 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified,
 			const int bx = simplified[ii*4+0];
 			const int bz = simplified[ii*4+2];
 			const int bi = simplified[ii*4+3];
-
+			
 			// Find maximum deviation from the segment.
 			int maxi = -1;
 			int ci = (ai+1) % pn;
-
+			
 			// Tessellate only outer edges or edges between areas.
 			bool tess = false;
 			// Wall edges.
@@ -469,32 +451,6 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified,
 	
 }
 
-static void removeDegenerateSegments(rcIntArray& simplified)
-{
-	// Remove adjacent vertices which are equal on xz-plane,
-	// or else the triangulator will get confused.
-	for (int i = 0; i < simplified.size()/4; ++i)
-	{
-		int ni = i+1;
-		if (ni >= (simplified.size()/4))
-			ni = 0;
-			
-		if (simplified[i*4+0] == simplified[ni*4+0] &&
-			simplified[i*4+2] == simplified[ni*4+2])
-		{
-			// Degenerate segment, remove.
-			for (int j = i; j < simplified.size()/4-1; ++j)
-			{
-				simplified[j*4+0] = simplified[(j+1)*4+0];
-				simplified[j*4+1] = simplified[(j+1)*4+1];
-				simplified[j*4+2] = simplified[(j+1)*4+2];
-				simplified[j*4+3] = simplified[(j+1)*4+3];
-			}
-			simplified.resize(simplified.size()-4);
-		}
-	}
-}
-
 static int calcAreaOfPolygon2D(const int* verts, const int nverts)
 {
 	int area = 0;
@@ -507,54 +463,155 @@ static int calcAreaOfPolygon2D(const int* verts, const int nverts)
 	return (area+1) / 2;
 }
 
-inline bool ileft(const int* a, const int* b, const int* c)
+// TODO: these are the same as in RecastMesh.cpp, consider using the same.
+
+inline int prev(int i, int n) { return i-1 >= 0 ? i-1 : n-1; }
+inline int next(int i, int n) { return i+1 < n ? i+1 : 0; }
+
+inline int area2(const int* a, const int* b, const int* c)
+{
+	return (b[0] - a[0]) * (c[2] - a[2]) - (c[0] - a[0]) * (b[2] - a[2]);
+}
+
+//	Exclusive or: true iff exactly one argument is true.
+//	The arguments are negated to ensure that they are 0/1
+//	values.  Then the bitwise Xor operator may apply.
+//	(This idea is due to Michael Baldwin.)
+inline bool xorb(bool x, bool y)
+{
+	return !x ^ !y;
+}
+
+// Returns true iff c is strictly to the left of the directed
+// line through a to b.
+inline bool left(const int* a, const int* b, const int* c)
+{
+	return area2(a, b, c) < 0;
+}
+
+inline bool leftOn(const int* a, const int* b, const int* c)
+{
+	return area2(a, b, c) <= 0;
+}
+
+inline bool collinear(const int* a, const int* b, const int* c)
+{
+	return area2(a, b, c) == 0;
+}
+
+//	Returns true iff ab properly intersects cd: they share
+//	a point interior to both segments.  The properness of the
+//	intersection is ensured by using strict leftness.
+static bool intersectProp(const int* a, const int* b, const int* c, const int* d)
+{
+	// Eliminate improper cases.
+	if (collinear(a,b,c) || collinear(a,b,d) ||
+		collinear(c,d,a) || collinear(c,d,b))
+		return false;
+	
+	return xorb(left(a,b,c), left(a,b,d)) && xorb(left(c,d,a), left(c,d,b));
+}
+
+// Returns T iff (a,b,c) are collinear and point c lies
+// on the closed segement ab.
+static bool between(const int* a, const int* b, const int* c)
+{
+	if (!collinear(a, b, c))
+		return false;
+	// If ab not vertical, check betweenness on x; else on y.
+	if (a[0] != b[0])
+		return	((a[0] <= c[0]) && (c[0] <= b[0])) || ((a[0] >= c[0]) && (c[0] >= b[0]));
+	else
+		return	((a[2] <= c[2]) && (c[2] <= b[2])) || ((a[2] >= c[2]) && (c[2] >= b[2]));
+}
+
+// Returns true iff segments ab and cd intersect, properly or improperly.
+static bool intersect(const int* a, const int* b, const int* c, const int* d)
+{
+	if (intersectProp(a, b, c, d))
+		return true;
+	else if (between(a, b, c) || between(a, b, d) ||
+			 between(c, d, a) || between(c, d, b))
+		return true;
+	else
+		return false;
+}
+
+static bool vequal(const int* a, const int* b)
+{
+	return a[0] == b[0] && a[2] == b[2];
+}
+
+static bool intersectSegCountour(const int* d0, const int* d1, int i, int n, const int* verts)
 {
-	return (b[0] - a[0]) * (c[2] - a[2]) - (c[0] - a[0]) * (b[2] - a[2]) <= 0;
+	// For each edge (k,k+1) of P
+	for (int k = 0; k < n; k++)
+	{
+		int k1 = next(k, n);
+		// Skip edges incident to i.
+		if (i == k || i == k1)
+			continue;
+		const int* p0 = &verts[k * 4];
+		const int* p1 = &verts[k1 * 4];
+		if (vequal(d0, p0) || vequal(d1, p0) || vequal(d0, p1) || vequal(d1, p1))
+			continue;
+		
+		if (intersect(d0, d1, p0, p1))
+			return true;
+	}
+	return false;
 }
 
-static void getClosestIndices(const int* vertsa, const int nvertsa,
-							  const int* vertsb, const int nvertsb,
-							  int& ia, int& ib)
+static bool	inCone(int i, int n, const int* verts, const int* pj)
 {
-	int closestDist = 0xfffffff;
-	ia = -1, ib = -1;
-	for (int i = 0; i < nvertsa; ++i)
+	const int* pi = &verts[i * 4];
+	const int* pi1 = &verts[next(i, n) * 4];
+	const int* pin1 = &verts[prev(i, n) * 4];
+	
+	// If P[i] is a convex vertex [ i+1 left or on (i-1,i) ].
+	if (leftOn(pin1, pi, pi1))
+		return left(pi, pj, pin1) && left(pj, pi, pi1);
+	// Assume (i-1,i,i+1) not collinear.
+	// else P[i] is reflex.
+	return !(leftOn(pi, pj, pi1) && leftOn(pj, pi, pin1));
+}
+
+
+static void removeDegenerateSegments(rcIntArray& simplified)
+{
+	// Remove adjacent vertices which are equal on xz-plane,
+	// or else the triangulator will get confused.
+	int npts = simplified.size()/4;
+	for (int i = 0; i < npts; ++i)
 	{
-		const int in = (i+1) % nvertsa;
-		const int ip = (i+nvertsa-1) % nvertsa;
-		const int* va = &vertsa[i*4];
-		const int* van = &vertsa[in*4];
-		const int* vap = &vertsa[ip*4];
+		int ni = next(i, npts);
 		
-		for (int j = 0; j < nvertsb; ++j)
+		if (vequal(&simplified[i*4], &simplified[ni*4]))
 		{
-			const int* vb = &vertsb[j*4];
-			// vb must be "infront" of va.
-			if (ileft(vap,va,vb) && ileft(va,van,vb))
+			// Degenerate segment, remove.
+			for (int j = i; j < simplified.size()/4-1; ++j)
 			{
-				const int dx = vb[0] - va[0];
-				const int dz = vb[2] - va[2];
-				const int d = dx*dx + dz*dz;
-				if (d < closestDist)
-				{
-					ia = i;
-					ib = j;
-					closestDist = d;
-				}
+				simplified[j*4+0] = simplified[(j+1)*4+0];
+				simplified[j*4+1] = simplified[(j+1)*4+1];
+				simplified[j*4+2] = simplified[(j+1)*4+2];
+				simplified[j*4+3] = simplified[(j+1)*4+3];
 			}
+			simplified.resize(simplified.size()-4);
+			npts--;
 		}
 	}
 }
 
+
 static bool mergeContours(rcContour& ca, rcContour& cb, int ia, int ib)
 {
 	const int maxVerts = ca.nverts + cb.nverts + 2;
 	int* verts = (int*)rcAlloc(sizeof(int)*maxVerts*4, RC_ALLOC_PERM);
 	if (!verts)
 		return false;
-
+	
 	int nv = 0;
-
+	
 	// Copy contour A.
 	for (int i = 0; i <= ca.nverts; ++i)
 	{
@@ -582,7 +639,7 @@ static bool mergeContours(rcContour& ca, rcContour& cb, int ia, int ib)
 	rcFree(ca.verts);
 	ca.verts = verts;
 	ca.nverts = nv;
-
+	
 	rcFree(cb.verts);
 	cb.verts = 0;
 	cb.nverts = 0;
@@ -590,18 +647,179 @@ static bool mergeContours(rcContour& ca, rcContour& cb, int ia, int ib)
 	return true;
 }
 
+struct rcContourHole
+{
+	rcContour* contour;
+	int minx, minz, leftmost;
+};
+
+struct rcContourRegion
+{
+	rcContour* outline;
+	rcContourHole* holes;
+	int nholes;
+};
+
+struct rcPotentialDiagonal
+{
+	int vert;
+	int dist;
+};
+
+// Finds the lowest leftmost vertex of a contour.
+static void findLeftMostVertex(rcContour* contour, int* minx, int* minz, int* leftmost)
+{
+	*minx = contour->verts[0];
+	*minz = contour->verts[2];
+	*leftmost = 0;
+	for (int i = 1; i < contour->nverts; i++)
+	{
+		const int x = contour->verts[i*4+0];
+		const int z = contour->verts[i*4+2];
+		if (x < *minx || (x == *minx && z < *minz))
+		{
+			*minx = x;
+			*minz = z;
+			*leftmost = i;
+		}
+	}
+}
+
+static int compareHoles(const void* va, const void* vb)
+{
+	const rcContourHole* a = (const rcContourHole*)va;
+	const rcContourHole* b = (const rcContourHole*)vb;
+	if (a->minx == b->minx)
+	{
+		if (a->minz < b->minz)
+			return -1;
+		if (a->minz > b->minz)
+			return 1;
+	}
+	else
+	{
+		if (a->minx < b->minx)
+			return -1;
+		if (a->minx > b->minx)
+			return 1;
+	}
+	return 0;
+}
+
+
+static int compareDiagDist(const void* va, const void* vb)
+{
+	const rcPotentialDiagonal* a = (const rcPotentialDiagonal*)va;
+	const rcPotentialDiagonal* b = (const rcPotentialDiagonal*)vb;
+	if (a->dist < b->dist)
+		return -1;
+	if (a->dist > b->dist)
+		return 1;
+	return 0;
+}
+
+
+static void mergeRegionHoles(rcContext* ctx, rcContourRegion& region)
+{
+	// Sort holes from left to right.
+	for (int i = 0; i < region.nholes; i++)
+		findLeftMostVertex(region.holes[i].contour, &region.holes[i].minx, &region.holes[i].minz, &region.holes[i].leftmost);
+	
+	qsort(region.holes, region.nholes, sizeof(rcContourHole), compareHoles);
+	
+	int maxVerts = region.outline->nverts;
+	for (int i = 0; i < region.nholes; i++)
+		maxVerts += region.holes[i].contour->nverts;
+	
+	rcScopedDelete<rcPotentialDiagonal> diags = (rcPotentialDiagonal*)rcAlloc(sizeof(rcPotentialDiagonal)*maxVerts, RC_ALLOC_TEMP);
+	if (!diags)
+	{
+		ctx->log(RC_LOG_WARNING, "mergeRegionHoles: Failed to allocated diags %d.", maxVerts);
+		return;
+	}
+	
+	rcContour* outline = region.outline;
+	
+	// Merge holes into the outline one by one.
+	for (int i = 0; i < region.nholes; i++)
+	{
+		rcContour* hole = region.holes[i].contour;
+		
+		int index = -1;
+		int bestVertex = region.holes[i].leftmost;
+		for (int iter = 0; iter < hole->nverts; iter++)
+		{
+			// Find potential diagonals.
+			// The 'best' vertex must be in the cone described by 3 cosequtive vertices of the outline.
+			// ..o j-1
+			//   |
+			//   |   * best
+			//   |
+			// j o-----o j+1
+			//         :
+			int ndiags = 0;
+			const int* corner = &hole->verts[bestVertex*4];
+			for (int j = 0; j < outline->nverts; j++)
+			{
+				if (inCone(j, outline->nverts, outline->verts, corner))
+				{
+					int dx = outline->verts[j*4+0] - corner[0];
+					int dz = outline->verts[j*4+2] - corner[2];
+					diags[ndiags].vert = j;
+					diags[ndiags].dist = dx*dx + dz*dz;
+					ndiags++;
+				}
+			}
+			// Sort potential diagonals by distance, we want to make the connection as short as possible.
+			qsort(diags, ndiags, sizeof(rcPotentialDiagonal), compareDiagDist);
+			
+			// Find a diagonal that is not intersecting the outline not the remaining holes.
+			index = -1;
+			for (int j = 0; j < ndiags; j++)
+			{
+				const int* pt = &outline->verts[diags[j].vert*4];
+				bool intersect = intersectSegCountour(pt, corner, diags[i].vert, outline->nverts, outline->verts);
+				for (int k = i; k < region.nholes && !intersect; k++)
+					intersect |= intersectSegCountour(pt, corner, -1, region.holes[k].contour->nverts, region.holes[k].contour->verts);
+				if (!intersect)
+				{
+					index = diags[j].vert;
+					break;
+				}
+			}
+			// If found non-intersecting diagonal, stop looking.
+			if (index != -1)
+				break;
+			// All the potential diagonals for the current vertex were intersecting, try next vertex.
+			bestVertex = (bestVertex + 1) % hole->nverts;
+		}
+		
+		if (index == -1)
+		{
+			ctx->log(RC_LOG_WARNING, "mergeHoles: Failed to find merge points for %p and %p.", region.outline, hole);
+			continue;
+		}
+		if (!mergeContours(*region.outline, *hole, index, bestVertex))
+		{
+			ctx->log(RC_LOG_WARNING, "mergeHoles: Failed to merge contours %p and %p.", region.outline, hole);
+			continue;
+		}
+	}
+}
+
+
 /// @par
 ///
 /// The raw contours will match the region outlines exactly. The @p maxError and @p maxEdgeLen
 /// parameters control how closely the simplified contours will match the raw contours.
 ///
-/// Simplified contours are generated such that the vertices for portals between areas match up. 
+/// Simplified contours are generated such that the vertices for portals between areas match up.
 /// (They are considered mandatory vertices.)
 ///
 /// Setting @p maxEdgeLength to zero will disabled the edge length feature.
-/// 
+///
 /// See the #rcConfig documentation for more information on the configuration parameters.
-/// 
+///
 /// @see rcAllocContourSet, rcCompactHeightfield, rcContourSet, rcConfig
 bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf,
 					 const float maxError, const int maxEdgeLen,
@@ -704,17 +922,17 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf,
 				
 				verts.resize(0);
 				simplified.resize(0);
-
+				
 				ctx->startTimer(RC_TIMER_BUILD_CONTOURS_TRACE);
 				walkContour(x, y, i, chf, flags, verts);
 				ctx->stopTimer(RC_TIMER_BUILD_CONTOURS_TRACE);
-
+				
 				ctx->startTimer(RC_TIMER_BUILD_CONTOURS_SIMPLIFY);
 				simplifyContour(verts, simplified, maxError, maxEdgeLen, buildFlags);
 				removeDegenerateSegments(simplified);
 				ctx->stopTimer(RC_TIMER_BUILD_CONTOURS_SIMPLIFY);
 				
-
+				
 				// Store region->contour remap info.
 				// Create contour.
 				if (simplified.size()/4 >= 3)
@@ -722,7 +940,7 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf,
 					if (cset.nconts >= maxContours)
 					{
 						// Allocate more contours.
-						// This can happen when there are tiny holes in the heightfield.
+						// This happens when a region has holes.
 						const int oldMax = maxContours;
 						maxContours *= 2;
 						rcContour* newConts = (rcContour*)rcAlloc(sizeof(rcContour)*maxContours, RC_ALLOC_PERM);
@@ -735,10 +953,10 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf,
 						}
 						rcFree(cset.conts);
 						cset.conts = newConts;
-					
+						
 						ctx->log(RC_LOG_WARNING, "rcBuildContours: Expanding max contours from %d to %d.", oldMax, maxContours);
 					}
-						
+					
 					rcContour* cont = &cset.conts[cset.nconts++];
 					
 					cont->nverts = simplified.size()/4;
@@ -779,17 +997,6 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf,
 						}
 					}
 					
-/*					cont->cx = cont->cy = cont->cz = 0;
-					for (int i = 0; i < cont->nverts; ++i)
-					{
-						cont->cx += cont->verts[i*4+0];
-						cont->cy += cont->verts[i*4+1];
-						cont->cz += cont->verts[i*4+2];
-					}
-					cont->cx /= cont->nverts;
-					cont->cy /= cont->nverts;
-					cont->cz /= cont->nverts;*/
-					
 					cont->reg = reg;
 					cont->area = area;
 				}
@@ -797,52 +1004,100 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf,
 		}
 	}
 	
-	// Check and merge droppings.
-	// Sometimes the previous algorithms can fail and create several contours
-	// per area. This pass will try to merge the holes into the main region.
-	for (int i = 0; i < cset.nconts; ++i)
+	// Merge holes if needed.
+	if (cset.nconts > 0)
 	{
-		rcContour& cont = cset.conts[i];
-		// Check if the contour is would backwards.
-		if (calcAreaOfPolygon2D(cont.verts, cont.nverts) < 0)
+		// Calculate winding of all polygons.
+		rcScopedDelete<char> winding = (char*)rcAlloc(sizeof(char)*cset.nconts, RC_ALLOC_TEMP);
+		if (!winding)
 		{
-			// Find another contour which has the same region ID.
-			int mergeIdx = -1;
-			for (int j = 0; j < cset.nconts; ++j)
+			ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'hole' (%d).", cset.nconts);
+			return false;
+		}
+		int nholes = 0;
+		for (int i = 0; i < cset.nconts; ++i)
+		{
+			rcContour& cont = cset.conts[i];
+			// If the contour is wound backwards, it is a hole.
+			winding[i] = calcAreaOfPolygon2D(cont.verts, cont.nverts) < 0 ? -1 : 1;
+			if (winding[i] < 0)
+				nholes++;
+		}
+		
+		if (nholes > 0)
+		{
+			// Collect outline contour and holes contours per region.
+			// We assume that there is one outline and multiple holes.
+			const int nregions = chf.maxRegions+1;
+			rcScopedDelete<rcContourRegion> regions = (rcContourRegion*)rcAlloc(sizeof(rcContourRegion)*nregions, RC_ALLOC_TEMP);
+			if (!regions)
+			{
+				ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'regions' (%d).", nregions);
+				return false;
+			}
+			memset(regions, 0, sizeof(rcContourRegion)*nregions);
+			
+			rcScopedDelete<rcContourHole> holes = (rcContourHole*)rcAlloc(sizeof(rcContourHole)*cset.nconts, RC_ALLOC_TEMP);
+			if (!holes)
+			{
+				ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'holes' (%d).", cset.nconts);
+				return false;
+			}
+			memset(holes, 0, sizeof(rcContourHole)*cset.nconts);
+			
+			for (int i = 0; i < cset.nconts; ++i)
 			{
-				if (i == j) continue;
-				if (cset.conts[j].nverts && cset.conts[j].reg == cont.reg)
+				rcContour& cont = cset.conts[i];
+				// Positively would contours are outlines, negative holes.
+				if (winding[i] > 0)
 				{
-					// Make sure the polygon is correctly oriented.
-					if (calcAreaOfPolygon2D(cset.conts[j].verts, cset.conts[j].nverts))
-					{
-						mergeIdx = j;
-						break;
-					}
+					if (regions[cont.reg].outline)
+						ctx->log(RC_LOG_ERROR, "rcBuildContours: Multiple outlines for region %d.", cont.reg);
+					regions[cont.reg].outline = &cont;
+				}
+				else
+				{
+					regions[cont.reg].nholes++;
 				}
 			}
-			if (mergeIdx == -1)
+			int index = 0;
+			for (int i = 0; i < nregions; i++)
 			{
-				ctx->log(RC_LOG_WARNING, "rcBuildContours: Could not find merge target for bad contour %d.", i);
+				if (regions[i].nholes > 0)
+				{
+					regions[i].holes = &holes[index];
+					index += regions[i].nholes;
+					regions[i].nholes = 0;
+				}
 			}
-			else
+			for (int i = 0; i < cset.nconts; ++i)
+			{
+				rcContour& cont = cset.conts[i];
+				rcContourRegion& reg = regions[cont.reg];
+				if (winding[i] < 0)
+					reg.holes[reg.nholes++].contour = &cont;
+			}
+			
+			// Finally merge each regions holes into the outline.
+			for (int i = 0; i < nregions; i++)
 			{
-				rcContour& mcont = cset.conts[mergeIdx];
-				// Merge by closest points.
-				int ia = 0, ib = 0;
-				getClosestIndices(mcont.verts, mcont.nverts, cont.verts, cont.nverts, ia, ib);
-				if (ia == -1 || ib == -1)
+				rcContourRegion& reg = regions[i];
+				if (!reg.nholes) continue;
+				
+				if (reg.outline)
 				{
-					ctx->log(RC_LOG_WARNING, "rcBuildContours: Failed to find merge points for %d and %d.", i, mergeIdx);
-					continue;
+					mergeRegionHoles(ctx, reg);
 				}
-				if (!mergeContours(mcont, cont, ia, ib))
+				else
 				{
-					ctx->log(RC_LOG_WARNING, "rcBuildContours: Failed to merge contours %d and %d.", i, mergeIdx);
-					continue;
+					// The region does not have an outline.
+					// This can happen if the contour becaomes selfoverlapping because of
+					// too aggressive simplification settings.
+					ctx->log(RC_LOG_ERROR, "rcBuildContours: Bad outline for region %d, contour simplification is likely too aggressive.", i);
 				}
 			}
 		}
+		
 	}
 	
 	ctx->stopTimer(RC_TIMER_BUILD_CONTOURS);
diff --git a/dep/recastnavigation/Recast/RecastFilter.cpp b/dep/recastnavigation/Recast/Source/RecastFilter.cpp
index bf985c362c9..bf985c362c9 100644
--- a/dep/recastnavigation/Recast/RecastFilter.cpp
+++ b/dep/recastnavigation/Recast/Source/RecastFilter.cpp
diff --git a/dep/recastnavigation/Recast/RecastLayers.cpp b/dep/recastnavigation/Recast/Source/RecastLayers.cpp
index 204f72e8cb2..cb1a39f4bda 100644
--- a/dep/recastnavigation/Recast/RecastLayers.cpp
+++ b/dep/recastnavigation/Recast/Source/RecastLayers.cpp
@@ -38,7 +38,7 @@ struct rcLayerRegion
 	unsigned char layerId;		// Layer ID
 	unsigned char nlayers;		// Layer count
 	unsigned char nneis;		// Neighbour count
-	unsigned char base;			// Flag indicating if the region is hte base of merged regions.
+	unsigned char base;			// Flag indicating if the region is the base of merged regions.
 };
 
 
diff --git a/dep/recastnavigation/Recast/RecastMesh.cpp b/dep/recastnavigation/Recast/Source/RecastMesh.cpp
index 8af609b79fb..e4f9c4b3629 100644
--- a/dep/recastnavigation/Recast/RecastMesh.cpp
+++ b/dep/recastnavigation/Recast/Source/RecastMesh.cpp
@@ -288,6 +288,53 @@ static bool diagonal(int i, int j, int n, const int* verts, int* indices)
 	return inCone(i, j, n, verts, indices) && diagonalie(i, j, n, verts, indices);
 }
 
+
+static bool diagonalieLoose(int i, int j, int n, const int* verts, int* indices)
+{
+	const int* d0 = &verts[(indices[i] & 0x0fffffff) * 4];
+	const int* d1 = &verts[(indices[j] & 0x0fffffff) * 4];
+	
+	// For each edge (k,k+1) of P
+	for (int k = 0; k < n; k++)
+	{
+		int k1 = next(k, n);
+		// Skip edges incident to i or j
+		if (!((k == i) || (k1 == i) || (k == j) || (k1 == j)))
+		{
+			const int* p0 = &verts[(indices[k] & 0x0fffffff) * 4];
+			const int* p1 = &verts[(indices[k1] & 0x0fffffff) * 4];
+			
+			if (vequal(d0, p0) || vequal(d1, p0) || vequal(d0, p1) || vequal(d1, p1))
+				continue;
+			
+			if (intersectProp(d0, d1, p0, p1))
+				return false;
+		}
+	}
+	return true;
+}
+
+static bool	inConeLoose(int i, int j, int n, const int* verts, int* indices)
+{
+	const int* pi = &verts[(indices[i] & 0x0fffffff) * 4];
+	const int* pj = &verts[(indices[j] & 0x0fffffff) * 4];
+	const int* pi1 = &verts[(indices[next(i, n)] & 0x0fffffff) * 4];
+	const int* pin1 = &verts[(indices[prev(i, n)] & 0x0fffffff) * 4];
+	
+	// If P[i] is a convex vertex [ i+1 left or on (i-1,i) ].
+	if (leftOn(pin1, pi, pi1))
+		return leftOn(pi, pj, pin1) && leftOn(pj, pi, pi1);
+	// Assume (i-1,i,i+1) not collinear.
+	// else P[i] is reflex.
+	return !(leftOn(pi, pj, pi1) && leftOn(pj, pi, pin1));
+}
+
+static bool diagonalLoose(int i, int j, int n, const int* verts, int* indices)
+{
+	return inConeLoose(i, j, n, verts, indices) && diagonalieLoose(i, j, n, verts, indices);
+}
+
+
 static int triangulate(int n, const int* verts, int* indices, int* tris)
 {
 	int ntris = 0;
@@ -328,14 +375,41 @@ static int triangulate(int n, const int* verts, int* indices, int* tris)
 		
 		if (mini == -1)
 		{
-			// Should not happen.
-/*			printf("mini == -1 ntris=%d n=%d\n", ntris, n);
+			// We might get here because the contour has overlapping segments, like this:
+			//
+			//  A o-o=====o---o B
+			//   /  |C   D|    \
+			//  o   o     o     o
+			//  :   :     :     :
+			// We'll try to recover by loosing up the inCone test a bit so that a diagonal
+			// like A-B or C-D can be found and we can continue.
+			minLen = -1;
+			mini = -1;
 			for (int i = 0; i < n; i++)
 			{
-				printf("%d ", indices[i] & 0x0fffffff);
+				int i1 = next(i, n);
+				int i2 = next(i1, n);
+				if (diagonalLoose(i, i2, n, verts, indices))
+				{
+					const int* p0 = &verts[(indices[i] & 0x0fffffff) * 4];
+					const int* p2 = &verts[(indices[next(i2, n)] & 0x0fffffff) * 4];
+					int dx = p2[0] - p0[0];
+					int dy = p2[2] - p0[2];
+					int len = dx*dx + dy*dy;
+					
+					if (minLen < 0 || len < minLen)
+					{
+						minLen = len;
+						mini = i;
+					}
+				}
+			}
+			if (mini == -1)
+			{
+				// The contour is messed up. This sometimes happens
+				// if the contour simplification is too aggressive.
+				return -ntris;
 			}
-			printf("\n");*/
-			return -ntris;
 		}
 		
 		int i = mini;
@@ -1463,7 +1537,7 @@ bool rcCopyPolyMesh(rcContext* ctx, const rcPolyMesh& src, rcPolyMesh& dst)
 		ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.flags' (%d).", src.npolys);
 		return false;
 	}
-	memcpy(dst.flags, src.flags, sizeof(unsigned char)*src.npolys);
+	memcpy(dst.flags, src.flags, sizeof(unsigned short)*src.npolys);
 	
 	return true;
 }
diff --git a/dep/recastnavigation/Recast/RecastMeshDetail.cpp b/dep/recastnavigation/Recast/Source/RecastMeshDetail.cpp
index 8325b883707..5cc2adf0320 100644
--- a/dep/recastnavigation/Recast/RecastMeshDetail.cpp
+++ b/dep/recastnavigation/Recast/Source/RecastMeshDetail.cpp
@@ -56,7 +56,7 @@ inline float vdist2(const float* p, const float* q)
 }
 
 inline float vcross2(const float* p1, const float* p2, const float* p3)
-{ 
+{
 	const float u1 = p2[0] - p1[0];
 	const float v1 = p2[2] - p1[2];
 	const float u2 = p3[0] - p1[0];
@@ -68,21 +68,27 @@ static bool circumCircle(const float* p1, const float* p2, const float* p3,
 						 float* c, float& r)
 {
 	static const float EPS = 1e-6f;
+	// Calculate the circle relative to p1, to avoid some precision issues.
+	const float v1[3] = {0,0,0};
+	float v2[3], v3[3];
+	rcVsub(v2, p2,p1);
+	rcVsub(v3, p3,p1);
 	
-	const float cp = vcross2(p1, p2, p3);
+	const float cp = vcross2(v1, v2, v3);
 	if (fabsf(cp) > EPS)
 	{
-		const float p1Sq = vdot2(p1,p1);
-		const float p2Sq = vdot2(p2,p2);
-		const float p3Sq = vdot2(p3,p3);
-		c[0] = (p1Sq*(p2[2]-p3[2]) + p2Sq*(p3[2]-p1[2]) + p3Sq*(p1[2]-p2[2])) / (2*cp);
-		c[2] = (p1Sq*(p3[0]-p2[0]) + p2Sq*(p1[0]-p3[0]) + p3Sq*(p2[0]-p1[0])) / (2*cp);
-		r = vdist2(c, p1);
+		const float v1Sq = vdot2(v1,v1);
+		const float v2Sq = vdot2(v2,v2);
+		const float v3Sq = vdot2(v3,v3);
+		c[0] = (v1Sq*(v2[2]-v3[2]) + v2Sq*(v3[2]-v1[2]) + v3Sq*(v1[2]-v2[2])) / (2*cp);
+		c[1] = 0;
+		c[2] = (v1Sq*(v3[0]-v2[0]) + v2Sq*(v1[0]-v3[0]) + v3Sq*(v2[0]-v1[0])) / (2*cp);
+		r = vdist2(c, v1);
+		rcVadd(c, c, p1);
 		return true;
 	}
-
-	c[0] = p1[0];
-	c[2] = p1[2];
+	
+	rcVcopy(c, p1);
 	r = 0;
 	return false;
 }
@@ -93,7 +99,7 @@ static float distPtTri(const float* p, const float* a, const float* b, const flo
 	rcVsub(v0, c,a);
 	rcVsub(v1, b,a);
 	rcVsub(v2, p,a);
-
+	
 	const float dot00 = vdot2(v0, v0);
 	const float dot01 = vdot2(v0, v1);
 	const float dot02 = vdot2(v0, v2);
@@ -178,7 +184,7 @@ static float distToTriMesh(const float* p, const float* verts, const int /*nvert
 
 static float distToPoly(int nvert, const float* verts, const float* p)
 {
-
+	
 	float dmin = FLT_MAX;
 	int i, j, c = 0;
 	for (i = 0, j = nvert-1; i < nvert; j = i++)
@@ -216,22 +222,13 @@ static unsigned short getHeight(const float fx, const float fy, const float fz,
 			if (nx < 0 || nz < 0 || nx >= hp.width || nz >= hp.height) continue;
 			const unsigned short nh = hp.data[nx+nz*hp.width];
 			if (nh == RC_UNSET_HEIGHT) continue;
-
+			
 			const float d = fabsf(nh*ch - fy);
 			if (d < dmin)
 			{
 				h = nh;
 				dmin = d;
 			}
-			
-/*			const float dx = (nx+0.5f)*cs - fx; 
-			const float dz = (nz+0.5f)*cs - fz;
-			const float d = dx*dx+dz*dz;
-			if (d < dmin)
-			{
-				h = nh;
-				dmin = d;
-			} */
 		}
 	}
 	return h;
@@ -263,7 +260,7 @@ static int addEdge(rcContext* ctx, int* edges, int& nedges, const int maxEdges,
 		return UNDEF;
 	}
 	
-	// Add edge if not already in the triangulation. 
+	// Add edge if not already in the triangulation.
 	int e = findEdge(edges, nedges, s, t);
 	if (e == UNDEF)
 	{
@@ -286,7 +283,7 @@ static void updateLeftFace(int* e, int s, int t, int f)
 		e[2] = f;
 	else if (e[1] == s && e[0] == t && e[3] == UNDEF)
 		e[3] = f;
-}	
+}
 
 static int overlapSegSeg2d(const float* a, const float* b, const float* c, const float* d)
 {
@@ -298,7 +295,7 @@ static int overlapSegSeg2d(const float* a, const float* b, const float* c, const
 		float a4 = a3 + a2 - a1;
 		if (a3 * a4 < 0.0f)
 			return 1;
-	}	
+	}
 	return 0;
 }
 
@@ -320,7 +317,7 @@ static bool overlapEdges(const float* pts, const int* edges, int nedges, int s1,
 static void completeFacet(rcContext* ctx, const float* pts, int npts, int* edges, int& nedges, const int maxEdges, int& nfaces, int e)
 {
 	static const float EPS = 1e-5f;
-
+	
 	int* edge = &edges[e*4];
 	
 	// Cache s and t.
@@ -337,11 +334,11 @@ static void completeFacet(rcContext* ctx, const float* pts, int npts, int* edges
 	}
 	else
 	{
-	    // Edge already completed. 
+	    // Edge already completed.
 	    return;
 	}
     
-	// Find best point on left of edge. 
+	// Find best point on left of edge.
 	int pt = npts;
 	float c[3] = {0,0,0};
 	float r = -1;
@@ -385,20 +382,20 @@ static void completeFacet(rcContext* ctx, const float* pts, int npts, int* edges
 		}
 	}
 	
-	// Add new triangle or update edge info if s-t is on hull. 
+	// Add new triangle or update edge info if s-t is on hull.
 	if (pt < npts)
 	{
-		// Update face information of edge being completed. 
+		// Update face information of edge being completed.
 		updateLeftFace(&edges[e*4], s, t, nfaces);
 		
-		// Add new edge or update face info of old edge. 
+		// Add new edge or update face info of old edge.
 		e = findEdge(edges, nedges, pt, s);
 		if (e == UNDEF)
 		    addEdge(ctx, edges, nedges, maxEdges, pt, s, nfaces, UNDEF);
 		else
 		    updateLeftFace(&edges[e*4], pt, s, nfaces);
 		
-		// Add new edge or update face info of old edge. 
+		// Add new edge or update face info of old edge.
 		e = findEdge(edges, nedges, t, pt);
 		if (e == UNDEF)
 		    addEdge(ctx, edges, nedges, maxEdges, t, pt, nfaces, UNDEF);
@@ -434,7 +431,7 @@ static void delaunayHull(rcContext* ctx, const int npts, const float* pts,
 			completeFacet(ctx, pts, npts, &edges[0], nedges, maxEdges, nfaces, currentEdge);
 		currentEdge++;
 	}
-
+	
 	// Create tris
 	tris.resize(nfaces*4);
 	for (int i = 0; i < nfaces*4; ++i)
@@ -489,6 +486,103 @@ static void delaunayHull(rcContext* ctx, const int npts, const float* pts,
 	}
 }
 
+// Calculate minimum extend of the polygon.
+static float polyMinExtent(const float* verts, const int nverts)
+{
+	float minDist = FLT_MAX;
+	for (int i = 0; i < nverts; i++)
+	{
+		const int ni = (i+1) % nverts;
+		const float* p1 = &verts[i*3];
+		const float* p2 = &verts[ni*3];
+		float maxEdgeDist = 0;
+		for (int j = 0; j < nverts; j++)
+		{
+			if (j == i || j == ni) continue;
+			float d = distancePtSeg2d(&verts[j*3], p1,p2);
+			maxEdgeDist = rcMax(maxEdgeDist, d);
+		}
+		minDist = rcMin(minDist, maxEdgeDist);
+	}
+	return rcSqrt(minDist);
+}
+
+inline int next(int i, int n)
+{
+	return (i+1) % n;
+}
+
+inline int prev(int i, int n)
+{
+	return (i + n-1) % n;
+}
+
+static void triangulateHull(const int nverts, const float* verts, const int nhull, const int* hull, rcIntArray& tris)
+{
+	int start = 0, left = 1, right = nhull-1;
+	
+	// Start from an ear with shortest perimeter.
+	// This tends to favor well formed triangles as starting point.
+	float dmin = 0;
+	for (int i = 0; i < nhull; i++)
+	{
+		int pi = prev(i, nhull);
+		int ni = next(i, nhull);
+		const float* pv = &verts[hull[pi]*3];
+		const float* cv = &verts[hull[i]*3];
+		const float* nv = &verts[hull[ni]*3];
+		const float d = vdist2(pv,cv) + vdist2(cv,nv) + vdist2(nv,pv);
+		if (d < dmin)
+		{
+			start = i;
+			left = ni;
+			right = pi;
+			dmin = d;
+		}
+	}
+	
+	// Add first triangle
+	tris.push(hull[start]);
+	tris.push(hull[left]);
+	tris.push(hull[right]);
+	tris.push(0);
+	
+	// Triangulate the polygon by moving left or right,
+	// depending on which triangle has shorter perimeter.
+	// This heuristic was chose emprically, since it seems
+	// handle tesselated straight edges well.
+	while (next(left, nhull) != right)
+	{
+		// Check to see if se should advance left or right.
+		int nleft = next(left, nhull);
+		int nright = prev(right, nhull);
+		
+		const float* cvleft = &verts[hull[left]*3];
+		const float* nvleft = &verts[hull[nleft]*3];
+		const float* cvright = &verts[hull[right]*3];
+		const float* nvright = &verts[hull[nright]*3];
+		const float dleft = vdist2(cvleft, nvleft) + vdist2(nvleft, cvright);
+		const float dright = vdist2(cvright, nvright) + vdist2(cvleft, nvright);
+		
+		if (dleft < dright)
+		{
+			tris.push(hull[left]);
+			tris.push(hull[nleft]);
+			tris.push(hull[right]);
+			tris.push(0);
+			left = nleft;
+		}
+		else
+		{
+			tris.push(hull[left]);
+			tris.push(hull[nright]);
+			tris.push(hull[right]);
+			tris.push(0);
+			right = nright;
+		}
+	}
+}
+
 
 inline float getJitterX(const int i)
 {
@@ -512,16 +606,22 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin,
 	float edge[(MAX_VERTS_PER_EDGE+1)*3];
 	int hull[MAX_VERTS];
 	int nhull = 0;
-
+	
 	nverts = 0;
-
+	
 	for (int i = 0; i < nin; ++i)
 		rcVcopy(&verts[i*3], &in[i*3]);
 	nverts = nin;
 	
+	edges.resize(0);
+	tris.resize(0);
+	
 	const float cs = chf.cs;
 	const float ics = 1.0f/cs;
 	
+	// Calculate minimum extents of the polygon based on input data.
+	float minExtent = polyMinExtent(verts, nverts);
+	
 	// Tessellate outlines.
 	// This is done in separate pass in order to ensure
 	// seamless height values across the ply boundaries.
@@ -628,27 +728,26 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin,
 		}
 	}
 	
-
+	// If the polygon minimum extent is small (sliver or small triangle), do not try to add internal points.
+	if (minExtent < sampleDist*2)
+	{
+		triangulateHull(nverts, verts, nhull, hull, tris);
+		return true;
+	}
+	
 	// Tessellate the base mesh.
-	edges.resize(0);
-	tris.resize(0);
-
-	delaunayHull(ctx, nverts, verts, nhull, hull, tris, edges);
+	// We're using the triangulateHull instead of delaunayHull as it tends to
+	// create a bit better triangulation for long thing triangles when there
+	// are no internal points.
+	triangulateHull(nverts, verts, nhull, hull, tris);
 	
 	if (tris.size() == 0)
 	{
 		// Could not triangulate the poly, make sure there is some valid data there.
-		ctx->log(RC_LOG_WARNING, "buildPolyDetail: Could not triangulate polygon, adding default data.");
-		for (int i = 2; i < nverts; ++i)
-		{
-			tris.push(0);
-			tris.push(i-1);
-			tris.push(i);
-			tris.push(0);
-		}
+		ctx->log(RC_LOG_WARNING, "buildPolyDetail: Could not triangulate polygon (%d verts).", nverts);
 		return true;
 	}
-
+	
 	if (sampleDist > 0)
 	{
 		// Create sample locations in a grid.
@@ -681,7 +780,7 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin,
 				samples.push(0); // Not added
 			}
 		}
-				
+		
 		// Add the samples starting from the one that has the most
 		// error. The procedure stops when all samples are added
 		// or when the max error is within treshold.
@@ -690,7 +789,7 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin,
 		{
 			if (nverts >= MAX_VERTS)
 				break;
-
+			
 			// Find sample with most error.
 			float bestpt[3] = {0,0,0};
 			float bestd = 0;
@@ -728,24 +827,24 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin,
 			edges.resize(0);
 			tris.resize(0);
 			delaunayHull(ctx, nverts, verts, nhull, hull, tris, edges);
-		}		
+		}
 	}
-
+	
 	const int ntris = tris.size()/4;
 	if (ntris > MAX_TRIS)
 	{
 		tris.resize(MAX_TRIS*4);
 		ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Shrinking triangle count from %d to max %d.", ntris, MAX_TRIS);
 	}
-
+	
 	return true;
 }
 
 
 static void getHeightDataSeedsFromVertices(const rcCompactHeightfield& chf,
-						  const unsigned short* poly, const int npoly,
-						  const unsigned short* verts, const int bs,
-						  rcHeightPatch& hp, rcIntArray& stack)
+										   const unsigned short* poly, const int npoly,
+										   const unsigned short* verts, const int bs,
+										   rcHeightPatch& hp, rcIntArray& stack)
 {
 	// Floodfill the heightfield to get 2D height data,
 	// starting at vertex locations as seeds.
@@ -849,7 +948,7 @@ static void getHeightDataSeedsFromVertices(const rcCompactHeightfield& chf,
 				continue;
 			
 			const int ai = (int)chf.cells[(ax+bs)+(ay+bs)*chf.width].index + rcGetCon(cs, dir);
-
+			
 			int idx = ax-hp.xmin+(ay-hp.ymin)*hp.width;
 			hp.data[idx] = 1;
 			
@@ -858,9 +957,9 @@ static void getHeightDataSeedsFromVertices(const rcCompactHeightfield& chf,
 			stack.push(ai);
 		}
 	}
-
+	
 	memset(hp.data, 0xff, sizeof(unsigned short)*hp.width*hp.height);
-
+	
 	// Mark start locations.
 	for (int i = 0; i < stack.size(); i += 3)
 	{
@@ -870,8 +969,8 @@ static void getHeightDataSeedsFromVertices(const rcCompactHeightfield& chf,
 		int idx = cx-hp.xmin+(cy-hp.ymin)*hp.width;
 		const rcCompactSpan& cs = chf.spans[ci];
 		hp.data[idx] = cs.y;
-
-		// getHeightData seeds are given in coordinates with borders 
+		
+		// getHeightData seeds are given in coordinates with borders
 		stack[i+0] += bs;
 		stack[i+1] += bs;
 	}
@@ -888,12 +987,12 @@ static void getHeightData(const rcCompactHeightfield& chf,
 {
 	// Note: Reads to the compact heightfield are offset by border size (bs)
 	// since border size offset is already removed from the polymesh vertices.
-
+	
 	stack.resize(0);
 	memset(hp.data, 0xff, sizeof(unsigned short)*hp.width*hp.height);
 	
 	bool empty = true;
-
+	
 	// Copy the height from the same region, and mark region borders
 	// as seed points to fill the rest.
 	for (int hy = 0; hy < hp.height; hy++)
@@ -911,7 +1010,7 @@ static void getHeightData(const rcCompactHeightfield& chf,
 					// Store height
 					hp.data[hx + hy*hp.width] = s.y;
 					empty = false;
-
+					
 					// If any of the neighbours is not in same region,
 					// add the current location as flood fill start
 					bool border = false;
@@ -940,8 +1039,8 @@ static void getHeightData(const rcCompactHeightfield& chf,
 				}
 			}
 		}
-	}	
-
+	}
+	
 	// if the polygon does not contian any points from the current region (rare, but happens)
 	// then use the cells closest to the polygon vertices as seeds to fill the height field
 	if (empty)
@@ -963,7 +1062,7 @@ static void getHeightData(const rcCompactHeightfield& chf,
 				memmove(&stack[0], &stack[RETRACT_SIZE*3], sizeof(int)*(stack.size()-RETRACT_SIZE*3));
 			stack.resize(stack.size()-RETRACT_SIZE*3);
 		}
-
+		
 		const rcCompactSpan& cs = chf.spans[ci];
 		for (int dir = 0; dir < 4; ++dir)
 		{
@@ -982,9 +1081,9 @@ static void getHeightData(const rcCompactHeightfield& chf,
 			
 			const int ai = (int)chf.cells[ax + ay*chf.width].index + rcGetCon(cs, dir);
 			const rcCompactSpan& as = chf.spans[ai];
-
+			
 			hp.data[hx + hy*hp.width] = as.y;
-
+			
 			stack.push(ax);
 			stack.push(ay);
 			stack.push(ai);
@@ -999,7 +1098,7 @@ static unsigned char getEdgeFlags(const float* va, const float* vb,
 	static const float thrSqr = rcSqr(0.001f);
 	for (int i = 0, j = npoly-1; i < npoly; j=i++)
 	{
-		if (distancePtSeg2d(va, &vpoly[j*3], &vpoly[i*3]) < thrSqr && 
+		if (distancePtSeg2d(va, &vpoly[j*3], &vpoly[i*3]) < thrSqr &&
 			distancePtSeg2d(vb, &vpoly[j*3], &vpoly[i*3]) < thrSqr)
 			return 1;
 	}
@@ -1028,7 +1127,7 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa
 	rcAssert(ctx);
 	
 	ctx->startTimer(RC_TIMER_BUILD_POLYMESHDETAIL);
-
+	
 	if (mesh.nverts == 0 || mesh.npolys == 0)
 		return true;
 	
@@ -1107,10 +1206,10 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa
 		ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.meshes' (%d).", dmesh.nmeshes*4);
 		return false;
 	}
-
+	
 	int vcap = nPolyVerts+nPolyVerts/2;
 	int tcap = vcap*2;
-
+	
 	dmesh.nverts = 0;
 	dmesh.verts = (float*)rcAlloc(sizeof(float)*vcap*3, RC_ALLOC_PERM);
 	if (!dmesh.verts)
@@ -1119,7 +1218,7 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa
 		return false;
 	}
 	dmesh.ntris = 0;
-	dmesh.tris = (unsigned char*)rcAlloc(sizeof(unsigned char*)*tcap*4, RC_ALLOC_PERM);
+	dmesh.tris = (unsigned char*)rcAlloc(sizeof(unsigned char)*tcap*4, RC_ALLOC_PERM);
 	if (!dmesh.tris)
 	{
 		ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.tris' (%d).", tcap*4);
@@ -1158,7 +1257,7 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa
 		{
 			return false;
 		}
-
+		
 		// Move detail verts to world space.
 		for (int j = 0; j < nverts; ++j)
 		{
@@ -1173,21 +1272,21 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa
 			poly[j*3+1] += orig[1];
 			poly[j*3+2] += orig[2];
 		}
-	
+		
 		// Store detail submesh.
 		const int ntris = tris.size()/4;
-
+		
 		dmesh.meshes[i*4+0] = (unsigned int)dmesh.nverts;
 		dmesh.meshes[i*4+1] = (unsigned int)nverts;
 		dmesh.meshes[i*4+2] = (unsigned int)dmesh.ntris;
-		dmesh.meshes[i*4+3] = (unsigned int)ntris;		
+		dmesh.meshes[i*4+3] = (unsigned int)ntris;
 		
 		// Store vertices, allocate more memory if necessary.
 		if (dmesh.nverts+nverts > vcap)
 		{
 			while (dmesh.nverts+nverts > vcap)
 				vcap += 256;
-				
+			
 			float* newv = (float*)rcAlloc(sizeof(float)*vcap*3, RC_ALLOC_PERM);
 			if (!newv)
 			{
@@ -1233,9 +1332,9 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa
 			dmesh.ntris++;
 		}
 	}
-		
+	
 	ctx->stopTimer(RC_TIMER_BUILD_POLYMESHDETAIL);
-
+	
 	return true;
 }
 
@@ -1245,11 +1344,11 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int
 	rcAssert(ctx);
 	
 	ctx->startTimer(RC_TIMER_MERGE_POLYMESHDETAIL);
-
+	
 	int maxVerts = 0;
 	int maxTris = 0;
 	int maxMeshes = 0;
-
+	
 	for (int i = 0; i < nmeshes; ++i)
 	{
 		if (!meshes[i]) continue;
@@ -1257,7 +1356,7 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int
 		maxTris += meshes[i]->ntris;
 		maxMeshes += meshes[i]->nmeshes;
 	}
-
+	
 	mesh.nmeshes = 0;
 	mesh.meshes = (unsigned int*)rcAlloc(sizeof(unsigned int)*maxMeshes*4, RC_ALLOC_PERM);
 	if (!mesh.meshes)
@@ -1265,7 +1364,7 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int
 		ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'pmdtl.meshes' (%d).", maxMeshes*4);
 		return false;
 	}
-
+	
 	mesh.ntris = 0;
 	mesh.tris = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxTris*4, RC_ALLOC_PERM);
 	if (!mesh.tris)
@@ -1273,7 +1372,7 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int
 		ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.tris' (%d).", maxTris*4);
 		return false;
 	}
-
+	
 	mesh.nverts = 0;
 	mesh.verts = (float*)rcAlloc(sizeof(float)*maxVerts*3, RC_ALLOC_PERM);
 	if (!mesh.verts)
@@ -1297,7 +1396,7 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int
 			dst[3] = src[3];
 			mesh.nmeshes++;
 		}
-			
+		
 		for (int k = 0; k < dm->nverts; ++k)
 		{
 			rcVcopy(&mesh.verts[mesh.nverts*3], &dm->verts[k*3]);
@@ -1312,7 +1411,7 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int
 			mesh.ntris++;
 		}
 	}
-
+	
 	ctx->stopTimer(RC_TIMER_MERGE_POLYMESHDETAIL);
 	
 	return true;
diff --git a/dep/recastnavigation/Recast/RecastRasterization.cpp b/dep/recastnavigation/Recast/Source/RecastRasterization.cpp
index 45a7d35bf3e..45a7d35bf3e 100644
--- a/dep/recastnavigation/Recast/RecastRasterization.cpp
+++ b/dep/recastnavigation/Recast/Source/RecastRasterization.cpp
diff --git a/dep/recastnavigation/Recast/RecastRegion.cpp b/dep/recastnavigation/Recast/Source/RecastRegion.cpp
index 589fac29203..38bc4ff476f 100644
--- a/dep/recastnavigation/Recast/RecastRegion.cpp
+++ b/dep/recastnavigation/Recast/Source/RecastRegion.cpp
@@ -315,6 +315,7 @@ static bool floodRegion(int x, int y, int i,
 			srcReg[ci] = 0;
 			continue;
 		}
+		
 		count++;
 		
 		// Expand neighbours.
@@ -516,7 +517,11 @@ struct rcRegion
 		id(i),
 		areaType(0),
 		remap(false),
-		visited(false)
+		visited(false),
+		overlap(false),
+		connectsToBorder(false),
+		ymin(0xffff),
+		ymax(0)
 	{}
 	
 	int spanCount;					// Number of spans belonging to this region
@@ -524,6 +529,9 @@ struct rcRegion
 	unsigned char areaType;			// Are type.
 	bool remap;
 	bool visited;
+	bool overlap;
+	bool connectsToBorder;
+	unsigned short ymin, ymax;
 	rcIntArray connections;
 	rcIntArray floors;
 };
@@ -768,10 +776,11 @@ static void walkContour(int x, int y, int i, int dir,
 	}
 }
 
-static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegionSize,
-							   unsigned short& maxRegionId,
-							   rcCompactHeightfield& chf,
-							   unsigned short* srcReg)
+
+static bool mergeAndFilterRegions(rcContext* ctx, int minRegionArea, int mergeRegionSize,
+								  unsigned short& maxRegionId,
+								  rcCompactHeightfield& chf,
+								  unsigned short* srcReg, rcIntArray& overlaps)
 {
 	const int w = chf.width;
 	const int h = chf.height;
@@ -780,7 +789,7 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio
 	rcRegion* regions = (rcRegion*)rcAlloc(sizeof(rcRegion)*nreg, RC_ALLOC_TEMP);
 	if (!regions)
 	{
-		ctx->log(RC_LOG_ERROR, "filterSmallRegions: Out of memory 'regions' (%d).", nreg);
+		ctx->log(RC_LOG_ERROR, "mergeAndFilterRegions: Out of memory 'regions' (%d).", nreg);
 		return false;
 	}
 
@@ -803,7 +812,6 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio
 				rcRegion& reg = regions[r];
 				reg.spanCount++;
 				
-				
 				// Update floors.
 				for (int j = (int)c.index; j < ni; ++j)
 				{
@@ -811,6 +819,8 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio
 					unsigned short floorId = srcReg[j];
 					if (floorId == 0 || floorId >= nreg)
 						continue;
+					if (floorId == r)
+						reg.overlap = true;
 					addUniqueFloorRegion(reg, floorId);
 				}
 				
@@ -906,7 +916,7 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio
 			}
 		}
 	}
-		
+	
 	// Merge too small regions to neighbour regions.
 	int mergeCount = 0 ;
 	do
@@ -916,7 +926,9 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio
 		{
 			rcRegion& reg = regions[i];
 			if (reg.id == 0 || (reg.id & RC_BORDER_REG))
-				continue;                       
+				continue;
+			if (reg.overlap)
+				continue;
 			if (reg.spanCount == 0)
 				continue;
 			
@@ -933,7 +945,7 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio
 			{
 				if (reg.connections[j] & RC_BORDER_REG) continue;
 				rcRegion& mreg = regions[reg.connections[j]];
-				if (mreg.id == 0 || (mreg.id & RC_BORDER_REG)) continue;
+				if (mreg.id == 0 || (mreg.id & RC_BORDER_REG) || mreg.overlap) continue;
 				if (mreg.spanCount < smallest &&
 					canMergeWithRegion(reg, mreg) &&
 					canMergeWithRegion(mreg, reg))
@@ -1003,6 +1015,224 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio
 		if ((srcReg[i] & RC_BORDER_REG) == 0)
 			srcReg[i] = regions[srcReg[i]].id;
 	}
+
+	// Return regions that we found to be overlapping.
+	for (int i = 0; i < nreg; ++i)
+		if (regions[i].overlap)
+			overlaps.push(regions[i].id);
+
+	for (int i = 0; i < nreg; ++i)
+		regions[i].~rcRegion();
+	rcFree(regions);
+	
+	
+	return true;
+}
+
+
+static void addUniqueConnection(rcRegion& reg, int n)
+{
+	for (int i = 0; i < reg.connections.size(); ++i)
+		if (reg.connections[i] == n)
+			return;
+	reg.connections.push(n);
+}
+
+static bool mergeAndFilterLayerRegions(rcContext* ctx, int minRegionArea,
+									   unsigned short& maxRegionId,
+									   rcCompactHeightfield& chf,
+									   unsigned short* srcReg, rcIntArray& overlaps)
+{
+	const int w = chf.width;
+	const int h = chf.height;
+	
+	const int nreg = maxRegionId+1;
+	rcRegion* regions = (rcRegion*)rcAlloc(sizeof(rcRegion)*nreg, RC_ALLOC_TEMP);
+	if (!regions)
+	{
+		ctx->log(RC_LOG_ERROR, "mergeAndFilterLayerRegions: Out of memory 'regions' (%d).", nreg);
+		return false;
+	}
+	
+	// Construct regions
+	for (int i = 0; i < nreg; ++i)
+		new(&regions[i]) rcRegion((unsigned short)i);
+	
+	// Find region neighbours and overlapping regions.
+	rcIntArray lregs(32);
+	for (int y = 0; y < h; ++y)
+	{
+		for (int x = 0; x < w; ++x)
+		{
+			const rcCompactCell& c = chf.cells[x+y*w];
+
+			lregs.resize(0);
+			
+			for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
+			{
+				const rcCompactSpan& s = chf.spans[i];
+				const unsigned short ri = srcReg[i];
+				if (ri == 0 || ri >= nreg) continue;
+				rcRegion& reg = regions[ri];
+				
+				reg.spanCount++;
+				
+				reg.ymin = rcMin(reg.ymin, s.y);
+				reg.ymax = rcMax(reg.ymax, s.y);
+				
+				// Collect all region layers.
+				lregs.push(ri);
+				
+				// Update neighbours
+				for (int dir = 0; dir < 4; ++dir)
+				{
+					if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
+					{
+						const int ax = x + rcGetDirOffsetX(dir);
+						const int ay = y + rcGetDirOffsetY(dir);
+						const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
+						const unsigned short rai = srcReg[ai];
+						if (rai > 0 && rai < nreg && rai != ri)
+							addUniqueConnection(reg, rai);
+						if (rai & RC_BORDER_REG)
+							reg.connectsToBorder = true;
+					}
+				}
+				
+			}
+			
+			// Update overlapping regions.
+			for (int i = 0; i < lregs.size()-1; ++i)
+			{
+				for (int j = i+1; j < lregs.size(); ++j)
+				{
+					if (lregs[i] != lregs[j])
+					{
+						rcRegion& ri = regions[lregs[i]];
+						rcRegion& rj = regions[lregs[j]];
+						addUniqueFloorRegion(ri, lregs[j]);
+						addUniqueFloorRegion(rj, lregs[i]);
+					}
+				}
+			}
+			
+		}
+	}
+
+	// Create 2D layers from regions.
+	unsigned short layerId = 1;
+
+	for (int i = 0; i < nreg; ++i)
+		regions[i].id = 0;
+
+	// Merge montone regions to create non-overlapping areas.
+	rcIntArray stack(32);
+	for (int i = 1; i < nreg; ++i)
+	{
+		rcRegion& root = regions[i];
+		// Skip already visited.
+		if (root.id != 0)
+			continue;
+		
+		// Start search.
+		root.id = layerId;
+
+		stack.resize(0);
+		stack.push(i);
+		
+		while (stack.size() > 0)
+		{
+			// Pop front
+			rcRegion& reg = regions[stack[0]];
+			for (int j = 0; j < stack.size()-1; ++j)
+				stack[j] = stack[j+1];
+			stack.resize(stack.size()-1);
+			
+			const int ncons = (int)reg.connections.size();
+			for (int j = 0; j < ncons; ++j)
+			{
+				const int nei = reg.connections[j];
+				rcRegion& regn = regions[nei];
+				// Skip already visited.
+				if (regn.id != 0)
+					continue;
+				// Skip if the neighbour is overlapping root region.
+				bool overlap = false;
+				for (int k = 0; k < root.floors.size(); k++)
+				{
+					if (root.floors[k] == nei)
+					{
+						overlap = true;
+						break;
+					}
+				}
+				if (overlap)
+					continue;
+					
+				// Deepen
+				stack.push(nei);
+					
+				// Mark layer id
+				regn.id = layerId;
+				// Merge current layers to root.
+				for (int k = 0; k < regn.floors.size(); ++k)
+					addUniqueFloorRegion(root, regn.floors[k]);
+				root.ymin = rcMin(root.ymin, regn.ymin);
+				root.ymax = rcMax(root.ymax, regn.ymax);
+				root.spanCount += regn.spanCount;
+				regn.spanCount = 0;
+				root.connectsToBorder = root.connectsToBorder || regn.connectsToBorder;
+			}
+		}
+		
+		layerId++;
+	}
+	
+	// Remove small regions
+	for (int i = 0; i < nreg; ++i)
+	{
+		if (regions[i].spanCount > 0 && regions[i].spanCount < minRegionArea && !regions[i].connectsToBorder)
+		{
+			unsigned short reg = regions[i].id;
+			for (int j = 0; j < nreg; ++j)
+				if (regions[j].id == reg)
+					regions[j].id = 0;
+		}
+	}
+	
+	// Compress region Ids.
+	for (int i = 0; i < nreg; ++i)
+	{
+		regions[i].remap = false;
+		if (regions[i].id == 0) continue;				// Skip nil regions.
+		if (regions[i].id & RC_BORDER_REG) continue;    // Skip external regions.
+		regions[i].remap = true;
+	}
+	
+	unsigned short regIdGen = 0;
+	for (int i = 0; i < nreg; ++i)
+	{
+		if (!regions[i].remap)
+			continue;
+		unsigned short oldId = regions[i].id;
+		unsigned short newId = ++regIdGen;
+		for (int j = i; j < nreg; ++j)
+		{
+			if (regions[j].id == oldId)
+			{
+				regions[j].id = newId;
+				regions[j].remap = false;
+			}
+		}
+	}
+	maxRegionId = regIdGen;
+	
+	// Remap regions.
+	for (int i = 0; i < chf.spanCount; ++i)
+	{
+		if ((srcReg[i] & RC_BORDER_REG) == 0)
+			srcReg[i] = regions[srcReg[i]].id;
+	}
 	
 	for (int i = 0; i < nreg; ++i)
 		regions[i].~rcRegion();
@@ -1011,6 +1241,8 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio
 	return true;
 }
 
+
+
 /// @par
 /// 
 /// This is usually the second to the last step in creating a fully built
@@ -1256,13 +1488,17 @@ bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf,
 		}
 	}
 
+
 	ctx->startTimer(RC_TIMER_BUILD_REGIONS_FILTER);
 
-	// Filter out small regions.
+	// Merge regions and filter out small regions.
+	rcIntArray overlaps;
 	chf.maxRegions = id;
-	if (!filterSmallRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg))
+	if (!mergeAndFilterRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg, overlaps))
 		return false;
 
+	// Monotone partitioning does not generate overlapping regions.
+	
 	ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FILTER);
 	
 	// Store the result out.
@@ -1407,11 +1643,18 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf,
 	
 	ctx->startTimer(RC_TIMER_BUILD_REGIONS_FILTER);
 	
-	// Filter out small regions.
+	// Merge regions and filter out smalle regions.
+	rcIntArray overlaps;
 	chf.maxRegions = regionId;
-	if (!filterSmallRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg))
+	if (!mergeAndFilterRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg, overlaps))
 		return false;
-	
+
+	// If overlapping regions were found during merging, split those regions.
+	if (overlaps.size() > 0)
+	{
+		ctx->log(RC_LOG_ERROR, "rcBuildRegions: %d overlapping regions.", overlaps.size());
+	}
+
 	ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FILTER);
 		
 	// Write the result out.
@@ -1424,3 +1667,157 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf,
 }
 
 
+bool rcBuildLayerRegions(rcContext* ctx, rcCompactHeightfield& chf,
+						 const int borderSize, const int minRegionArea)
+{
+	rcAssert(ctx);
+	
+	ctx->startTimer(RC_TIMER_BUILD_REGIONS);
+	
+	const int w = chf.width;
+	const int h = chf.height;
+	unsigned short id = 1;
+	
+	rcScopedDelete<unsigned short> srcReg = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP);
+	if (!srcReg)
+	{
+		ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'src' (%d).", chf.spanCount);
+		return false;
+	}
+	memset(srcReg,0,sizeof(unsigned short)*chf.spanCount);
+	
+	const int nsweeps = rcMax(chf.width,chf.height);
+	rcScopedDelete<rcSweepSpan> sweeps = (rcSweepSpan*)rcAlloc(sizeof(rcSweepSpan)*nsweeps, RC_ALLOC_TEMP);
+	if (!sweeps)
+	{
+		ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'sweeps' (%d).", nsweeps);
+		return false;
+	}
+	
+	
+	// Mark border regions.
+	if (borderSize > 0)
+	{
+		// Make sure border will not overflow.
+		const int bw = rcMin(w, borderSize);
+		const int bh = rcMin(h, borderSize);
+		// Paint regions
+		paintRectRegion(0, bw, 0, h, id|RC_BORDER_REG, chf, srcReg); id++;
+		paintRectRegion(w-bw, w, 0, h, id|RC_BORDER_REG, chf, srcReg); id++;
+		paintRectRegion(0, w, 0, bh, id|RC_BORDER_REG, chf, srcReg); id++;
+		paintRectRegion(0, w, h-bh, h, id|RC_BORDER_REG, chf, srcReg); id++;
+		
+		chf.borderSize = borderSize;
+	}
+	
+	rcIntArray prev(256);
+	
+	// Sweep one line at a time.
+	for (int y = borderSize; y < h-borderSize; ++y)
+	{
+		// Collect spans from this row.
+		prev.resize(id+1);
+		memset(&prev[0],0,sizeof(int)*id);
+		unsigned short rid = 1;
+		
+		for (int x = borderSize; x < w-borderSize; ++x)
+		{
+			const rcCompactCell& c = chf.cells[x+y*w];
+			
+			for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
+			{
+				const rcCompactSpan& s = chf.spans[i];
+				if (chf.areas[i] == RC_NULL_AREA) continue;
+				
+				// -x
+				unsigned short previd = 0;
+				if (rcGetCon(s, 0) != RC_NOT_CONNECTED)
+				{
+					const int ax = x + rcGetDirOffsetX(0);
+					const int ay = y + rcGetDirOffsetY(0);
+					const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0);
+					if ((srcReg[ai] & RC_BORDER_REG) == 0 && chf.areas[i] == chf.areas[ai])
+						previd = srcReg[ai];
+				}
+				
+				if (!previd)
+				{
+					previd = rid++;
+					sweeps[previd].rid = previd;
+					sweeps[previd].ns = 0;
+					sweeps[previd].nei = 0;
+				}
+				
+				// -y
+				if (rcGetCon(s,3) != RC_NOT_CONNECTED)
+				{
+					const int ax = x + rcGetDirOffsetX(3);
+					const int ay = y + rcGetDirOffsetY(3);
+					const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3);
+					if (srcReg[ai] && (srcReg[ai] & RC_BORDER_REG) == 0 && chf.areas[i] == chf.areas[ai])
+					{
+						unsigned short nr = srcReg[ai];
+						if (!sweeps[previd].nei || sweeps[previd].nei == nr)
+						{
+							sweeps[previd].nei = nr;
+							sweeps[previd].ns++;
+							prev[nr]++;
+						}
+						else
+						{
+							sweeps[previd].nei = RC_NULL_NEI;
+						}
+					}
+				}
+				
+				srcReg[i] = previd;
+			}
+		}
+		
+		// Create unique ID.
+		for (int i = 1; i < rid; ++i)
+		{
+			if (sweeps[i].nei != RC_NULL_NEI && sweeps[i].nei != 0 &&
+				prev[sweeps[i].nei] == (int)sweeps[i].ns)
+			{
+				sweeps[i].id = sweeps[i].nei;
+			}
+			else
+			{
+				sweeps[i].id = id++;
+			}
+		}
+		
+		// Remap IDs
+		for (int x = borderSize; x < w-borderSize; ++x)
+		{
+			const rcCompactCell& c = chf.cells[x+y*w];
+			
+			for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
+			{
+				if (srcReg[i] > 0 && srcReg[i] < rid)
+					srcReg[i] = sweeps[srcReg[i]].id;
+			}
+		}
+	}
+	
+	
+	ctx->startTimer(RC_TIMER_BUILD_REGIONS_FILTER);
+	
+	// Merge monotone regions to layers and remove small regions.
+	rcIntArray overlaps;
+	chf.maxRegions = id;
+	if (!mergeAndFilterLayerRegions(ctx, minRegionArea, chf.maxRegions, chf, srcReg, overlaps))
+		return false;
+	
+	ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FILTER);
+	
+	
+	// Store the result out.
+	for (int i = 0; i < chf.spanCount; ++i)
+		chf.spans[i].reg = srcReg[i];
+	
+	ctx->stopTimer(RC_TIMER_BUILD_REGIONS);
+	
+	return true;
+}
diff --git a/dep/recastnavigation/TODO.txt b/dep/recastnavigation/TODO.txt
deleted file mode 100644
index b911c0e4720..00000000000
--- a/dep/recastnavigation/TODO.txt
+++ /dev/null
@@ -1,20 +0,0 @@
-TODO/Roadmap
-
-Summer/Autumn 2009
-
-- Off mesh links (jump links)
-- Area annotations
-- Embed extra data per polygon
-- Height conforming navmesh
-
-
-Autumn/Winter 2009/2010
-
-- Detour path following
-- More dynamic example with tile navmesh
-- Faster small tile process
-
-
-More info at http://digestingduck.blogspot.com/2009/07/recast-and-detour-roadmap.html
-
--
diff --git a/dep/recastnavigation/recast_hotfix1.diff b/dep/recastnavigation/recast_hotfix1.diff
deleted file mode 100644
index d370b0a68c8..00000000000
--- a/dep/recastnavigation/recast_hotfix1.diff
+++ /dev/null
@@ -1,13 +0,0 @@
-diff --git a/dep/recastnavigation/Detour/DetourNavMesh.h b/dep/recastnavigation/Detour/DetourNavMesh.h
-index 52d2c50..99e30c7 100644
---- a/dep/recastnavigation/Detour/DetourNavMesh.h
-+++ b/dep/recastnavigation/Detour/DetourNavMesh.h
-@@ -21,7 +21,7 @@
- 
- #include "DetourAlloc.h"
- 
--#ifdef WIN32
-+#if defined(WIN32) && !defined(__MINGW32__)
-     typedef unsigned __int64   uint64;
- #else
- #include <stdint.h>
diff --git a/dep/recastnavigation/recast_hotfix2.diff b/dep/recastnavigation/recast_hotfix2.diff
deleted file mode 100644
index cd73165dcb7..00000000000
--- a/dep/recastnavigation/recast_hotfix2.diff
+++ /dev/null
@@ -1,38 +0,0 @@
-diff --git a/dep/recastnavigation/Detour/DetourNavMesh.h b/dep/recastnavigation/Detour/DetourNavMesh.h
-index c094e41..9c61a9b 100644
---- a/dep/recastnavigation/Detour/DetourNavMesh.h
-+++ b/dep/recastnavigation/Detour/DetourNavMesh.h
-@@ -25,7 +25,8 @@
- 
- // Edited by TC
- #if defined(WIN32) && !defined(__MINGW32__)
--typedef unsigned __int64    uint64;
-+/// Do not rename back to uint64. Otherwise mac complains about typedef redefinition
-+typedef unsigned __int64    uint64_d;
- #else
- #include <stdint.h>
- #ifndef uint64_t
-@@ -33,7 +34,8 @@ typedef unsigned __int64    uint64;
- #include <linux/types.h>
- #endif
- #endif
--typedef uint64_t            uint64;
-+/// Do not rename back to uint64. Otherwise mac complains about typedef redefinition
-+typedef uint64_t            uint64_d;
- #endif 
- 
- // Note: If you want to use 64-bit refs, change the types of both dtPolyRef & dtTileRef.
-@@ -48,11 +50,11 @@ static const int STATIC_POLY_BITS = 31;
- 
- /// A handle to a polygon within a navigation mesh tile.
- /// @ingroup detour
--typedef uint64 dtPolyRef; // Edited by TC
-+typedef uint64_d dtPolyRef; // Edited by TC
- 
- /// A handle to a tile within a navigation mesh.
- /// @ingroup detour
--typedef uint64 dtTileRef; // Edited by TC
-+typedef uint64_d dtTileRef; // Edited by TC
- 
- /// The maximum number of vertices per navigation polygon.
- /// @ingroup detour
diff --git a/dep/recastnavigation/recastnavigation.diff b/dep/recastnavigation/recastnavigation.diff
new file mode 100644
index 00000000000..42bab6474e3
--- /dev/null
+++ b/dep/recastnavigation/recastnavigation.diff
@@ -0,0 +1,448 @@
+From b84e9ffbd1d1e1fb2f5d78cc53d2bb7b56c3fce3 Mon Sep 17 00:00:00 2001
+From: jackpoz <giacomopoz@gmail.com>
+Date: Fri, 20 Jun 2014 23:15:04 +0200
+Subject: [PATCH] Add custom trinitycore changes
+
+---
+ Detour/Include/DetourNavMesh.h                 | 76 ++++++++------------------
+ Detour/Source/DetourCommon.cpp                 |  4 +-
+ Detour/Source/DetourNavMesh.cpp                | 32 ++++-------
+ Detour/Source/DetourNavMeshBuilder.cpp         |  6 +-
+ Detour/Source/DetourNavMeshQuery.cpp           |  9 +--
+ Detour/Source/DetourNode.cpp                   | 29 +++-------
+ DetourCrowd/Source/DetourObstacleAvoidance.cpp |  6 +-
+ Recast/Include/Recast.h                        |  8 +--
+ 8 files changed, 59 insertions(+), 111 deletions(-)
+
+diff --git a/Detour/Include/DetourNavMesh.h b/Detour/Include/DetourNavMesh.h
+index 1060845..782ddbc 100644
+--- a/Detour/Include/DetourNavMesh.h
++++ b/Detour/Include/DetourNavMesh.h
+@@ -22,39 +22,35 @@
+ #include "DetourAlloc.h"
+ #include "DetourStatus.h"
+ 
+-// Undefine (or define in a build cofnig) the following line to use 64bit polyref.
+-// Generally not needed, useful for very large worlds.
+-// Note: tiles build using 32bit refs are not compatible with 64bit refs!
+-//#define DT_POLYREF64 1
+-
+-#ifdef DT_POLYREF64
+-// TODO: figure out a multiplatform version of uint64_t
+-// - maybe: https://code.google.com/p/msinttypes/
+-// - or: http://www.azillionmonkeys.com/qed/pstdint.h
++
++// Edited by TC
++#if defined(WIN32) && !defined(__MINGW32__)
++/// Do not rename back to uint64. Otherwise mac complains about typedef redefinition
++typedef unsigned __int64    uint64_d;
++#else
+ #include <stdint.h>
++#ifndef uint64_t
++#ifdef __linux__
++#include <linux/types.h>
++#endif
+ #endif
++/// Do not rename back to uint64. Otherwise mac complains about typedef redefinition
++typedef uint64_t            uint64_d;
++#endif 
+ 
+ // Note: If you want to use 64-bit refs, change the types of both dtPolyRef & dtTileRef.
+ // It is also recommended that you change dtHashRef() to a proper 64-bit hash.
+ 
++// Edited by TC
++// We cannot have over 31 bits for either tile nor poly
++// without changing polyCount to use 64bits too.
+ /// A handle to a polygon within a navigation mesh tile.
+ /// @ingroup detour
+-#ifdef DT_POLYREF64
+-static const unsigned int DT_SALT_BITS = 16;
+-static const unsigned int DT_TILE_BITS = 28;
+-static const unsigned int DT_POLY_BITS = 20;
+-typedef uint64_t dtPolyRef;
+-#else
+-typedef unsigned int dtPolyRef;
+-#endif
++typedef uint64_d dtPolyRef; // Edited by TC
+ 
+ /// A handle to a tile within a navigation mesh.
+ /// @ingroup detour
+-#ifdef DT_POLYREF64
+-typedef uint64_t dtTileRef;
+-#else
+-typedef unsigned int dtTileRef;
+-#endif
++typedef uint64_d dtTileRef; // Edited by TC
+ 
+ /// The maximum number of vertices per navigation polygon.
+ /// @ingroup detour
+@@ -94,6 +90,12 @@ static const unsigned int DT_OFFMESH_CON_BIDIR = 1;
+ /// @ingroup detour
+ static const int DT_MAX_AREAS = 64;
+ 
++static const int STATIC_SALT_BITS = 12;
++static const int STATIC_TILE_BITS = 21;
++static const int STATIC_POLY_BITS = 31;
++// we cannot have over 31 bits for either tile nor poly
++// without changing polyCount to use 64bits too.
++
+ /// Tile flags used for various functions and fields.
+ /// For an example, see dtNavMesh::addTile().
+ enum dtTileFlags
+@@ -511,11 +513,7 @@ public:
+ 	///  @param[in]	ip		The index of the polygon within the tile.
+ 	inline dtPolyRef encodePolyId(unsigned int salt, unsigned int it, unsigned int ip) const
+ 	{
+-#ifdef DT_POLYREF64
+-		return ((dtPolyRef)salt << (DT_POLY_BITS+DT_TILE_BITS)) | ((dtPolyRef)it << DT_POLY_BITS) | (dtPolyRef)ip;
+-#else
+ 		return ((dtPolyRef)salt << (m_polyBits+m_tileBits)) | ((dtPolyRef)it << m_polyBits) | (dtPolyRef)ip;
+-#endif
+ 	}
+ 	
+ 	/// Decodes a standard polygon reference.
+@@ -527,21 +525,12 @@ public:
+ 	///  @see #encodePolyId
+ 	inline void decodePolyId(dtPolyRef ref, unsigned int& salt, unsigned int& it, unsigned int& ip) const
+ 	{
+-#ifdef DT_POLYREF64
+-		const dtPolyRef saltMask = ((dtPolyRef)1<<DT_SALT_BITS)-1;
+-		const dtPolyRef tileMask = ((dtPolyRef)1<<DT_TILE_BITS)-1;
+-		const dtPolyRef polyMask = ((dtPolyRef)1<<DT_POLY_BITS)-1;
+-		salt = (unsigned int)((ref >> (DT_POLY_BITS+DT_TILE_BITS)) & saltMask);
+-		it = (unsigned int)((ref >> DT_POLY_BITS) & tileMask);
+-		ip = (unsigned int)(ref & polyMask);
+-#else
+ 		const dtPolyRef saltMask = ((dtPolyRef)1<<m_saltBits)-1;
+ 		const dtPolyRef tileMask = ((dtPolyRef)1<<m_tileBits)-1;
+ 		const dtPolyRef polyMask = ((dtPolyRef)1<<m_polyBits)-1;
+ 		salt = (unsigned int)((ref >> (m_polyBits+m_tileBits)) & saltMask);
+ 		it = (unsigned int)((ref >> m_polyBits) & tileMask);
+ 		ip = (unsigned int)(ref & polyMask);
+-#endif
+ 	}
+ 
+ 	/// Extracts a tile's salt value from the specified polygon reference.
+@@ -550,13 +539,8 @@ public:
+ 	///  @see #encodePolyId
+ 	inline unsigned int decodePolyIdSalt(dtPolyRef ref) const
+ 	{
+-#ifdef DT_POLYREF64
+-		const dtPolyRef saltMask = ((dtPolyRef)1<<DT_SALT_BITS)-1;
+-		return (unsigned int)((ref >> (DT_POLY_BITS+DT_TILE_BITS)) & saltMask);
+-#else
+ 		const dtPolyRef saltMask = ((dtPolyRef)1<<m_saltBits)-1;
+ 		return (unsigned int)((ref >> (m_polyBits+m_tileBits)) & saltMask);
+-#endif
+ 	}
+ 	
+ 	/// Extracts the tile's index from the specified polygon reference.
+@@ -565,13 +549,8 @@ public:
+ 	///  @see #encodePolyId
+ 	inline unsigned int decodePolyIdTile(dtPolyRef ref) const
+ 	{
+-#ifdef DT_POLYREF64
+-		const dtPolyRef tileMask = ((dtPolyRef)1<<DT_TILE_BITS)-1;
+-		return (unsigned int)((ref >> DT_POLY_BITS) & tileMask);
+-#else
+ 		const dtPolyRef tileMask = ((dtPolyRef)1<<m_tileBits)-1;
+ 		return (unsigned int)((ref >> m_polyBits) & tileMask);
+-#endif
+ 	}
+ 	
+ 	/// Extracts the polygon's index (within its tile) from the specified polygon reference.
+@@ -580,13 +559,8 @@ public:
+ 	///  @see #encodePolyId
+ 	inline unsigned int decodePolyIdPoly(dtPolyRef ref) const
+ 	{
+-#ifdef DT_POLYREF64
+-		const dtPolyRef polyMask = ((dtPolyRef)1<<DT_POLY_BITS)-1;
+-		return (unsigned int)(ref & polyMask);
+-#else
+ 		const dtPolyRef polyMask = ((dtPolyRef)1<<m_polyBits)-1;
+ 		return (unsigned int)(ref & polyMask);
+-#endif
+ 	}
+ 
+ 	/// @}
+@@ -645,11 +619,9 @@ private:
+ 	dtMeshTile* m_nextFree;				///< Freelist of tiles.
+ 	dtMeshTile* m_tiles;				///< List of tiles.
+ 		
+-#ifndef DT_POLYREF64
+ 	unsigned int m_saltBits;			///< Number of salt bits in the tile ID.
+ 	unsigned int m_tileBits;			///< Number of tile bits in the tile ID.
+ 	unsigned int m_polyBits;			///< Number of poly bits in the tile ID.
+-#endif
+ };
+ 
+ /// Allocates a navigation mesh object using the Detour allocator.
+diff --git a/Detour/Source/DetourCommon.cpp b/Detour/Source/DetourCommon.cpp
+index a98d8c8..b5700f5 100644
+--- a/Detour/Source/DetourCommon.cpp
++++ b/Detour/Source/DetourCommon.cpp
+@@ -16,14 +16,14 @@
+ // 3. This notice may not be removed or altered from any source distribution.
+ //
+ 
++#include <math.h>
+ #include "DetourCommon.h"
+-#include "DetourMath.h"
+ 
+ //////////////////////////////////////////////////////////////////////////////////////////
+ 
+ float dtSqrt(float x)
+ {
+-	return dtMathSqrtf(x);
++	return sqrtf(x);
+ }
+ 
+ void dtClosestPtPointTriangle(float* closest, const float* p,
+diff --git a/Detour/Source/DetourNavMesh.cpp b/Detour/Source/DetourNavMesh.cpp
+index 9d627be..5174050 100644
+--- a/Detour/Source/DetourNavMesh.cpp
++++ b/Detour/Source/DetourNavMesh.cpp
+@@ -16,13 +16,13 @@
+ // 3. This notice may not be removed or altered from any source distribution.
+ //
+ 
++#include <math.h>
+ #include <float.h>
+ #include <string.h>
+ #include <stdio.h>
+ #include "DetourNavMesh.h"
+ #include "DetourNode.h"
+ #include "DetourCommon.h"
+-#include "DetourMath.h"
+ #include "DetourAlloc.h"
+ #include "DetourAssert.h"
+ #include <new>
+@@ -193,13 +193,11 @@ dtNavMesh::dtNavMesh() :
+ 	m_tileLutMask(0),
+ 	m_posLookup(0),
+ 	m_nextFree(0),
+-	m_tiles(0)
++	m_tiles(0),
++	m_saltBits(0),
++	m_tileBits(0),
++	m_polyBits(0)
+ {
+-#ifndef DT_POLYREF64
+-	m_saltBits = 0;
+-	m_tileBits = 0;
+-	m_polyBits = 0;
+-#endif
+ 	memset(&m_params, 0, sizeof(dtNavMeshParams));
+ 	m_orig[0] = 0;
+ 	m_orig[1] = 0;
+@@ -250,17 +248,11 @@ dtStatus dtNavMesh::init(const dtNavMeshParams* params)
+ 		m_nextFree = &m_tiles[i];
+ 	}
+ 	
+-	// Init ID generator values.
+-#ifndef DT_POLYREF64
+-	m_tileBits = dtIlog2(dtNextPow2((unsigned int)params->maxTiles));
+-	m_polyBits = dtIlog2(dtNextPow2((unsigned int)params->maxPolys));
+-	// Only allow 31 salt bits, since the salt mask is calculated using 32bit uint and it will overflow.
+-	m_saltBits = dtMin((unsigned int)31, 32 - m_tileBits - m_polyBits);
+-
+-	if (m_saltBits < 10)
+-		return DT_FAILURE | DT_INVALID_PARAM;
+-#endif
+-	
++    // Edited by TC
++    m_tileBits = STATIC_TILE_BITS;
++    m_polyBits = STATIC_POLY_BITS; 
++    m_saltBits = STATIC_SALT_BITS; 
++
+ 	return DT_SUCCESS;
+ }
+ 
+@@ -1242,11 +1234,7 @@ dtStatus dtNavMesh::removeTile(dtTileRef ref, unsigned char** data, int* dataSiz
+ 	tile->offMeshCons = 0;
+ 
+ 	// Update salt, salt should never be zero.
+-#ifdef DT_POLYREF64
+-	tile->salt = (tile->salt+1) & ((1<<DT_SALT_BITS)-1);
+-#else
+ 	tile->salt = (tile->salt+1) & ((1<<m_saltBits)-1);
+-#endif
+ 	if (tile->salt == 0)
+ 		tile->salt++;
+ 
+diff --git a/Detour/Source/DetourNavMeshBuilder.cpp b/Detour/Source/DetourNavMeshBuilder.cpp
+index 1bf271b..9d8471b 100644
+--- a/Detour/Source/DetourNavMeshBuilder.cpp
++++ b/Detour/Source/DetourNavMeshBuilder.cpp
+@@ -16,13 +16,13 @@
+ // 3. This notice may not be removed or altered from any source distribution.
+ //
+ 
++#include <math.h>
+ #include <stdio.h>
+ #include <stdlib.h>
+ #include <string.h>
+ #include <float.h>
+ #include "DetourNavMesh.h"
+ #include "DetourCommon.h"
+-#include "DetourMath.h"
+ #include "DetourNavMeshBuilder.h"
+ #include "DetourAlloc.h"
+ #include "DetourAssert.h"
+@@ -202,8 +202,8 @@ static int createBVTree(const unsigned short* verts, const int /*nverts*/,
+ 			if (z > it.bmax[2]) it.bmax[2] = z;
+ 		}
+ 		// Remap y
+-		it.bmin[1] = (unsigned short)dtMathFloorf((float)it.bmin[1]*ch/cs);
+-		it.bmax[1] = (unsigned short)dtMathCeilf((float)it.bmax[1]*ch/cs);
++		it.bmin[1] = (unsigned short)floorf((float)it.bmin[1]*ch/cs);
++		it.bmax[1] = (unsigned short)ceilf((float)it.bmax[1]*ch/cs);
+ 	}
+ 	
+ 	int curNode = 0;
+diff --git a/Detour/Source/DetourNavMeshQuery.cpp b/Detour/Source/DetourNavMeshQuery.cpp
+index 9debb4d..ec3a294 100644
+--- a/Detour/Source/DetourNavMeshQuery.cpp
++++ b/Detour/Source/DetourNavMeshQuery.cpp
+@@ -16,13 +16,13 @@
+ // 3. This notice may not be removed or altered from any source distribution.
+ //
+ 
++#include <math.h>
+ #include <float.h>
+ #include <string.h>
+ #include "DetourNavMeshQuery.h"
+ #include "DetourNavMesh.h"
+ #include "DetourNode.h"
+ #include "DetourCommon.h"
+-#include "DetourMath.h"
+ #include "DetourAlloc.h"
+ #include "DetourAssert.h"
+ #include <new>
+@@ -99,8 +99,9 @@ inline float dtQueryFilter::getCost(const float* pa, const float* pb,
+ 	return dtVdist(pa, pb) * m_areaCost[curPoly->getArea()];
+ }
+ #endif	
+-	
+-static const float H_SCALE = 0.999f; // Search heuristic scale.
++
++// Edited by TC
++static const float H_SCALE = 2.0f; // Search heuristic scale. 
+ 
+ 
+ dtNavMeshQuery* dtAllocNavMeshQuery()
+@@ -3504,7 +3505,7 @@ dtStatus dtNavMeshQuery::findDistanceToWall(dtPolyRef startRef, const float* cen
+ 	dtVsub(hitNormal, centerPos, hitPos);
+ 	dtVnormalize(hitNormal);
+ 	
+-	*hitDist = dtMathSqrtf(radiusSqr);
++	*hitDist = sqrtf(radiusSqr);
+ 	
+ 	return status;
+ }
+diff --git a/Detour/Source/DetourNode.cpp b/Detour/Source/DetourNode.cpp
+index 5cf6548..1d18977 100644
+--- a/Detour/Source/DetourNode.cpp
++++ b/Detour/Source/DetourNode.cpp
+@@ -22,30 +22,17 @@
+ #include "DetourCommon.h"
+ #include <string.h>
+ 
+-#ifdef DT_POLYREF64
+-// From Thomas Wang, https://gist.github.com/badboy/6267743
+ inline unsigned int dtHashRef(dtPolyRef a)
+ {
+-	a = (~a) + (a << 18); // a = (a << 18) - a - 1;
+-	a = a ^ (a >> 31);
+-	a = a * 21; // a = (a + (a << 2)) + (a << 4);
+-	a = a ^ (a >> 11);
+-	a = a + (a << 6);
+-	a = a ^ (a >> 22);
+-	return (unsigned int)a;
++    // Edited by TC
++    a = (~a) + (a << 18);
++    a = a ^ (a >> 31);
++    a = a * 21;
++    a = a ^ (a >> 11);
++    a = a + (a << 6);
++    a = a ^ (a >> 22);
++    return (unsigned int)a;
+ }
+-#else
+-inline unsigned int dtHashRef(dtPolyRef a)
+-{
+-	a += ~(a<<15);
+-	a ^=  (a>>10);
+-	a +=  (a<<3);
+-	a ^=  (a>>6);
+-	a += ~(a<<11);
+-	a ^=  (a>>16);
+-	return (unsigned int)a;
+-}
+-#endif
+ 
+ //////////////////////////////////////////////////////////////////////////////////////////
+ dtNodePool::dtNodePool(int maxNodes, int hashSize) :
+diff --git a/DetourCrowd/Source/DetourObstacleAvoidance.cpp b/DetourCrowd/Source/DetourObstacleAvoidance.cpp
+index 0fad9ef..d3f90b7 100644
+--- a/DetourCrowd/Source/DetourObstacleAvoidance.cpp
++++ b/DetourCrowd/Source/DetourObstacleAvoidance.cpp
+@@ -18,10 +18,10 @@
+ 
+ #include "DetourObstacleAvoidance.h"
+ #include "DetourCommon.h"
+-#include "DetourMath.h"
+ #include "DetourAlloc.h"
+ #include "DetourAssert.h"
+ #include <string.h>
++#include <math.h>
+ #include <float.h>
+ #include <new>
+ 
+@@ -58,7 +58,7 @@ static int isectRaySeg(const float* ap, const float* u,
+ 	dtVsub(v,bq,bp);
+ 	dtVsub(w,ap,bp);
+ 	float d = dtVperp2D(u,v);
+-	if (dtMathFabs(d) < 1e-6f) return 0;
++	if (fabsf(d) < 1e-6f) return 0;
+ 	d = 1.0f/d;
+ 	t = dtVperp2D(v,w) * d;
+ 	if (t < 0 || t > 1) return 0;
+@@ -482,7 +482,7 @@ int dtObstacleAvoidanceQuery::sampleVelocityAdaptive(const float* pos, const flo
+ 	const int nd = dtClamp(ndivs, 1, DT_MAX_PATTERN_DIVS);
+ 	const int nr = dtClamp(nrings, 1, DT_MAX_PATTERN_RINGS);
+ 	const float da = (1.0f/nd) * DT_PI*2;
+-	const float dang = dtMathAtan2f(dvel[2], dvel[0]);
++	const float dang = atan2f(dvel[2], dvel[0]);
+ 	
+ 	// Always add sample at zero
+ 	pat[npat*2+0] = 0;
+diff --git a/Recast/Include/Recast.h b/Recast/Include/Recast.h
+index 83ca606..66974cd 100644
+--- a/Recast/Include/Recast.h
++++ b/Recast/Include/Recast.h
+@@ -243,7 +243,7 @@ struct rcConfig
+ };
+ 
+ /// Defines the number of bits allocated to rcSpan::smin and rcSpan::smax.
+-static const int RC_SPAN_HEIGHT_BITS = 13;
++static const int RC_SPAN_HEIGHT_BITS = 16; // EDITED BY TC
+ /// Defines the maximum value for rcSpan::smin and rcSpan::smax.
+ static const int RC_SPAN_MAX_HEIGHT = (1<<RC_SPAN_HEIGHT_BITS)-1;
+ 
+@@ -255,9 +255,9 @@ static const int RC_SPANS_PER_POOL = 2048;
+ /// @see rcHeightfield
+ struct rcSpan
+ {
+-	unsigned int smin : 13;			///< The lower limit of the span. [Limit: < #smax]
+-	unsigned int smax : 13;			///< The upper limit of the span. [Limit: <= #RC_SPAN_MAX_HEIGHT]
+-	unsigned int area : 6;			///< The area id assigned to the span.
++	unsigned int smin : 16;			///< The lower limit of the span. [Limit: < #smax]
++	unsigned int smax : 16;			///< The upper limit of the span. [Limit: <= #RC_SPAN_MAX_HEIGHT]
++	unsigned char area;			    ///< The area id assigned to the span.
+ 	rcSpan* next;					///< The next span higher up in column.
+ };
+ 
+-- 
+1.9.0.msysgit.0
+