#
基本网络框架基于IOCP模型，这次主要在以前写的IPC通信的基础上修改，参考了当前项目网络库的设计思路。
先介绍几个主要的类:
1.CSocket重新套接字，CConnection继承CSocket表示一个连接对象主要重写Recv和Send接口，以及组包过程。
2.CAccept处理客户端的链接，
3.Cpacket一个消息数据包头，CMessage继承CPacket带数据消息包。
4.CConnectManger保存一个连接CConnection的内存池对象，CAcceptManager一个接收客户端Accept的线程，CPacketManager参考了Loki的小对象管理做的一个缓冲区数据包内存池。
5.CLibObject包含上面3个Manager(Singleton)，CNetWork网络初始化。
6.CIOCP类主要IO的线程类，接收处理所有的客户端连接CConnection。
7.CServer类包括一个IOCP初始化和网络库管理类，IOCP会把接收到的数据重组成数据包后保存到CServer的一个CMsgQueue中.
8.我们的重写一个Server只需要继承CServer，然后实现run和AccedeProcess即可。run从CMsgQueue缓冲区提取一个消息包，AccedeProcess处理消息。
一些细节设计:
1.为了节约带宽Connection这里采用了Negles算法，这里采用Negle的并没有马上把每一个需要发送MSG采用缓存队列的方式保存起来，而是每一个Connection自身都保存数据，CServer通过一个线程把每一个存在的Connection是否有消息缓存，然后发送。因而让IOCP只处理接收的消息，发送消息通过CServer来处理。
出网络库基本框架如下:
网络库代码的代码http://code.google.com/p/tpgame/source/browse/#svn/trunk/GServerEngine/NetLibrary
问题肯定较多，希望多多指教。
最近一直在构思与写一套游戏AI系统，主要是通过状态机响应事件，更多是想运用自己学习到的一些优秀的算法，以及一些高级
的AI以此来锻炼对一些复杂的数据结构的编写和设计思维的提升。
算法和数据结构方面:
1.2D和3D寻路(主要包括2D寻路的初始化条件优化 ，3D的空间划分以及多叉树的划分，以及堆维护)。
2.带有更多思维的角色系统(附带更多的数据信息)判断。
3.查询线段树和树状数数组的运用。
4.一个线性的字符串过滤程序。
5.一个动态基于角色的最优二叉查找树的动态维护。(主要解决不同的角色AI触发频率建立一颗最优二叉查找树)
6.追踪算法以及游戏的群集算法都会整合到现在的AI系统中。
设计方面：
1.尽量让类之间耦合性更小，复杂度更低，浅显明确。
注：Ai系统写完会把代码和网络库的最新代码更新都会上传，希望大家多多指教。
最近做一个东西正好需要生成字典的算法，类似一些密码字典生成器(主要运用在暴力破解)。生成的密码会根据密码长度与字典集合的长度成指数关系。
可以用一个函数来表示
f( x , y ) = x ^y ; x表示我们要生产的密码长度，y表示我们要生成的密码字典字符集合。
当时想到就有3个算法。
1.循环
关于循环，可以参考水仙花数的多层嵌套求解，主要算法如下:
1
/**//// Dict 为生成的密码 ， g_Dict为字典集合 2
for ( int i = 0 ; i < Len ; i++ )
3
{
4
Dict[0] = g_Dict[i];
5
6 for ( int j = 0 ; j < Len ; j++)
7
{
8 Dict[1] = g_Dict[j];
9
10 for ( int k = 0 ; k < Len ; k++ )
11 {
12 Dict[2] = g_Dict[k];
13
14 /**//*
15 * 几位密码就嵌套几层循环
16
*/
17
18 }
19 }
20
}
这种方式移植不好，而且代码臃肿。
2.递归
做过字符串的全排列的都明白这个算法，这种也是基于这种方式：但是由于随着字典集合或者密码长度的增加，很容易会出现堆栈的内存溢出。
1void solve(int len,int p , int s,int n)
2{
3 int i;
4 if( s == n )
5 {
6 /**////std::cout << Dict << std::endl;
7 return ;
8 }
9 if(s>n||p>n)
10 return;
11 for( i=p ; i < len ; i++ )
12 {
13 solve(len,i+1,s+1,n);
14 }
15}
3.BFS
有了前2种方法的不错，然后写了一个非递归的算法
主要借用横向扫描的方式，借鉴一个数组来进行记录当前应该生成的密码。
主要算法如下:
1/**//*
2* 生成字典的函数
3* @parm 需要生成的长度
4*/
5void MakeDict( int Len )
6{
7 char Dict[MaxDictLen+1]; // 生成的字典字符串
8 int Array[MaxDictLen]; // 记录当前应该生成字典数组
9
10 memset( Array , 0 , sizeof(Array) );
11
12 bool bStop = true;
13
14 int i,j;
15 for ( ; bStop ; ) // 是否生成完毕
16 {
17 for ( i = 0 ; i < Len ; i++ )
18 {
19 Dict[i] = g_Dict[Array[i]];
20 }
21 Dict[Len] = '\0';
22
23 std::cout << Dict << std::endl;
24
25 /**//// 字典数组坐标更新
26 for ( j = Len - 1 ; j >= 0 ; j -- )
27 {
28 Array[j] ++ ;
29
30 if ( Array[j] != ((int)g_Dict.length()) )
31 {
32 break;
33 }
34 else
35 {
36 Array [j] = 0;
37 if( j == 0 ) // 生成完毕
38 bStop = false;
39 }
40 }
41 }
42}
附上第三个生成算法源码:
link
问题描述如下:
2个整数(int32)，我需要对这2个数的第n位进行二进制数交换值。是否有一个高效的算法，或者高效的运算。
例子如下:
2个整数10，7，把第1位的数值交换。
整数 二进制 交换后二进制 交换后的值
10 0x1010 0x1011 11
7 0x0111 0x0110 6
我的思路如下:
1.如果要对第n位数值交换，先求出第n位的值(1或者0),如果相等则不交换。
2.交换第n位，通过通过原理发现只需通过加减法运算即可，如果1->0 则减 1<<(n-1) ，否则加1<<(n-1)。
代码如下：
1void prjfun( int & des , int & src , int n)
2{
3 if( n <= 0 ) return ;
4
5 int x = (des & (1<<(n-1))) >>(n-1); // 求出第n位的数值
6 int y = (src & (1<<(n-1))) >>(n-1); // 求出第n位的数值
7 if ( x != y )
8 {
9 des += (y-x)*(1<<(n-1)); // 交换
10 stc += (x-y)*(1<<(n-1)); // 交换
11 }
12}
是否有一种高效的算法，只是进行一，两步位与或运算即可。。
关于游戏寻路，网络上也有很多相关的文章，一般都是已A*为主，他只是一种启发式搜索，最开始写A*是在大三，主要还是做一个路径搜索的算法。
关于游戏中A*的算法优化，由于在搜索的过程中会通过open表和close保存一些结点，为了加快查找效率一般采用对维护的方式，利用map的最小堆(按照估价值的大小排序)来构架数据结构。其实还可以利用线性的hash_map来创建维护。
而3D中游戏寻路也是采用同样的方法，只是在不同于2D的8个方向搜索而是3*8个方向的搜索。所以他的复杂度之高，在对于一个3维的N*N*N的空间，他的搜索运算为n^3*24，就需要考虑算法中的优化。
总之一句3D寻路费时又费空间！
下面是我总结的优化
1.总体还是利用a*和堆维护。
2.由于点是实心，可以直接进行对角线的行走，也就是对角线行走一步后x,y,z的坐标都会改变，从而降低通过2次二维变换的过程。二步变一步！
3.利用凸包的方式来优化。
4.把一个场景的3D地图全部细分，利用多叉树进行管理。
关于凸包的优化可以通过这样一个例子说明(因为在2D中更好的描述通过2维的地图)：
A、假设1要到2的，通过A*的搜索，他会先到0然后发现不能通过在回溯，重新寻找新的路径，这样可能浪费一些搜索时间。
B. 可以通过多边形的最小矩形凸包的方式，这样就可以减少不必要的搜索，如图所示。
那么1到2就不会经过0点。。因为次区域设置为不可通过。
C. 如果我们要查找的点在我们凸包内，所以我们在寻路最开始应该验证点是否在凸包内，如果在此区域内，在行走时不能过滤这个矩形空间。
注：游戏中地图一般是不变的，所以这些都是不变，凸包已知，验证点在凸包中也是线性的。
由于在计算3D的凸包的时候计算量大，最开始采用静态的方式来记录数据。
简单的3D寻路算法源码(不包含凸包优化)：
/Files/expter/3DAStar.rar
所谓追踪，相对于另外一个角色来说是逃跑，首先需要做出追和逃跑的决策判断。
1.坐标追踪
也是最基本追逐方式，他根据要追踪对象的坐标来修改追踪者的坐标，使两者的距离逐渐缩短。
一个简单的例子:
Point m_pPrey; /// 被追踪者
Point m_pAtta; /// 追踪者
对于追踪者来说： 新位置 = 旧位置 + XY速度 ;
1if( m_pAtta.x < m_pPrey.x )
2 m_pAtta.x ++;
3else if( m_pAtta.x > m_pPrey.x )
4 m_pAtta.x --;
5
6
7if( m_pAtta.y < m_pPrey.y )
8 m_pAtta.y ++;
9else if( m_pAtta.y > m_pPrey.y )
10 m_pAtta.y --;
2.视线追踪
视线追踪方式，主要是描述每一时刻都追踪者会沿着被追逐者之间的直线方向运动。如图所示：
通过图可以更好描述此问题，此问题的求解关键在于求出连接追踪者与猎物之间的直线，可以通过向量知道：2个向量想减即可得到。
可以分别用追踪者与猎物的位置坐标构造出两个向量,假设b 代表追踪者位置向量,a 代表猎物位置向量。做向量减法a-b 便得到了向量c，将c 的起点置于追踪者的位置上,就得到了一条指向猎物的向量c. 此时，令：
追踪者X 方向速度 / 追踪者Y 方向速度 ＝ c 向量x 轴分量/ c 向量y 轴分量 .即可求解。
3.拦截追踪
所谓拦截追踪，如果考虑的是被追逐的目标太远，如果2者速度一样，或者相差不大，有可能很难追上，玩过实况足球的都知道，如果采用上面的2中追逐方式，可能错过最佳的防守位置。下面是拦截追踪的一个示例图:
对于追踪者来说，他只需要知道被追踪者的位置，方向与速度，讲会计算一个最佳的拦截位置。然后你会发现这只是一个简单的追踪问题。且需要的时间t最少。
整个3种追踪的源码代码 以及 demo都共享：
/Files/expter/chase.rar
下一篇通过实例demo来记录学习的聚类算法：
摘要: 定制自己的new 和 delete，让对象在静态块上进行分配。
一般常见的new和delete操作符，就意味着使用堆进行内存分配，使用new操作符是名为operator new的函数调用，且函数返回返回一个指向某块内存分配器分配内存指针。
对于内存的分配到底从哪儿来没有任何限制，它可能来自一个特殊的堆，也可能来自一个静态分配的块，也可能来自一个标准容器内部，也可能来自某个函数范围的局部存储区。而对于现在的各自软件中主流内存管理方式，一般通过内存池的管理方式，它可能即包含静态分配也同时包含动态分配。
阅读全文
在多线程过程中，对于线程间的数据共享同步问题，具体针对多线程需要对一个Vector进行读与写的操作，不考虑缓冲区的操作，一般情况下为了保证稳定性的同时在读写的时候都要进行加锁，其实可以通过一个技巧，就是通过一个临时变量在写数据的时候把第一个值付给临时变量，那么在读取数据的线程中会直接读取临时变量，此时只需要加锁一次即可。
我写了一个测试例子，就是关于开3个读，写，删的操作。。。一般情况进行加锁，与通过通过临时变量来减少一次加锁速度与效率明显低于后者。
针对1000000个数据的操作，操作1比操作2快2倍以上。
下面是我的测试代码，简单。。。只是为了说明问题
/Files/expter/l_thread.rar
摘要: 编译DShow程序出现 无法打开包括文件:“dsound.h”
阅读全文
摘要: 关于IE插件，关于BHO的弹出窗口
阅读全文