|
對于一個(gè)游戲而言，定時(shí)器是必須的，而它一般作為一個(gè)游戲基本公共組件，而定時(shí)器在游戲邏輯中運(yùn)用是非常明顯的(比如吃藥回血，每幾秒回血多少)，而對于游戲邏輯而言需要開發(fā)一個(gè)高效率高精度(毫秒級別)的定時(shí)器。 一：分析Ace庫定時(shí)器實(shí)現(xiàn)方式 1.Ace種定時(shí)器實(shí)現(xiàn)有4種，這里不具體介紹實(shí)現(xiàn)細(xì)節(jié)，主要介紹實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)，性能。 具體的4種定時(shí)器都是從ACE_Timer_Queue_T繼承，每種定時(shí)器用不同的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)具體Timer的算法。 1）ACE_Timer_Heap定時(shí)器，根據(jù)觸發(fā)時(shí)間建立一個(gè)優(yōu)先級隊(duì)列(一個(gè)最小堆數(shù)據(jù)結(jié)構(gòu))來維護(hù)所有的定時(shí)器，代價(jià)就是刪除和插入過程為O(logn),代價(jià)比較高。 2）ACE_Timer_List定時(shí)器，根據(jù)觸發(fā)時(shí)間建立一個(gè)有序的雙向鏈表，代價(jià)就是插入定時(shí)器代價(jià)較高。 3）ACE_Timer_Hash定時(shí)器，采用開鏈的Hash方式每一個(gè)桶為一個(gè)單鏈表，在檢查所有桶超時(shí)的時(shí)候會遍歷鏈表所有的元素。為了提高效率這里所用的Hash桶應(yīng)該足夠 大，而對于定時(shí)器一般是頻繁的超時(shí)響應(yīng)定時(shí)器，已經(jīng)插入和刪除，響應(yīng)會采用迭代的方式。所以效率并不是那么高效。 4）ACE_Timer_Wheel定時(shí)器，采用的一種時(shí)間輪的方式，具體實(shí)現(xiàn)就好象一個(gè)輪子上面有很多插槽，每一個(gè)插槽下面包括一個(gè)有序雙向鏈表，在Ace中把輪子叫做Wheel,插槽叫做Spoke，每一個(gè)定時(shí)器被Hash到Spoke中，而Spoke也可以理解為timer的分辨率，而Spoke的計(jì)算公式為 :( 觸發(fā)時(shí)間 >> 分辨率的位數(shù))&(spoke大小-1).然后在根據(jù)觸發(fā)時(shí)間把定時(shí)器插入到每一個(gè)Spoke的有序雙向鏈表中， 與Ace_timer_Hash的實(shí)現(xiàn)類似，只是這里用戶可以指定Spoke大小。這里代價(jià)就是插入的時(shí)候可能最壞為O(n). 我們公司現(xiàn)在CTimer就是采用Ace的ACE_Timer_Wheel原理設(shè)計(jì)的。 這里有一個(gè)圖更能直觀的描述這種思想: 實(shí)現(xiàn)方式為Vector,list組合。 二: 本文介紹一種采用linux中斷處理的定時(shí)器設(shè)計(jì)方式 此定時(shí)器的查找，刪除，插入都是O(1) 1） 介紹設(shè)計(jì)原理 定時(shí)器是基于時(shí)間的中斷函數(shù)，即是根據(jù)觸發(fā)時(shí)間來超時(shí)響應(yīng)。所以只要我們設(shè)計(jì)一個(gè)基于時(shí)間的Hash算法。只要我們能我們把一個(gè)函數(shù)觸發(fā)時(shí)間全部Hash到此Hash算法的桶中，就實(shí)現(xiàn)了查找，插入，刪除O(1)的操作了，其實(shí)不然基于時(shí)間的hash算法好像挺復(fù)雜，而且桶的數(shù)量太大，內(nèi)存消耗太多，所以把一個(gè)時(shí)間直接Hash代價(jià)太大。是否有一種其他的方式呢，linux中斷處理采用一種類似水表計(jì)算水量的方式，方式就是生活中的水表，第一個(gè)指針轉(zhuǎn)一圈后一個(gè)轉(zhuǎn)一格，假設(shè)每一個(gè)圈都是10個(gè)刻度，第一個(gè)圈能表示10，那么第二圈沒一個(gè)刻度表示第一個(gè)圈的1圈，就能表示10*10, 二個(gè)圈一共就能表示10*10 + 10。 以此類推，5個(gè)圈就能表示10^5+10^4+10^3+10^2+10... 一個(gè)32bits的整數(shù)，如果精確到1毫秒，則2^32位可以表示49.3天，而一般服務(wù)器應(yīng)該不會直接運(yùn)行49.3天，這里我們采用5個(gè)輪子(即圈), 輪子大小分別為256,64,64,64,64 ,輪子依次類推表示范圍在0"256, 256"256*64, 256*64"256*64^2, 256*64^2"256*64^3, 256*64^3"256*64^4, 假設(shè)這里精度為n毫秒，第一個(gè)輪子表示n*256秒時(shí)間內(nèi)觸發(fā)函數(shù)，第二個(gè)輪子的第二個(gè)插孔則表示n*256*2時(shí)間范圍內(nèi)的， 2）一些定義: A. 輪子，這里采用的輪子與上面介紹的Ace輪子大概一樣，一個(gè)循環(huán)列隊(duì)，每一個(gè)插槽你們有一個(gè)雙向鏈表，注意這里鏈表不需要排序，所以在插入的是O(1)的操作。輪子為5個(gè)。 3) 操作： A. Hash算法:這里Hash算法根據(jù)他的多少時(shí)間后觸發(fā)，直接Hash得到輪子以及插槽，然后插入到某個(gè)插槽雙向的鏈表中。 B.定時(shí)器觸發(fā): 定時(shí)器觸發(fā)只會觸發(fā)第一個(gè)輪子超時(shí)的所有定時(shí)器，因?yàn)楹竺?個(gè)輪子定時(shí)器表示都在前1輪子觸發(fā)完了才會觸發(fā)，所以這里讓后面4個(gè)輪子維護(hù)表示將要發(fā)生的定時(shí)。這里會根據(jù)當(dāng)?shù)谝粋�(gè)輪子轉(zhuǎn)第幾圈后，第二個(gè)輪子會把第幾插槽的所有定時(shí)器全部插入到第一個(gè)輪子中，依次類推，第二個(gè)輪子轉(zhuǎn)一個(gè)第三個(gè)輪子某個(gè)插槽又會插入到第二個(gè)輪子中。。。 4）注意的地方: A.將一個(gè)定時(shí)器插入到它應(yīng)該所處的定時(shí)器輪子插槽中。 B.定時(shí)器的遷移，也即將一個(gè)定時(shí)器從它原來所處的輪子插槽遷移到另一個(gè)輪子插槽中。 C.超時(shí)響應(yīng)執(zhí)行當(dāng)前已經(jīng)到期的定時(shí)器。 三：編碼實(shí)現(xiàn) 1) 常量定義 /**//// define m #define lnum 5 #define sbits 6 #define ebits 8 #define sbitsize ( 1 #define ebitsize ( 1 #define sMask ( sbitsize- 1) #define eMask ( ebitsize -1) 2) 數(shù)據(jù)結(jié)構(gòu) 1/**//// 定時(shí)器指針結(jié)點(diǎn) 2struct ListNode 3{ 4 ListNode *next,*prev; 5}; 6 7/**//// 8/// 定時(shí)器類型 9/// 10enum eTimerType 11{ 12 eTimer1 = 10, 13 eTimer2 , 14 eTimer3 15}; 16 17/**//// 18/// 定時(shí)器結(jié)點(diǎn),tlist表示結(jié)點(diǎn)的指針,expires循環(huán)周期時(shí)間 19/// etime 觸發(fā)周期時(shí)間,pFun觸發(fā)函數(shù). 20/// 21struct timernode 22{ 23 ListNode tlist; 24 ulong expires; 25 ulong etime; 26 void *pFun; 27 eTimerType eType; 28}; 3) 輪子類 1/**//// 2/// 一個(gè)輪子,一個(gè)循環(huán)隊(duì)列 3/// 4/// 5class CLinkList 6{ 7 8public: 9 10 CLinkList(void); 11 12 CLinkList( int size ); 13 14 "CLinkList(void); 15 16 /**//// 17 /// 初始化 18 /// 19 void init(); 20 21 /**//// 22 /// 讓指針指向自己 23 /// 24 void init_list_self( int index); 25 26 /**//// 27 /// 把news插入到prev,next之間 28 /// 29 void insert_listnode(ListNode *news , ListNode* prev , ListNode* next); 30 31 /**//// 32 /// 插入到鏈表頭 33 /// 34 void insert_head( ListNode* news , ListNode* head ); 35 36 /**//// 37 /// 插入到鏈表尾 38 /// 39 void insert_tail( ListNode* news , ListNode* head ); 40 41 /**//// 42 /// 刪除節(jié)點(diǎn) 43 /// 44 void list_del( ListNode* list); 45 46 /**//// 47 /// 得到改輪子轉(zhuǎn)到第幾個(gè)插槽 48 /// 49 int GetIndex( ) const { return m_index ;} 50 51 /**//// 52 /// 更新輪子的插槽 53 /// 54 void SetIndex(int idx) { m_index = idx ;} 55 56 /**//// 57 /// 得到輪子插槽的指針 58 /// 59 ListNode* GetNode(int index) const; 60 61private: 62 /**//// 63 /// 輪子的插槽數(shù)組 64 /// 65 ListNode *m_List; 66 67 /**//// 68 /// 輪子當(dāng)前轉(zhuǎn)到的索引 69 /// 70 int m_index; 71 72 /**//// 73 /// 輪子大小 74 /// 75 int m_Size; 76 77}; 4)定時(shí)器管理類 定時(shí)器管理類 1/**//// 2/// 定時(shí)器管理類,管理定時(shí)器的五個(gè)輪子 3/// 4class CTimer 5{ 6public: 7 /**//// 8 /// 構(gòu)造函數(shù)如下 9 /// 10 CTimer(void); 11 12 CTimer( int second); 13 14 "CTimer(void); 15 16public: 17 /**//// 18 /// 初始化定時(shí)器管理類 19 /// 20 void Init(int Second = 0); 21 22 /**//// 23 /// 增加一個(gè)定時(shí)器 24 /// 25 void add_timer(timernode *times ); 26 27 /**//// 28 /// 檢測定時(shí)器是否存在 29 /// 30 /// @return 如果存在返回true,否則為false 31 /// 32 bool check_timer(timernode* times); 33 34 /**//// 35 /// 刪除定時(shí)器 36 /// 37 /// @return 如果刪除成功返回true,否則為false 38 /// 39 bool delete_timer(CLinkList* list, timernode *times); 40 41 /**//// 42 /// 重新初始化一個(gè)定時(shí)器 43 /// 44 void init_timer(timernode* timers); 45 46 /**//// 47 /// 定時(shí)器的遷移，也即將一個(gè)定時(shí)器從它原來所處的定時(shí)器向量遷移到另一個(gè)定時(shí)器向量中。 48 /// 49 void cascade_timer(CLinkList* timers); 50 51 /**//// 52 /// 執(zhí)行當(dāng)前已經(jīng)到期的定時(shí)器,所有小于jeffies的定時(shí)器 53 /// 54 void Expires( ulong jeffies); 55 56 /**//// 57 /// 重新初始化一個(gè)定時(shí)器 58 /// 59 void Cancel(timernode* timers); 60 61 /**//// 62 /// 重新計(jì)算一個(gè)定時(shí)器 63 /// 64 void Mod_timer(timernode* timers); 65 66private: 67 /**//// 5個(gè)輪子 68 CLinkList* m_tv1; 69 CLinkList* m_tv2; 70 CLinkList* m_tv3; 71 CLinkList* m_tv4; 72 CLinkList* m_tv5; 73 CLinkList** g_vecs; 74 75 /**//// 定時(shí)器全局tick 76 ulong m_jeffies; 77 /**//// 上次運(yùn)行時(shí)間 78 ulong m_Lasttime; 79 /**//// 精確到毫秒 80 ulong m_mSecond; 81}; 82 四： 測試 通過本文的介紹可以理解次定時(shí)器的的查找，刪除，插入都是O(1)的復(fù)雜度。 /**//// 游戲事件基類 class CGameEvent { public: virtual long TimeOut( eTimerType type) = 0; }; 測試?yán)樱?nbsp; 1long Sum1= 0 ; 2long Sum2= 0 ; 3long Sum3= 0 ; 4long Sum = 0; 5 6class CTimertest : public CGameEvent 7{ 8public: 9 long TimeOut( eTimerType type) 10 { 11 switch ( type) 12 { 13 case eTimer1: 14 std::cout 15 break; 16 case eTimer2: 17 std::cout 18 break; 19 case eTimer3: 20 std::cout 21 break; 22 default: 23 std::cout 24 break; 25 } 26 return 0; 27 } 28}; 29 30int _tmain(int argc, _TCHAR* argv[]) 31{ 32 CTimer mytimer( 40 ); 33 34 long n; 35 std::cin >> n; 36 CTimerTest test; 37 for ( int i = 0 ; i 38 { 39 timernode* tim = new timernode ; 40 tim->expires = 0; 41 tim->etime = GetCurrSystemTime() + (rand() % 1000 ) * 6; 42 tim->pFun =&test; 43 tim->eType =(eTimerType)( i%3 + 10 ); 44 45 mytimer.add_timer( tim ); 46 } 47 48 for ( ;; ) 49 { 50 if ( (Sum1 + Sum2 + Sum3) == n ) 51 break; 52 53 /**//// 運(yùn)行所有的定時(shí)器 54 mytimer.Expires( GetCurrSystemTime() ); 55 } 56 57 std::cout 58 59 60 61 return 0; 62} |
