勤能补拙,Expter

成都游戏Coder,记录游戏开发过程的笔记和心得!

#

一个小型的IOCP网络库

        基本网络框架基于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系统写完会把代码和网络库的最新代码更新都会上传,希望大家多多指教。




posted @ 2009-12-20 14:21 expter 阅读(3721) | 评论 (5)编辑 收藏

一个字典生成算法几种解法:

        最近做一个东西正好需要生成字典的算法,类似一些密码字典生成器(主要运用在暴力破解)。生成的密码会根据密码长度与字典集合的长度成指数关系。
       可以用一个函数来表示
        f( x , y  )  = x ^y ;           x表示我们要生产的密码长度,y表示我们要生成的密码字典字符集合。

      当时想到就有3个算法。
      
    1.循环
         关于循环,可以参考水仙花数的多层嵌套求解,主要算法如下:

 1/// Dict 为生成的密码 , g_Dict为字典集合
 2for ( 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

posted @ 2009-11-08 00:56 expter 阅读(3294) | 评论 (1)编辑 收藏

一个问题,如何优化? 是否有高效的算法

        问题描述如下:
                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}

 

           是否有一种高效的算法,只是进行一,两步位与或运算即可。。

        

posted @ 2009-10-18 22:27 expter 阅读(1934) | 评论 (13)编辑 收藏

3D游戏寻路算法(A*)

        关于游戏寻路,网络上也有很多相关的文章,一般都是已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

posted @ 2009-10-10 22:50 expter 阅读(7541) | 评论 (1)编辑 收藏

游戏中常见的几种追踪算法

    所谓追踪,相对于另外一个角色来说是逃跑,首先需要做出追和逃跑的决策判断。

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来记录学习的聚类算法:

posted @ 2009-10-09 23:57 expter 阅读(4661) | 评论 (2)编辑 收藏

定制自己的new 和 delete,让对象在静态块上进行分配。

     摘要: 定制自己的new 和 delete,让对象在静态块上进行分配。
一般常见的new和delete操作符,就意味着使用堆进行内存分配,使用new操作符是名为operator new的函数调用,且函数返回返回一个指向某块内存分配器分配内存指针。
对于内存的分配到底从哪儿来没有任何限制,它可能来自一个特殊的堆,也可能来自一个静态分配的块,也可能来自一个标准容器内部,也可能来自某个函数范围的局部存储区。而对于现在的各自软件中主流内存管理方式,一般通过内存池的管理方式,它可能即包含静态分配也同时包含动态分配。  阅读全文

posted @ 2009-08-16 19:47 expter 阅读(2478) | 评论 (10)编辑 收藏

一个关于vector在读取和压入技巧性的效率优化

         在多线程过程中,对于线程间的数据共享同步问题,具体针对多线程需要对一个Vector进行读与写的操作,不考虑缓冲区的操作,一般情况下为了保证稳定性的同时在读写的时候都要进行加锁,其实可以通过一个技巧,就是通过一个临时变量在写数据的时候把第一个值付给临时变量,那么在读取数据的线程中会直接读取临时变量,此时只需要加锁一次即可。



         我写了一个测试例子,就是关于开3个读,写,删的操作。。。一般情况进行加锁,与通过通过临时变量来减少一次加锁速度与效率明显低于后者。
         针对1000000个数据的操作,操作1比操作2快2倍以上。


         下面是我的测试代码,简单。。。只是为了说明问题
         
/Files/expter/l_thread.rar
        

posted @ 2009-08-14 23:52 expter 阅读(2199) | 评论 (5)编辑 收藏

一个简单线程池的实现

     摘要: 一个简单线程池的实现  阅读全文

posted @ 2009-08-09 18:10 expter 阅读(4118) | 评论 (8)编辑 收藏

编译DShow程序出现记录

     摘要: 编译DShow程序出现 无法打开包括文件:“dsound.h”  阅读全文

posted @ 2009-07-29 23:34 expter 阅读(1091) | 评论 (0)编辑 收藏

关于IE插件,关于BHO的弹出窗口

     摘要: 关于IE插件,关于BHO的弹出窗口  阅读全文

posted @ 2009-07-26 20:06 expter 阅读(1378) | 评论 (0)编辑 收藏

仅列出标题
共7页: 1 2 3 4 5 6 7