MGridMap.h
00001 #ifndef MGRIDHASH_H 00002 #define MGRIDHASH_H 00003 00004 #include <crtdbg.h> 00005 #include <list> 00006 #include <math.h> 00007 using namespace std; 00008 00009 00017 template<class _T> 00018 class MGridMap{ 00019 public: 00021 struct MITEM{ 00022 float x, y, z; 00023 _T Obj; 00024 }; 00026 class MRefCell : public list<MITEM>{}; 00027 00029 struct HREF{ 00030 MRefCell* pRefCell; 00031 MRefCell::iterator RefIterator; 00032 }; 00033 00034 protected: 00035 MRefCell* m_pGridMap; 00036 float m_fSX; 00037 float m_fSY; 00038 float m_fEX; 00039 float m_fEY; 00040 //float GetXSize(); ///< 맵의 X축 크기 00041 //float GetYSize(); ///< 맵의 Y축 크기 00042 int m_nXDivision; 00043 int m_nYDivision; 00044 00045 protected: 00046 MRefCell* GetCell(float x, float y){ 00047 int nXPos = int((x-m_fSX)/(GetXSize()/(float)m_nXDivision)); 00048 int nYPos = int((y-m_fSY)/(GetYSize()/(float)m_nYDivision)); 00049 00050 // 영영 검사 00051 _ASSERT(nXPos>=0 && nYPos>=0); 00052 if(nXPos>=m_nXDivision) return NULL; 00053 if(nYPos>=m_nYDivision) return NULL; 00054 00055 return &(m_pGridMap[nXPos+nYPos*m_nXDivision]); 00056 } 00057 public: 00058 MGridMap(void){ 00059 m_pGridMap = NULL; 00060 } 00061 virtual ~MGridMap(void){ 00062 Destroy(); 00063 } 00064 00072 //void Create(float fSX, float fSY, float fXSize, float fYSize, int nXDivision, int nYDivision){ 00073 void Create(float fSX, float fSY, float fEX, float fEY, int nXDivision, int nYDivision){ 00074 m_pGridMap = new MRefCell[nXDivision*nYDivision]; 00075 m_fSX = fSX; 00076 m_fSY = fSY; 00077 m_fEX = fEX; 00078 m_fEY = fEY; 00079 //GetXSize() = fXSize; 00080 //GetYSize() = fYSize; 00081 m_nXDivision = nXDivision; 00082 m_nYDivision = nYDivision; 00083 } 00085 void Destroy(void){ 00086 if(m_pGridMap!=NULL){ 00087 delete[] m_pGridMap; 00088 m_pGridMap = NULL; 00089 } 00090 } 00091 00094 HREF Add(float x, float y, float z, _T Obj){ 00095 _ASSERT(x>=m_fSX && y>=m_fSY); 00096 _ASSERT(x<=m_fEX && y<=m_fEY); 00097 HREF hPos; 00098 MRefCell* pCell = GetCell(x, y); 00099 if(pCell==NULL){ 00100 hPos.pRefCell = NULL; 00101 return hPos; 00102 } 00103 MITEM item; 00104 item.x = x; 00105 item.y = y; 00106 item.z = z; 00107 item.Obj = Obj; 00108 hPos.RefIterator = pCell->insert(pCell->end(), item); 00109 hPos.pRefCell = pCell; 00110 return hPos; 00111 } 00113 void Del(HREF hRef){ 00114 _ASSERT(hRef.pRefCell!=NULL); 00115 hRef.pRefCell->erase(hRef.RefIterator); 00116 } 00118 void Get(list<_T>* pObjs, float x, float y, float z, float fRadius){ 00119 float fXCellSize = GetXSize()/(float)m_nXDivision; 00120 float fYCellSize = GetYSize()/(float)m_nYDivision; 00121 int nXPos = int((x-m_fSX)/fXCellSize); 00122 int nYPos = int((y-m_fSY)/fYCellSize); 00123 #define MORE_SEARCH 2 00124 int nXRadius = int(fRadius/fXCellSize) + MORE_SEARCH; 00125 int nYRadius = int(fRadius/fYCellSize) + MORE_SEARCH; 00126 float fRadiusPow = fRadius*fRadius; 00127 for(int yp=-nYRadius; yp<=nYRadius; yp++){ 00128 for(int xp=-nXRadius; xp<=nXRadius; xp++){ 00129 float fCellX = (nXPos+xp+(xp>=0?1:0))*fXCellSize + m_fSX; 00130 float fCellY = (nYPos+yp+(yp>=0?1:0))*fYCellSize + m_fSY; 00131 float f2DLenPow = float(pow(fCellX-x, 2) + pow(fCellY-y, 2)); 00132 if(f2DLenPow>fRadiusPow) continue; // 셀 자체의 길이 범위가 벗어났을 경우 00133 int nX = nXPos+xp; 00134 int nY = nYPos+yp; 00135 if(nX<0 || nX>=m_nXDivision) continue; 00136 if(nY<0 || nY>=m_nYDivision) continue; 00137 MRefCell* pRefCell = &(m_pGridMap[nX+nY*m_nXDivision]); 00138 for(MRefCell::iterator it=pRefCell->begin(); it!=pRefCell->end(); it++){ 00139 MITEM* pItem = &(*it); 00140 float f3DLenPow = float(pow(pItem->x-x, 2)+pow(pItem->y-y, 2)+pow(pItem->z-z, 2)); 00141 if(f3DLenPow<=fRadiusPow){ 00142 pObjs->insert(pObjs->end(), pItem->Obj); 00143 } 00144 } 00145 } 00146 } 00147 } 00148 00150 HREF Move(float x, float y, float z, _T Obj, HREF& hRef){ 00151 _ASSERT(hRef.pRefCell!=NULL); 00152 _ASSERT((&(*hRef.RefIterator))->Obj==Obj); 00153 00154 MRefCell* pRefCell = GetCell(x, y); 00155 // 같은 RefCell을 가지면 아무것도 하지 않는다. 00156 if(pRefCell==hRef.pRefCell) return hRef; 00157 // 이전 참조 지우기 00158 hRef.pRefCell->erase(hRef.RefIterator); 00159 // 새로운 참조 만들기 00160 return Add(x, y, z, Obj); 00161 } 00162 00164 float GetSX(void) const { return m_fSX; } 00166 float GetSY(void) const { return m_fSY; } 00168 float GetEX(void) const { return m_fEX; } 00170 float GetEY(void) const { return m_fEY; } 00171 00173 float GetXSize(void) const { return m_fEX-m_fSX; } 00175 float GetYSize(void) const { return m_fEY-m_fSY; } 00177 int GetXDivision(void) const { return m_nXDivision; } 00179 int GetYDivision(void) const { return m_nYDivision; } 00180 00182 float GetXDivisionSize(void) const { return GetXSize() / (float)m_nXDivision; } 00184 float GetYDivisionSize(void) const { return GetYSize() / (float)m_nYDivision; } 00185 00187 MRefCell* GetCell(int x, int y){ 00188 if(x<0 || x>=m_nXDivision) return NULL; 00189 if(y<0 || y>=m_nYDivision) return NULL; 00190 00191 return &(m_pGridMap[x+y*m_nXDivision]); 00192 } 00194 MRefCell* GetCell(int i){ 00195 if(i<0 || i>=m_nXDivision*m_nYDivision) return NULL; 00196 return &(m_pGridMap[i]); 00197 } 00199 int GetCellCount(void){ 00200 return m_nXDivision*m_nYDivision; 00201 } 00203 void ClearAllCell(void){ 00204 int nCellCount = GetCellCount(); 00205 for(int i=0; i<nCellCount; i++){ 00206 MRefCell* pRefCell = GetCell(i); 00207 for(MMap::MRefCell::iterator it=pRefCell->begin(); it!=pRefCell->end(); it++){ 00208 MMap::MITEM* pItem = &(*it); 00209 } 00210 pRefCell->clear(); 00211 } 00212 } 00213 }; 00214 00215 #endif
MAIET entertainment