本篇知識(shí)點(diǎn)來(lái)源于《游戲引擎架構(gòu)》第五章，此章節(jié)主要討論多數(shù)游戲引擎中都會(huì)出現(xiàn)的底層支持系統(tǒng)。

系統(tǒng)的啟動(dòng)和終止次序控制

C++靜態(tài)初始化次序是無(wú)法使用的，原因是我們無(wú)法預(yù)引擎子系統(tǒng)的構(gòu)造函數(shù)調(diào)用次序和析構(gòu)函數(shù)調(diào)用次序。比如我要啟動(dòng)引擎的A，B，C系統(tǒng)，無(wú)法保證這些系統(tǒng)是按照規(guī)定次序進(jìn)行創(chuàng)建的。所以這對(duì)含有互相依賴(lài)關(guān)系的引擎系統(tǒng)都不適合。

雖然我們可以通過(guò)全局靜態(tài)單例構(gòu)造來(lái)實(shí)現(xiàn)控制構(gòu)建次序，但是依然沒(méi)辦法控制析構(gòu)次序，而且我們無(wú)法確定什么時(shí)候這個(gè)單例會(huì)被創(chuàng)建（即顯式調(diào)用:get()）

簡(jiǎn)單有效的方法就是不在構(gòu)造函數(shù)和析構(gòu)函數(shù)里做事，而是定義一個(gè)啟動(dòng)和終止函數(shù)，再在一個(gè)主管理器里去顯式調(diào)用這些函數(shù)即可達(dá)到效果。

更高端的方式即是讓各個(gè)管理器登記在一個(gè)全局的優(yōu)先隊(duì)列里，之后就可以按照恰當(dāng)?shù)捻樞蛑鹨粏?dòng)所有管理器，在結(jié)束之前就可以逐一彈出并調(diào)用相應(yīng)的終止函數(shù)，以此來(lái)達(dá)到自動(dòng)管理。

內(nèi)存管理

實(shí)際上C++的全局new/delete運(yùn)算符，或者malloc()/free()來(lái)動(dòng)態(tài)分配內(nèi)存（又稱(chēng)為堆分配）是很低效的，原因一個(gè)是必須處理任何大小的分配請(qǐng)求，這需要大量的管理開(kāi)銷(xiāo)，二是分配內(nèi)存需要從用戶(hù)模式轉(zhuǎn)換至內(nèi)核模式，上下文切換可能會(huì)耗費(fèi)非常多的時(shí)間。因此我們需要做到：維持最低限度的堆分配，并且永不在緊湊循環(huán)中使用堆分配。

當(dāng)然多數(shù)游戲引擎會(huì)實(shí)現(xiàn)一個(gè)或多個(gè)定制分配器。

基于堆棧的分配器

分配一大塊連續(xù)內(nèi)存，再安排一個(gè)指針指向堆棧的頂端，指針以下的內(nèi)存是已分配的，以上的內(nèi)存是未分配的，對(duì)于分配需求，只是移動(dòng)指針位置即可。注意，這個(gè)模式下必須是以請(qǐng)求內(nèi)存時(shí)的相反次序來(lái)釋放內(nèi)存。

當(dāng)然有個(gè)高階分配技巧，即雙端堆棧分配器，由兩個(gè)指針進(jìn)行管理，一個(gè)從內(nèi)存底端向上分配，一個(gè)從內(nèi)存頂端向下分配。有個(gè)使用案例即是底堆棧用來(lái)加載和卸載游戲關(guān)卡，頂堆棧用來(lái)分配臨時(shí)內(nèi)存塊，這些臨時(shí)內(nèi)存塊會(huì)頻繁被分配/釋放，此舉可保證不會(huì)產(chǎn)生內(nèi)存碎片問(wèn)題。

池分配器

預(yù)分配一大塊內(nèi)存，大小剛好是分配元素的大小的倍數(shù)。池內(nèi)每個(gè)元素被加到一個(gè)存放自由元素的單鏈中，分配的時(shí)候從鏈表中取出一個(gè)來(lái)用，釋放的時(shí)候再返回鏈表即可。分配和釋放都是O(1)。

含對(duì)齊功能的分配器

分配內(nèi)存時(shí)，分配比請(qǐng)求多一點(diǎn)的內(nèi)存，再向上調(diào)整其內(nèi)存地址至適當(dāng)?shù)膶?duì)齊，最后傳回調(diào)整后的地址。大多數(shù)實(shí)現(xiàn)里，額外分配的字節(jié)等于對(duì)齊字節(jié)。

單幀和雙緩沖分配器

單幀分配器即是預(yù)留一塊內(nèi)存用作簡(jiǎn)單堆棧分配管理器，每段重復(fù)地做著以下工作：每幀開(kāi)始時(shí)，把堆棧的頂端指針重置到內(nèi)存塊底端地址，用于這一幀的分配需求。指針只在目前的幀里使用，分配器每幀會(huì)自動(dòng)清除所有內(nèi)存。

雙緩沖分配器即是兩個(gè)單幀分配器循環(huán)交替使用，用以在第i+2幀之前仍能處理第i幀的結(jié)果，防止數(shù)據(jù)被重寫(xiě)。

內(nèi)存碎片

動(dòng)態(tài)堆分配會(huì)產(chǎn)生另一個(gè)問(wèn)題，即是會(huì)隨時(shí)間產(chǎn)生內(nèi)存碎片。分配次序和釋放次序不一樣、尺寸不一樣的情況隨著時(shí)間愈演愈烈，會(huì)發(fā)現(xiàn)自由區(qū)域被切成無(wú)數(shù)個(gè)相對(duì)很小的“洞”，此為內(nèi)存碎片。會(huì)導(dǎo)致就算有足夠的自由內(nèi)存，分配請(qǐng)求也仍然可能會(huì)失敗。

可以使用虛擬內(nèi)存技術(shù)，即把不連續(xù)的物理內(nèi)存塊映射至虛擬地址空間，使它看上去是連續(xù)的。

當(dāng)然可以使用上述說(shuō)的堆棧分配器和池分配器解決問(wèn)題，前者分配和釋放后剩下的內(nèi)存塊總是連續(xù)的，而后者因?yàn)槊科瑑?nèi)存都是完全一樣大的，所以釋放和使用都不會(huì)因?yàn)槿狈ψ銐虼蟮倪B續(xù)內(nèi)存塊。

我們也可以對(duì)堆定期進(jìn)行碎片整理，也就是把“洞”從低地址移向高地址，所有可用堆內(nèi)存空間沉到底端。但那些原先指向已分配的內(nèi)存塊的指針就會(huì)失效，于是引出一個(gè)新概念：指針重定位，即碎片整理后指針重新指向正確的位置?？梢允褂?strong>智能指針或者句柄來(lái)完成這項(xiàng)工作。

智能指針是一個(gè)類(lèi)，可以編寫(xiě)代碼正確處理內(nèi)存重定位，其中一個(gè)方法即是把自身加進(jìn)全局鏈表中，移動(dòng)內(nèi)存后通知全局鏈表掃描并找到那些指向相關(guān)內(nèi)存的智能指針去更新他們的指向。

句柄通常實(shí)現(xiàn)為索引，這些索引指向表內(nèi)的元素，元素存儲(chǔ)指針。句柄表本身不能被重定位。移動(dòng)內(nèi)存塊時(shí)，掃描整個(gè)句柄表并更新指針。

重定位另一個(gè)問(wèn)題就是有些內(nèi)存不能被重定位，有一個(gè)方法是讓這些內(nèi)存置于特別緩沖區(qū)中，這緩沖區(qū)在可重定位內(nèi)存的范圍之外。另一個(gè)方法是這些內(nèi)存塊直接不能被重定位。

碎片整理通常很慢，我們可以把碎片整理成本分?jǐn)傊炼鄠€(gè)幀，每幀進(jìn)行N（很?。┐蝺?nèi)存塊移動(dòng)。只要分配及釋放的次數(shù)低于碎片整理的移動(dòng)次數(shù)，那么堆就會(huì)經(jīng)常保持接近完全整理的狀態(tài)。如果是重定位非常大的內(nèi)存塊，可以把它切分成兩個(gè)或更多的小塊進(jìn)行重定位。

容器

動(dòng)態(tài)數(shù)組

數(shù)組大小不能編譯時(shí)期決定時(shí)，常用鏈表或者動(dòng)態(tài)數(shù)組來(lái)代替。動(dòng)態(tài)數(shù)組的簡(jiǎn)單使用技巧即是在開(kāi)始時(shí)分配n個(gè)元素緩沖區(qū)，當(dāng)已含有n個(gè)元素并想再次擴(kuò)大時(shí)，則創(chuàng)建一個(gè)更大的緩沖區(qū)（可以翻倍當(dāng)前大小，也可以只加n個(gè)元素的大?。?，將原緩沖區(qū)內(nèi)的元素移動(dòng)到新緩沖區(qū)并釋放原緩沖區(qū)。

鏈表

鏈表的每個(gè)元素都有指針指向下一個(gè)節(jié)點(diǎn)，在雙向鏈表中，每個(gè)元素還有指針指向上一個(gè)節(jié)點(diǎn)。分為兩種數(shù)據(jù)結(jié)構(gòu)形式。

外露式表是一種鏈表，其節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)完全和元素的數(shù)據(jù)結(jié)構(gòu)分離，每個(gè)節(jié)點(diǎn)含指針指向元素（類(lèi)似于編程課上那種最簡(jiǎn)單形式的，數(shù)據(jù)結(jié)構(gòu)內(nèi)部維護(hù)一個(gè)指針）。

侵入式表是另一種鏈表，數(shù)據(jù)結(jié)構(gòu)被嵌進(jìn)目標(biāo)元素本身。

循環(huán)鏈表里，真正的首個(gè)節(jié)點(diǎn)的prev指針和真正的最后節(jié)點(diǎn)的next指針可指向同一個(gè)root節(jié)點(diǎn)。有時(shí)候還會(huì)包括頭尾指針這兩個(gè)屬性變量用來(lái)存儲(chǔ)頭部和尾部節(jié)點(diǎn)。這樣設(shè)計(jì)可以非常快檢測(cè)節(jié)點(diǎn)是否屬于鏈表（任何一個(gè)節(jié)點(diǎn)在循環(huán)鏈表里都有prev指針指向和next指針指向）。

在大學(xué)里學(xué)到的鏈表概念默認(rèn)是單向鏈表，單向鏈表的劣勢(shì)是移除某個(gè)特定節(jié)點(diǎn)時(shí)因?yàn)闆](méi)有存儲(chǔ)prev節(jié)點(diǎn)，所以刪除時(shí)要遍歷整個(gè)鏈表并找到前一個(gè)節(jié)點(diǎn)才能移除，相當(dāng)于O(n)操作，而雙向鏈表僅需O(1)。它的最大缺點(diǎn)還在于不能高效的逆向遍歷。如果僅是?；蛘哧?duì)列需求，那么可以采用單向鏈表來(lái)節(jié)省一些內(nèi)存。

字典和散列表

字典是由鍵值對(duì)組成的表，通過(guò)字典能快速用鍵找到對(duì)應(yīng)的值。通常實(shí)現(xiàn)方式是二叉查找樹(shù)或者散列，只不過(guò)前者所需復(fù)雜度是O(logn)而后者是O(1)。

散列表的實(shí)現(xiàn)就是所有值存在固定大小的表里，表的每個(gè)位置表示1個(gè)或多個(gè)鍵。插入鍵值對(duì)時(shí)把鍵轉(zhuǎn)換為整數(shù)（不同類(lèi)型有不同映射整數(shù)的方式，比如str可以映射ascii碼，浮點(diǎn)數(shù)可以按照32位模式轉(zhuǎn)換為32位整數(shù)），再把整數(shù)除表的大小就能獲得表的索引。如果兩個(gè)或以上的鍵會(huì)占用散列表的同一位置，即索引是一樣的，這種情況稱(chēng)之為碰撞，對(duì)此有兩種解決方式：

開(kāi)放式散列里，多個(gè)相同的鍵會(huì)以鏈表形式存儲(chǔ)，容易實(shí)現(xiàn)，但是每次在相同的索引中插入鍵值對(duì)都需要?jiǎng)討B(tài)分配內(nèi)存。

閉合式散列里，會(huì)進(jìn)行探查過(guò)程，在附近或者通過(guò)其他巡查規(guī)律來(lái)找到下一個(gè)鍵值對(duì)位置。比較難實(shí)現(xiàn)，而且必須要設(shè)定表的鍵值對(duì)數(shù)目上限，好處是建立之后不用再動(dòng)態(tài)分配內(nèi)存。

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-793321.html

到了這里，關(guān)于游戲引擎架構(gòu)-游戲支持的系統(tǒng)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！