-
Notifications
You must be signed in to change notification settings - Fork 513
Expand file tree
/
Copy pathbytecode.html
More file actions
1180 lines (1133 loc) · 72.3 KB
/
bytecode.html
File metadata and controls
1180 lines (1133 loc) · 72.3 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
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!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>Bytecode · Behavioral Patterns · 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="behavioral-patterns.html">Previous Chapter</a></span>
<span class="next"><a href="subclass-sandbox.html">Next Chapter</a> →</span>
<span class="toc">≡ <a href="/">The Book</a></span>
</nav>
<h1>Bytecode</h1>
<h1 class="book"><a href="/">Game Programming Patterns</a><span class="section"><a href="behavioral-patterns.html">Behavioral Patterns</a></span></h1>
<h2><a href="#intent" name="intent">Intent</a></h2>
<p><em>Give behavior the flexibility of data by encoding it as instructions for a
virtual machine.</em></p>
<h2><a href="#motivation" name="motivation">Motivation</a></h2>
<p>Making games may be fun, but it certainly ain’t easy. Modern games require <span
name="sprawling">enormous</span>, complex codebases. Console manufacturers and
app marketplace gatekeepers have stringent quality requirements, and a single
crash bug can prevent your game from shipping.</p>
<aside name="sprawling">
<p>I worked on a game that had six million lines of C++ code. For comparison, the
software controlling the Mars Curiosity rover is less than half that.</p>
</aside>
<p>At the same time, we’re expected to squeeze every drop of performance out of the
platform. Games push hardware like nothing else, and we have to optimize
relentlessly just to keep pace with the competition.</p>
<p>To handle these high stability and performance requirements, we reach for
heavyweight languages like C++ that have both low-level expressiveness to make
the most of the hardware and rich type systems to prevent or at least corral
bugs.</p>
<p>We pride ourselves on our skill at this, but it has its cost. Being a proficient
programmer takes years of dedicated training, after which you must contend with
the sheer scale of your codebase. Build times for large games can vary somewhere
between “go get a coffee” and “go roast your own beans, hand-grind them, pull an
espresso, foam some milk, and practice your latte art in the froth”.</p>
<p>On top of these challenges, games have one more nasty constraint: <em>fun</em>. Players
demand a play experience that’s both novel and yet carefully balanced. That
requires constant iteration, but if every tweak requires bugging an engineer to
muck around in piles of low-level code and then waiting for a glacial recompile,
you’ve killed your creative flow.</p>
<h3><a href="#spell-fight" name="spell-fight">Spell fight!</a></h3>
<p>Let’s say we’re working on a magic-based fighting game. A pair of wizards square
off and fling enchantments at each other until a victor is pronounced. We could
define these spells in code, but that means an engineer has to be involved every
time one is modified. When a designer wants to tweak a few numbers and get a
feel for them, they have to recompile the entire game, reboot it, and get back
into a fight.</p>
<p>Like most games these days, we also need to be able to update the game after it ships,
both to fix bugs and to add new content. If all of these spells are hard-coded,
then updating them means patching the actual game executable.</p>
<p>Let’s take things a bit further and say that we also want to support <em>modding</em>.
We want <em>users</em> to be able to create their own spells. If those are in code,
that means every modder needs a full compiler toolchain to build the game, and
we have to release the sources. Worse, if they have a bug in their spell, it can
crash the game on some other player’s machine.</p>
<h3><a href="#data->-code" name="data->-code">Data > code</a></h3>
<p>It’s pretty clear that our engine’s implementation language isn’t the right fit.
We need spells to be safely sandboxed from the core game. We want them to be
easy to modify, easy to reload, and physically separate from the rest of the
executable.</p>
<p>I don’t know about you, but to me that sounds a lot like <em>data</em>. If we can
define our behavior in separate data files that the game engine loads and
“executes” in some way, we can achieve all of our goals.</p>
<p>We just need to figure out what “execute” means for data. How do you make some
bytes in a file express behavior? There are a few ways to do this. I think it
will help you get a picture of <em>this</em> pattern’s strengths and weaknesses if we
compare it to another one: the <a
href="http://en.wikipedia.org/wiki/Interpreter_pattern"
class="gof-pattern">Interpreter</a> pattern.</p>
<h3><a href="#the-interpreter-pattern" name="the-interpreter-pattern">The Interpreter pattern</a></h3>
<p>I could write a whole chapter on this pattern, but four other guys already
covered that for me. Instead, I’ll cram the briefest of introductions in here.
It starts with a language — think <em>programming</em> language — that you want to
execute. Say, for example, it supports arithmetic expressions like this:</p>
<div class="codehilite"><pre><span></span><code>(1 + 2) * (3 - 4)
</code></pre></div>
<p>Then, you take each piece of that expression, each rule in the language’s
grammar, and turn it into an <em>object</em>. The number literals will be objects:</p>
<p><img src="images/bytecode-numbers.png" alt="A series of number literal objects." /></p>
<p>Basically, they’re little wrappers around the raw value. The operators will be
objects too, and they’ll have references to their operands. If you take into
account the parentheses and precedence, that expression <span
name="magic">magically</span> turns into a little tree of objects like so:</p>
<p><img src="images/bytecode-ast.png" alt="A syntax tree. The number literals are connected by operator objects." /></p>
<aside name="magic">
<p>What “magic” is this? It’s simple — <em>parsing</em>. A parser takes a string of
characters and turns it into an <em>abstract syntax tree</em>, a collection of objects
representing the grammatical structure of the text.</p>
<p>Whip up one of these and you’ve got yourself half of a compiler.</p>
</aside>
<p>The Interpreter pattern isn’t about <em>creating</em> that tree; it’s about <em>executing</em>
it. The way it works is pretty clever. Each object in the tree is an expression
or a subexpression. In true object-oriented fashion, we’ll let expressions
evaluate themselves.</p>
<p>First, we define a base interface that all expressions implement:</p>
<div class="codehilite"><pre><span></span><code><span class="k">class</span> <span class="nc">Expression</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
<span class="k">virtual</span> <span class="o">~</span><span class="n">Expression</span><span class="p">()</span> <span class="p">{}</span>
<span class="k">virtual</span> <span class="kt">double</span> <span class="n">evaluate</span><span class="p">()</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">};</span>
</code></pre></div>
<p>Then, we define a class that implements this interface for each kind of expression in our
language’s grammar. The simplest one is numbers:</p>
<div class="codehilite"><pre><span></span><code><span class="k">class</span> <span class="nc">NumberExpression</span> <span class="o">:</span> <span class="k">public</span> <span class="n">Expression</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
<span class="n">NumberExpression</span><span class="p">(</span><span class="kt">double</span> <span class="n">value</span><span class="p">)</span>
<span class="o">:</span> <span class="n">value_</span><span class="p">(</span><span class="n">value</span><span class="p">)</span>
<span class="p">{}</span>
<span class="k">virtual</span> <span class="kt">double</span> <span class="n">evaluate</span><span class="p">()</span>
<span class="p">{</span>
<span class="k">return</span> <span class="n">value_</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">private</span><span class="o">:</span>
<span class="kt">double</span> <span class="n">value_</span><span class="p">;</span>
<span class="p">};</span>
</code></pre></div>
<p>A literal number expression simply evaluates to its value. Addition and
multiplication are a bit more complex because they contain subexpressions.
Before they can evaluate themselves, they need to recursively evaluate their
subexpressions. Like so:</p>
<p><span name="addition"></span></p>
<div class="codehilite"><pre><span></span><code><span class="k">class</span> <span class="nc">AdditionExpression</span> <span class="o">:</span> <span class="k">public</span> <span class="n">Expression</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
<span class="n">AdditionExpression</span><span class="p">(</span><span class="n">Expression</span><span class="o">*</span> <span class="n">left</span><span class="p">,</span> <span class="n">Expression</span><span class="o">*</span> <span class="n">right</span><span class="p">)</span>
<span class="o">:</span> <span class="n">left_</span><span class="p">(</span><span class="n">left</span><span class="p">),</span>
<span class="n">right_</span><span class="p">(</span><span class="n">right</span><span class="p">)</span>
<span class="p">{}</span>
<span class="k">virtual</span> <span class="kt">double</span> <span class="n">evaluate</span><span class="p">()</span>
<span class="p">{</span>
<span class="c1">// Evaluate the operands.</span>
<span class="kt">double</span> <span class="n">left</span> <span class="o">=</span> <span class="n">left_</span><span class="o">-></span><span class="n">evaluate</span><span class="p">();</span>
<span class="kt">double</span> <span class="n">right</span> <span class="o">=</span> <span class="n">right_</span><span class="o">-></span><span class="n">evaluate</span><span class="p">();</span>
<span class="c1">// Add them.</span>
<span class="k">return</span> <span class="n">left</span> <span class="o">+</span> <span class="n">right</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">private</span><span class="o">:</span>
<span class="n">Expression</span><span class="o">*</span> <span class="n">left_</span><span class="p">;</span>
<span class="n">Expression</span><span class="o">*</span> <span class="n">right_</span><span class="p">;</span>
<span class="p">};</span>
</code></pre></div>
<aside name="addition">
<p>I’m sure you can figure out what the implementation of multiply looks like.</p>
</aside>
<p>Pretty neat right? Just a couple of simple classes and now we can represent and
evaluate arbitrarily complex arithmetic expressions. We just need to create the
right objects and wire them up correctly.</p>
<aside name="ruby">
<p>Ruby was implemented like this for something like 15 years. At version 1.9, they
switched to bytecode like this chapter describes. Look how much time I’m saving
you!</p>
</aside>
<p>It’s a <span name="ruby">beautiful</span>, simple pattern, but it has some
problems. Look up at the illustration. What do you see? Lots of little boxes,
and lots of arrows between them. Code is represented as a sprawling fractal tree
of tiny objects. That has some unpleasant consequences:</p>
<ul>
<li>
<p>Loading it from disk requires instantiating and wiring up tons of these
small objects.</p>
</li>
<li>
<p>Those objects and the pointers between them use a lot of <span
name="vtable">memory</span>. On a 32-bit machine, that little arithmetic
expression up there takes up at least 68 bytes, not including padding.</p>
<aside name="vtable">
<p>If you’re playing along at home, don’t forget to take into account the
vtable pointers.</p>
</aside>
</li>
<li>
<p>Traversing the pointers into subexpressions is murder on your <span
name="cache">data cache</span>. Meanwhile, all of those virtual method calls
wreak carnage on your instruction cache.</p>
<aside name="cache">
<p>See the chapter on <a href="data-locality.html" class="pattern">Data
Locality</a> for more on what the cache is and how it affects your
performance.</p>
</aside>
</li>
</ul>
<p>Put those together, and what do they spell? S-L-O-W. There’s a reason most
programming languages in wide use aren’t based on the Interpreter pattern. It’s
just too slow, and it uses up too much memory.</p>
<h3><a href="#machine-code,-virtually" name="machine-code,-virtually">Machine code, virtually</a></h3>
<p>Consider our game. When we run it, the player’s computer doesn’t traverse a
bunch of C++ grammar tree structures at runtime. Instead, we compile it ahead of
time to machine code, and the CPU runs that. What’s machine code got going for
it?</p>
<ul>
<li>
<p><em>It’s dense.</em> It’s a solid, contiguous blob of binary data, and no bit goes
to waste.</p>
</li>
<li>
<p><em>It’s linear.</em> Instructions are packed together and executed one right after
another. No jumping around in memory (unless you’re doing actual control
flow, of course).</p>
</li>
<li>
<p><em>It’s low-level.</em> Each instruction does one relatively minimal thing, and
interesting behavior comes from <em>composing</em> them.</p>
</li>
<li>
<p><em>It’s fast.</em> As a consequence of all of these (well, and the fact that it’s
implemented directly in hardware), machine code runs like the wind.</p>
</li>
</ul>
<p>This sounds swell, but we don’t want actual machine code for our spells. Letting
users provide machine code which our game executes is just begging for <span
name="jit">security problems</span>. What we need is a compromise between the
performance of machine code and the safety of the Interpreter pattern.</p>
<p>What if instead of loading actual machine code and executing it directly, we
defined our own <em>virtual</em> machine code? We’d then write a little emulator for it
in our game. It would be similar to machine code — dense, linear, relatively
low-level — but would also be handled entirely by our game so we could safely
sandbox it.</p>
<aside name="jit">
<p>This is why many game consoles and iOS don’t allow programs to execute machine
code loaded or generated at runtime. That’s a drag because the fastest
programming language implementations do exactly that. They contain a
“just-in-time” compiler, or <em>JIT</em>, that translates the language to optimized
machine code on the fly.</p>
</aside>
<p>We’d call our little emulator a <span name="virtual"><em>virtual machine</em></span>
(or “VM” for short), and the synthetic binary machine code it runs <em>bytecode</em>.
It’s got the flexibility and ease of use of defining things in data, but it has better
performance than higher-level representations like the Interpreter pattern.</p>
<aside name="virtual">
<p>In programming language circles, “virtual machine” and “interpreter” are
synonymous, and I use them interchangeably here. When I refer to the Gang of
Four’s Interpreter pattern, I’ll use “pattern” to make it clear.</p>
</aside>
<p>This sounds daunting, though. My goal for the rest of this chapter is to show
you that if you keep your feature list pared down, it’s actually pretty
approachable. Even if you end up not using this pattern yourself, you’ll at
least have a better understanding of Lua and many other languages which are
implemented using it.</p>
<h2><a href="#the-pattern" name="the-pattern">The Pattern</a></h2>
<p>An <strong>instruction set</strong> defines the low-level operations that can be performed.
A series of instructions is encoded as a <strong>sequence of bytes</strong>. A <strong>virtual machine</strong> executes
these instructions one at a time, using a <strong>stack for intermediate values</strong>. By
combining instructions, complex high-level behavior can be defined.</p>
<h2><a href="#when-to-use-it" name="when-to-use-it">When to Use It</a></h2>
<p>This is the most complex pattern in this book, and it’s not something to throw into
your game lightly. Use it when you have a lot of behavior you need to define and
your game’s implementation language isn’t a good fit because:</p>
<ul>
<li>
<p>It’s too low-level, making it tedious or error-prone to program in.</p>
</li>
<li>
<p>Iterating on it takes too long due to slow compile times or other tooling
issues.</p>
</li>
<li>
<p>It has too much trust. If you want to ensure the behavior being defined
can’t break the game, you need to sandbox it from the rest of the codebase.</p>
</li>
</ul>
<p>Of course, that list describes a bunch of your game. Who doesn’t want a faster
iteration loop or more safety? However, that doesn’t come for free. Bytecode is
slower than native code, so it isn’t a good fit for performance-critical parts
of your engine.</p>
<h2><a href="#keep-in-mind" name="keep-in-mind">Keep in Mind</a></h2>
<p>There’s something <span name="seductive">seductive</span> about creating your
own language or system-within-a-system. I’ll be doing a minimal example here,
but in the real world, these things tend to grow like vines.</p>
<aside name="seductive">
<p>For me, game development is seductive in the same way. In both cases, I’m
striving to create a virtual space for others to play and be creative in.</p>
</aside>
<p>Every time I see someone define a little language or a scripting system, they
say, “Don’t worry, it will be tiny.” Then, inevitably, they add more and more
little features until it’s a full-fledged <span name="template">language</span>.
Except, unlike some other languages, it grew in an ad-hoc, organic fashion and
has all of the architectural elegance of a shanty town.</p>
<aside name="template">
<p>For example, see every templating language ever.</p>
</aside>
<p>Of course, there’s nothing <em>wrong</em> with making a full-fledged language. Just
make sure you do so deliberately. Otherwise, be very careful to control the
scope of what your bytecode can express. Put a short leash on it before it runs
away from you.</p>
<h3><a href="#you'll-need-a-front-end" name="you'll-need-a-front-end">You’ll need a front-end</a></h3>
<p>Low-level bytecode instructions are great for performance, but a binary bytecode
format is <em>not</em> what your users are going to author. One reason we’re moving
behavior out of code is so that we can express it at a <em>higher</em> level. If C++ is
too low-level, making your users effectively write in <span
name="assembly">assembly language</span> — even one of your own design — isn’t
an improvement!</p>
<aside name="assembly">
<p>Challenging that assertion is the venerable game
<a href="http://en.wikipedia.org/wiki/RoboWar">RoboWar</a>. In that game, <em>players</em> write
little programs to control a robot in a language very similar to assembly and
the kind of instruction sets we’ll be discussing here.</p>
<p>It was my first introduction to assembly-like languages.</p>
</aside>
<p>Much like the Gang of Four’s Interpreter pattern, it’s assumed that you also
have some way to <em>generate</em> the bytecode. Usually, users author their behavior
in some higher-level format, and a tool translates that to the bytecode that our
virtual machine understands. In other words, a compiler.</p>
<p>I know, that sounds scary. That’s why I’m mentioning it here. If you don’t have
the resources to build an authoring tool, then bytecode isn’t for you. But as
we’ll see later, it may not be as bad as you think.</p>
<h3><a href="#you'll-miss-your-debugger" name="you'll-miss-your-debugger">You’ll miss your debugger</a></h3>
<p>Programming is hard. We know what we want the machine to do, but we don’t always
communicate that correctly — we write bugs. To help find and fix those, we’ve
amassed a pile of tools to understand what our code is doing wrong, and how to
right it. We have debuggers, static analyzers, decompilers, etc. All of those tools are
designed to work with some existing language: either machine code or something
higher level.</p>
<p>When you define your own bytecode VM, you leave those tools behind. Sure, you
can step through the VM in your debugger, but that tells you what the VM
<em>itself</em> is doing, and not what the bytecode it’s interpreting is up to. It
certainly doesn’t help you map that bytecode back to the high-level form it was
compiled from.</p>
<p>If the behavior you’re defining is simple, you can scrape by without too much
tooling to help you debug it. But as the scale of your content grows, plan to
invest real time into features that help users see what their bytecode is doing.
Those features might not <span name="debugger">ship</span> in your game, but
they’ll be critical to ensure that you actually <em>can</em> ship your game.</p>
<aside name="debugger">
<p>Of course, if you want your game to be moddable, then you <em>will</em> ship those
features, and they’ll be even more important.</p>
</aside>
<h2><a href="#sample-code" name="sample-code">Sample Code</a></h2>
<p>After the previous couple of sections, you might be surprised how
straightforward the implementation is. First, we need to craft an instruction
set for our VM. Before we start thinking about bytecode and stuff, let’s just
think about it like an API.</p>
<h3><a href="#a-magical-api" name="a-magical-api">A magical API</a></h3>
<p>If we were defining spells in straight C++ code, what kind of API would we need
for that code to call into? What are the basic operations in the game engine
that spells are defined in terms of?</p>
<p>Most spells ultimately change one of the stats of a wizard, so we’ll start with
a couple for that:</p>
<div class="codehilite"><pre><span></span><code><span class="kt">void</span> <span class="nf">setHealth</span><span class="p">(</span><span class="kt">int</span> <span class="n">wizard</span><span class="p">,</span> <span class="kt">int</span> <span class="n">amount</span><span class="p">);</span>
<span class="kt">void</span> <span class="nf">setWisdom</span><span class="p">(</span><span class="kt">int</span> <span class="n">wizard</span><span class="p">,</span> <span class="kt">int</span> <span class="n">amount</span><span class="p">);</span>
<span class="kt">void</span> <span class="nf">setAgility</span><span class="p">(</span><span class="kt">int</span> <span class="n">wizard</span><span class="p">,</span> <span class="kt">int</span> <span class="n">amount</span><span class="p">);</span>
</code></pre></div>
<p>The first parameter identifies which wizard is affected, say <code>0</code> for the
player’s and <code>1</code> for their opponent. This way, healing spells can affect the
player’s own wizard, while damaging attacks harm their nemesis. These three
little methods cover a surprisingly wide variety of magical effects.</p>
<p>If the spells just silently tweaked stats, the game logic would be fine, but
playing it would bore players to tears. Let’s fix that:</p>
<div class="codehilite"><pre><span></span><code><span class="kt">void</span> <span class="nf">playSound</span><span class="p">(</span><span class="kt">int</span> <span class="n">soundId</span><span class="p">);</span>
<span class="kt">void</span> <span class="nf">spawnParticles</span><span class="p">(</span><span class="kt">int</span> <span class="n">particleType</span><span class="p">);</span>
</code></pre></div>
<p>These don’t affect gameplay, but they crank up the intensity of the gameplay
<em>experience</em>. We could add more for camera shake, animation, etc., but this is
enough to get us started.</p>
<h3><a href="#a-magical-instruction-set" name="a-magical-instruction-set">A magical instruction set</a></h3>
<p>Now let’s see how we’d turn this <em>programmatic</em> API into something that can be
controlled from data. Let’s start small and then we’ll work our way up to the
whole shebang. For now, we’ll ditch all of the parameters to these methods.
We’ll say the <code>set___()</code> methods always affect the player’s own wizard and
always max out the stat. Likewise, the FX operations always play a single
hard-coded sound and particle effect.</p>
<p>Given that, a spell is just a series of instructions. Each one identifies which
operation you want to perform. We can enumerate them:</p>
<div class="codehilite"><pre><span></span><code><span class="k">enum</span> <span class="nc">Instruction</span>
<span class="p">{</span>
<span class="n">INST_SET_HEALTH</span> <span class="o">=</span> <span class="mh">0x00</span><span class="p">,</span>
<span class="n">INST_SET_WISDOM</span> <span class="o">=</span> <span class="mh">0x01</span><span class="p">,</span>
<span class="n">INST_SET_AGILITY</span> <span class="o">=</span> <span class="mh">0x02</span><span class="p">,</span>
<span class="n">INST_PLAY_SOUND</span> <span class="o">=</span> <span class="mh">0x03</span><span class="p">,</span>
<span class="n">INST_SPAWN_PARTICLES</span> <span class="o">=</span> <span class="mh">0x04</span>
<span class="p">};</span>
</code></pre></div>
<p>To encode a spell in data, we store an array of <code>enum</code> values. We’ve only got
a few different primitives, so the range of <code>enum</code> values easily fits into a byte.
This means the code for a spell is just a list of <span name="byte">bytes</span> — ergo
“bytecode”.</p>
<p><img src="images/bytecode-code.png" alt="A sequence of bytecode instructions: 0x00 HEALTH, 0x03 SOUND, 0x004 PARTICLES, ..." /></p>
<aside name="byte">
<p>Some bytecode VMs use more than a single byte for each instruction and have more
complicated rules for how they are decoded. Actual machine code on common chips
like x86 is a good bit more complex.</p>
<p>But a single byte is good enough for the <a href="http://en.wikipedia.org/wiki/Java_virtual_machine">Java Virtual
Machine</a> and Microsoft’s
<a href="http://en.wikipedia.org/wiki/Common_Language_Runtime">Common Language Runtime</a>,
which forms the backbone of the .NET platform, and it’s good enough for us.</p>
</aside>
<p>To execute a single instruction, we see which primitive it is and dispatch to
the right API method:</p>
<div class="codehilite"><pre><span></span><code><span class="k">switch</span> <span class="p">(</span><span class="n">instruction</span><span class="p">)</span>
<span class="p">{</span>
<span class="k">case</span> <span class="nl">INST_SET_HEALTH</span><span class="p">:</span>
<span class="n">setHealth</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">100</span><span class="p">);</span>
<span class="k">break</span><span class="p">;</span>
<span class="k">case</span> <span class="nl">INST_SET_WISDOM</span><span class="p">:</span>
<span class="n">setWisdom</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">100</span><span class="p">);</span>
<span class="k">break</span><span class="p">;</span>
<span class="k">case</span> <span class="nl">INST_SET_AGILITY</span><span class="p">:</span>
<span class="n">setAgility</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">100</span><span class="p">);</span>
<span class="k">break</span><span class="p">;</span>
<span class="k">case</span> <span class="nl">INST_PLAY_SOUND</span><span class="p">:</span>
<span class="n">playSound</span><span class="p">(</span><span class="n">SOUND_BANG</span><span class="p">);</span>
<span class="k">break</span><span class="p">;</span>
<span class="k">case</span> <span class="nl">INST_SPAWN_PARTICLES</span><span class="p">:</span>
<span class="n">spawnParticles</span><span class="p">(</span><span class="n">PARTICLE_FLAME</span><span class="p">);</span>
<span class="k">break</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div>
<p>In this way, our interpreter forms the bridge between code world and data world.
We can wrap this in a little VM that executes an entire spell like so:</p>
<div class="codehilite"><pre><span></span><code><span class="k">class</span> <span class="nc">VM</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
<span class="kt">void</span> <span class="n">interpret</span><span class="p">(</span><span class="kt">char</span> <span class="n">bytecode</span><span class="p">[],</span> <span class="kt">int</span> <span class="n">size</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">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">size</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
<span class="p">{</span>
<span class="kt">char</span> <span class="n">instruction</span> <span class="o">=</span> <span class="n">bytecode</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
<span class="k">switch</span> <span class="p">(</span><span class="n">instruction</span><span class="p">)</span>
<span class="p">{</span>
<span class="c1">// Cases for each instruction...</span>
<span class="p">}</span>
<span class="p">}</span>
<span class="p">}</span>
<span class="p">};</span>
</code></pre></div>
<p>Type that in and you’ll have written your first virtual machine. Unfortunately,
it’s not very flexible. We can’t define a spell that touches the player’s
opponent or lowers a stat. We can only play one sound!</p>
<p>To get something that starts to have the expressive feel of an actual language,
we need to get parameters in here.</p>
<h3><a href="#a-stack-machine" name="a-stack-machine">A stack machine</a></h3>
<p>To execute a complex nested expression, you start with the innermost
subexpressions. You calculate those, and the results flow outward as arguments to
the expressions that contain them until eventually, the whole expression has been
evaluated.</p>
<p>The Interpreter pattern models this explicitly as a tree of nested objects, but
we want the speed of a flat list of instructions. We still need to ensure
results from subexpressions flow to the right surrounding expressions. But,
since our data is flattened, we’ll have to use the <em>order</em> of the instructions
to control that. We’ll do it the same way your CPU does — <span
name="stack-machine">with a stack</span>.</p>
<aside name="stack-machine">
<p>This architecture is unimaginatively called a <a href="http://en.wikipedia.org/wiki/Stack_machine"><em>stack
machine</em></a>. Programming languages
like <a href="http://en.wikipedia.org/wiki/Forth_(programming_language)">Forth</a>,
<a href="http://en.wikipedia.org/wiki/PostScript">PostScript</a>, and
<a href="http://en.wikipedia.org/wiki/Factor_(programming_language)">Factor</a> expose this
model directly to the user.</p>
</aside>
<div class="codehilite"><pre><span></span><code><span class="k">class</span> <span class="nc">VM</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
<span class="n">VM</span><span class="p">()</span>
<span class="o">:</span> <span class="n">stackSize_</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span>
<span class="p">{}</span>
<span class="c1">// Other stuff...</span>
<span class="k">private</span><span class="o">:</span>
<span class="k">static</span> <span class="k">const</span> <span class="kt">int</span> <span class="n">MAX_STACK</span> <span class="o">=</span> <span class="mi">128</span><span class="p">;</span>
<span class="kt">int</span> <span class="n">stackSize_</span><span class="p">;</span>
<span class="kt">int</span> <span class="n">stack_</span><span class="p">[</span><span class="n">MAX_STACK</span><span class="p">];</span>
<span class="p">};</span>
</code></pre></div>
<p>The VM maintains an internal stack of values. In our example, the only kinds of
values our instructions work with are numbers, so we can use a simple array
of <code>int</code>s. Whenever a bit of data needs to work its way from one instruction to
another, it gets there through the stack.</p>
<p>Like the name implies, values can be pushed onto or popped off of the stack, so
let’s add a couple of methods for that:</p>
<div class="codehilite"><pre><span></span><code><span class="k">class</span> <span class="nc">VM</span>
<span class="p">{</span>
<span class="k">private</span><span class="o">:</span>
<span class="kt">void</span> <span class="n">push</span><span class="p">(</span><span class="kt">int</span> <span class="n">value</span><span class="p">)</span>
<span class="p">{</span>
<span class="c1">// Check for stack overflow.</span>
<span class="n">assert</span><span class="p">(</span><span class="n">stackSize_</span> <span class="o"><</span> <span class="n">MAX_STACK</span><span class="p">);</span>
<span class="n">stack_</span><span class="p">[</span><span class="n">stackSize_</span><span class="o">++</span><span class="p">]</span> <span class="o">=</span> <span class="n">value</span><span class="p">;</span>
<span class="p">}</span>
<span class="kt">int</span> <span class="n">pop</span><span class="p">()</span>
<span class="p">{</span>
<span class="c1">// Make sure the stack isn't empty.</span>
<span class="n">assert</span><span class="p">(</span><span class="n">stackSize_</span> <span class="o">></span> <span class="mi">0</span><span class="p">);</span>
<span class="k">return</span> <span class="n">stack_</span><span class="p">[</span><span class="o">--</span><span class="n">stackSize_</span><span class="p">];</span>
<span class="p">}</span>
<span class="c1">// Other stuff...</span>
<span class="p">};</span>
</code></pre></div>
<p>When an instruction needs to receive parameters, it pops them off the stack like
so:</p>
<div class="codehilite"><pre><span></span><code><span class="k">switch</span> <span class="p">(</span><span class="n">instruction</span><span class="p">)</span>
<span class="p">{</span>
<span class="k">case</span> <span class="nl">INST_SET_HEALTH</span><span class="p">:</span>
<span class="p">{</span>
<span class="kt">int</span> <span class="n">amount</span> <span class="o">=</span> <span class="n">pop</span><span class="p">();</span>
<span class="kt">int</span> <span class="n">wizard</span> <span class="o">=</span> <span class="n">pop</span><span class="p">();</span>
<span class="n">setHealth</span><span class="p">(</span><span class="n">wizard</span><span class="p">,</span> <span class="n">amount</span><span class="p">);</span>
<span class="k">break</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">case</span> <span class="nl">INST_SET_WISDOM</span><span class="p">:</span>
<span class="k">case</span> <span class="nl">INST_SET_AGILITY</span><span class="p">:</span>
<span class="c1">// Same as above...</span>
<span class="k">case</span> <span class="nl">INST_PLAY_SOUND</span><span class="p">:</span>
<span class="n">playSound</span><span class="p">(</span><span class="n">pop</span><span class="p">());</span>
<span class="k">break</span><span class="p">;</span>
<span class="k">case</span> <span class="nl">INST_SPAWN_PARTICLES</span><span class="p">:</span>
<span class="n">spawnParticles</span><span class="p">(</span><span class="n">pop</span><span class="p">());</span>
<span class="k">break</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div>
<p>To get some values <em>onto</em> that stack, we need one more instruction: a literal.
It represents a raw integer value. But where does <em>it</em> get its value from? How
do we avoid some turtles-all-the-way-down infinite regress here?</p>
<p>The trick is to take advantage of the fact that our instruction stream is a
sequence of bytes — we can stuff the number directly in the byte array.
We define another instruction type for a number literal like so:</p>
<div class="codehilite"><pre><span></span><code><span class="k">case</span> <span class="nl">INST_LITERAL</span><span class="p">:</span>
<span class="p">{</span>
<span class="c1">// Read the next byte from the bytecode.</span>
<span class="kt">int</span> <span class="n">value</span> <span class="o">=</span> <span class="n">bytecode</span><span class="p">[</span><span class="o">++</span><span class="n">i</span><span class="p">];</span>
<span class="n">push</span><span class="p">(</span><span class="n">value</span><span class="p">);</span>
<span class="k">break</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div>
<aside name="single">
<p>Here, I’m reading a single byte for the value to avoid the fiddly code
required to decode a multiple-byte integer, but in a real implementation, you’ll
want to support literals that cover your full numeric range.</p>
</aside>
<p><img src="images/bytecode-literal.png" alt="Binary encoding of a literal instruction: 0x05 (LITERAL) followed by 123 (the value)." /></p>
<p>It reads the next <span name="single">byte</span> in the bytecode stream <em>as a
number</em> and pushes it onto the stack.</p>
<p>Let’s string a few of these instructions together and watch the interpreter
execute them to get a feel for how the stack works. We start with an empty stack
and the interpreter pointing to the first instruction:</p>
<p><img src="images/bytecode-stack-1.png" alt="Executing a bytecode sequence. The execution pointer points to the first literal instruction and the stack is empty." /></p>
<p>First, it executes the first <code>INST_LITERAL</code>. That reads the next byte from the
bytecode (<code>0</code>) and pushes it onto the stack:</p>
<p><img src="images/bytecode-stack-2.png" alt="The next step. The literal 0 has been pushed onto the stack and the execution pointer is on the next literal." /></p>
<p>Then, it executes the second <code>INST_LITERAL</code>. That reads the <code>10</code> and pushes it:</p>
<p><img src="images/bytecode-stack-3.png" alt="The next step. Now 10 has been pushed onto the stack and the execution pointer is at the Health instruction." /></p>
<p>Finally, it executes <code>INST_SET_HEALTH</code>. That pops <code>10</code> and stores it in
<code>amount</code>, then pops <code>0</code> and stores it in <code>wizard</code>. Then, it calls <code>setHealth()</code>
with those parameters.</p>
<p>Ta-da! We’ve got a spell that sets the player’s wizard’s health to ten points.
Now, we’ve got enough flexibility to define spells that set either wizard’s stats
to whatever amounts we want. We can also play different sounds and spawn
particles.</p>
<p>But… this still feels like a <em>data</em> format. We can’t, for example, raise
a wizard’s health by half of their wisdom. Our designers want to be able to
express <em>rules</em> for spells, not just <em>values</em>.</p>
<h3><a href="#behavior-=-composition" name="behavior-=-composition">Behavior = composition</a></h3>
<p>If we think of our little VM like a programming language, all it supports now is
a couple of built-in functions and constant parameters for them. To get bytecode
to feel like <em>behavior</em>, what we’re missing is <em>composition</em>.</p>
<p>Our designers need to be able to create expressions that combine different
values in interesting ways. For a simple example, they want spells that modify a
stat <em>by</em> a certain amount instead of <em>to</em> a certain amount.</p>
<p>That requires taking into account a stat’s current value. We have instructions
for <em>writing</em> a stat, but we need to add a couple to <em>read</em> stats:</p>
<div class="codehilite"><pre><span></span><code><span class="k">case</span> <span class="nl">INST_GET_HEALTH</span><span class="p">:</span>
<span class="p">{</span>
<span class="kt">int</span> <span class="n">wizard</span> <span class="o">=</span> <span class="n">pop</span><span class="p">();</span>
<span class="n">push</span><span class="p">(</span><span class="n">getHealth</span><span class="p">(</span><span class="n">wizard</span><span class="p">));</span>
<span class="k">break</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">case</span> <span class="nl">INST_GET_WISDOM</span><span class="p">:</span>
<span class="k">case</span> <span class="nl">INST_GET_AGILITY</span><span class="p">:</span>
<span class="c1">// You get the idea...</span>
</code></pre></div>
<p>As you can see, these work with the stack in both directions. They pop a
parameter to determine which wizard to get the stat for, and then they look up the stat’s
value and push that back onto the stack.</p>
<p>This lets us write spells that copy stats around. We could create a spell that
set a wizard’s agility to their wisdom or a strange incantation that set one
wizard’s health to mirror his opponent’s.</p>
<p>Better, but still quite limited. Next, we need arithmetic. It’s time our baby VM
learned how to add 1 + 1. We’ll add a few more instructions. By now, you’ve
probably got the hang of it and can guess how they look. I’ll just show
addition:</p>
<div class="codehilite"><pre><span></span><code><span class="k">case</span> <span class="nl">INST_ADD</span><span class="p">:</span>
<span class="p">{</span>
<span class="kt">int</span> <span class="n">b</span> <span class="o">=</span> <span class="n">pop</span><span class="p">();</span>
<span class="kt">int</span> <span class="n">a</span> <span class="o">=</span> <span class="n">pop</span><span class="p">();</span>
<span class="n">push</span><span class="p">(</span><span class="n">a</span> <span class="o">+</span> <span class="n">b</span><span class="p">);</span>
<span class="k">break</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div>
<p>Like our other instructions, it pops a couple of values, does a bit of work, and
then pushes the result back. Up until now, every new instruction gave us an
incremental improvement in expressiveness, but we just made a big leap. It isn’t
obvious, but we can now handle all sorts of complicated, deeply nested
arithmetic expressions.</p>
<p>Let’s walk through a slightly more complex example. Say we want a spell that
increases the player’s wizard’s health by the average of their agility and
wisdom. In code, that’s:</p>
<div class="codehilite"><pre><span></span><code><span class="n">setHealth</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="n">getHealth</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span> <span class="o">+</span>
<span class="p">(</span><span class="n">getAgility</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span> <span class="o">+</span> <span class="n">getWisdom</span><span class="p">(</span><span class="mi">0</span><span class="p">))</span> <span class="o">/</span> <span class="mi">2</span><span class="p">);</span>
</code></pre></div>
<p>You might think we’d need instructions to handle the explicit grouping that
parentheses give you in the expression here, but the stack supports that
implicitly. Here’s how you could evaluate this by hand:</p>
<ol>
<li>Get the wizard’s current health and remember it.</li>
<li>Get the wizard’s agility and remember it.</li>
<li>Do the same for their wisdom.</li>
<li>Get those last two, add them, and remember the result.</li>
<li>Divide that by two and remember the result.</li>
<li>Recall the wizard’s health and add it to that result.</li>
<li>Take that result and set the wizard’s health to that value.</li>
</ol>
<p>Do you see all of those “remembers” and “recalls”? Each “remember” corresponds
to a push, and the “recalls” are pops. That means we can translate this to
bytecode pretty easily. For example, the first line to get the wizard’s current
health is:</p>
<div class="codehilite"><pre><span></span><code>LITERAL 0
GET_HEALTH
</code></pre></div>
<p>This bit of bytecode pushes the wizard’s health onto the stack. If we
mechanically translate each line like that, we end up with a chunk of bytecode
that evaluates our original expression. To give you a feel for how the
instructions compose, I’ve done that below.</p>
<p>To show how the stack changes over time, we’ll walk through a sample execution
where the wizard’s current stats are 45 health, 7 agility, and 11 wisdom. Next
to each instruction is what the stack looks like after executing it and then a
little comment explaining the instruction’s purpose:</p>
<div class="codehilite"><pre><span></span><code>LITERAL 0 [0] # Wizard index
LITERAL 0 [0, 0] # Wizard index
GET_HEALTH [0, 45] # getHealth()
LITERAL 0 [0, 45, 0] # Wizard index
GET_AGILITY [0, 45, 7] # getAgility()
LITERAL 0 [0, 45, 7, 0] # Wizard index
GET_WISDOM [0, 45, 7, 11] # getWisdom()
ADD [0, 45, 18] # Add agility and wisdom
LITERAL 2 [0, 45, 18, 2] # Divisor
DIVIDE [0, 45, 9] # Average agility and wisdom
ADD [0, 54] # Add average to current health
SET_HEALTH [] # Set health to result
</code></pre></div>
<p>If you watch the stack at each step, you can see how data flows through it
almost like <span name="threshold">magic</span>. We push <code>0</code> for the wizard
index at the beginning, and it just hangs around at the bottom of the stack until
we finally need it for the last <code>SET_HEALTH</code> at the end.</p>
<aside name="threshold">
<p>Maybe my threshold for “magic” is a little too low here.</p>
</aside>
<h3><a href="#a-virtual-machine" name="a-virtual-machine">A virtual machine</a></h3>
<p>I could keep going, adding more and more instructions, but this is a good place
to stop. As it is, we’ve got a nice little VM that lets us define fairly
open-ended behavior using a simple, compact data format. While “bytecode” and
“virtual machines” sound intimidating, you can see they’re often as simple as a
stack, a loop, and a switch statement.</p>
<p>Remember our original goal to have behavior be nicely sandboxed? Now that you’ve
seen exactly how the VM is implemented, it’s obvious that we’ve accomplished
that. The bytecode can’t do anything malicious or reach out into weird parts of
the game engine because we’ve only defined a few instructions that touch the
rest of the game.</p>
<p>We control how much memory it uses by how big of a stack we create, and we’re
careful to make sure it can’t overflow that. We can even <span
name="looping">control how much <em>time</em></span> it uses. In our instruction loop,
we can track how many we’ve executed and bail out if it goes over some limit.</p>
<aside name="looping">
<p>Controlling execution time isn’t necessary in our sample because we don’t have
any instructions for looping. We could limit execution time by limiting the
total size of the bytecode. This also means our bytecode isn’t Turing-complete.</p>
</aside>
<p>There’s just one problem left: actually creating the bytecode. So far, we’ve
taken bits of pseudocode and compiled them to bytecode by hand. Unless you’ve
got a <em>lot</em> of free time, that’s not going to work in practice.</p>
<h3><a href="#spellcasting-tools" name="spellcasting-tools">Spellcasting tools</a></h3>
<p>One of our initial goals was to have a <em>higher</em>-level way to author behavior,
but we’ve gone and created something <em>lower</em>-level than C++. It has the runtime
performance and safety we want, but absolutely none of the designer-friendly
usability.</p>
<p>To fill that gap, we need some tooling. We need a program that lets users define
the high-level behavior of a spell and then takes that and generates the
appropriate low-level stack machine bytecode.</p>
<p>That probably sounds way harder than making the VM. Many programmers were
dragged through a compilers class in college and took away from it nothing but
PTSD triggered by the sight of a <span name="dragon">book</span> with a dragon
on the cover or the words “<a href="http://en.wikipedia.org/wiki/Lex_(software)">lex</a>”
and “<a href="http://en.wikipedia.org/wiki/Yacc">yacc</a>”.</p>
<aside name="dragon">
<p>I’m referring, of course, to the classic text <a href="http://en.wikipedia.org/wiki/Compilers:_Principles,_Tech
niques,_and_Tools"><em>Compilers: Principles,
Techniques, and Tools</em></a>.</p>
</aside>
<p>In truth, compiling a text-based language isn’t that bad, though it’s a <em>bit</em>
too broad of a topic to cram in here. However, you don’t have to do that. What I
said we need is a <em>tool</em> — it doesn’t have to be a <em>compiler</em> whose input
format is a <em>text file</em>.</p>
<p>On the contrary, I encourage you to consider building a graphical interface to
let users define their behavior, especially if the people using it won’t be
highly technical. Writing text that’s free of syntax errors is difficult for
people who haven’t spent years getting used to a compiler yelling at them.</p>
<p>Instead, you can build an app that lets users “script” by clicking and dragging
little boxes, pulling down menu items, or whatever else makes sense for the
kind of behavior you want them to create.</p>
<p><span name="text"></span></p>
<p><img src="images/bytecode-ui.png" alt="A mock-up of a little tree-based UI for authoring behavior." /></p>
<aside name="text">
<p>The scripting system I wrote for <a href="http://en.wikipedia.org/wiki/Henry_Hatsworth_in_the_Puzzling_Adventure">Henry Hatsworth in the Puzzling
Adventure</a> worked like this.</p>
</aside>
<p>The nice thing about this is that your UI can make it impossible for users to
create <span name="errors">“invalid”</span> programs. Instead of vomiting error
messages on them, you can proactively disable buttons or provide default
values to ensure that the thing they’ve created is valid at all points in time.</p>
<aside name="errors">
<p>I want to stress how important error-handling is. As programmers, we tend to
view human error as a shameful personality flaw that we strive to eliminate in
ourselves.</p>
<p>To make a system that users enjoy, you have to embrace their humanity,
<em>including their fallibility</em>. Making mistakes is what people do, and is a
fundamental part of the creative process. Handling them gracefully with features
like undo helps your users be more creative and create better work.</p>
</aside>
<p>This spares you from designing a grammar and writing a parser for a little
language. But, I know, some of you find UI programming equally unpleasant. Well,
in that case, I don’t have any good news for you.</p>
<p>Ultimately, this pattern is about expressing behavior in a user-friendly,
high-level way. You have to craft the user experience. To execute the behavior
efficiently, you then need to translate that into a lower-level form. It is real
work, but if you’re up to the challenge, it can pay off.</p>
<h2><a href="#design-decisions" name="design-decisions">Design Decisions</a></h2>
<p>I <span name="failed">tried</span> to keep this chapter as simple as I could,
but what we’re really doing is creating a language. That’s a pretty open-ended
design space. Exploring it can be tons of fun, so make sure you don’t forget to
finish your game.</p>
<aside name="failed">
<p>Since this is the longest chapter in the book, it seems I failed that task.</p>
</aside>
<h3><a href="#how-do-instructions-access-the-stack" name="how-do-instructions-access-the-stack">How do instructions access the stack?</a></h3>
<p>Bytecode VMs come in two main flavors: stack-based and register-based. In a
stack-based VM, instructions always work from the top of the stack, like in our
sample code. For example, <code>INST_ADD</code> pops two values, adds them, and pushes the
result.</p>
<p>Register-based VMs still have a stack. The only difference is that instructions
can read their inputs from deeper in the stack. Instead of <code>INST_ADD</code> always <em>popping</em>
its operands, it has two indexes stored in the bytecode that identify where in
the stack to read the operands from.</p>
<ul>
<li>
<p><strong>With a stack-based VM:</strong></p>
<ul>
<li>
<p><em>Instructions are small.</em> Since each instruction implicitly finds its
arguments on top of the stack, you don’t need to encode any data for
that. This means each instruction can be pretty small, usually a single
byte.</p>
</li>
<li>
<p><em>Code generation is simpler.</em> When you get around to writing the
compiler or tool that outputs bytecode, you’ll find it simpler to
generate stack-based bytecode. Since each instruction implicitly works
from the top of the stack, you just need to output instructions in the
right order to pass parameters between them.</p>
</li>
<li>
<p><em>You have more instructions.</em> Each instruction only sees the very top of
the stack. This means that to generate code for something like <code>a = b +
c</code>, you need separate instructions to move <code>b</code> and <code>c</code> to the top of the
stack, perform the operation, then move the result into <code>a</code>.</p>
</li>
</ul>
</li>
<li>
<p><strong>With a register-based VM:</strong></p>
<ul>
<li>
<p><em>Instructions are larger.</em> Since instructions need arguments for stack
offsets, a single instruction needs more bits. For example, an
instruction in <span name="lua">Lua</span> — probably the most
well-known register-based VM — is a full 32-bits. It uses 6 bits for
the instruction type, and the rest are arguments.</p>
<aside name="lua">
<p>The Lua folks don’t specify Lua’s bytecode format, and it changes from version to
version. What I’m describing here is true as of Lua 5.1. For an
absolutely amazing deep dive into Lua’s internals, read <a href="http://lu
aforge.net/docman/83/98/ANoFrillsIntroToLua51VMInstructions.pdf">this</a>.</p>
</aside>
</li>
<li>
<p><em>You have fewer instructions.</em> Since each instruction can do more work,
you don’t need as many of them. Some say you get a performance
improvement since you don’t have to shuffle values around in the stack
as much.</p>
</li>
</ul>
</li>
</ul>
<p>So which should you do? My recommendation is to stick with a stack-based VM.
They’re simpler to implement and much simpler to generate code for.
Register-based VMs got a reputation for being a bit faster after Lua converted
to that style, but it depends <em>deeply</em> on your actual instructions and on lots of
other details of your VM.</p>
<h3><a href="#what-instructions-do-you-have" name="what-instructions-do-you-have">What instructions do you have?</a></h3>
<p>Your instruction set defines the boundaries of what can and cannot be expressed
in bytecode, and it also has a big impact on the performance of your VM. Here’s a
laundry list of the different kinds of instructions you may want:</p>
<ul>
<li>
<p><strong>External primitives.</strong> These are the ones that reach out of the VM into
the rest of the game engine and do stuff that the user can see. They control
what kinds of real behavior can be expressed in bytecode. Without these,
your VM can’t do anything more than burn CPU cycles.</p>
</li>
<li>
<p><strong>Internal primitives.</strong> These manipulate values inside the VM — things
like literals, arithmetic, comparison operators, and instructions that juggle
the stack around.</p>
</li>
<li>
<p><strong>Control flow.</strong> Our example didn’t cover these, but when you want behavior
that’s imperative and conditionally executes instructions or loops and
executes instructions more than once, you need control flow. In the
low-level language of bytecode, they’re surprisingly simple: jumps.</p>
<p>In our instruction loop, we had an index to track where we were in the
bytecode. All a jump instruction does is modify that variable and change
where we’re currently executing. In other words, it’s a <code>goto</code>. You can
build all kinds of higher-level control flow using that.</p>
</li>
<li>
<p><strong>Abstraction.</strong> If your users start defining a <em>lot</em> of stuff in data,
eventually they’ll want to start reusing bits of bytecode instead of having
to copy and paste it. You may want something like callable procedures.</p>
<p>In their simplest form, procedures aren’t much more complex than a jump. The only
difference is that the VM maintains a second <em>return</em> stack. When it
executes a “call” instruction, it pushes the current instruction index onto
the return stack and then jumps to the called bytecode. When it hits a “return”,
the VM pops the index from the return stack and jumps back to it.</p>
</li>
</ul>
<h3><a href="#how-are-values-represented" name="how-are-values-represented">How are values represented?</a></h3>
<p>Our sample VM only works with one kind of value, integers. That makes answering this easy —
the stack is just a stack of <code>int</code>s. A more full-featured VM will support
different data types: strings, objects, lists, etc. You’ll have to decide how
those are stored internally.</p>
<ul>
<li>
<p><strong>A single datatype:</strong></p>
<ul>
<li>
<p><em>It’s simple.</em> You don’t have to worry about tagging, conversions, or
type-checking.</p>
</li>
<li>
<p><em>You can’t work with different data types.</em> This is the obvious downside.
Cramming different types into a single representation — think storing
numbers as strings — is asking for pain.</p>
</li>
</ul>
</li>
<li>
<p><strong>A tagged variant:</strong></p>
<p>This is the common representation for dynamically typed languages. Every
value has two pieces. The first is a type tag — an <code>enum</code> — that identifies
what data type is being stored. The rest of the bits are then interpreted
appropriately according to that type, like:</p>
<div class="codehilite"><pre><span></span><code><span class="k">enum</span> <span class="nc">ValueType</span>
<span class="p">{</span>
<span class="n">TYPE_INT</span><span class="p">,</span>
<span class="n">TYPE_DOUBLE</span><span class="p">,</span>
<span class="n">TYPE_STRING</span>
<span class="p">};</span>
<span class="k">struct</span> <span class="nc">Value</span>
<span class="p">{</span>
<span class="n">ValueType</span> <span class="n">type</span><span class="p">;</span>
<span class="k">union</span>
<span class="p">{</span>
<span class="kt">int</span> <span class="n">intValue</span><span class="p">;</span>
<span class="kt">double</span> <span class="n">doubleValue</span><span class="p">;</span>
<span class="kt">char</span><span class="o">*</span> <span class="n">stringValue</span><span class="p">;</span>
<span class="p">};</span>
<span class="p">};</span>
</code></pre></div>
<ul>
<li>
<p><em>Values know their type.</em> The nice thing about this representation is
that you can check the type of a value at runtime. That’s important for
dynamic dispatch and for ensuring that you don’t try to perform operations on
types that don’t support it.</p>
</li>
<li>
<p><em>It takes more memory.</em> Every value has to carry around a few extra bits
with it to identify its type. In something as low-level as a VM, a few
bits here and there add up quickly.</p>
</li>
</ul>
</li>
<li>
<p><strong>An untagged union:</strong></p>
<p>This uses a union like the previous form, but it does <em>not</em> have a type tag
that goes along with it. You have a little blob of bits that could represent
more than one type, and it’s up to you to ensure you don’t misinterpret
them.</p>
<p>This is how <span name="untyped">statically typed</span> languages represent
things in memory. Since the type system ensures at compile time that you
aren’t misinterpreting values, you don’t need to validate it at runtime.</p>
<aside name="untyped">
<p>This is also how <em>untyped</em> languages like assembly and Forth store values.
Those languages leave it to the <em>user</em> to make sure they don’t write code
that misinterprets a value’s type. Not for the faint of heart!</p>
</aside>
<ul>
<li>
<p><em>It’s compact.</em> You can’t get any more efficient than storing just the
bits you need for the value itself.</p>
</li>
<li>
<p><em>It’s fast.</em> Not having type tags implies you’re not spending cycles
checking them at runtime either. This is one of the reasons
statically typed languages tend to be faster than dynamic ones.</p>
</li>
<li>
<p><em>It’s unsafe.</em> <span name="unsafe">This</span> is the real cost, of
course. A bad chunk of bytecode that causes you to misinterpret a value and
treat a number like a pointer or vice versa can violate the security of
your game or make it crash.</p>
<aside name="unsafe">
<p>If your bytecode was compiled from a statically typed language, you
might think you’re safe here because the compiler won’t generate unsafe
bytecode. That may be true, but remember that malicious users may hand-craft
evil bytecode without going through your compiler.</p>
<p>That’s why, for example, the Java Virtual Machine has to do <em>bytecode
verification</em> when it loads a program.</p>
</aside>
</li>
</ul>
</li>
<li>
<p><strong>An interface:</strong></p>
<p>The object-oriented solution for a value that maybe be one of several
different types is through polymorphism. An interface provides virtual
methods for the various type tests and conversions, along the lines of:</p>
<div class="codehilite"><pre><span></span><code><span class="k">class</span> <span class="nc">Value</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
<span class="k">virtual</span> <span class="o">~</span><span class="n">Value</span><span class="p">()</span> <span class="p">{}</span>