Cyd
2b8ca921cb
Complete disaster-recovery snapshot: engine/game source, game data assets, VC6 toolchain + DX SDKs, build outputs, deployed game, and _UNUSED archive. Large binaries in Git LFS; text preserved byte-for-byte (core.autocrlf=false, no eol attributes). See RECOVERY.md for the one-clone rebuild procedure.
158 lines
3.3 KiB
C++
158 lines
3.3 KiB
C++
#pragma once
|
|
#ifndef __QUADTREEHPP__
|
|
#define __QUADTREEHPP__
|
|
|
|
template<typename _T>
|
|
class QuadTreeNode
|
|
{
|
|
protected:
|
|
QuadTreeNode<_T> *m_TL,*m_TR,*m_BL,*m_BR;
|
|
_T m_Data;
|
|
int m_Left,m_Top,m_Right,m_Bottom;
|
|
QuadTreeNode<_T> *m_Parent;
|
|
|
|
public:
|
|
QuadTreeNode (QuadTreeNode *parent)
|
|
{
|
|
m_Parent = parent;
|
|
m_TL = m_TR = m_BL = m_BR = NULL;
|
|
m_Left = m_Top = m_Right = m_Bottom = 0;
|
|
}
|
|
~QuadTreeNode (void)
|
|
{
|
|
delete m_TL;
|
|
delete m_TR;
|
|
delete m_BL;
|
|
delete m_BR;
|
|
m_TL = m_TR = m_BL = m_BR = NULL;
|
|
m_Parent = NULL;
|
|
}
|
|
void Subdivide (int splithorz=0,int splitvert = 0)
|
|
{
|
|
delete m_TL;
|
|
delete m_TR;
|
|
delete m_BL;
|
|
delete m_BR;
|
|
m_TL = m_TR = m_BL = m_BR = NULL;
|
|
if (splithorz == 0)
|
|
splithorz = ((m_Bottom - m_Top) / 2) + m_Top;
|
|
if (splitvert == 0)
|
|
splitvert = ((m_Right - m_Left) / 2) + m_Left;
|
|
if (splitvert<= m_Left)
|
|
return;
|
|
if (splitvert >= m_Right)
|
|
return;
|
|
if (splithorz <= m_Top)
|
|
return;
|
|
if (splithorz >= m_Bottom)
|
|
return;
|
|
m_TL = new QuadTreeNode<_T> (this);
|
|
m_TR = new QuadTreeNode<_T> (this);
|
|
m_BL = new QuadTreeNode<_T> (this);
|
|
m_BR = new QuadTreeNode<_T> (this);
|
|
m_TL->SetSize (m_Left,m_Top,splitvert,splithorz);
|
|
m_TR->SetSize (splitvert+1,m_Top,m_Right,splithorz);
|
|
m_BL->SetSize (m_Left,splithorz+1,splitvert,m_Bottom);
|
|
m_BR->SetSize (splitvert+1,splithorz+1,m_Right,m_Bottom);
|
|
}
|
|
|
|
QuadTreeNode *TL (void)
|
|
{ return m_TL; }
|
|
QuadTreeNode *TR (void)
|
|
{ return m_TR; }
|
|
QuadTreeNode *BL (void)
|
|
{ return m_BL; }
|
|
QuadTreeNode *BR (void)
|
|
{ return m_BR; }
|
|
const _T& Data (void) const
|
|
{ return m_Data; }
|
|
_T& Data (void)
|
|
{ return m_Data; }
|
|
int Left (void) const
|
|
{ return m_Left; }
|
|
int Right (void) const
|
|
{ return m_Right; }
|
|
int Top (void) const
|
|
{ return m_Top; }
|
|
int Bottom (void) const
|
|
{ return m_Bottom; }
|
|
int Width (void) const
|
|
{ return m_Right - m_Left; }
|
|
int Height (void) const
|
|
{ return m_Bottom - m_Top; }
|
|
|
|
void SetSize (int left,int top,int right,int bottom)
|
|
{
|
|
if (left > right)
|
|
{
|
|
m_Left = right;
|
|
m_Right = left;
|
|
}
|
|
else
|
|
{
|
|
m_Left = left;
|
|
m_Right = right;
|
|
}
|
|
if (top > bottom)
|
|
{
|
|
m_Top = bottom;
|
|
m_Bottom = top;
|
|
}
|
|
else
|
|
{
|
|
m_Top = top;
|
|
m_Bottom = bottom;
|
|
}
|
|
}
|
|
};
|
|
|
|
template<typename _T>
|
|
class QuadTree
|
|
{
|
|
public:
|
|
|
|
protected:
|
|
QuadTreeNode<_T> *m_Root;
|
|
|
|
bool TraverseHelper (QuadTreeNode<_T> *node,int level,DWORD param) // true to continue traverse
|
|
{
|
|
if (!node)
|
|
return true;
|
|
if (!TraverseFunction (node,level,param))
|
|
return false;
|
|
if (!TraverseHelper (node->TL (),level+1,param))
|
|
return false;
|
|
if (!TraverseHelper (node->TR (),level+1,param))
|
|
return false;
|
|
if (!TraverseHelper (node->BL (),level+1,param))
|
|
return false;
|
|
if (!TraverseHelper (node->BR (),level+1,param))
|
|
return false;
|
|
return true;
|
|
}
|
|
|
|
public:
|
|
QuadTree (void)
|
|
{ m_Root = NULL; }
|
|
~QuadTree (void)
|
|
{
|
|
delete m_Root;
|
|
m_Root = NULL;
|
|
}
|
|
void Create (int left,int top,int right,int bottom)
|
|
{
|
|
m_Root = new QuadTreeNode<_T> (NULL);
|
|
m_Root->SetSize (left,top,right,bottom);
|
|
}
|
|
QuadTreeNode *Root (void)
|
|
{ return m_Root; }
|
|
bool TraverseFunction (QuadTreeNode<_T> *node,int level,DWORD param)
|
|
{
|
|
return true;
|
|
}
|
|
void Traverse (DWORD param)
|
|
{ TraverseHelper (m_Root,1,param); }
|
|
};
|
|
|
|
|
|
#endif |