field.h

QuadTree.rar

#pragma once

#include <windows.h>

/* 
    <一些公式及算法>:

    公式(1):    r = (num ^ (~param + 1)) + param;
    ~~~~~~~
    条件: 给定一个任意正数 num 和一个参数 param (param 只能是 1 或 0), 
    要求: 若 param = 1 则 返回 -num, 否则返回 num (既:不变)
    备注: STile::GetChild(), STile::GetNeighbor()

    公式(2):    r = (num ^ (~(num - 1))) >> 31
    ~~~~~~~
    条件: 给定一个任意数 num
    要求: 若 num != 0 则返回 1 ,否则返回 0
    备注: STile::GetParent()

    公式(3):    r = a & (b - 1)
    ~~~~~~~
    条件: 给定二个数 a(任意正数), b(必须是2的n次方)
    要求: 求 a / b 的余数
    备注: STile::GetParent()	感谢"吴承昊"提供该公式

    求子节点所在片区:
    ~~~~~~~~~~~~~~~~
    虽然每个"块"的父节点都有四种可能,但是只有一个能符合条件,那就是它的
    中心点坐标"x" 和 "z"的值都不能整除它的尺寸(size)
    备注: STile::GetParent()
*/

// ----------------------------------------------------------------
// 用来记录"块"的偏移参数.
struct STileParam
{
    int value1;
    int value2;
};

// 子节点(片区)的偏移参数
// "value1"表示"x"的加减,"value2"表示"z"的加减(0代表"加", 1代表"减")
// 注意: 为了STile::GetSection中能快速计算,子节点(片区)顺序是不能修改的.(如:图1)
extern STileParam child_param[4]    /*= {{0, 0}, {1, 0}, {0, 1}, {1, 1}}*/;

// 临节点的偏移参数
// 注意: 相对于当前节点,临节点的坐标可能是"加、减、相等"这三种情况,而每次变动的
//       要么是"x"要么是"z",所以"value1"用来表明"加减",而"value2"用来标记是谁在
//       改动,(x:0) (z:1) (参考 图2)
extern STileParam neighbor_param[4] /*= {{1, 0}, {1, 1}, {0, 0}, {0, 1}}*/;

/*
                                    ---
     -------                       | 1 |
    | 3 | 2 |                   -----------
     -------                   | 0 |   | 2 |
    | 1 | 0 |                   -----------
     -------                       | 3 |
                                    ---

    <图1> 子节点(片区)         <图2> 临节点
*/


// ----------------------------------------------------------------
// "块"数据
struct STile
{
public:
    STile(void){}
    STile(int cx, int cz, int size){
        SetData(cx, cz, size);
    }

    // 填充数据
    void SetData(int cx, int cz, int size){
        m_cx    = cx;
        m_cz    = cz;
        m_size  = size;
    }

public:
    // 得到子节点
    void GetChild(int nIndex, STile* pTile){
        pTile->m_size = m_size >> 1;
        pTile->m_cx = m_cx + (((m_size >> 2) ^ (~child_param[nIndex].value1 + 1)) + child_param[nIndex].value1);
        pTile->m_cz = m_cz + (((m_size >> 2) ^ (~child_param[nIndex].value2 + 1)) + child_param[nIndex].value2);
    }

    // 得到父节点
    void GetParent(STile* pTile){        
        int nPlus[2] = {m_size, 0};
        unsigned int nMod;

        pTile->m_size = m_size << 1;

        pTile->m_cx = m_cx - (m_size >> 1);
        nMod = pTile->m_cx & (pTile->m_size - 1);
        pTile->m_cx += nPlus[(nMod ^ (~(nMod - 1))) >> 31];

        pTile->m_cz = m_cz - (m_size >> 1);
        nMod = pTile->m_cz & (pTile->m_size - 1);
        pTile->m_cz += nPlus[(nMod ^ (~(nMod - 1))) >> 31];
    }

    // 得到临节点
    void GetNeighbor(int nIndex, STile* pTile){
        int* sxy[2] = {&m_cx, &m_cz};
        int* dxy[2] = {&pTile->m_cx, &pTile->m_cz};

        int value1 = neighbor_param[nIndex].value1;
        int value2 = neighbor_param[nIndex].value2;

        *dxy[value2] = *sxy[value2] + (m_size ^ (~value1 + 1)) + value1;
        *dxy[value2 ^ 1] = *sxy[value2 ^ 1];
        pTile->m_size = m_size;
    }

    // 得到子节点所在片区
    int GetSection(const STile* pChild){
        int x = unsigned (pChild->m_cx - m_cx) >> 31;
        int y = unsigned (pChild->m_cz - m_cz) >> 31;
        return x | (y << 1);
    }

public:
	int m_cx;   // 中心点x
	int m_cz;   // 中心点z
	int m_size; // 尺寸
};

// ----------------------------------------------------------------
// 场地
class CField
{
public:
	CField(void);
public:
	~CField(void);

public:
    //   创建、销毁
	bool Create(int nFieldSize);
	void Destroy(void);

    //   更新(重新计算)所有"块"
	//	 nMinError:	最低允许误差
	void UpdateQuarters(int nMinError);

    //   随机生成高度数据
	//	 fRoughness:	粗糙度(0.0f - 1.0f)
	//	 fSlab:			层次趋向(0.0f - 1.0f)
	//	 nBlur:			模糊次数
    void RandomHeight(float fRoughness = 0.5f, float fSlab = 0.5f, int nBlur = 2);

    //   绘制块到hdc设备
    void Paint(HDC hdc);

public:
    int  GetBorderSize(void){
        return m_nBorderSize;
    }

    const unsigned char* GetHeights(void)const{
        return m_byHeights;
    }

    const unsigned char* GetQuarters(void)const{
        return m_byQuarters;
    }

    float GetMinHeight(void){
        return m_byMinHeight;
    }

    float GetMaxHeight(void){
        return m_byMaxHeight;
    }

    unsigned char GetHeight(int x, int z){
        return m_byHeights[z * m_nBorderSize + x];
    }
    void SetHeight(int x, int z, unsigned char value){
        m_byHeights[z * m_nBorderSize + x] = value;
    }

private:
    //    得到"块"的粗糙程度
    int	  GetTileError(const STile* pTile);

    //    验证"块"是否有效
    bool  IsTileValid(const STile* pTile);

    //    计算最大影响"块"数(递归过程)
    int   CalculateMaxTouchNum(int nFieldSize);

private:
	void  MakeHeightsPlasma(float* fHeights, float* fMinHeight, float* fMaxHeight, float fRoughness);
	void  SlabHeights(float* fHeights, float* fMinHeight, float* fMaxHeight, float fDegree);
	void  BlurHeights(float* fHeights, float* fMinHeight, float* fMaxHeight, int nTimes);
	void  NormalizeHeights(float* fHeights, float fMinHeight, float fMaxHeight);

private:
	unsigned char*	m_byQuarters;	// "四分标记"数据
	STile*			m_Tiles;		// "块"数组(分配最大可能的空间, 方便快速遍历)
    STile*          m_TouchTiles;   // 由于某"块"划分子节点而影响的其他的"块"数组

	int m_nFieldSize;	// 地形尺寸
	int m_nBorderSize;	// 地形边数

private:
	bool m_bValid;		// 该对象是否有效
	int	 m_nMaxTilesNum;// 最大"块"数
    int  m_nMaxTouchNum;// 最大受影响"块"数
    int  m_nHeightsNum; // "高度数据"元素个数

private:
    unsigned char*	m_byHeights;	// 高度数据
    unsigned char	m_byMinHeight;	// 最小高度值
    unsigned char	m_byMaxHeight;	// 最大高度值
};