-
Notifications
You must be signed in to change notification settings - Fork 513
Expand file tree
/
Copy pathflyweight.html
More file actions
438 lines (415 loc) · 30.4 KB
/
flyweight.html
File metadata and controls
438 lines (415 loc) · 30.4 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-type" content="text/html;charset=UTF-8" />
<title>Flyweight · Design Patterns Revisited · Game Programming Patterns</title>
<!-- Tell mobile browsers we're optimized for them and they don't need to crop
the viewport. -->
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<link rel="stylesheet" type="text/css" href="style.css" />
<link href="https://fonts.googleapis.com/css?family=Merriweather:400,400italic,700,700italic|Source+Code+Pro|Source+Sans+Pro:200,300,400,600,400italic,600italic|Rock+Salt" rel="stylesheet" type="text/css">
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-42804721-1', 'gameprogrammingpatterns.com');
ga('send', 'pageview');
</script>
<script src="jquery-3.6.0.min.js"></script>
<script src="script.js"></script>
</head>
<body id="top">
<div class="page sidebar">
<span class="theme-toggler" title="dark theme" onclick="toggleTheme()"></span>
<div class="content">
<nav class="top">
<span class="prev">← <a href="command.html">Previous Chapter</a></span>
<span class="next"><a href="observer.html">Next Chapter</a> →</span>
<span class="toc">≡ <a href="/">The Book</a></span>
</nav>
<h1>Flyweight</h1>
<h1 class="book"><a href="/">Game Programming Patterns</a><span class="section"><a href="design-patterns-revisited.html">Design Patterns Revisited</a></span></h1>
<p>The fog lifts, revealing a majestic old growth forest. Ancient hemlocks,
countless in number, tower over you forming a cathedral of greenery. The stained
glass canopy of leaves fragments the sunlight into golden shafts of mist.
Between giant trunks, you can make out the massive forest receding into the
distance.</p>
<p>This is the kind of otherworldly setting we dream of as game developers, and
scenes like these are often enabled by a pattern whose name couldn’t possibly be
more modest: the humble Flyweight.</p>
<h2><a href="#forest-for-the-trees" name="forest-for-the-trees">Forest for the Trees</a></h2>
<p>I can describe a sprawling woodland with just a few sentences, but actually
<em>implementing</em> it in a realtime game is another story. When you’ve got an entire
forest of individual trees filling the screen, all that a graphics programmer
sees is the millions of polygons they’ll have to somehow shovel onto the GPU
every sixtieth of a second.</p>
<p>We’re talking thousands of trees, each with detailed geometry containing
thousands of polygons. Even if you have enough <em>memory</em> to describe that forest,
in order to render it, that data has to make its way over the bus from the CPU
to the GPU.</p>
<p>Each tree has a bunch of bits associated with it:</p>
<ul>
<li>A mesh of polygons that define the shape of the trunk, branches, and greenery.</li>
<li>Textures for the bark and leaves.</li>
<li>Its location and orientation in the forest.</li>
<li>Tuning parameters like size and tint so that each tree looks different.</li>
</ul>
<p>If you were to sketch it out in code, you’d have something like this:</p>
<div class="codehilite"><pre><span></span><code><span class="k">class</span> <span class="nc">Tree</span>
<span class="p">{</span>
<span class="k">private</span><span class="o">:</span>
<span class="n">Mesh</span> <span class="n">mesh_</span><span class="p">;</span>
<span class="n">Texture</span> <span class="n">bark_</span><span class="p">;</span>
<span class="n">Texture</span> <span class="n">leaves_</span><span class="p">;</span>
<span class="n">Vector</span> <span class="n">position_</span><span class="p">;</span>
<span class="kt">double</span> <span class="n">height_</span><span class="p">;</span>
<span class="kt">double</span> <span class="n">thickness_</span><span class="p">;</span>
<span class="n">Color</span> <span class="n">barkTint_</span><span class="p">;</span>
<span class="n">Color</span> <span class="n">leafTint_</span><span class="p">;</span>
<span class="p">};</span>
</code></pre></div>
<p>That’s a lot of data, and the mesh and textures are particularly large. An entire
forest of these objects is too much to throw at the GPU in one frame.
Fortunately, there’s a time-honored trick to handling this.</p>
<p>The key observation is that even though there may be thousands of trees in the
forest, they mostly look similar. They will likely all use the <span
name="same">same</span> mesh and textures. That means most of the fields in
these objects are the <em>same</em> between all of those instances.</p>
<aside name="same">
<p>You’d have to be crazy or a billionaire to budget for the artists to
individually model each tree in an entire forest.</p>
</aside>
<p><span name="trees"></span></p>
<p><img src="images/flyweight-trees.png" alt="A row of trees, each of which has its own Mesh, Bark, Leaves, Params, and Position." /></p>
<aside name="trees">
<p>Note that the stuff in the small boxes is the same for each tree.</p>
</aside>
<p>We can model that explicitly by splitting the object in half. First, we pull
out the data that all trees have <span name="type">in common</span> and move it
into a separate class:</p>
<div class="codehilite"><pre><span></span><code><span class="k">class</span> <span class="nc">TreeModel</span>
<span class="p">{</span>
<span class="k">private</span><span class="o">:</span>
<span class="n">Mesh</span> <span class="n">mesh_</span><span class="p">;</span>
<span class="n">Texture</span> <span class="n">bark_</span><span class="p">;</span>
<span class="n">Texture</span> <span class="n">leaves_</span><span class="p">;</span>
<span class="p">};</span>
</code></pre></div>
<p>The game only needs a single one of these, since there’s no reason to have the
same meshes and textures in memory a thousand times. Then, each <em>instance</em> of a
tree in the world has a <em>reference</em> to that shared <code>TreeModel</code>. What remains in
<code>Tree</code> is the state that is instance-specific:</p>
<div class="codehilite"><pre><span></span><code><span class="k">class</span> <span class="nc">Tree</span>
<span class="p">{</span>
<span class="k">private</span><span class="o">:</span>
<span class="n">TreeModel</span><span class="o">*</span> <span class="n">model_</span><span class="p">;</span>
<span class="n">Vector</span> <span class="n">position_</span><span class="p">;</span>
<span class="kt">double</span> <span class="n">height_</span><span class="p">;</span>
<span class="kt">double</span> <span class="n">thickness_</span><span class="p">;</span>
<span class="n">Color</span> <span class="n">barkTint_</span><span class="p">;</span>
<span class="n">Color</span> <span class="n">leafTint_</span><span class="p">;</span>
<span class="p">};</span>
</code></pre></div>
<p>You can visualize it like this:</p>
<p><img src="images/flyweight-tree-model.png" alt="A row of trees each with its own Params and Position, but pointing to a shared Model with a Mesh, Bark, and Leaves." /></p>
<aside name="type">
<p>This looks a lot like the <a href="type-object.html" class="pattern">Type
Object</a> pattern. Both involve delegating part of an object’s state to some
other object shared between a number of instances. However, the intent behind
the patterns differs.</p>
<p>With a type object, the goal is to minimize the number of classes you have to
define by lifting “types” into your own object model. Any memory sharing you get
from that is a bonus. The Flyweight pattern is purely about efficiency.</p>
</aside>
<p>This is all well and good for storing stuff in main memory, but that doesn’t
help rendering. Before the forest gets on screen, it has to work its way over to
the GPU. We need to express this resource sharing in a way that the graphics
card understands.</p>
<h2><a href="#a-thousand-instances" name="a-thousand-instances">A Thousand Instances</a></h2>
<p>To minimize the amount of data we have to push to the GPU, we want to be able to
send the shared data — the <code>TreeModel</code> — just <em>once</em>. Then, separately, we
push over every tree instance’s unique data — its position, color, and scale.
Finally, we tell the GPU, “Use that one model to render each of these
instances.”</p>
<p>Fortunately, today’s graphics APIs and <span name="hardware">cards</span>
support exactly that. The details are fiddly and out of the scope of this book,
but both Direct3D and OpenGL can do something called <a href="http://en.wikipedia.org/wiki/Geometry_instancing"><em>instanced
rendering</em></a>.</p>
<p>In both APIs, you provide two streams of data. The first is the blob of common
data that will be rendered multiple times — the mesh and textures in our
arboreal example. The second is the list of instances and their parameters that
will be used to vary that first chunk of data each time it’s drawn. With a
single draw call, an entire forest grows.</p>
<aside name="hardware">
<p>The fact that this API is implemented directly by the graphics card means the
Flyweight pattern may be the only Gang of Four design pattern to have actual
hardware support.</p>
</aside>
<h2><a href="#the-flyweight-pattern" name="the-flyweight-pattern">The Flyweight Pattern</a></h2>
<p>Now that we’ve got one concrete example under our belts, I can walk you through
the general pattern. Flyweight, like its name implies, comes into play when you
have objects that need to be more lightweight, generally because you have too
many of them.</p>
<p>With instanced rendering, it’s not so much that they take up too much memory as
it is they take too much <em>time</em> to push each separate tree over the bus to the
GPU, but the basic idea is the same.</p>
<p>The pattern solves that by separating out an object’s data into two kinds. The
first kind of data is the stuff that’s not specific to a single <em>instance</em> of
that object and can be shared across all of them. The Gang of Four calls this
the <em>intrinsic</em> state, but I like to think of it as the “context-free” stuff. In
the example here, this is the geometry and textures for the tree.</p>
<p>The rest of the data is the <em>extrinsic</em> state, the stuff that is unique to that
instance. In this case, that is each tree’s position, scale, and color. Just
like in the chunk of sample code up there, this pattern saves memory by sharing
one copy of the intrinsic state across every place where an object appears.</p>
<p>From what we’ve seen so far, this seems like basic resource sharing,
hardly worth being called a pattern. That’s partially because in this example
here, we could come up with a clear separate <em>identity</em> for the shared state:
the <code>TreeModel</code>.</p>
<p>I find this pattern to be less obvious (and thus more clever) when used in cases
where there isn’t a really well-defined identity for the shared object. In those
cases, it feels more like an object is magically in multiple places at the same
time. Let me show you another example.</p>
<h2><a href="#a-place-to-put-down-roots" name="a-place-to-put-down-roots">A Place To Put Down Roots</a></h2>
<p>The ground these trees are growing on needs to be represented in our game too.
There can be patches of grass, dirt, hills, lakes, rivers, and whatever other
terrain you can dream up. We’ll make the ground <em>tile-based</em>: the surface of the
world is a huge grid of tiny tiles. Each tile is covered in one kind of terrain.</p>
<p>Each terrain type has a number of properties that affect gameplay:</p>
<ul>
<li>A movement cost that determines how quickly players can move through it.</li>
<li>A flag for whether it’s a watery terrain that can be crossed by boats.</li>
<li>A texture used to render it.</li>
</ul>
<p>Because we game programmers are paranoid about efficiency, there’s no way we’d
store all of that state in <span name="learned">each</span> tile in the world.
Instead, a common approach is to use an enum for terrain types:</p>
<aside name="learned">
<p>After all, we already learned our lesson with those trees.</p>
</aside>
<div class="codehilite"><pre><span></span><code><span class="k">enum</span> <span class="nc">Terrain</span>
<span class="p">{</span>
<span class="n">TERRAIN_GRASS</span><span class="p">,</span>
<span class="n">TERRAIN_HILL</span><span class="p">,</span>
<span class="n">TERRAIN_RIVER</span>
<span class="c1">// Other terrains...</span>
<span class="p">};</span>
</code></pre></div>
<p>Then the world maintains a huge grid of those:</p>
<p><span name="grid"></span></p>
<div class="codehilite"><pre><span></span><code><span class="k">class</span> <span class="nc">World</span>
<span class="p">{</span>
<span class="k">private</span><span class="o">:</span>
<span class="n">Terrain</span> <span class="n">tiles_</span><span class="p">[</span><span class="n">WIDTH</span><span class="p">][</span><span class="n">HEIGHT</span><span class="p">];</span>
<span class="p">};</span>
</code></pre></div>
<aside name="grid">
<p>Here I’m using a nested array to store the 2D grid. That’s efficient in C/C++
because it will pack all of the elements together. In Java or other memory-
managed languages, doing that will actually give you an array of rows where each
element is a <em>reference</em> to the array of columns, which may not be as memory-
friendly as you’d like.</p>
<p>In either case, real code would be better served by hiding this implementation
detail behind a nice 2D grid data structure. I’m doing this here just to keep it
simple.</p>
</aside>
<p>To actually get the useful data about a tile, we do something like:</p>
<div class="codehilite"><pre><span></span><code><span class="kt">int</span> <span class="nf">World::getMovementCost</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="kt">int</span> <span class="n">y</span><span class="p">)</span>
<span class="p">{</span>
<span class="k">switch</span> <span class="p">(</span><span class="n">tiles_</span><span class="p">[</span><span class="n">x</span><span class="p">][</span><span class="n">y</span><span class="p">])</span>
<span class="p">{</span>
<span class="k">case</span> <span class="nl">TERRAIN_GRASS</span><span class="p">:</span> <span class="k">return</span> <span class="mi">1</span><span class="p">;</span>
<span class="k">case</span> <span class="nl">TERRAIN_HILL</span><span class="p">:</span> <span class="k">return</span> <span class="mi">3</span><span class="p">;</span>
<span class="k">case</span> <span class="nl">TERRAIN_RIVER</span><span class="p">:</span> <span class="k">return</span> <span class="mi">2</span><span class="p">;</span>
<span class="c1">// Other terrains...</span>
<span class="p">}</span>
<span class="p">}</span>
<span class="kt">bool</span> <span class="nf">World::isWater</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="kt">int</span> <span class="n">y</span><span class="p">)</span>
<span class="p">{</span>
<span class="k">switch</span> <span class="p">(</span><span class="n">tiles_</span><span class="p">[</span><span class="n">x</span><span class="p">][</span><span class="n">y</span><span class="p">])</span>
<span class="p">{</span>
<span class="k">case</span> <span class="nl">TERRAIN_GRASS</span><span class="p">:</span> <span class="k">return</span> <span class="nb">false</span><span class="p">;</span>
<span class="k">case</span> <span class="nl">TERRAIN_HILL</span><span class="p">:</span> <span class="k">return</span> <span class="nb">false</span><span class="p">;</span>
<span class="k">case</span> <span class="nl">TERRAIN_RIVER</span><span class="p">:</span> <span class="k">return</span> <span class="nb">true</span><span class="p">;</span>
<span class="c1">// Other terrains...</span>
<span class="p">}</span>
<span class="p">}</span>
</code></pre></div>
<p>You get the idea. This works, but I find it ugly. I think of movement cost and
wetness as <em>data</em> about a terrain, but here that’s embedded in code. Worse, the
data for a single terrain type is smeared across a bunch of methods. It would be
really nice to keep all of that encapsulated together. After all, that’s what
objects are designed for.</p>
<p>It would be great if we could have an actual terrain <em>class</em>, like:</p>
<p><span name="const"></span></p>
<div class="codehilite"><pre><span></span><code><span class="k">class</span> <span class="nc">Terrain</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
<span class="n">Terrain</span><span class="p">(</span><span class="kt">int</span> <span class="n">movementCost</span><span class="p">,</span>
<span class="kt">bool</span> <span class="n">isWater</span><span class="p">,</span>
<span class="n">Texture</span> <span class="n">texture</span><span class="p">)</span>
<span class="o">:</span> <span class="n">movementCost_</span><span class="p">(</span><span class="n">movementCost</span><span class="p">),</span>
<span class="n">isWater_</span><span class="p">(</span><span class="n">isWater</span><span class="p">),</span>
<span class="n">texture_</span><span class="p">(</span><span class="n">texture</span><span class="p">)</span>
<span class="p">{}</span>
<span class="kt">int</span> <span class="n">getMovementCost</span><span class="p">()</span> <span class="k">const</span> <span class="p">{</span> <span class="k">return</span> <span class="n">movementCost_</span><span class="p">;</span> <span class="p">}</span>
<span class="kt">bool</span> <span class="n">isWater</span><span class="p">()</span> <span class="k">const</span> <span class="p">{</span> <span class="k">return</span> <span class="n">isWater_</span><span class="p">;</span> <span class="p">}</span>
<span class="k">const</span> <span class="n">Texture</span><span class="o">&</span> <span class="n">getTexture</span><span class="p">()</span> <span class="k">const</span> <span class="p">{</span> <span class="k">return</span> <span class="n">texture_</span><span class="p">;</span> <span class="p">}</span>
<span class="k">private</span><span class="o">:</span>
<span class="kt">int</span> <span class="n">movementCost_</span><span class="p">;</span>
<span class="kt">bool</span> <span class="n">isWater_</span><span class="p">;</span>
<span class="n">Texture</span> <span class="n">texture_</span><span class="p">;</span>
<span class="p">};</span>
</code></pre></div>
<aside name="const">
<p>You’ll notice that all of the methods here are <code>const</code>. That’s no coincidence.
Since the same object is used in multiple contexts, if you were to modify it,
the changes would appear in multiple places simultaneously.</p>
<p>That’s probably not what you want. Sharing objects to save memory should be an
optimization that doesn’t affect the visible behavior of the app. Because of
this, Flyweight objects are almost always immutable.</p>
</aside>
<p>But we don’t want to pay the cost of having an instance of that for each tile in
the world. If you look at that class, you’ll notice that there’s actually
<em>nothing</em> in there that’s specific to <em>where</em> that tile is. In flyweight terms,
<em>all</em> of a terrain’s state is “intrinsic” or “context-free”.</p>
<p>Given that, there’s no reason to have more than one of each terrain type. Every
grass tile on the ground is identical to every other one. Instead of having the
world be a grid of enums or Terrain objects, it will be a grid of <em>pointers</em> to
<code>Terrain</code> objects:</p>
<div class="codehilite"><pre><span></span><code><span class="k">class</span> <span class="nc">World</span>
<span class="p">{</span>
<span class="k">private</span><span class="o">:</span>
<span class="n">Terrain</span><span class="o">*</span> <span class="n">tiles_</span><span class="p">[</span><span class="n">WIDTH</span><span class="p">][</span><span class="n">HEIGHT</span><span class="p">];</span>
<span class="c1">// Other stuff...</span>
<span class="p">};</span>
</code></pre></div>
<p>Each tile that uses the same terrain will point to the same terrain instance.</p>
<p><img src="images/flyweight-tiles.png" alt="A row of tiles. Each tile points to either a shared Grass, River, or Hill object." /></p>
<p>Since the terrain instances are used in multiple places, their lifetimes would
be a little more complex to manage if you were to dynamically allocate them.
Instead, we’ll just store them directly in the world:</p>
<div class="codehilite"><pre><span></span><code><span class="k">class</span> <span class="nc">World</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
<span class="n">World</span><span class="p">()</span>
<span class="o">:</span> <span class="n">grassTerrain_</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="nb">false</span><span class="p">,</span> <span class="n">GRASS_TEXTURE</span><span class="p">),</span>
<span class="n">hillTerrain_</span><span class="p">(</span><span class="mi">3</span><span class="p">,</span> <span class="nb">false</span><span class="p">,</span> <span class="n">HILL_TEXTURE</span><span class="p">),</span>
<span class="n">riverTerrain_</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="nb">true</span><span class="p">,</span> <span class="n">RIVER_TEXTURE</span><span class="p">)</span>
<span class="p">{}</span>
<span class="k">private</span><span class="o">:</span>
<span class="n">Terrain</span> <span class="n">grassTerrain_</span><span class="p">;</span>
<span class="n">Terrain</span> <span class="n">hillTerrain_</span><span class="p">;</span>
<span class="n">Terrain</span> <span class="n">riverTerrain_</span><span class="p">;</span>
<span class="c1">// Other stuff...</span>
<span class="p">};</span>
</code></pre></div>
<p>Then we can use those to paint the ground like this:</p>
<p><span name="generate"></span></p>
<div class="codehilite"><pre><span></span><code><span class="kt">void</span> <span class="nf">World::generateTerrain</span><span class="p">()</span>
<span class="p">{</span>
<span class="c1">// Fill the ground with grass.</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">x</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">x</span> <span class="o"><</span> <span class="n">WIDTH</span><span class="p">;</span> <span class="n">x</span><span class="o">++</span><span class="p">)</span>
<span class="p">{</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">y</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">y</span> <span class="o"><</span> <span class="n">HEIGHT</span><span class="p">;</span> <span class="n">y</span><span class="o">++</span><span class="p">)</span>
<span class="p">{</span>
<span class="c1">// Sprinkle some hills.</span>
<span class="k">if</span> <span class="p">(</span><span class="n">random</span><span class="p">(</span><span class="mi">10</span><span class="p">)</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">tiles_</span><span class="p">[</span><span class="n">x</span><span class="p">][</span><span class="n">y</span><span class="p">]</span> <span class="o">=</span> <span class="o">&</span><span class="n">hillTerrain_</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">else</span>
<span class="p">{</span>
<span class="n">tiles_</span><span class="p">[</span><span class="n">x</span><span class="p">][</span><span class="n">y</span><span class="p">]</span> <span class="o">=</span> <span class="o">&</span><span class="n">grassTerrain_</span><span class="p">;</span>
<span class="p">}</span>
<span class="p">}</span>
<span class="p">}</span>
<span class="c1">// Lay a river.</span>
<span class="kt">int</span> <span class="n">x</span> <span class="o">=</span> <span class="n">random</span><span class="p">(</span><span class="n">WIDTH</span><span class="p">);</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">y</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">y</span> <span class="o"><</span> <span class="n">HEIGHT</span><span class="p">;</span> <span class="n">y</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
<span class="n">tiles_</span><span class="p">[</span><span class="n">x</span><span class="p">][</span><span class="n">y</span><span class="p">]</span> <span class="o">=</span> <span class="o">&</span><span class="n">riverTerrain_</span><span class="p">;</span>
<span class="p">}</span>
<span class="p">}</span>
</code></pre></div>
<aside name="generate">
<p>I’ll admit this isn’t the world’s greatest procedural terrain generation
algorithm.</p>
</aside>
<p>Now instead of methods on <code>World</code> for accessing the terrain properties, we can
expose the <code>Terrain</code> object directly:</p>
<div class="codehilite"><pre><span></span><code><span class="k">const</span> <span class="n">Terrain</span><span class="o">&</span> <span class="nf">World::getTile</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="kt">int</span> <span class="n">y</span><span class="p">)</span> <span class="k">const</span>
<span class="p">{</span>
<span class="k">return</span> <span class="o">*</span><span class="n">tiles_</span><span class="p">[</span><span class="n">x</span><span class="p">][</span><span class="n">y</span><span class="p">];</span>
<span class="p">}</span>
</code></pre></div>
<p>This way, <code>World</code> is no longer coupled to all sorts of details of terrains. If
you want some property of the tile, you can get it right from that object:</p>
<div class="codehilite"><pre><span></span><code><span class="kt">int</span> <span class="n">cost</span> <span class="o">=</span> <span class="n">world</span><span class="p">.</span><span class="n">getTile</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">).</span><span class="n">getMovementCost</span><span class="p">();</span>
</code></pre></div>
<p>We’re back to the pleasant API of working with real objects, and we did this
with almost no overhead — a pointer is often no larger than an enum.</p>
<h2><a href="#what-about-performance" name="what-about-performance">What About Performance?</a></h2>
<p>I say “almost” here because the performance bean counters will rightfully want
to know how this compares to using an enum. Referencing the terrain by pointer
implies an indirect lookup. To get to some terrain data like the movement cost,
you first have to follow the pointer in the grid to find the terrain object and
then find the movement cost there. Chasing a pointer like this can cause a <span
name="cache">cache miss</span>, which can slow things down.</p>
<aside name="cache">
<p>For lots more on pointer chasing and cache misses, see the chapter on <a href
="data-locality.html" class="pattern">Data Locality</a>.</p>
</aside>
<p>As always, the golden rule of optimization is <em>profile first</em>. Modern computer
hardware is too complex for performance to be a game of pure reason anymore. In
my tests for this chapter, there was no penalty for using a flyweight over an
enum. Flyweights were actually noticeably faster. But that’s entirely dependent
on how other stuff is laid out in memory.</p>
<p>What I <em>am</em> confident of is that using flyweight objects shouldn’t be dismissed
out of hand. They give you the advantages of an object-oriented style without
the expense of tons of objects. If you find yourself creating an enum and doing
lots of switches on it, consider this pattern instead. If you’re worried about
performance, at least profile first before changing your code to a less
maintainable style.</p>
<h2><a href="#see-also" name="see-also">See Also</a></h2>
<ul>
<li>
<p>In the tile example, we just eagerly created an instance for each terrain
type and stored it in <code>World</code>. That made it easy to find and reuse the
shared instances. In many cases, though, you won’t want to create <em>all</em> of
the flyweights up front.</p>
<p>If you can’t predict which ones you actually need, it’s better to create
them on demand. To get the advantage of sharing, when you request one, you
first see if you’ve already created an identical one. If so, you just return
that instance.</p>
<p>This usually means that you have to encapsulate construction behind some
interface that can first look for an existing object. Hiding a constructor
like this is an example of the <a
href="http://en.wikipedia.org/wiki/Factory_method_pattern" class="gof-
pattern">Factory Method</a> pattern.</p>
</li>
<li>
<p>In order to return a previously created flyweight, you’ll have to keep track
of the pool of ones that you’ve already instantiated. As the name implies,
that means that an <a href="object-pool.html" class="pattern">Object
Pool</a> might be a helpful place to store them.</p>
</li>
<li>
<p>When you’re using the <a class="pattern" href="state.html">State</a>
pattern, you often have “state” objects that don’t have any fields specific
to the machine that the state is being used in. The state’s
identity and methods are enough to be useful. In that case, you can apply
this pattern and reuse that same state instance in multiple state machines
at the same time without any problems.</p>
</li>
</ul>
<nav>
<span class="prev">← <a href="command.html">Previous Chapter</a></span>
<span class="next"><a href="observer.html">Next Chapter</a> →</span>
<span class="toc">≡ <a href="/">The Book</a></span>
</nav>
</div>
</div>
<footer>© 2009-2021 Robert Nystrom</footer>
</body>
</html>