遊戲程式設計模式-事件隊列

　　“對消息或事件的發送與受理進行事件上的解耦。”

動機

　　如果你曾從事過使用者界面程式設計，那肯定對“事件”不陌生了。每當你在界面中點選一個按鈕或下拉菜單，系統都會生成一個事件，系統會把這個事件抛給你的應用程式，你的任務就是擷取到這些事件并将其與你自定義的行為關聯起來。那麼為了擷取到這些事件，你的代碼通常都會由個事件循環。就像這樣：

while(running)
{
    Event e = pollEvent();
    //handle event
}      

　　可以看到，這段代碼會不斷的擷取事件，然後處理。但如果期間再事件發生，應該如何處理了？這裡必須得有個位置安置這些輸入，避免漏掉，而這個所謂的“安置位置”正是一個隊列。

中心事件總線

　　多數遊戲的事件驅動機制并非如此，但是對于一個遊戲而言維護它自身的事件隊列作為其神經系統的主幹是很常見的。你會經常聽到“中心式”、“全局的”、“主要的”類似這樣的描述。它被用于那些希望保持子產品間低耦合的遊戲，起到遊戲内部進階通信子產品的作用。比如你的遊戲有一個新手教程，該新手教程會在完成指定的遊戲事件後彈出幫助框。簡單的做法就是在代碼中判斷事件是否發生，如果發生則執行處理代碼。但随着事件的增多，代碼需要判斷的情況也越來越多，代碼也變得越來越複雜。這個時候你可能會想到用一個中心事件隊列來取代它。遊戲的任何一個系統都可以向這個隊列發送事件，同時也可以從隊列中“收取”事件。新手引導子產品向事件隊列注冊自身，并向其聲明接收“敵人死亡”事件。借此，敵人死亡的消息可以在戰鬥系統和新手子產品不進行直接互動的情況下在兩者間傳遞。

可能的問題

　　中心事件隊列雖然解決了一些問題，但也還有一些問題存在。我們來看一個例子，比如我們在遊戲中播放音效：

class Audio
{
public:
    static void playSound(SoundId id,int volume);
};

void Audio:playSound(SoundId id,int volume)
{
    ReourceId resource = loadSound(id);
    int channel = findOpenChannel();
    if(channel == -1) return;
    startSound(resource,channel,volume);
}      

　　在UI代碼中我們這樣調用。

class Menu
{
public:
    void onSelect(int index)
    {
        Audio::playSound(SOUND_BLOOP,VOL_MAX);
        //other stuff....     
    }
};      

　　我們可能需要面對的問題有：

• 　　在音效引擎完全處理完播放請求前，API的調用會一直阻塞着調用者

　　因為playSound是”同步“執行的，它隻有在音效被完全播放出來後才會傳回至調用者的代碼；除此外，我們還會面臨着另一個問題，比如我們的英雄角色擊中兩個以上的怪物，那麼就會播放多次怪物的哀嚎聲，如果你了解一些音效的知識，你就會知道多個聲音混合在一起會疊加它們的聲波。也就是說，當聲波相同時，聲音聽起來和第一個聲音一樣，但音量會大兩倍，這會讓聲音聽起來很刺耳，而且一旦場景中的聲音更多的時候，因為硬體的處理能力有限，超出門檻值的聲音就會被忽略或中斷。為了處理這些問題，我們需要對所有的音效進行彙總和區分。但從上述代碼可以看出，我們的處理每次隻處理一個音效，無法滿足這個需求。

• 　　不能批量處理處理請求

　　代碼庫中，有很多不同的子系統都會調用”playSound“，而我們的遊戲通常運作在現代多核硬體上面。為了充分利用多核，它們通常都配置設定在不同的線程中。由于我們的API是同步的，它會在調用者的線程中執行，是以當不同的系統調用playSound時，我們就遇到了線程同步調用API的情況。

• 　　請求在錯誤的線程被處理

　　這些問題的共同點就是聲音引擎調用”playSound“函數的意思就是”放下所有的事情，馬上播放音樂“。”馬上處理“就是問題所在。其它遊戲系統在它們合适的時候調用”play Sound“，而聲音引擎此時卻未必能處理這一需求，為修複這個問題，我們将對請求的接收和手裡進行解耦。

事件隊列模式

　　事件隊列是一個按照先進先出順序存儲一系列通知或請求的隊列。發出通知時系統會将請求置入隊列并随即傳回，請求處理器随後從事件隊列中取出事件并進行處理。請求可由處理器直接處理或轉交給對其感興趣的子產品。這一模式的發送者與受理者進行了解耦，使消息的處理變得動态且非實時。

使用情境

　　如果你隻是向對一條消息的發送者和接收者進行解耦，那麼諸如觀察者模式和指令模式都能以更低的複雜度滿足你。需要在某個問題上對時間進行解耦時，一個隊列往往足矣。

　　按照推送和拉去的方式思考：代碼A希望另一個代碼塊B做一些事情。A發起這一請求最自然的方式就是把它推送給B。同時，B在其循環中适時拉取該請求并進行處理也是非常自然的。當你具備推送端和拉取端之後，在兩者之間需要一個緩沖。這正是緩沖隊列比簡單的解耦模式多出來的優勢。

　　隊列提供給拉取請求的代碼塊一些控制權：接收者可以延遲處理，聚合請求或者完全廢棄它們。但這是通過”剝奪“發送者對隊列的控制來實作的。所有發送端能做的就是往隊列中投遞消息。這使得隊列在發送端需要實時回報時顯得很不适用。

注意事項

　　不像其它更簡單的模式，事件隊列會更複雜一些并對遊戲架構産生廣泛而深遠的影響。這意味着你在決定如何适用、是否适用本模式時須三思。

• 　　中心事件隊列是個全局變量

　　該模式的一種普遍用法被稱為”中央樞紐站“，遊戲中所有子產品的消息都可以通過它來傳遞。它是強大的基礎設施，但強大并不意味着好用。關于”全局變量是糟糕的“這一點我們之前在單例模式中也講過，全局變量的使用意味着遊戲的任何部分都可以通路它，這會在不知不覺中讓這些部分産生互相依賴，雖然本模式将這些狀态封裝成一種不錯的小協定，但仍然具備全局變量所包含的危險性。

• 　　遊戲世界的狀态任你掌控

　　使用事件隊列，你需要非常謹慎。因為投遞和接收事件的解耦，一個事件發送到事件隊列中大多時候都不會馬上得到處理，也就是說處理事件的時候不能想當然的認為目前的世界狀态和事件發生時的世界狀态時一緻的，比如一個實體收到攻擊，可能會引起附近的同伴過來反擊，但如果這個事件是後來被處理，而附近的同伴那時移動到其它位置，那麼共同反擊這個行為就不會發生。是以這意味着隊列的事件視圖要比同步系統的事件具有更重量級的結構，這個結構用來記錄事件發生時的細節，以便後面處理時使用。而同步系統隻需要知道事件發生了，然後檢查環境即可了解這些細節。

• 　　你會在回報中繞圈子

　　　　任何一個事件或消息系統都得留意循環。

　　1.A發送一個事件；

　　2.B接收事件并處理，然後發送另一個事件；

　　3.恰好，這個事件是A關心的，A接收後回報，同時發送事件……

　　4.回到2.

　　當你的資訊系統是同步的時候，你會很快的發現死循環——它們會導緻棧溢出然後遊戲崩潰。對于隊列來說，異步的放開棧處理會導緻這些僞事件在系統中徘徊，但遊戲會保持運作。這個很難發現，一個規避的辦法就是避免在事件處理代碼中再發送事件。還有就是再系統中實作一個小的調試日志也是個不錯的主意。

執行個體代碼

　　之前的代碼已經具備一定的功能，但它們不完美，現在讓我們使用一些手段來完善它們。

　　首先，針對playSond是同步調用的問題，我們選擇讓它推遲執行，進而快速傳回。這個時候我們需要把這個播放請求先存起來，這裡我們使用最簡單的數組。

struct PlayMessage
{
    SoundId id;
    int volume;
};

class Audio
{
public:
    static void init(){numPending_=0;}
    void playSound(SoundId id, int volume)
    {
           assert(numPending_<MAX_PENDING);
           pending_[numPending_].id = id;
           pending_[numPending_].volume=volume;
           numPending_++;
    }

    static void update()
    {
        for(int i=0;i<numPending_;++i)
        {
             ResourceId resource = loadSound(pending_[i].id);
             int channel = findOpenChannel();
             if(channel == -1) continue;
             startSound(resource,channel,pending_[i].volume);
        }
        numPending_ = 0;
      }
private：
    static const int MAX_PENDING=16;

    static PlayMessage pending_[MAX_PENDING];
    static int numPending_;
};      

       在這裡我們把事件處理代碼移到了update中，接下來我們隻需要在合适的時候調用它即可。比如在遊戲主循環中調用或在一個專用的聲音線程中調用。這樣可以很好的運作，但上述代碼是假定我們對每個音效的處理都能夠在一次“update”中完成。如果你做一些，例如在聲音資源加載後異步處理其它請求的事情，上面的代碼就不湊效了。為了保證“update（）”一次隻處理一個請求，它必須能夠在保證保留隊列中其它請求而把将要處理的請求單獨拉出緩沖區。換句話說，我們需要一個真正的隊列。

環狀緩沖區

　　有很多的方法可以實作隊列。一種值得推薦的方法是環狀緩沖區。它保有數組的優點，同時允許我們從隊列的前端持續的移除元素。

class Audio
{
public:
    static void init(){head_=0;tail_=0;}
    void playSound(SoundId id, int volume)
    {
        assert((tail_+1) % MAX_PENDING_ != head_);
        pending_[tail_].id = id;
        pending_[tail_].volume=volume;
        tail_ = (tail_+1) % MAX_PENDING;
    }

    void update()
    {
        if(head_ == tail_) return;
        
        ResourceId resource = loadSound(pending_[head_].id);
        int channel = findOpenChannel();
        if(channel == -1) return;
        startSound(resource,channel,pending_[head_].volume);

        head_ = (head_+1) % MAX_PENDING;
    }

private:
    static const int MAX_PENDING=16;

     PlayMessage pending_[MAX_PENDING];
     int head_;
     int tail_;
};      

　　環狀緩沖區的實作非常簡單，就是使用兩個指針，一個指向對頭，一個指向隊尾，一開始兩個指針重合表示為空，然後隊尾在添加請求時向前移動，隊頭則在處理請求後向前移動，但它們到達數組的尾部時，則繞回頭部。當然，我們添加請求時，首先要檢視目前隊列是否已滿，已滿則丢棄事件。

彙總請求

　　現在我們已經有一個隊列了，可以處理聲音疊加過大的問題。處理方法就是彙總并合并請求。

void Audio::playSound(SoundId id,int volume)
{
    for(int i=head_;i!=tail_;i=(i+1) % MAX_PENDING)
    {
        if(pending_[i].id == id)
        {
            pending_[i].volume=max(pending_[i].volume,volume);
            return;
        }
    }

    //previous code...       
}      

　　這裡我們簡單的判斷請求中是否有相同的音效，如果有，則合并它們，聲音則其最大的為準。這裡需要考察的一點就是合并的時候需要周遊整個隊列，如果隊列較大，這個會比較耗時，這個時候可以把合并代碼移動到“update”中去處理。

　　除此之外，還有一個重要事情，我們可彙總的“同步發生”的請求數量之和隊列一般大小。如果我們更快的處理請求，隊列保持的很小，那麼可批量處理請求的機會就小。同樣，如果處理請求滞後，隊列被填滿，那麼我們發生崩潰的機率就更大。

　　這種模式将請求方與請求被處理的時間進行隔離，但是當你把整個隊列作為一個動态的資料結構去操作時，提出請求和處理請求之間的之後會顯著的影響系統表現。是以，确定這麼做之前你已經準備好了。

跨越線程

　　最後的問題就是線程同步的問題。在現今多核硬體的時代，這是必須解決的一個問題。而因為現在我們已經使用隊列把請求代碼和處理請求的代碼解耦了，是以我們隻需要做到隊列不被同時修改即可。最簡單的做法就是給添加請求的時候給隊列的時候加鎖，而在處理請求的時候等待一個條件變量，避免沒有請求或事件的時候cpu空轉。這部分可參照線程池實作方案：https://blog.csdn.net/caoshangpa/article/details/80374651

設計決策

　　入隊的是什麼

　　　　迄今為止，“事件”和“消息”總是被混着使用，因為這無傷大雅，無論你往隊列裡塞什麼，它都具備相同的解耦和聚合能力，但二者仍然有一些概念上的不同。

• 　　如果隊列中是事件
  • 一個“事件”或“通知”描述的是已經發生的事情。是以，如果你将它入隊，
  • 　　你可能會允許多個監聽器。因為隊列中的事情已經發生，發送者不關心誰會接到它。從這個角度看，這個事件已經過去并且被忘記；
  • 　　可通路隊列的域往往更廣。事件隊列經常用于給任何和所有感興趣的部分廣播事件。為了允許感興趣的部分有更大的靈活性，這些隊列往往有更多的全局可見性。

• 　　如果隊列中是消息
  • 　　一個“消息”或“請求”描述的是一種“我們期望”發生在“将來”的行為。類似于“播放音樂”。你可以認為這是一個異步API服務。這樣，
  • 　　你更可能隻有單一的監聽器。比如示例中的播放音樂的請求，我們并不希望遊戲的其它部分來偷竊隊列中的消息。

　　誰能從隊列中讀取

　　　　在播放音樂的示例中，隻有“Audio”類能讀取隊列。這是一中單點傳播的方式，還有廣播和工作隊列方式，它們有多個讀取者。

• 　　單點傳播隊列

  當一個隊列是一個類的API本身的一部分時，單點傳播是最合适的。比如在上述示例中，調用者隻能調用“playSound”函數。單點傳播隊列的特點：

  • 　　隊列稱為讀取者的實作細節。所有的發送者知道的隻是它發送了一個消息；
  • 　　隊列被更多的封裝。所有其它條件都相同的情況下，更多的封裝通常是更好的；
  • 　　你不必擔心多個監聽器競争的情況。在多個監聽器下，你不得不決定它們是否都擷取隊列的每一項（廣播）還是隊列中的每一項都配置設定給一個監聽器（更像一個工作隊列）；

• 　　廣播隊列

  這是大多數“事件”系統所作的事情。當一個事件進來時，它有多個監聽器。這樣，

  • 　　事件可以被删除。在大多數廣播系統中，如果某一時刻事件沒有監聽器，則事件會被廢棄；
  • 　　可能需要過濾事件。廣播隊列通常是在系統内大範圍可見的，而且你會有大量的監聽器。大量的監聽器乘以大量的事件，于是你要調用大量的事件句柄。為了縮減規模，大部分的廣播系統會為讓監聽器過濾它們收到的事件集合。比如隻接受UI事件。
• 　　工作隊列

　　　類似于廣播隊列，此時你也有多個監聽器。不同的是隊列中每一項隻會被配置設定給一個監聽器。這是一種對于并發線程支援友好的系統中的常見工作配置設定模式。這個方式讓你必須做好規劃。因為一個項目之投遞給一個監聽器，隊列邏輯需要找到最好的選擇。這可能是一個簡單循環或随機選擇，亦或者是一個更複雜的優先級系統。

　　誰可以寫入隊列

　　　　寫入隊列的可能模式有：一對一、一對多、多對多。

• 　　一個寫入者

　　　　一個寫入者類似于同步觀察者模式。你擁有一個生成事件的特權對象，以供其它子產品接收。它的特點是：

• • 　　你隐式的知道事件的來源。因為隻有一個對象往隊列中添加事件，是以可以安全的假定事件來自于該發送者；
  • 　　通常允許多個讀取者。你可以創造一個一對一的接收者的隊列。但是，這樣不太像通信系統，而更像一個普通的隊列資料結構。

• 　　多個寫入者

　　　　這個是我們音頻引擎例子的工作原理。遊戲的任何子產品都可以向隊列中添加事件。就先“全局”或“中央”事件總線。對于它

• • 　　你必須小心回報循環。因為任何東西都可以進入隊列，是以很可能會觸發回報循環；
  • 　　你可能會想要一些發送方在事件本身的引用。當監聽器得到一個事件時，它可能想要知道是誰發送的。這個時候就需要把發送方的引用打包到事件對象中。

　　隊列中對象的聲明周期管理

• 轉移所有權

     這是抖動管理記憶體時的額一個中傳統方法。當一個消息入隊時，發送者不再擁有它。當消息處理時，接收者取得所有權并負責釋放它。

• 共享所有權

　　　　這個其實就是智能指針了。持有消息的對象共享消息的所有權，但消息沒有被引用時，自動釋放記憶體。

• 隊列擁有它

　　　　另一個觀點是消息總是存在于隊列中。不用自己釋放消息，發送者會先從隊列中請求要給消息，而隊列傳回已經存在消息的引用，發送者填充它。就像一個對象池。