BSH

[翻譯] Evolve Your Hierarchy


Evolve Your Hierarchy ( 2007 )
By Mick West
http://cowboyprogramming.com/2007/01/05/evolve-your-heirachy/

元件式的重構
Evolve Your Hierarchy
By Mick West

Refactoring Game Entities with Components
用元件來重構遊戲實體

Up until fairly recent years, game programmers have consistently used a deep class hierarchy to represent game entities. The tide is beginning to shift from this use of deep hierarchies to a variety of methods that compose a game entity object as an aggregation of components. This article explains what this means, and explores some of the benefits and practical considerations of such an approach. I will describe my personal experience in implementing this system on a large code base, including how to sell the idea to other programmers and management.
時至今日,遊戲程式設計者往往使用深度的繼承來表達遊戲實體(譯按我喜歡稱作game object)。"趨勢"漸漸轉換為以各種方式把這個實體物件包裝為元件的集成。本篇文章就是在討論這個方法,以及他的好處跟實際面。這篇文章還會描述個人實作這種系統的經歷,包含如何推銷這個想法給其他程式設計者與管理階層。

GAME ENTITIES

遊戲實體

Different games have different requirements as to what is needed in a game entity, but in most games the concept of a game entity is quite similar. A game entity is some object that exists in the game world, usually the object is visible to the player, and usually it can move around.
在不同的遊戲中遊戲實體可以有不同的需求,但是概念上是類似的。遊戲實體就是存在於遊戲世界的某一個物件,通常可以被玩家看到,也通常可以移動。

(略)
如清單所述遊戲實體可以包含:飛彈,車輛,坦克,手榴彈,槍枝,英雄,行人,外星人,鋼鐵人飛行裝,醫療裝備,石頭。

(略)
遊戲實體可以有以下的功能:執行script,移動,被物理引擎推動,發出粒子,發出區域音效,被玩家拾取,被玩家損害,爆炸,磁力反應,被玩家瞄準,跟隨路徑,播放動畫。

TRADITIONAL DEEP HIERARCHIES

傳統的深度繼承

The traditional way of representing a set of game entities like this is to perform an object-oriented decomposition of the set of entities we want to represent. This usually starts out with good intentions, but is frequently modified as the game development progresses – particularly if a game engine is re-used for a different game. We usually end up with something like figure 1, but with a far greater number of nodes in the class hierarchy.
傳統表示遊戲實體集合的方式大多遵循物件導向分解的概念。概念上一開始都是好意。但是隨著遊戲繼續開發或是把就程式想辦法套到新遊戲上的時候,就會發現問題。這個傳統方式通常會變成像圖1一樣,有著大量數目的類別繼承。

As development progresses, we usually need to add various points of functionality to the entities. The objects must either encapsulate the functionality themselves, or be derived from an object that includes that functionality. Often, the functionality is added to the class hierarchy at some level near the root, such as the CEntity class. This has the benefit of the functionality being available to all derived classes, but has the downside of the associated overhead also being carried by those classes.
隨著開發進行,我們通常會增加很多的功能到這些實體上,要不是直接裝到這些物件上,就是要從其他物件那邊繼承這些功能過來。通常這些功能是在接近root的地方,好處是大家都能共享這個功能。但是在底層的新物件就會被層層這些重擔所包覆。

Even fairly simple objects such as rocks or grenades can end up with a large amount of additional functionality (and associated member variables, and possibly unnecessary execution of member functions). Often, the traditional game object hierarchy ends up creating the type of object known as “the blob". The blob is a classic “anti-pattern" which manifests as a huge single class (or a specific branch of a class hierarchy) with a large amount of complex interwoven functionality.
即便是石頭或是手榴彈這種簡單物件都會有一卡車繼承而來的函式跟無關緊要的變數。通常我們把這種情況叫做blob(像一團的大型物件)。這種blob通常不是一個好的設計模式,因為他代表了一個巨大的單一類別或是繼承的集合,包含了一堆交雜的函式。

While the blob anti-pattern often shows up near the root of the object hierarchy, it will also show up in leaf nodes. The most likely candidate for this is the class representing the player character. Since the game is usually programmed around a single character, then the object representing that character often has a very large amount of functionality. Frequently this is implemented as a large number of member functions in a class such as CPlayer.
這種blob不只會出現在繼承的根部(root),也會出現在繼承的底部(leaf)。最常見的這種blob就是玩家人物物件,因為我們的遊戲都是圍繞著玩家角色來進行。所以通常被命名為CPlayer的玩家人物物件就有一卡車函式。

The result of implementing functionality near the root of the hierarchy is an overburdening of the leaf objects with unneeded functionality. However, the opposite method of implementing the functionality in the leaf nodes can also have unfortunate consequence. Functionality now becomes compartmentalized, so that only the objects specifically programmed for that particular functionality can use it. Programmers often duplicate code to mirror functionality already implemented in a different object. Eventually messy re-factoring is required by re-structuring the class hierarchy to move and combine functionality.
在根部出現的這種blob就會導致底部的物件有很多無用處的函式。然而若是把這些函式實做在底部物件,卻又會發生功能無法透過繼承共享的現象(導致再不同的底部物件中重複作相同的功能)。最後就會發生必須重構的情況發生。

Take for example the functionality of having an object react under physics as a rigid body. Not every object needs to be able to do this. As you can see in figure 1, we just have the CRock and the CGrenade classes derived from CRigid. What happens when we want to apply this functionality to the vehicles? You have to move the CRigid class further up the hierarchy, making it more and more like the root-heavy blob pattern we saw before, with all the functionality bunched in a narrow chain of classes from which most other entity classes are derived.
舉例來說,若是有一個會受到物理引擎影響的固體類別(CRigid),繼承之後變成石頭或手榴彈。若是現在要加一個車輛物件到這個CRigid的繼承樹上時就會變得這個CRigid必須往繼承的根部移動,讓他有更多能夠包含車輛使用的功能。慢慢地他就變成所謂的blob。

AN AGGREGATION OF COMPONENTS

元件的集成

The component approach, which is gaining more acceptance in current game development, is one of separating the functionality into individual components that are mostly independent of one another. The traditional object hierarchy is dispensed with, and an object is now created as an aggregation (a collection) of independent components.
元件的方式慢慢被遊戲開發所接受,是一種把功能區別變成單一互相獨立元件的方法。傳統的繼承被揚棄,物件變成一個元件的集成。

Each object now only has the functionality that it needs. Any distinct new functionality is implemented by adding a component.
每個物件只有他所需要的功能,每個新功能就只需實做成一個元件。

A system of forming an object from aggregating components can be implemented in one of three ways, which may be viewed as separate stages in moving from a blob object hierarchy to a composite object.
若是要把一個已經成為blob的繼承系統變成元件式的系統,我們可以用三種方法來進行重構。

OBJECT AS ORGANIZED BLOB

組織過的blob

A common way of re-factoring a blob object is to break out the functionality of that object into sub-objects, which are then referenced by the first object. Eventually the parent blob object can mostly be replaced by a series of pointers to other objects, and the blob object’s member functions become interface functions for the functions of those sub-objects.
最常見的重構blob物件的方式就是把這些物件依照功能分成小的物件,然後被原來的物件所使用。最終這個blob就可以被一堆指到其他小物件的指標所取代。這個blob的物件就變成一個使用其他小物件功能的介面(interface)。

This may actually be a reasonable solution if the amount of functionality in your game objects is reasonably small, or if time is limited. You can implement arbitrary object aggregation simply by allowing some of the sub-objects to be absent (by having a NULL pointer to them). Assuming there are not too many sub-objects, then this still allows you the advantage of having lightweight pseudo-composite objects without having to implement a framework for managing the components of that object.
若是時間有限,或是要重構的物件還算小的時候,這種方法是最合理的方式。這種方式可以隨意的組成你要的物件,尤其是當你不想要某一個功能的時候,就把那個小物件的指標設為NULL即可。甚至不用實做整個管理物件的系統,很快的就可以建立一個虛擬的組合物件出來。

The downside is that this is still essentially a blob. All the functionality is still encapsulated within one large object. It is unlikely you will fully factor the blob into purely sub-objects, so you will still be left with some significant overhead, which will weight down your lightweight objects. You still have the overhead of constantly checking all the NULL pointers to see if they need updating.
但是實際上這仍是一個所有功能都被包住的blob。只是你必須用是否為NULL的方式檢查那些功能有沒有裝進來。

OBJECT AS COMPONENT CONTAINER

元件的容器

The next stage is to factor out each of the components (the “sub-objects" in the previous example) into objects that share a common base class, so we can store a list of components inside of an object.
下一步就是打造每一個元件(先前說的小物件)為繼承一個共通基底的物件,然後我們就可以在物件裡面用一個串列把他用得到的元件都串起來。

This is an intermediate solution, as we still have the root “object" that represents the game entity. However, it may be a reasonable solution, or indeed the only practical solution, if a large part of the code base requires this notion of a game object as a concrete object.
這是一個中間層的解法,我們仍有一個根部的物件來衍生我們的遊戲實體。但這可能是唯一有用且合理的解決方案。

Your game object then becomes an interface object that acts as a bridge between the legacy code in your game, and the new system of composite objects. As time permits, you will eventually remove the notion of game entity as being a monolithic object, and instead address the object more and more directly via its components. Eventually you may be able to transition to a pure aggregation.
我們的遊戲物件就會變成一個介於原本程式與新的組合元件的介面。只要時間允許,最終就會移除這一個原本是龐大整塊的遊戲實體,變為使用這個物件透過他的元件。然後就可以轉為一個單純的集合體(pure aggregation)。

OBJECT AS A PURE AGGREGATION

單純的集合體

In this final arrangement, an object is simply the sum of its parts. Figure 2 shows a scheme where each game entity is comprised of a collection of components. There is no “game entity object" as such. Each column in the diagram represents a list of identical components, each row can be though of as representing an objects. The components themselves can be treated as being independent of the objects they make up.
最後的佈置會像這樣,一個物件就是他元件的總和。圖2展示了一個每一個遊戲實體是由元件組成的結構。沒有所謂遊戲實體物件這樣的東西,每一欄都表示了單一的元件,每一列表示獨立的物件。元件終於可以獨立於物件之外。

PRACTICAL EXPERIENCE

實際的實做經驗

I first implemented a system of object composition from components when working at Neversoft, on the Tony Hawk series of games. Our game object system had developed over the course of three successive games until we had a game object hierarchy that resembled the blob anti-pattern I described earlier. It suffered from all the same problems: the objects tended to be heavyweight. Objects had unnecessary data and functionality. Sometimes the unnecessary functionality slowed down the game. Functionality was sometimes duplicated in different branches of the tree.
作者在Neversoft的Tony Hawk遊戲系列中實做了一個元件集合的系統。在那之前專案已經延續了三代的遊戲,年代久遠的繼承架構就變成先前提到的blob。造成那些令人困擾的問題:物件很大;物件有不相關的資料與功能;不相關的功能減緩遊戲執行的速度;功能重複的在不同的繼承樹上被實做。

I had heard about this new-fangled “component based objects" system on the sweng-gamedev mailing list, and decided it sounded like a very good idea. I set to re-organizing the code-base and two years later, it was done.
作者那時在sweng-gamedev新聞群組聽到了這種新奇的元件式的物件系統,因此花了兩年去重新組織這個程式。

Why so long? Well, firstly we were churning out Tony Hawk games at the rate of one per year, so there was little time between games to devote to re-factoring. Secondly, I miscalculated the scale of the problem. A three-year old code-base contains a lot of code. A lot of that code became somewhat inflexible over the years. Since the code relied on the game objects being game objects, and very particular game objects at that, it proved to be a lot of work to make everything work as components.
為什麼花了這麼長的時間才完成?首先Tony Hawk遊戲系列進入每年一款的量產,以至於每次都只有一點時間來作重構。第二,錯估了這個問題的大小。一個跑了三年的程式基底包含了一堆不彈性的程式碼,每個物件都很獨特,難以解構。

EXPECT RESISTANCE

碰到抗拒

The first problem I encountered was in trying to explain the system to other programmers. If you are not particularly familiar with the idea of object composition and aggregation, then it can strike you as pointless, needlessly complex, and unnecessary extra work. Programmers who have worked with the traditional system of object hierarchies for many years become very used to working that way. They even become very good at working that way, and manage to work around the problems as they arise.
第一個作者碰到的問題就是如何說服這個系統給其他的程式設計人員。假如用不是很熟這個物件組合與集成的問題的態度去說服其他人,通常會終結於沒有意義;不需要這麼複雜;不想增加其他工作等回應。程式設計師已經很習慣於傳統的繼承寫作方式。甚至很用的很好。

Selling the idea to management is also a difficult. You need to be able to explain in plain words exactly how this is going to help get the game done faster. Something along the lines of:

“Whenever we add new stuff to the game now, it takes a long time to do, and there are lots of bugs. If we do this new component object thing, it will let us add new stuff a lot quicker, and have fewer bugs."
推銷這個想法給管理階層也是一個困難。這需要能夠用簡單的文字去表達這樣的新方法是如何能夠加速遊戲的完成,就像這樣說:"每當我們再遊戲中新增一個元素,總是要花很多時間,同時產生很多錯誤。假如我們採用元件式的方式,就會讓我們更快,更少錯誤。"

My approach was to introduce it in a stealth manner. I first discussed the idea with a couple of programmers individually, and eventually convinced them it was a good idea. I then implemented the basic framework for generic components, and implemented one small aspect of game object functionality as a component.
作者推銷的作法是採用低調的作法。先分別對一些程式設計師閒聊這個想法,說服他們這是個好方法。實做這個架構的基礎工作,且修改一個遊戲物件為元件式作例子。

I then presented this to the rest of the programmers. There was some confusion and resistance, but since it was implemented and working there was not much argument.
然後展示給剩餘的程式設計師,有些人會有疑惑跟抗拒,但既然已經有實做的結果了,就沒有太大的爭論。

SLOW PROGRESS

步調緩慢

Once the framework was established, the conversion from static hierarchy to object composition happened slowly. It is thankless work, since you spend hours and days re-factoring code into something that seems functionally no different to the code it replaces. In addition, we were doing this while still implementing new features for the next iteration of the game.
基礎的架構已經被建立之後,轉換原本的繼承架構為元件集合是的過程卻十分的緩慢。這是份不被感激的工作,因為只是花時間重作那些一樣功能的東西。更糟的是,同時間還在開發下一代遊戲的功能。

At an early point, we hit the problem of re-factoring our largest class, the skater class. Since it contained a vast amount of functionality, it was almost impossible to re-factor a piece at a time. In addition, it could not really be re-factored until the other object systems in the game conformed to the component way of doing things. These in turn could not be cleanly refactored as components unless the skater was also a component.
早期的重點就是解構那個最大的類別-滑板者(skater)。他包含了龐大的功能根本不可能一口氣重構為元件。甚至是必須在其他物件都遵循元件式的架構後才能進行。也就是說skater這個類別要先變成元件式才能重構其他元件。

The solution here was to create a “blob component." This was a single huge component, which encapsulated much of the functionality of the skater class. A few other blob components were required in other places, and we eventually shoehorned the entire object system into a collection of components. Once this was in place, the blob components could gradually be refactored into more atomic components.
解法就是創造一個blob的元件。一個超大的元件,包含了skater的所有功能。當然其他blob也這樣作。最後終於硬塞了整個物件系統到這個元件集合裡面。一旦這步驟做完,blob元件就可以被解構為簡單的元件。

RESULTS

結果

The first results of this re-factoring were barely tangible. But over time the code became cleaner and easier to maintain as functionality was encapsulated in discreet components. Programmers began to create new types of object in less time simply by combining a few components and adding a new one.
第一次重構的結果看起來沒有什麼顯著幫助。但是當功能被塞成離散的元件,程式越來越清楚簡單。

We created a system of data-driven object creation, so that entirely new types of object could be created by the designers. This proved invaluable in the speedy creation and configuration of new types of objects.
建立的系統是資料驅動的物件創造系統,因此整個新的物件能夠由設計人員來創造,使得開發速度跟調整變得十分快速。

Eventually the programmers came (at different rates) to embrace the component system, and became very adept at adding new functionality via components. The common interface and the strict encapsulation led to a reduction in bugs, and code that that was easier to read, maintain and re-use.
程式設計人員最終愛上了這種元件系統,也非常適應以元件的方式增加功能。這種設計方式使得錯誤率降低,程式可讀性上升,容易維護與重新使用。

IMPLEMENTATION DETAILS

實作的細節

Giving each component a common interface means deriving from a base class with virtual functions. This introduces some additional overhead. Do not let this turn you against the idea, as the additional overhead is small, compared to the savings due to simplification of objects.
元件有著共通的介面意思是在繼承的基底類別有一些虛擬函式。在建構這部份的時候花了不少精神。但別讓這步驟阻止了重構,因為重構的結果會帶來相對很多在開發上的省力。

Since each component has a common interface, it is very easy to add additional debug member functions to each component. That made it a relatively simple matter to add an object inspector that could dump the contents of the components of a composite object in a human readable manner. Later this would evolve into a sophisticated remote debugging tool that was always up to date with all possible types of game object. This is something that would have been very tiresome to implement and maintain with the traditional hierarchy.
既然元件都是相同介面,當然非常容易增加相同除錯的架構上去。用可讀的方式把資料dump出來看。而且可以與複雜的遠端除錯工具結合,同時保持可以除錯最新的物件類別。若是用繼承的方式是十分難以作到的。

Ideally, components should not know about each other. However, in a practical world, there are always going to be dependencies between specific components. Performance issues also dictate that components should be able to quickly access other components. Initially we had all component references going through the component manager, however when this started using up over 5% of our CPU time, we allowed the components to store pointers to one another, and call member functions in other components directly.
原則上,元件彼此之間應該互相不知道。然而實際應用時,某些元件總是必須相依彼此。效能的考量使得應該要讓元件彼此能夠互相溝通。最初我們透過元件管理器reference住全部的元件,然而這管理器竟然消耗了百分之五的處理時間。因此我們允許元件儲存其他元件的指標直接呼叫成員函式。

The order of composition of the components in an object can be important. In our initial system, we stored the components as a list inside a container object. Each component had an update function, which was called as we iterated over the list of components for each object.
建構元件的順序是重要的,在初始的系統中,我們用串列把元件儲存在容器裡。每一個元件有自己的更新函式,然後走訪串列一起更新他們。

Since the object creation was data driven, it could create problems if the list of components is in an unexpected order. If one object updates physics before animation, and the other updates animation before physics, then they might get out of sync with each other. Dependencies such as this need to be identified, and then enforced in code.
既然物件的創造是由資料所驅動,可能會因為再串列上的順序導致不預期的問題。譬如說某些流程應該比某些流程先更新。這種相依性必須考慮進去。

CONCLUSIONS

結論

Moving from blob style object hierarchies to composite objects made from a collection of components was one of the best decisions I made. The initial results were disappointing as it took a long time to re-factor existing code. However, the end results were well worth it, with lightweight, flexible, robust and re-usable code.
從繼承的blob風格改為元件組合式的方式是作者的成功經驗之一。最初因為花了很多時間所以有點失望。然而最後的結果卻相當值得,輕量,有彈性,通用,又能重複利用。

Resources

其他資源

Scott Bilas: GDC 2002 Presentation: A Data-Driven Game Object System
http://www.drizzle.com/~scottb/gdc/game-objects.htm

Bjarne Rene: Component Based Object Management. Game Programming Gems 5, 2005, page 25.

Kyle Wilson: Game Object Structure: Inheritence vs Aggregation, 2002, http://www.gamearchitect.net/Articles/GameObjects1.html

other reference :

Game Object Structure: Inheritance vs. Aggregation ( 2002 )
By Kyle Wilson
http://www.gamearchitect.net/Articles/GameObjects1.html

Ogre Wiki :
Architecture and Design in Games – A list of various must-read articles
http://www.ogre3d.org/tikiwiki/Architecture+and+Design+in+Games

廣告

3 thoughts on “[翻譯] Evolve Your Hierarchy

  1. Great post ive bookmarked it on Digg under “[翻譯] Evolve Your Hierarchy Black Straits Historical". So hopefully our friends can give you a visit. Keep up the good stuff.

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s