#include "stdafx.h"
#include "TerrainMapEngine.h"
#include "TerrainSeamlessWorldInfoForClient.h"
#include "TerrainAttributeInfoForMap.h"
#include <geometry/X2DPathFinder.h>

#include <toolkit/XCyclicIndex.h>
#include "SDebug_Util.h"

/// 2라는 수치는 기존에 길찾기 할 때 쓰이던 수치이다.
int CTerrainMapEngine::MIN_ATTRIBUTE_COLLISION_LENGTH = 2;

//void CTerrainMapEngine::CreateAttributePolygonInfoForMap( const char* szAttributePolygonFileName, int nMapX, int nMapY )
void CTerrainMapEngine::CreateAttributePolygonInfoForMap( const K3DVector& vStart, const K3DVector& vEnd )
{
	float fMapLen = float( m_pSeamlessWorldInfo->GetTileCountPerSegment() ) * float(m_pSeamlessWorldInfo->GetSegmentCountPerMap() )
		* m_pSeamlessWorldInfo->GetTileLength();

	int nStartMapX = (int)(vStart.x / fMapLen);
	int nStartMapY = (int)(vStart.y / fMapLen);
	int nEndMapX = (int)(vEnd.x / fMapLen);
	int nEndMapY = (int)(vEnd.y / fMapLen);
	int nTemp;

	if(nStartMapX > nEndMapX)
	{
		nTemp = nEndMapX;
		nEndMapX = nStartMapX;
		nStartMapX = nTemp;
	}
	if(nStartMapY > nEndMapY)
	{
		nTemp = nEndMapY;
		nEndMapY = nStartMapY;
		nStartMapY = nTemp;
	}

	assert( ( nStartMapX >= 0 && nStartMapY >= 0 ) && "Map Index Wrong!!!" );

	int numMapsToLoad = (nEndMapX - nStartMapX + 1) * (nEndMapY - nStartMapY + 1);

	int numAttributeInfos = m_vAttributeInfos.size();
	bool bNeedLoading = false;
	int nRes = 0;

	//if(numAttributeInfos != numMapsToLoad)
	//{
	//	bNeedLoading = true;
	//}
	if(numAttributeInfos < numMapsToLoad)
	{
		bNeedLoading = true;
	}
	else
	{
		//for(int i = 0; i < numMapsToLoad; i++)
		for(int i = 0; i < numAttributeInfos; i++)
		{
			for(int j = nStartMapY; j <= nEndMapY; j++)
			{
				for(int k = nStartMapX; k <= nEndMapX; k++)
				{
					if(!m_vAttributeInfos[i]->CheckMap(k, j)) ++nRes;
				}                
			}
		}

		if(numMapsToLoad != nRes) bNeedLoading = true;
	}

	std::string strFileName;

	if(bNeedLoading)
	{
		SAFE_DELETE_VECTOR(m_vAttributeInfos);
		//SAFE_DELETE_VECTOR(m_vAttributePolygons);
		DeleteAttrQuadTree();

		//if(m_bDrawAttributeWire) m_prWireAttributePolygon->Clear();
		if(m_bCreateAttributeWire) m_prWireAttributePolygon->Clear();

		for(int i = nStartMapY; i <= nEndMapY; i++)
		{
			for(int j = nStartMapX; j <= nEndMapX; j++)
			{
				strFileName = m_pSeamlessWorldInfo->GetAttributePolygonFileName( j, i );

				if( strFileName.length() <= 0 ) continue;
				
				//CTerrainAttributeInfoForMap* pAttrubiteInfo = new CTerrainAttributeInfoForMap( this, strFileName.c_str(), j, i, m_bDrawAttributeWire );
				CTerrainAttributeInfoForMap* pAttrubiteInfo = new CTerrainAttributeInfoForMap( this, strFileName.c_str(), j, i, m_bCreateAttributeWire );
				m_vAttributeInfos.push_back(pAttrubiteInfo);
			}                
		}
	}

	//if( m_pCurAttributePolygonInfo == NULL )
	//{
	//	m_pCurAttributePolygonInfo	=	new CTerrainAttributeInfoForMap( this, szAttributePolygonFileName, nMapX, nMapY, m_bDrawAttributeWire );
	//}
	//else
	//{
	//	if( m_pCurAttributePolygonInfo->CheckMap(nMapX, nMapY))
	//	{
	//		SAFE_DELETE(m_pCurAttributePolygonInfo);
	//		SAFE_DELETE_VECTOR(m_vAttributePolygons);

	//		if(m_bDrawAttributeWire) m_prWireAttributePolygon->Clear();

	//		m_pCurAttributePolygonInfo	=	new CTerrainAttributeInfoForMap( this, szAttributePolygonFileName, nMapX, nMapY, m_bDrawAttributeWire );
	//	}
	//}

	//if( m_pCurAttributePolygonInfo == NULL )
	//{
	//	m_pCurAttributePolygonInfo	=	new CTerrainAttributeInfoForMap( this, szAttributePolygonFileName, nMapX, nMapY, m_bDrawAttributeWire );
	//}
	//else
	//{
	//	if( m_pCurAttributePolygonInfo->CheckMap(nMapX, nMapY))
	//	{
	//		SAFE_DELETE(m_pCurAttributePolygonInfo);
	//		SAFE_DELETE_VECTOR(m_vAttributePolygons);
	//		
	//		if(m_bDrawAttributeWire) m_prWireAttributePolygon->Clear();

	//		m_pCurAttributePolygonInfo	=	new CTerrainAttributeInfoForMap( this, szAttributePolygonFileName, nMapX, nMapY, m_bDrawAttributeWire );
	//	}
	//}

	if( m_bDrawAttributeWire )
	{
		m_prWireQuadTree->Clear();
		struct QuadTreeSegmentCollector
		{
			void operator()( const attribute_point_quadtree_t::Node& node )
			{
				mSegments.push_back( node.GetEffectiveArea() );
			}
			std::vector< X2D::Rect< int > > mSegments;
		};
		QuadTreeSegmentCollector Collector;
		m_AttrPointQuadTree.Iterate( Collector );

		if( !Collector.mSegments.empty() )
		{
			K3DVector v1, v2, v3, v4;
			WORD tile = 0;
			for( std::vector< X2D::Rect< int > >::iterator it = Collector.mSegments.begin(); it != Collector.mSegments.end(); ++it )
			{
				X2D::Rect< int >& Area = (*it);
				
				v1.x = (K3DVALUE)Area.GetLeft();
				v1.y = (K3DVALUE)Area.GetTop();
				v1.z = 15.f;
				
				v2.x = (K3DVALUE)Area.GetRight();
				v2.y = (K3DVALUE)Area.GetTop();
				v2.z = 15.f;

				v3.x = (K3DVALUE)Area.GetRight();
				v3.y = (K3DVALUE)Area.GetBottom();
				v3.z = 15.f;

				v4.x = (K3DVALUE)Area.GetLeft();
				v4.y = (K3DVALUE)Area.GetBottom();
				v4.z = 15.f;
				
				m_prWireQuadTree->AddLine( v1, v2, KColor( 0, 255, 0, 255 ) );
				m_prWireQuadTree->AddLine( v2, v3, KColor( 0, 255, 0, 255 ) );
				m_prWireQuadTree->AddLine( v3, v4, KColor( 0, 255, 0, 255 ) );
				m_prWireQuadTree->AddLine( v4, v1, KColor( 0, 255, 0, 255 ) );
			}
		}
	}
}

bool CTerrainMapEngine::CollisionToLine( const K3DVector& vStart, const K3DVector& vEnd )
{
	X2D::Line<int> line( vStart.x, vStart.y, vEnd.x, vEnd.y );
	if( m_AttrPolygonsQuadTree.Collision( line ) == false )
	{
		return false;
	}

	// 끝지점이 못가는 지역이라면 일단 허용한다.
	X2D::Point<int> ptStart( vStart.x, vStart.y );
	X2D::Point<int> ptEnd( vEnd.x, vEnd.y );
	if( m_AttrPolygonsQuadTree.Collision( ptStart ) == false &&
		m_AttrPolygonsQuadTree.Collision( ptEnd ) == true )
	{
		return false;
	}

	return true;
}

void CTerrainMapEngine::FindDetour( const K3DVector& vStart, const K3DVector& vEnd, PATH& vPath, bool bRestraint )
{
	CreateAttributePolygonInfoForMap(vStart, vEnd);

	X2D::Point<int> ptStart, ptEnd;
	ptStart.x = static_cast<int>(vStart.x);
	ptStart.y = static_cast<int>(vStart.y);
	ptEnd.x = static_cast<int>(vEnd.x);
	ptEnd.y = static_cast<int>(vEnd.y);

	static size_t s_unLimit = 500;

	typedef X2D::IndexedPoint< int >		indexed_point_t;
	typedef X2D::LeakyPolygon< int >		leaky_polygon_t;
	typedef std::vector< indexed_point_t* >	indexed_point_vector_t;
	typedef std::vector< leaky_polygon_t* >	leaky_polygon_vector_t;

	indexed_point_vector_t	vIndexedPoints;
	leaky_polygon_vector_t	vLeakyPolygons;

	// ptStart와 ptEnd를 포함하는 직각 삼각형을 만든다.
	X2D::Point<int> ptRegion[3];

	ptRegion[0] = ptStart - ptEnd;

	//각도 제한 크기를 두배로 확대 시켜 약화
	ptRegion[0].x = ptRegion[0].x*2;
	ptRegion[0].y = ptRegion[0].y*2;

	ptRegion[1].x = -ptRegion[0].y;
	ptRegion[1].y = ptRegion[0].x;
	ptRegion[2].x = ptRegion[0].y;
	ptRegion[2].y = -ptRegion[0].x;
	ptRegion[0] += ptEnd;
	ptRegion[1] += ptEnd;
	ptRegion[2] += ptEnd;

	X2D::Polygon<int> plRegion((X2D::Point<int>*) ptRegion, ((X2D::Point<int>*) ptRegion) + 3);

	const int c_nOfsLimit = 10;
	bool bBreak = false;

	{
		X2D::Line<int> line( vStart.x, vStart.y, vEnd.x, vEnd.y );
		if( m_AttrPolygonsQuadTree.Collision( line ) == false )
		{
			vPath.push_back(ptStart);
			vPath.push_back(ptEnd);

			goto _DRAWWIRE;
		}
	}

	/// 2012.02.22 길찾기 블럭을 임의로 추가하는 테스트 코드 - prodongi
#ifdef KMOVE_DEBUG
	static bool testAdd = false;
	static bool testDel = false;
	///								x0	   y0	  x1	 y1     x2     y2						
	static int cl[3][10] = {	{	7037, 6691, 6917, 6967, 6942, 6979, 7061, 6714, 7037, 6691 },  
	{	6942, 6979, 6808, 6682, 6786, 6719, 6917, 6967, 6942, 6979 }, 
	{	6786, 6719, 7061, 6714, 7037, 6691, 6808, 6682, 6786, 6719 } };

	static X2D::IndexedPoint< int >* testP[3] = {	NULL, NULL, NULL };

	if (testAdd)
	{
		testAdd = false;		

		if (!testP[0])
		{
			for (int i = 0; i < 3; ++i)
			{
				X2D::Point<int>* p = new X2D::Point<int>[5];
				p[0].Set(cl[i][0], cl[i][1]);
				p[1].Set(cl[i][2], cl[i][3]);
				p[2].Set(cl[i][4], cl[i][5]);
				p[3].Set(cl[i][6], cl[i][7]);
				p[4].Set(cl[i][8], cl[i][9]);

				X2D::Polygon<int>* polygon = new X2D::Polygon<int>;
				if (polygon->Set(p, p+3))
				{
					int index = 0;
					testP[i] = new X2D::IndexedPoint<int>(polygon, index);
					m_AttrPointQuadTree.DuplicateAdd(testP[i], X2D::IndexedPoint< int >::InputQuadTree());
				}
			}			
		}		
	}
	if (testDel)
	{
		testDel = false;
		if (testP[0])
		{
			for (int i = 0; i < 3; ++i)
			{
				X2D::Point<int> t(cl[i][0], cl[i][1]);
				m_AttrPointQuadTree.Remove(t);
				SAFE_DELETE(testP[i]);
			}
		}
	}
#endif

	if( m_AttrPolygonsQuadTree.Collision( ptStart ) )
	{
		X2D::Point< int > ptTemp = ptStart;

		for( int i = 0; i <= c_nOfsLimit; i++ )
		{
			if( bBreak ) break;

			for( int nY = -i; nY <= i; nY++ )
			{
				if( bBreak ) break;

				for( int nX = -i; nX <= i; nX++ )
				{
					if( bBreak ) break;

					if( nY != -i && nY != i && nX != -i && nX != i ) continue;

					ptTemp = ptStart;
					ptTemp.x += nX;
					ptTemp.y += nY;

					if( m_AttrPolygonsQuadTree.Collision( ptTemp ) )
					{
						if( i == c_nOfsLimit && nY == c_nOfsLimit && nX == c_nOfsLimit )
						{
							assert( 0 );
							ptTemp = ptStart;
						}
					}
					else
					{
						bBreak = true;
					}
				}
			}
		}

		ptStart = ptTemp;
	}

	//   // 디버그용 코드 by blackfish ->
	//X2D::Point< int > ptTemp( 164148, 52534 );

	//if( !m_AttrPointQuadTree.Collision( ptTemp ) )
	//{
	//	assert( 0 );
	//}

	//// <- 디버그용 코드 by blackfish

	//// 디버그용 코드 by blackfish ->
	////X2D::Line< int > theLine( ptStart.x, ptStart.y, ptEnd.x, ptEnd.y );
	//X2D::Box< int > theBox( ptStart, ptEnd );

	////m_AttrPointQuadTree.Enum( theLine, &vIndexedPoints );
	//m_AttrPointQuadTree.Enum( theBox, &vIndexedPoints );

	//_oprint( "Start Point\n");
	//_oprint( "X : %d, Y : %d\n", ptStart.x, ptStart.y );
	//_oprint( "End Point\n");
	//_oprint( "X : %d, Y : %d\n", ptEnd.x, ptEnd.y );

	//_oprint( "Number of Polygons : %d\n", vIndexedPoints.size() );

	//for( size_t i = 0; i < vIndexedPoints.size(); i++ )
	//{
	//	_oprint( "Polygon %d\n", i );
	//	_oprint( "Number of Points : %d\n", vIndexedPoints[ i ]->Size() );

	//	for( size_t j = 0; j < vIndexedPoints[ i ]->Size(); j++ )
	//	{
	//		_oprint( "Point %d\n", j );
	//		_oprint( "X : %d, Y : %d\n", vIndexedPoints[ i ]->GetPoint( j ).x, vIndexedPoints[ i ]->GetPoint( j ).y );
	//	}
	//}

	//vIndexedPoints.erase( vIndexedPoints.begin(), vIndexedPoints.end() );
	//// <- 디버그용 코드 by blackfish

	if(m_AttrPolygonsQuadTree.Collision(ptEnd))
	{
		if(vPath.size() > s_unLimit) vPath.clear();
		else vPath.erase(vPath.begin(), vPath.end());

		X2D::Point<int> ptThePoint;
		int intersectDistance;
		if( getIntersectInfoNearbyEndPoint( ptStart, ptEnd, ptThePoint, intersectDistance ) == true )
		{
			ptEnd = ptThePoint;
		}
		else
		{
			X2D::Point< int > ptTemp = ptEnd;

			for( int i = 0; i <= c_nOfsLimit; i++ )
			{
				if( bBreak ) break;

				for( int nY = -i; nY <= i; nY++ )
				{
					if( bBreak ) break;

					for( int nX = -i; nX <= i; nX++ )
					{
						if( bBreak ) break;

						if( nY != -i && nY != i && nX != -i && nX != i ) continue;

						ptTemp = ptEnd;
						ptTemp.x += nX;
						ptTemp.y += nY;

						if( m_AttrPolygonsQuadTree.Collision( ptTemp ) )
						{
							if( i == c_nOfsLimit && nY == c_nOfsLimit && nX == c_nOfsLimit )
							{
								assert( 0 );
								ptTemp = ptEnd;
							}
						}
						else
						{
							bBreak = true;
						}
					}
				}
			}

			ptEnd = ptTemp;
		}
	}

	if( plRegion.Size() >= 3 )
	{
		if( bRestraint )
		{
			m_AttrPointQuadTree.EnumLoose( plRegion, &vIndexedPoints );
		}
		else
		{
			m_AttrPointQuadTree.Enum( &vIndexedPoints );
		}
	}

	if(vPath.size() > s_unLimit) vPath.clear();
	//else vPath.erase(vPath.begin(), vPath.end());	// Find에서 해주니까 필요없다.

	// make leaky polygon resource -------------------------------------------------------------------------------------------------
	{
		std::sort( vIndexedPoints.begin(), vIndexedPoints.end(), indexed_point_t::Less() );
		vIndexedPoints.erase( std::unique( vIndexedPoints.begin(), vIndexedPoints.end() ), vIndexedPoints.end() );
		indexed_point_vector_t::iterator itPt = vIndexedPoints.begin(), endPt = vIndexedPoints.end();
		std::vector< indexed_point_t > vPtBuffer;

		xmod::cyclic_index< int > CurrGlobalIndex( 0, vIndexedPoints.size() );
		xmod::cyclic_index< int > NextGlobalIndex( 0, vIndexedPoints.size() );
		indexed_point_vector_t LocalPoints;
		for( ; itPt != endPt; ++itPt, ++CurrGlobalIndex )
		{
			NextGlobalIndex = CurrGlobalIndex + 1;

			indexed_point_t* pCurrGlobalPoint = *itPt;
			indexed_point_t* pNextGlobalPoint = vIndexedPoints.at( NextGlobalIndex );

			LocalPoints.push_back( pCurrGlobalPoint );

			if( !pNextGlobalPoint->hasSameOwner( *pCurrGlobalPoint ) || pCurrGlobalPoint == pNextGlobalPoint || CurrGlobalIndex == CurrGlobalIndex.getMax() )
			{
				// end of point list which has a same owner
				// let's find hole in the point list
				const size_t LocalSize	= LocalPoints.size();
				bool		 FoundHole	= false;
				xmod::cyclic_index< int > CurrIndex( 0, LocalSize );
				xmod::cyclic_index< int > PrevIndex( 0, LocalSize );
				CurrIndex = CurrIndex.getMax();

				for( size_t index = 0; index < LocalSize; ++index, --CurrIndex )
				{
					PrevIndex = CurrIndex - 1;
					if( !LocalPoints.at( CurrIndex )->isPrevLinked( *LocalPoints.at( PrevIndex ) ) )
					{
						FoundHole = true;
						break;
					}
				}

				if( FoundHole )
				{
					// we found a hole in the point list, the index of hole is CurrIndex.
					xmod::cyclic_index< int > NextIndex( 0, LocalSize );

					for( size_t index = 0; index < LocalSize; ++index, ++CurrIndex )
					{
						NextIndex = CurrIndex + 1;
						indexed_point_t* pCurrPoint = LocalPoints.at( CurrIndex );
						indexed_point_t* pNextPoint = LocalPoints.at( NextIndex );
						vPtBuffer.push_back( *pCurrPoint );

						if( !pNextPoint->isPrevLinked( *pCurrPoint ) )
						{
							// found a dead end
							vLeakyPolygons.push_back( new leaky_polygon_t( vPtBuffer.begin(), vPtBuffer.end() ) );
							vPtBuffer.clear();
						}
					}
				}
				else
				{
					for( size_t index = 0; index < LocalSize; ++index )
						vPtBuffer.push_back( *LocalPoints.at( index ) );
					vLeakyPolygons.push_back( new leaky_polygon_t( vPtBuffer.begin(), vPtBuffer.end() ) );
					vPtBuffer.clear();
				}

				LocalPoints.clear();
			}
		}
	}
	// -----------------------------------------------------------------------------------------------------------------------------

	//X2D::PathFinder< int, X2D::Polygon<int>* >::Find( vIndexedPoints.begin(), vIndexedPoints.end(), ptStart, ptEnd, vPath, 1000 );
	X2D::PathFinder< int, X2D::LeakyPolygon<int>* >::Find( vLeakyPolygons.begin(), vLeakyPolygons.end(), ptStart, ptEnd, vPath );

	bool bCancelPathFind = vPath.empty();

	if( vPath.empty() ) { vPath.push_back( ptStart ); vPath.push_back( ptEnd ); }

	if( bRestraint && !vPath.empty() )
	{
		for(size_t i = 1; i + 1 < vPath.size() ; i++)	// ptStart와 ptEnd는 빼고 계산한다
		{
			assert( vPath.size() > i && "i 범위 Over" );

			if(!plRegion.IsInclude(vPath[i]))	// vPath 중 plRegion 밖으로 나간 point 가 있다면
			{
				bCancelPathFind = true;
				break;
			}
		}
	}

	if( bCancelPathFind )
	{
		if(vPath.size() > s_unLimit) vPath.clear();
		else vPath.erase(vPath.begin(), vPath.end());

		X2D::Point<int> ptThePoint;
		int intersectDistance;
		if( getIntersectInfo(ptStart, ptEnd, ptThePoint, intersectDistance) )
		{
			if( ptStart.GetDistance( ptThePoint ) > 2 )	// 충돌 폴리곤이랑 붙어있을때 뻘짓하는 거 방지
			{
				vPath.push_back(ptStart);
				vPath.push_back(ptThePoint);
			}
		}

		if(m_bDrawAttributeWire )
			goto _DRAWWIRE;
	}

	//if(vIndexedPoints.size() > s_unLimit) vIndexedPoints.clear();
	//else vIndexedPoints.erase(vIndexedPoints.begin(), vIndexedPoints.end());

_DRAWWIRE:
	if(m_bDrawAttributeWire)
	{
		int size = vPath.size();

		m_prWireDetour->Clear();

		K3DVertex v1, v2;
		WORD wTile=0;

		for(int i = 1; i < size; i++)
		{
			v1.x = (float) vPath[i - 1].x;
			v1.y = (float) vPath[i - 1].y;
			GetTerrainHeight(v1.x, v1.y, v1.z,wTile );
			v1.z += 20.0f;

			v2.x = (float) vPath[i].x;
			v2.y = (float) vPath[i].y;
			GetTerrainHeight(v2.x, v2.y, v2.z,wTile );
			v2.z +=	20.f;

			m_prWireDetour->AddLine(v1, v2, KColor(255, 192, 203, 255));
		}

		// draw candidate polygon
		for( leaky_polygon_vector_t::iterator it = vLeakyPolygons.begin(); it != vLeakyPolygons.end(); ++it )
		{
			X2D::LeakyPolygon< int >& Polygon = *(*it);
			for( size_t index = 0; index < Polygon.Size(); ++index )
			{
				v1.x = (float)Polygon.GetPoint( index ).x;
				v1.y = (float)Polygon.GetPoint( index ).y;
				GetTerrainHeight( v1.x, v1.y, v1.z, wTile );
				v1.z += 20.0f;

				v2.x = (float)Polygon.GetNextPoint( index ).x;
				v2.y = (float)Polygon.GetNextPoint( index ).y;
				GetTerrainHeight( v2.x, v2.y, v2.z, wTile );
				v2.z += 20.0f;

				m_prWireDetour->AddLine( v1, v2, KColor( 255, 255, 0, 255 ) );
			}
		}
	}

	for( leaky_polygon_vector_t::iterator it = vLeakyPolygons.begin(); it != vLeakyPolygons.end(); ++it )
		if( (*it) ) delete *it;

/*
	X2D::Point<int> ptStart( vStart.x, vStart.y ), ptEnd( vEnd.x, vEnd.y );
	X2D::Line<int> line( vStart.x, vStart.y, vEnd.x, vEnd.y );
	if( m_AttrPolygonsQuadTree.Collision( line ) == false )
	{
		vPath.push_back(ptStart);
		vPath.push_back(ptEnd);
		return;
	}

	bool bSkipFind = false;

	if( m_AttrPolygonsQuadTree.Collision( ptStart ) )
	{
		const int c_nOfsLimit = 10;
		bool bBreak = false;
		X2D::Point< int > ptTemp = ptStart;

		for( int i = 0; i <= c_nOfsLimit; i++ )
		{
			if( bBreak ) break;

			for( int nY = -i; nY <= i; nY++ )
			{
				if( bBreak ) break;

				for( int nX = -i; nX <= i; nX++ )
				{
					if( bBreak ) break;

					if( nY != -i && nY != i && nX != -i && nX != i ) continue;

					ptTemp = ptStart;
					ptTemp.x += nX;
					ptTemp.y += nY;

					if( m_AttrPolygonsQuadTree.Collision( ptTemp ) )
					{
						if( i == c_nOfsLimit && nY == c_nOfsLimit && nX == c_nOfsLimit )
						{
							assert( 0 );
							ptTemp = ptStart;
						}
					}
					else
					{
						bBreak = true;
					}
				}
			}
		}

		ptStart = ptTemp;
	}

	if(m_AttrPolygonsQuadTree.Collision(ptEnd))
	{
		const size_t s_unLimit = 500;
		if(vPath.size() > s_unLimit) vPath.clear();
		else vPath.erase(vPath.begin(), vPath.end());

		X2D::Point<int> ptThePoint;
		int intersectDistance;
		if( getIntersectInfo(ptStart, ptEnd, ptThePoint, intersectDistance) )
		{
			if( ptStart.GetDistance( ptThePoint ) > 2 )	// 충돌 폴리곤이랑 붙어있을때 뻘짓하는 거 방지
			{
				vPath.push_back(ptStart);
				vPath.push_back(ptThePoint);
			}
		}

		bSkipFind = true;
	}

	if( bSkipFind == false )
	{
		X2D::Box<int> boxRegion( ptStart, ptEnd );
		std::vector<X2D::Polygon<int> *> pathFindPolygons;
		m_AttrPolygonsQuadTree.Enum( boxRegion, &pathFindPolygons );

		X2D::PathFinder< int, X2D::Polygon<int>* >::Find( pathFindPolygons.begin(), pathFindPolygons.end(), ptStart, ptEnd, vPath );

		// 길찾기가 실패했다면 직선 거리로 가장 가까이 출돌 되는 곳으로 이동한다.
		if( vPath.empty() )
		{
			X2D::Point<int> ptThePoint;
			int intersectDistance;
			if( getIntersectInfo(ptStart, ptEnd, ptThePoint, intersectDistance) )
			{
				if( ptStart.GetDistance( ptThePoint ) > 2 )	// 충돌 폴리곤이랑 붙어있을때 뻘짓하는 거 방지
				{
					vPath.push_back(ptStart);
					vPath.push_back(ptThePoint);
				}
			}
		}
	}

	if(m_bDrawAttributeWire)
	{
		int size = vPath.size();

		m_prWireDetour->Clear();

		K3DVertex v1, v2;
		WORD wTile=0;

		for(int i = 1; i < size; i++)
		{
			v1.x = (float) vPath[i - 1].x;
			v1.y = (float) vPath[i - 1].y;
			GetTerrainHeight(v1.x, v1.y, v1.z,wTile );
			v1.z += 20.0f;

			v2.x = (float) vPath[i].x;
			v2.y = (float) vPath[i].y;
			GetTerrainHeight(v2.x, v2.y, v2.z,wTile );
			v2.z +=	20.f;

			m_prWireDetour->AddLine(v1, v2, KColor(255, 192, 203, 255));
		}
	}
	*/
}

void CTerrainMapEngine::addCustomBlock(unsigned int handle, int* line)
{
	X2D::Point<int>* p = new X2D::Point<int>[2];
	p[0].Set(line[0], line[1]);
	p[1].Set(line[2], line[3]);

	m_blockList.insert(std::make_pair(handle, p));
}

void CTerrainMapEngine::delCustomBlock(unsigned int handle)
{
	std::map<unsigned int, X2D::Point<int>*>::iterator it = m_blockList.find(handle);
	if (it == m_blockList.end())
		return ;

	delete[] it->second;
	m_blockList.erase(it);
}

bool CTerrainMapEngine::collisionAttrQuad(float sx, float sy, float& ex, float& ey, float& collisionTheta, bool checkStartZeroLen)
{
	X2D::Point<int> ptStart, ptEnd;
	ptStart.x = (int)sx;
	ptStart.y = (int)sy;
	ptEnd.x = (int)ex;
	ptEnd.y = (int)ey;

#ifdef KMOVE_DEBUG
	CreateAttributePolygonInfoForMap(K3DVector(sx, sy, 0.0f), K3DVector(ex, ey, 0.0f));
#endif

	X2D::Point<int> ptThePoint;
	X2D::Line<int> intersectLine;
	int intersectDistance;

	if (getIntersectInfo(ptStart, ptEnd, ptThePoint, intersectDistance, &intersectLine))
	{
		K3DVector a((float)intersectLine.begin.x, (float)intersectLine.begin.y, 0.0f);
		K3DVector b((float)intersectLine.end.x, (float)intersectLine.end.y, 0.0f);
		K3DVector c(sx, sy, 0.0f);
		int len = (int)sMathUtil::getIntersectDistance(a, b, c);
		if( len <= CTerrainMapEngine::MIN_ATTRIBUTE_COLLISION_LENGTH)
		{
			if (0 == len && checkStartZeroLen)
			{
				/// 끼인 경우를 방지 하기 위한 코드
				/// 시작 위치가 바운딩 라인과 겹쳐 있는 경우에 이동이 되지 않고 있다. 
				/// 목적 위치로의 길찾기가 가능 할 경우에는 이동이 되야 되기 때문에  길찾기가 가능한지를 체크하고 가능하다면 
				/// 시작 위치에서 목적 위치로의 각 축에 1을 더해 줘서 다시 교차 점을 찾는다. 1을 더해 준 이유는 교차점 검사가 정수형이고
				/// 다시 끼이는걸 방지하기 위해서이다.
				K3DVector s(sx, sy, 0.0f);
				K3DVector e(ex, ey, 0.0f);
				PATH path;
				FindDetour(s, e, path, true);
				if (!path.empty())
				{
					if (ptEnd.x > ptStart.x) s.x++;
					if (ptEnd.x < ptStart.x) s.x--;
					if (ptEnd.y > ptStart.y) s.y++;
					if (ptEnd.y < ptStart.y) s.y--;
					path.clear();
					return collisionAttrQuad(s.x, s.y, ex, ey, collisionTheta, false);
				}
				path.clear();
			}
			collisionTheta = getDegreeBetweenLine(ptStart, ptEnd, intersectLine.begin, intersectLine.end, ptThePoint);
			return true;
		}
		else
		{
			K3DVector interP((float)ptThePoint.x, (float)ptThePoint.y, 0.0f);
			K3DVector perP = sMathUtil::getPerpendicularVector(a, b, c, interP, (float)CTerrainMapEngine::MIN_ATTRIBUTE_COLLISION_LENGTH);

			ptEnd.x = (int)perP.x;
			ptEnd.y = (int)perP.y;
			if (m_AttrPolygonsQuadTree.Collision(ptEnd))
			{
				return true;
			}

			ex = perP.x;
			ey = perP.y;

			return false;
		}
	}
	else
	{
		/// 충돌 지점을 못 찾았지만 이동할려는 위치가 갈수 없는 지역일 경우가 있다.
		if (m_AttrPolygonsQuadTree.Collision(ptEnd))
		{
			return true;
		}
	}

	return false;
}

bool CTerrainMapEngine::collisionCustomBlock(float sx, float sy, float& ex, float& ey)
{
	X2D::Line<int> ray(sx, sy, ex, ey);
	/// 시작 점
	//X2D::Point<int> sp(sx, sy);
	X2D::Point<int> i_p;
	/// 시작점과 가장 가까운 충돌 점
	//X2D::Point<int> min_ip;
	//bool intersection = false;
	//int min_len = -1;

	std::map<unsigned int, X2D::Point<int>*>::iterator it = m_blockList.begin();
	for (; it != m_blockList.end(); ++it)
	{
		X2D::Point<int>* p = it->second;
		X2D::Line<int> line(p[0].x, p[0].y, p[1].x, p[1].y);

		if (ray.GetIntersectPoint(line, &i_p))
		{
			X2D::Line<int> temp_line(sx, sy,i_p.x, i_p.y );
			if( m_AttrPolygonsQuadTree.Collision( temp_line ) == false )
			{
				//ex = sx;//i_p.x;
				//ey = sy;//i_p.y;

				ex = i_p.x;
				ey = i_p.y;
				return true;
			}
/*


			intersection = true;

			if (-1 == min_len)
			{
				min_ip = i_p;
				min_len = i_p.GetDistance(sp);
			}
			else
			{
				int len = i_p.GetDistance(sp);
				if (len < min_len)
				{
					min_ip = i_p;
					min_len = len;					
				}
			}
*/
		}
	}
/*
	if (intersection)
	{
		/// 최소 거리보다 작으면 그냥 멈춰 있게 한다
		if (2 >= min_len)
		{
			ex = sx;
			ey = sy;
			return true;
		}

		/// normalize
		X2D::Point<int> n;
		n = min_ip - sp;
		int sqr = n.GetDistance(X2D::Point<int>(0, 0));
		n /= sqr;

		/// 충돌 위치를 2만큼 줄여준다
		min_len -= 2;
		n *= min_len;

		ex = sx + n.x;
		ey = sy + n.y;
		return true;
	}
*/
	return false;
}


bool CTerrainMapEngine::collisionCustomBlock(float sx, float sy, float& ex, float& ey, std::vector<K3DVector2> const& blockList)
{
	if (2 > blockList.size())
		return false;

	X2D::Line<int> ray(sx, sy, ex, ey);
	X2D::Point<int> i_p;

	size_t size = blockList.size();
	size_t si = 0;
	for (; si < size-1; ++si)
	{
		size_t ei = si + 1;
		X2D::Line<int> line(blockList[si].x, blockList[si].y, blockList[ei].x, blockList[ei].y);

		if (ray.GetIntersectPoint(line, &i_p))
		{
			X2D::Line<int> temp_line(sx, sy,i_p.x, i_p.y );
			if( m_AttrPolygonsQuadTree.Collision( temp_line ) == false )
			{
				//ex = sx;//i_p.x;
				//ey = sy;//i_p.y;

				ex = i_p.x;
				ey = i_p.y;
				return true;
			}
		}
	}

	return false;
}

bool CTerrainMapEngine::getIntersectInfo(X2D::Point<int> const& ptStart, X2D::Point<int> const& ptEnd, X2D::Point<int>& ptThePoint, int& intersectDistance, X2D::Line<int>* intersectLine)
{

	X2D::Line<int> ray(ptStart.x, ptStart.y, ptEnd.x, ptEnd.y);
	int nSmallestSquareDist = abs((ptEnd.x - ptStart.x) * (ptEnd.x - ptStart.x) + (ptEnd.y - ptStart.y) * (ptEnd.y - ptStart.y));

	X2D::Box<int> boxRegion(ptStart, ptEnd);
	std::vector<X2D::Polygon<int> *> vPolygons;
	m_AttrPolygonsQuadTree.EnumLoose(boxRegion, &vPolygons);

	bool isIntersect = false;
	for( std::vector<X2D::Polygon<int> *>::iterator it = vPolygons.begin(); it != vPolygons.end(); ++it )
	{
		for( size_t my_idx = 0; my_idx < (*it)->Size(); ++my_idx )
		{
			X2D::Point<int> ptTemp;
			X2D::Line<int> currLine = (*it)->GetSegment( my_idx );
			if( ray.GetIntersectPoint( currLine, &ptTemp ) )
			{
				int nSquareDist = abs((ptTemp.x - ptStart.x) * (ptTemp.x - ptStart.x) + (ptTemp.y - ptStart.y) * (ptTemp.y - ptStart.y));
				if(nSmallestSquareDist > nSquareDist)
				{
					nSmallestSquareDist = nSquareDist;
					ptThePoint = ptTemp;
					intersectDistance = nSmallestSquareDist;
					if (intersectLine)
					{	*intersectLine = currLine;
					}
					isIntersect = true;

					// 충돌위치 버퍼 처리
					int depth = 5;
					for (int i=0;i<depth;i++)
					{
						if (ptEnd.x < ptThePoint.x && ptThePoint.x < ptStart.x ) ptThePoint.x++;
						if (ptEnd.x > ptThePoint.x && ptThePoint.x > ptStart.x ) ptThePoint.x--;
						if (ptEnd.y < ptThePoint.y && ptThePoint.y < ptStart.y ) ptThePoint.y++;
						if (ptEnd.y > ptThePoint.y && ptThePoint.y > ptStart.y ) ptThePoint.y--;
					}


					//


				}
			}
		}
	}

	return isIntersect;
}

bool CTerrainMapEngine::getIntersectInfoNearbyEndPoint(X2D::Point<int> const& ptStart, X2D::Point<int> const& ptEnd, X2D::Point<int>& ptThePoint, int& intersectDistance, X2D::Line<int>* intersectLine)
{
	X2D::Line<int> ray(ptStart.x, ptStart.y, ptEnd.x, ptEnd.y);
	int nSmallestSquareDist = abs((ptEnd.x - ptStart.x) * (ptEnd.x - ptStart.x) + (ptEnd.y - ptStart.y) * (ptEnd.y - ptStart.y));

	X2D::Box<int> boxRegion(ptStart, ptEnd);
	std::vector<X2D::Polygon<int> *> vPolygons;
	m_AttrPolygonsQuadTree.EnumLoose(boxRegion, &vPolygons);

	bool isIntersect = false;
	for( std::vector<X2D::Polygon<int> *>::iterator it = vPolygons.begin(); it != vPolygons.end(); ++it )
	{
		for( size_t my_idx = 0; my_idx < (*it)->Size(); ++my_idx )
		{
			X2D::Point<int> ptTemp;
			X2D::Line<int> currLine = (*it)->GetSegment( my_idx );
			if( ray.GetIntersectPoint( currLine, &ptTemp ) )
			{
				int nSquareDist = abs( (ptEnd.x - ptTemp.x) * (ptEnd.x - ptTemp.x) + (ptEnd.y - ptTemp.y) * (ptEnd.y - ptTemp.y));
				if(nSmallestSquareDist > nSquareDist)
				{
					if( m_AttrPolygonsQuadTree.Collision( ptTemp ) == false )
					{
						nSmallestSquareDist = nSquareDist;

						ptThePoint = ptTemp;
						intersectDistance = nSmallestSquareDist;
						if (intersectLine)
						{
							*intersectLine = currLine;
						}

						isIntersect = true;
					}
				}
			}
		}
	}

	return isIntersect;
}

float CTerrainMapEngine::getDegreeBetweenLine(X2D::Point<int> const& sp, X2D::Point<int> const& ep, 
														   X2D::Point<int> const& i_sp, X2D::Point<int> const& i_ep, 
														   X2D::Point<int> const& intersectP)
{
	X2D::Point<int> ri_ep, ri_sp;

	/// ep와 i_ep의 각을 구한다.
	float theta = calcTheta(ep, i_ep, intersectP);
	/// 양수로 만듬
	sMathUtil::makeAbsTheta(theta);

	X2D::Point<int> xr(1, 0);
	if (theta < sMathUtil::degree90)
	{
		ri_ep = i_ep - i_sp;
		theta = calcTheta(ri_ep, xr, X2D::Point<int>(0, 0));
		if (ri_ep.y < 0.0f)	theta = sMathUtil::degree360 - theta;
	}
	else
	{
		ri_sp = i_sp - i_ep;
		theta = calcTheta(ri_sp, xr, X2D::Point<int>(0, 0));
		if (ri_sp.y < 0.0f)	theta = sMathUtil::degree360 - theta;
	}

	return theta;
}

float CTerrainMapEngine::calcTheta(X2D::Point<int> const& _p1, X2D::Point<int> const& _p2, X2D::Point<int> const& origin)
{
	X2D::Point<int> __p1 = _p1 - origin;
	X2D::Point<int> __p2 = _p2 - origin;

	K3DVector p1(__p1.x, __p1.y, 0.0f);
	K3DVector p2(__p2.x, __p2.y, 0.0f);

	p1.Normalize();
	p2.Normalize();
	float dot = p1.x * p2.x + p1.y * p2.y;
	float theta = acosf(dot);

	return theta;
}