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