{"id":138,"date":"2024-04-16T18:46:00","date_gmt":"2024-04-16T18:46:00","guid":{"rendered":"https:\/\/permutationcity.co.uk\/bp\/?p=138"},"modified":"2024-07-27T08:52:41","modified_gmt":"2024-07-27T08:52:41","slug":"game-programming-patterns","status":"publish","type":"post","link":"https:\/\/permutationcity.co.uk\/bp\/2024\/04\/16\/game-programming-patterns\/","title":{"rendered":"Game Programming Patterns"},"content":{"rendered":"\n<p>I wanted to cleanse my palette and decided to read <a href=\"https:\/\/gameprogrammingpatterns.com\/\">Game Programming Patterns<\/a>\nby Robert Nystrom.\nI&#8217;ve read it before so I knew what to expect.\nIt&#8217;s a clearly written pattern book with simple example situation taken from the games industry.\nDon&#8217;t expect to get all the patterns here or advanced game programming knowledge.\nHowever if you want to get a general introduction for patterns before you read\n<a href=\"https:\/\/en.wikipedia.org\/wiki\/Design_Patterns\">something bigger<\/a> then this is great.\nSimilarly if you want to write games but your spaghetti code is getting out of hand then this could be a lifeline.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"design-patterns\">Design patterns<\/h2>\n\n\n\n<p>Algorithms are often likened to recipes, a series of precise instructions.\nFollowing the instructions in a recipe takes ingredients and turns them into food.\nFollowing the instructions in an algorithm can, say, take an unsorted list of values and turn it into a sorted list.\nLibraries can often offer specific algorithms pre-packaged for easy use.<\/p>\n\n\n\n<p>Design patterns are normally less precise, more a list of expected features than a proscription on how to do them.\nSo less a recipe and more a style of cooking or a set of ingredients to use.\nLibraries might offer tools to help but it&#8217;s more often about recreating the pattern in your own code.<\/p>\n\n\n\n<p>I don&#8217;t really think about named design patterns or plan my projects around them but I still use them all the time.\nFor me a <a href=\"https:\/\/en.wikipedia.org\/wiki\/Builder_pattern\">Builder<\/a> is a classic example of this.\nYou could try to manually construct a complicated object.\nHowever that can be require in-depth knowledge to do correctly or\ntransform the object through a series of intermediate states.\nIt can be safer and easier to encapsulate the construction within a builder.\nThis can collect the information necessary for construction and then, in one go, produce the object.\nI don&#8217;t think &#8220;Let me use the builder pattern.&#8221;\nI think &#8220;Having a <code>CommandLineBuilder<\/code> means I don&#8217;t have to worry about escaping arguments with spaces.&#8221;<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"presentation\">Presentation<\/h2>\n\n\n\n<p>Each section of the book covers a number of associated patterns.\nEach pattern gets one or two examples to get you familiar with them.\nThen there&#8217;s a discussion about the pros and cons of different variations of the pattern.\nFor games the balance is normally between the flexibility of the system and the performance it provides.\nReally this is exactly what I&#8217;m writing about for balance programming.\nHaving everything isn&#8217;t normally possible so how do you go about picking what&#8217;s best for your situation.<\/p>\n\n\n\n<p>The sample code is really simple, sticking to straight C.\nI might have preferred something more modern but he&#8217;s made it accessible to everyone.\nI understand the choice.\nYou&#8217;ll have to translate the examples into your preferred language.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"content-overview\">Content overview<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Design Patterns Revisited\n<ul class=\"wp-block-list\">\n<li>Command: A reified method call, configuring input controls plus undo-redo.<\/li>\n\n\n\n<li>Observer: Achievements, I&#8217;ll talk about this later.<\/li>\n\n\n\n<li>Flyweight: A light weight placeholder, a forest of trees and terrain grids.<\/li>\n\n\n\n<li>Prototype: Cloning an original, monster spawners and inheritance.<\/li>\n\n\n\n<li>Singleton: A potentially dangerous singular global service.<\/li>\n\n\n\n<li>State: Changing behaviour, finite state machines and variations.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Sequencing Patterns\n<ul class=\"wp-block-list\">\n<li>Double Buffer: Dealing with simultaneous access, rendering and state changes.<\/li>\n\n\n\n<li>Game Loop: Running the game, separating rendering and physics.<\/li>\n\n\n\n<li>Update Method: Simulating many objects, movement and combat.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Behavioural Patterns\n<ul class=\"wp-block-list\">\n<li>Bytecode: Virtual machines for complex behaviours, building magic spells.<\/li>\n\n\n\n<li>Subclass Sandbox: Separating classes from the environment they need to interact with.<\/li>\n\n\n\n<li>Type Object: Different monsters without different classes of monster.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Decoupling Patterns\n<ul class=\"wp-block-list\">\n<li>Component: Composing behaviours from individual components, avoiding duplication and multiple inheritance.<\/li>\n\n\n\n<li>Event Queue: Separating requests from fulfilling those requests.<\/li>\n\n\n\n<li>Service Locator: Swapping out one system for another, plus null and logging services.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Optimization Patterns\n<ul class=\"wp-block-list\">\n<li>Data Locality: High performance by organising your data. Better than the <a href=\"https:\/\/permutationcity.co.uk\/bp\/2024\/04\/09\/data-oriented-design\/\">last book<\/a> that covered it.<\/li>\n\n\n\n<li>Dirty Flag: One bit to skip a lot of recalculation, fewer matrix multiplies.<\/li>\n\n\n\n<li>Object Pool: Controlling object creation and avoiding fragmentation.<\/li>\n\n\n\n<li>Spatial Partition: Divide and conquer space for faster processing.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"implementing-achievements\">Implementing Achievements<\/h2>\n\n\n\n<p>I think an achievement system might be one of the best examples of avoiding spaghetti code. An achievement could be practically anything:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Killing a specific number of giant rats.<\/li>\n\n\n\n<li>Finding all four quarters of the treasure map.<\/li>\n\n\n\n<li>Surviving 10 nights outside the city.<\/li>\n\n\n\n<li>Dying in an explosion that you caused.<\/li>\n\n\n\n<li>Playing for 24 hours of real time.<\/li>\n<\/ul>\n\n\n\n<p>A naive implementation might have calls to the achievement system everywhere in your codebase. So physics, rendering, collision detection, inventory management, the weather system, it could go on and on. Every time the designer comes up with a new achievement the developers would have to rewire things. If the interface to the achievement system ever change then <em>everything<\/em> connected to it would also change. This can work on a <em>small<\/em> scale but sounds like a nightmare on a large scale. You don&#8217;t want to write a quick hack and then gradually find it growing until you are living that nightmare.<\/p>\n\n\n\n<p>One solution to this is the Observer pattern.\nIt allows one piece of code to announce something is happening <em>without caring about who is listening<\/em>.\nThere might be no-one listening, there might be a dozens of other systems listening.<\/p>\n\n\n\n<p>This is classically done with an <code>Observer<\/code> and a <code>Subject<\/code> but I might use <code>Observer<\/code> and <code>Observed<\/code> instead:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;showPanel&quot;:true,&quot;languageLabel&quot;:&quot;language&quot;,&quot;fullScreenButton&quot;:true,&quot;copyButton&quot;:true,&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-c++src&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:false,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:true,&quot;readOnly&quot;:true,&quot;fileName&quot;:&quot;C++&quot;,&quot;language&quot;:&quot;C++&quot;,&quot;maxHeight&quot;:&quot;400px&quot;,&quot;modeName&quot;:&quot;cpp&quot;}\">class Observed {\n    void Add(Observer&amp; observer) {\n        m_Observers.push_back(&amp;observer);\n    }\n\n    void Remove(Observer&amp; observer) {\n        std::erase(m_Observers, observer);\n    }\n\n    void Notify(const Entity&amp; entity, Event event) {\n        for (const auto observer : m_Observers) {\n            observer-&gt;OnNotify(entity, event);\n        }\n    }\n\nprivate:\n    std::vector&lt;Observer*&gt; m_Observers;\n};\n\nclass Observer {\npublic:\n    virtual void OnNotify(const Entity&amp; entity, Event event) = 0;\n};<\/pre><\/div>\n\n\n\n<p>Dead simple. So in our achievement system example we would make our <code>AchievementManager<\/code> an <code>Observer<\/code> and\nvarious game subsystems would be <code>Observed<\/code>.<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;showPanel&quot;:true,&quot;languageLabel&quot;:&quot;language&quot;,&quot;fullScreenButton&quot;:true,&quot;copyButton&quot;:true,&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-c++src&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:false,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:true,&quot;readOnly&quot;:true,&quot;fileName&quot;:&quot;C++&quot;,&quot;language&quot;:&quot;C++&quot;,&quot;maxHeight&quot;:&quot;400px&quot;,&quot;modeName&quot;:&quot;cpp&quot;}\">class AchievementManager: public Observer {\n...\n    void Register() {\n        Get&lt;MonsterManager&gt;().Add(*this);\n        Get&lt;InventoryManager&gt;().Add(*this);\n        Get&lt;MapManager&gt;().Add(*this);\n        Get&lt;TimeManager&gt;().Add(*this);\n    }\n\n    void OnNotify(const Entity&amp; entity, Event event) override {\n        switch (event) {\n        case DEATH:\n            if (entity.IsSpecies(&quot;giant rat&quot;)) {\n                ...\n            }\n            else if (entity.IsPlayer()) {\n                ...\n            }\n        }\n    }\n...\n};<\/pre><\/div>\n\n\n\n<p>I think this is still a bit rough and ready.\nEach manager is an <code>Observed<\/code> class and so has to distinguish any action entirely based on the <code>Entity<\/code> and <code>Event<\/code>.\nThis means it a lot of messages might get sent only to be ignored at the other end.\nIt might be better to have each manager contain a number of <code>Observed<\/code> objects.\nThat way the <code>AchievementManager<\/code> can pick and choose what it is really interested in:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;showPanel&quot;:true,&quot;languageLabel&quot;:&quot;language&quot;,&quot;fullScreenButton&quot;:true,&quot;copyButton&quot;:true,&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-c++src&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:false,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:true,&quot;readOnly&quot;:true,&quot;fileName&quot;:&quot;C++&quot;,&quot;language&quot;:&quot;C++&quot;,&quot;maxHeight&quot;:&quot;400px&quot;,&quot;modeName&quot;:&quot;cpp&quot;}\">class MonsterManager {\n...\n    Observed&amp; Spawn;\n    Observed&amp; Arrive;\n    Observed&amp; Summon;\n    Observed&amp; Damage;\n    Observed&amp; Death;\n    Observed&amp; Despawn;\n...\n};<\/pre><\/div>\n\n\n\n<p>This pattern is very flexible and open to extension.\nIf, say, you want the <code>SaveManager<\/code> to auto-save after a boss is killed then\nnothing has to change in <code>MonsterManager<\/code>, just add in another registration.<\/p>\n\n\n\n<p>The book covers some perceived problems with this pattern:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>It could slow things down: The overhead of sending is low although you have to make sure observers don&#8217;t take too long. Keep it out of the tightest of loops but it should be okay otherwise.<\/li>\n\n\n\n<li>It could be too fast: Notifications are sent immediately and if threads are involved this could complicate things. You might need to involve an Event Queue.<\/li>\n\n\n\n<li>It allocates memory: Excessive memory allocation can fragment the heap in games. If this is a problem then pre-allocating more space or using a list based approach is an option.<\/li>\n\n\n\n<li>Destroying objects: If an <code>Observer<\/code> is destroyed then the <code>Observer<\/code> needs to be updated. This can be done manually although it can need some care or<br>the association can be made two-way so that objects are automatically unregistered. If it&#8217;s done wrong then you can end up with zombie observers forever taking up processing.<\/li>\n\n\n\n<li>More complex debugging: Although the pattern stops systems from knowing about each other they are still interacting. If something is going wrong it can be much less obvious what system is responsible.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">On balance<\/h2>\n\n\n\n<p>If any of this sounds remotely interesting I&#8217;d highly recommend giving this a read. It&#8217;s inspired me to put another pattern book on my list but I doubt it will be as nice as this one.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I wanted to cleanse my palette and decided to read Game Programming Patterns by Robert Nystrom. I&#8217;ve read it before so I knew what to expect. It&#8217;s a clearly written pattern book with simple example situation taken from the games industry. Don&#8217;t expect to get all the patterns here or advanced game programming knowledge. However [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","footnotes":""},"categories":[34],"tags":[20,16],"class_list":["post-138","post","type-post","status-publish","format-standard","hentry","category-review","tag-books","tag-methodologies"],"_links":{"self":[{"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/posts\/138","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/comments?post=138"}],"version-history":[{"count":5,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/posts\/138\/revisions"}],"predecessor-version":[{"id":198,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/posts\/138\/revisions\/198"}],"wp:attachment":[{"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/media?parent=138"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/categories?post=138"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/tags?post=138"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}