#
基本網(wǎng)絡(luò)框架基于IOCP模型，這次主要在以前寫(xiě)的IPC通信的基礎(chǔ)上修改，參考了當(dāng)前項(xiàng)目網(wǎng)絡(luò)庫(kù)的設(shè)計(jì)思路。
先介紹幾個(gè)主要的類(lèi):
1.CSocket重新套接字，CConnection繼承CSocket表示一個(gè)連接對(duì)象主要重寫(xiě)Recv和Send接口，以及組包過(guò)程。
2.CAccept處理客戶(hù)端的鏈接，
3.Cpacket一個(gè)消息數(shù)據(jù)包頭，CMessage繼承CPacket帶數(shù)據(jù)消息包。
4.CConnectManger保存一個(gè)連接CConnection的內(nèi)存池對(duì)象，CAcceptManager一個(gè)接收客戶(hù)端Accept的線程，CPacketManager參考了Loki的小對(duì)象管理做的一個(gè)緩沖區(qū)數(shù)據(jù)包內(nèi)存池。
5.CLibObject包含上面3個(gè)Manager(Singleton)，CNetWork網(wǎng)絡(luò)初始化。
6.CIOCP類(lèi)主要IO的線程類(lèi)，接收處理所有的客戶(hù)端連接CConnection。
7.CServer類(lèi)包括一個(gè)IOCP初始化和網(wǎng)絡(luò)庫(kù)管理類(lèi)，IOCP會(huì)把接收到的數(shù)據(jù)重組成數(shù)據(jù)包后保存到CServer的一個(gè)CMsgQueue中.
8.我們的重寫(xiě)一個(gè)Server只需要繼承CServer，然后實(shí)現(xiàn)run和AccedeProcess即可。run從CMsgQueue緩沖區(qū)提取一個(gè)消息包，AccedeProcess處理消息。
一些細(xì)節(jié)設(shè)計(jì):
1.為了節(jié)約帶寬Connection這里采用了Negles算法，這里采用Negle的并沒(méi)有馬上把每一個(gè)需要發(fā)送MSG采用緩存隊(duì)列的方式保存起來(lái)，而是每一個(gè)Connection自身都保存數(shù)據(jù)，CServer通過(guò)一個(gè)線程把每一個(gè)存在的Connection是否有消息緩存，然后發(fā)送。因而讓IOCP只處理接收的消息，發(fā)送消息通過(guò)CServer來(lái)處理。
出網(wǎng)絡(luò)庫(kù)基本框架如下:
網(wǎng)絡(luò)庫(kù)代碼的代碼http://code.google.com/p/tpgame/source/browse/#svn/trunk/GServerEngine/NetLibrary
問(wèn)題肯定較多，希望多多指教。
最近一直在構(gòu)思與寫(xiě)一套游戲AI系統(tǒng)，主要是通過(guò)狀態(tài)機(jī)響應(yīng)事件，更多是想運(yùn)用自己學(xué)習(xí)到的一些優(yōu)秀的算法，以及一些高級(jí)
的AI以此來(lái)鍛煉對(duì)一些復(fù)雜的數(shù)據(jù)結(jié)構(gòu)的編寫(xiě)和設(shè)計(jì)思維的提升。
算法和數(shù)據(jù)結(jié)構(gòu)方面:
1.2D和3D尋路(主要包括2D尋路的初始化條件優(yōu)化 ，3D的空間劃分以及多叉樹(shù)的劃分，以及堆維護(hù))。
2.帶有更多思維的角色系統(tǒng)(附帶更多的數(shù)據(jù)信息)判斷。
3.查詢(xún)線段樹(shù)和樹(shù)狀數(shù)數(shù)組的運(yùn)用。
4.一個(gè)線性的字符串過(guò)濾程序。
5.一個(gè)動(dòng)態(tài)基于角色的最優(yōu)二叉查找樹(shù)的動(dòng)態(tài)維護(hù)。(主要解決不同的角色AI觸發(fā)頻率建立一顆最優(yōu)二叉查找樹(shù))
6.追蹤算法以及游戲的群集算法都會(huì)整合到現(xiàn)在的AI系統(tǒng)中。
設(shè)計(jì)方面：
1.盡量讓類(lèi)之間耦合性更小，復(fù)雜度更低，淺顯明確。
注：Ai系統(tǒng)寫(xiě)完會(huì)把代碼和網(wǎng)絡(luò)庫(kù)的最新代碼更新都會(huì)上傳，希望大家多多指教。
最近做一個(gè)東西正好需要生成字典的算法，類(lèi)似一些密碼字典生成器(主要運(yùn)用在暴力破解)。生成的密碼會(huì)根據(jù)密碼長(zhǎng)度與字典集合的長(zhǎng)度成指數(shù)關(guān)系。
可以用一個(gè)函數(shù)來(lái)表示
f( x , y ) = x ^y ; x表示我們要生產(chǎn)的密碼長(zhǎng)度，y表示我們要生成的密碼字典字符集合。
當(dāng)時(shí)想到就有3個(gè)算法。
1.循環(huán)
關(guān)于循環(huán)，可以參考水仙花數(shù)的多層嵌套求解，主要算法如下:
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 * 幾位密碼就嵌套幾層循環(huán)
16
*/
17
18 }
19 }
20
}
這種方式移植不好，而且代碼臃腫。
2.遞歸
做過(guò)字符串的全排列的都明白這個(gè)算法，這種也是基于這種方式：但是由于隨著字典集合或者密碼長(zhǎng)度的增加，很容易會(huì)出現(xiàn)堆棧的內(nèi)存溢出。
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種方法的不錯(cuò)，然后寫(xiě)了一個(gè)非遞歸的算法
主要借用橫向掃描的方式，借鑒一個(gè)數(shù)組來(lái)進(jìn)行記錄當(dāng)前應(yīng)該生成的密碼。
主要算法如下:
1/**//*
2* 生成字典的函數(shù)
3* @parm 需要生成的長(zhǎng)度
4*/
5void MakeDict( int Len )
6{
7 char Dict[MaxDictLen+1]; // 生成的字典字符串
8 int Array[MaxDictLen]; // 記錄當(dāng)前應(yīng)該生成字典數(shù)組
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 /**//// 字典數(shù)組坐標(biāo)更新
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}
附上第三個(gè)生成算法源碼:
link
問(wèn)題描述如下:
2個(gè)整數(shù)(int32)，我需要對(duì)這2個(gè)數(shù)的第n位進(jìn)行二進(jìn)制數(shù)交換值。是否有一個(gè)高效的算法，或者高效的運(yùn)算。
例子如下:
2個(gè)整數(shù)10，7，把第1位的數(shù)值交換。
整數(shù) 二進(jìn)制 交換后二進(jìn)制 交換后的值
10 0x1010 0x1011 11
7 0x0111 0x0110 6
我的思路如下:
1.如果要對(duì)第n位數(shù)值交換，先求出第n位的值(1或者0),如果相等則不交換。
2.交換第n位，通過(guò)通過(guò)原理發(fā)現(xiàn)只需通過(guò)加減法運(yù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位的數(shù)值
6 int y = (src & (1<<(n-1))) >>(n-1); // 求出第n位的數(shù)值
7 if ( x != y )
8 {
9 des += (y-x)*(1<<(n-1)); // 交換
10 stc += (x-y)*(1<<(n-1)); // 交換
11 }
12}
是否有一種高效的算法，只是進(jìn)行一，兩步位與或運(yùn)算即可。。
關(guān)于游戲?qū)ぢ罚W(wǎng)絡(luò)上也有很多相關(guān)的文章，一般都是已A*為主，他只是一種啟發(fā)式搜索，最開(kāi)始寫(xiě)A*是在大三，主要還是做一個(gè)路徑搜索的算法。
關(guān)于游戲中A*的算法優(yōu)化，由于在搜索的過(guò)程中會(huì)通過(guò)open表和close保存一些結(jié)點(diǎn)，為了加快查找效率一般采用對(duì)維護(hù)的方式，利用map的最小堆(按照估價(jià)值的大小排序)來(lái)構(gòu)架數(shù)據(jù)結(jié)構(gòu)。其實(shí)還可以利用線性的hash_map來(lái)創(chuàng)建維護(hù)。
而3D中游戲?qū)ぢ芬彩遣捎猛瑯拥姆椒ǎ皇窃诓煌?D的8個(gè)方向搜索而是3*8個(gè)方向的搜索。所以他的復(fù)雜度之高，在對(duì)于一個(gè)3維的N*N*N的空間，他的搜索運(yùn)算為n^3*24，就需要考慮算法中的優(yōu)化。
總之一句3D尋路費(fèi)時(shí)又費(fèi)空間！
下面是我總結(jié)的優(yōu)化
1.總體還是利用a*和堆維護(hù)。
2.由于點(diǎn)是實(shí)心，可以直接進(jìn)行對(duì)角線的行走，也就是對(duì)角線行走一步后x,y,z的坐標(biāo)都會(huì)改變，從而降低通過(guò)2次二維變換的過(guò)程。二步變一步！
3.利用凸包的方式來(lái)優(yōu)化。
4.把一個(gè)場(chǎng)景的3D地圖全部細(xì)分，利用多叉樹(shù)進(jìn)行管理。
關(guān)于凸包的優(yōu)化可以通過(guò)這樣一個(gè)例子說(shuō)明(因?yàn)樵?D中更好的描述通過(guò)2維的地圖)：
A、假設(shè)1要到2的，通過(guò)A*的搜索，他會(huì)先到0然后發(fā)現(xiàn)不能通過(guò)在回溯，重新尋找新的路徑，這樣可能浪費(fèi)一些搜索時(shí)間。
B. 可以通過(guò)多邊形的最小矩形凸包的方式，這樣就可以減少不必要的搜索，如圖所示。
那么1到2就不會(huì)經(jīng)過(guò)0點(diǎn)。。因?yàn)榇螀^(qū)域設(shè)置為不可通過(guò)。
C. 如果我們要查找的點(diǎn)在我們凸包內(nèi)，所以我們?cè)趯ぢ纷铋_(kāi)始應(yīng)該驗(yàn)證點(diǎn)是否在凸包內(nèi)，如果在此區(qū)域內(nèi)，在行走時(shí)不能過(guò)濾這個(gè)矩形空間。
注：游戲中地圖一般是不變的，所以這些都是不變，凸包已知，驗(yàn)證點(diǎn)在凸包中也是線性的。
由于在計(jì)算3D的凸包的時(shí)候計(jì)算量大，最開(kāi)始采用靜態(tài)的方式來(lái)記錄數(shù)據(jù)。
簡(jiǎn)單的3D尋路算法源碼(不包含凸包優(yōu)化)：
/Files/expter/3DAStar.rar
所謂追蹤，相對(duì)于另外一個(gè)角色來(lái)說(shuō)是逃跑，首先需要做出追和逃跑的決策判斷。
1.坐標(biāo)追蹤
也是最基本追逐方式，他根據(jù)要追蹤對(duì)象的坐標(biāo)來(lái)修改追蹤者的坐標(biāo)，使兩者的距離逐漸縮短。
一個(gè)簡(jiǎn)單的例子:
Point m_pPrey; /// 被追蹤者
Point m_pAtta; /// 追蹤者
對(duì)于追蹤者來(lái)說(shuō)： 新位置 = 舊位置 + 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.視線追蹤
視線追蹤方式，主要是描述每一時(shí)刻都追蹤者會(huì)沿著被追逐者之間的直線方向運(yùn)動(dòng)。如圖所示：
通過(guò)圖可以更好描述此問(wèn)題，此問(wèn)題的求解關(guān)鍵在于求出連接追蹤者與獵物之間的直線，可以通過(guò)向量知道：2個(gè)向量想減即可得到。
可以分別用追蹤者與獵物的位置坐標(biāo)構(gòu)造出兩個(gè)向量,假設(shè)b 代表追蹤者位置向量,a 代表獵物位置向量。做向量減法a-b 便得到了向量c，將c 的起點(diǎn)置于追蹤者的位置上,就得到了一條指向獵物的向量c. 此時(shí)，令：
追蹤者X 方向速度 / 追蹤者Y 方向速度 ＝ c 向量x 軸分量/ c 向量y 軸分量 .即可求解。
3.攔截追蹤
所謂攔截追蹤，如果考慮的是被追逐的目標(biāo)太遠(yuǎn)，如果2者速度一樣，或者相差不大，有可能很難追上，玩過(guò)實(shí)況足球的都知道，如果采用上面的2中追逐方式，可能錯(cuò)過(guò)最佳的防守位置。下面是攔截追蹤的一個(gè)示例圖:
對(duì)于追蹤者來(lái)說(shuō)，他只需要知道被追蹤者的位置，方向與速度，講會(huì)計(jì)算一個(gè)最佳的攔截位置。然后你會(huì)發(fā)現(xiàn)這只是一個(gè)簡(jiǎn)單的追蹤問(wèn)題。且需要的時(shí)間t最少。
整個(gè)3種追蹤的源碼代碼 以及 demo都共享：
/Files/expter/chase.rar
下一篇通過(guò)實(shí)例demo來(lái)記錄學(xué)習(xí)的聚類(lèi)算法：
摘要: 定制自己的new 和 delete，讓對(duì)象在靜態(tài)塊上進(jìn)行分配。
一般常見(jiàn)的new和delete操作符，就意味著使用堆進(jìn)行內(nèi)存分配，使用new操作符是名為operator new的函數(shù)調(diào)用，且函數(shù)返回返回一個(gè)指向某塊內(nèi)存分配器分配內(nèi)存指針。
對(duì)于內(nèi)存的分配到底從哪兒來(lái)沒(méi)有任何限制，它可能來(lái)自一個(gè)特殊的堆，也可能來(lái)自一個(gè)靜態(tài)分配的塊，也可能來(lái)自一個(gè)標(biāo)準(zhǔn)容器內(nèi)部，也可能來(lái)自某個(gè)函數(shù)范圍的局部存儲(chǔ)區(qū)。而對(duì)于現(xiàn)在的各自軟件中主流內(nèi)存管理方式，一般通過(guò)內(nèi)存池的管理方式，它可能即包含靜態(tài)分配也同時(shí)包含動(dòng)態(tài)分配。
閱讀全文
在多線程過(guò)程中，對(duì)于線程間的數(shù)據(jù)共享同步問(wèn)題，具體針對(duì)多線程需要對(duì)一個(gè)Vector進(jìn)行讀與寫(xiě)的操作，不考慮緩沖區(qū)的操作，一般情況下為了保證穩(wěn)定性的同時(shí)在讀寫(xiě)的時(shí)候都要進(jìn)行加鎖，其實(shí)可以通過(guò)一個(gè)技巧，就是通過(guò)一個(gè)臨時(shí)變量在寫(xiě)數(shù)據(jù)的時(shí)候把第一個(gè)值付給臨時(shí)變量，那么在讀取數(shù)據(jù)的線程中會(huì)直接讀取臨時(shí)變量，此時(shí)只需要加鎖一次即可。
我寫(xiě)了一個(gè)測(cè)試?yán)樱褪顷P(guān)于開(kāi)3個(gè)讀，寫(xiě)，刪的操作。。。一般情況進(jìn)行加鎖，與通過(guò)通過(guò)臨時(shí)變量來(lái)減少一次加鎖速度與效率明顯低于后者。
針對(duì)1000000個(gè)數(shù)據(jù)的操作，操作1比操作2快2倍以上。
下面是我的測(cè)試代碼，簡(jiǎn)單。。。只是為了說(shuō)明問(wèn)題
/Files/expter/l_thread.rar
摘要: 一個(gè)簡(jiǎn)單線程池的實(shí)現(xiàn)
閱讀全文
摘要: 編譯DShow程序出現(xiàn) 無(wú)法打開(kāi)包括文件:“dsound.h”
閱讀全文
摘要: 關(guān)于IE插件，關(guān)于BHO的彈出窗口
閱讀全文