Sebastien St-Laurent

Thomson Course Technology PTR

The Premier Press and Thomson Course Technology PTR logo and related
trade dress are trademarks of Thomson Course Technology PTR and may not
be used without written permission.
NVIDIA® is a registered trademark of NVIDIA Corporation.
RenderMonkey™ is a trademark of ATI Technologies, Inc.
DirectX® is a registered trademark of Microsoft Corporation.
All other trademarks are the property of their respective owners.

Shaders for Game Programming and Artists

Acknowledgments
First and foremost, I want to thank my wife Nicole for all of her support throughout
this project.Writing a book can be a major undertaking, and without her help
and love, I would never have completed this one or might have lost my sanity doing so. I love you!

I also want to extend a big thanks to the Thomson Course Technology PTR team, first for
giving me the opportunity to write this book, but also for all your help and support in making it come true.

Mathieu Mazerolle also deserves special mention for his efforts as a longtime friend and
technical editor. His help proved invaluable in making sure I was in line and ensuring this
book was the best possible book it could be. I also want to send my thanks to the kind people
at NVIDIA and ATI Technologies for their technical information, which helped
immensely with this production.

Finally, I want to thank everyone who has taught me in some way, including the awesome
teachers at Sherbrooke University and, more importantly, Larry Landry and Glen Eagan
for offering me an internship as part of the video game industry; thus launching my career.

About the Author
SEBASTIEN ST-LAURENT has been programming games professionally for several years,
working on titles for the Xbox, PlayStation 2, GameCube, and PC. He started in the video
game industry while studying computer engineering at Sherbrooke University in Sherbrooke,
Quebec. By interning in a small company called Future Endeavors during his college
years, he got into the industry and stood out in the line of graphics engineering.
After graduating from college, he moved to California to work full time with Z-Axis as
lead Xbox engineer, where he worked on several titles including the Dave Mirra Freestyle
BMX series. He is a graphics engineer in the ACES group at Microsoft, Inc, where he is
currently working on the next incarnation of Microsoft’s Flight Simulator product.

About the Series Editor
ANDRÉ LAMOTHE, CEO, Xtreme Games LLC, has been involved in the computing
industry for more than 25 years. He wrote his first game for the TRS-80 and has been
hooked ever since! His experience includes 2D/3D graphics, AI research at NASA, compiler
design, robotics, virtual reality, and telecommunications. His books are top sellers
in the game programming genre, and his experience is echoed in the Thomson Course
Technology PTR Game Development series.


Introduction

During the summer of 2003, I was approached by André LaMothe to write a book

on the topic of shaders. My experience on the PC and Xbox and writing game

engines and shader architectures made me a great candidate for such an

endeavor. Having always wanted to write a technical book, I simply could not resist and

jumped into this great adventure.

My first task was to determine the approach I would take in writing this book. At that

time, there were already several books available on the topic of shaders, and I felt the need

to innovate and explore this topic in a form not done before. One of my gripes with many

of the books already in print was that they all spent so much time explaining how to use

rendering APIs, such as DirectX, and little time making shaders. This is where the idea of

using ATI’s RenderMonkey came into being. This new tool offered a rich set of features,

allowing the quick, easy, and intuitive development of shaders.

I set off to do a brain dump of all my shader knowledge, taking advantage of

RenderMonkey to make the learning process even easier. Throughout this book, you

can expect to spend most of your time learning about shaders and how to create them. I

do not just focus on the basics; several useful techniques, from basic to advanced, are presented

in a straightforward manner aimed at allowing you to quickly absorb and apply the

knowledge you gain from this book.

Who Should Read This Book

The topic of Shaders for Game Programmers and Artists is shader development; therefore,

the book is written for anybody who has some interest in the topic. Because the topics and

techniques covered throughout this book are so varied, it is bound to be of interest to

everybody from hobbyist programmers to professional shader developers.

The approach I take in this book, using RenderMonkey, allows the content to be distanced

from rendering APIs, such as DirectX or OpenGL. This allows you, the reader, to focus

essentially on shader development and not on the development of framework applications.

My approach to this book has the added advantage of making shader development

available not only to engineers but also to technically minded artists.

Finally, with the approach taken throughout this book and the extensive exercises at the

end of each chapter, Shaders for Game Programmers and Artists can also be a valuable asset

in the classroom where real-time graphics have taken an even more important place in the

computer science curriculum.

What Will Be Covered (And What Won’t)

The topic of Shaders for Game Programmers and Artists is shaders, and it is all I will focus

on. I will explain a variety of techniques that cover a wide range of topics, from image filtering

to advanced lighting techniques. The following list summarizes some of the topics

covered in this book:

■ Introduction to several basic shader-related topics, including shaders, their history,

and extensive documentation on how to use RenderMonkey and develop shaders

using the HLSL shader language.

■ An extensive set of screen-based techniques that can be used to enhance existing

scenes. This book covers simple techniques, including everything from basic color

filters to more advanced topics such as depth of field, heat shimmer, and highdynamic

range rendering.

■ Lighting techniques ranging from simple per-vertex and per-pixel lighting

approaches to more advanced topics such as bumpmapping, spherical harmonics,

and polynomial texture maps.

■ The rendering of varying materials is also covered through several techniques

ranging from bi-directional refractance functions to procedural materials.

With this in mind, all shaders are developed making use of the RenderMonkey platform.

This tool, developed by ATI Technologies, provides an easy-to-use framework for shader

development. This approach allows you to focus solely on shaders and not on any specific

APIs or the writing of framework code.

The preceding paragraph implies what we will not cover in this book. Because I want to

focus solely on shader development, I will not go into any detail regarding general C/C++

programming; nor will I go into detail about how any of the rendering APIs work.

In simple words, this book covers shaders, using both RenderMonkey and the HLSL shader language.

Exercises

To facilitate the learning process throughout your reading of this book, I have included

several exercises at the end of each chapter in a section called “It’s Your Turn.” These exercises

invite you to expand upon the shaders developed throughout the chapters and

increase your understanding of shaders. Extensive solutions to each exercise are to be

found in Appendix D, “Exercise Solutions.”

Support

Finally, a Web site is maintained at http://www.courseptr.com that provides support for

this book. This site will be updated regularly to post errata and updates to the example

programs as needed. Be sure to check it if you have any problems.

And if you have any questions or comments about this book, feel free to contact me,

Sebastien St-Laurent, at sebastien_st_laurent@hotmail.com.

Screenshot

Purchase Now !
Just with Paypal

Product details

Price
File Size	9,908 KB
Pages	513 p
File Type	PDF format
ISBN	1-59200-092-4
Copyright	2004 by Thomson Course Technology PTR

Contents at a Glance
Introduction
Part I From the Ground Up
Chapter 1 Welcome to the World of Shaders
Chapter 2 The Art of 3D
Chapter 3 RenderMonkey Version 1.5
Chapter 4 Getting Started, Your First Shaders
Part II Screen Effects
Chapter 5 Looking Through a Filter
Chapter 6 Blurring Things Up
Chapter 7 It’s Getting Hot in Here
Chapter 8 Making Your Day Brighter
Part III Making It Look Real 
Chapter 9 May There Be Light
Chapter 10 Shiny Little Pixels
Chapter 11 Mirror, Mirror, On the Wall
Chapter 12 Not All Materials Are the Same
Chapter 13 Building Materials from Scratch
Chapter 14 Why Does It Always Need to Look Real?
Part IV Advanced Topics
Chapter 15 Watch Out for That Morning Fog
Chapter 16 Moving Objects Around
Chapter 17 Advanced Lighting
Chapter 18 Shadowing
Chapter 19 Geometry Tricks
Part V Appendixes
Appendix A High-Level Shader Language Reference
Appendix B Render Monkey 1.5 User Manual
Appendix C What’s on the CD
Appendix D Exercise Solutions
Appendix E Shader Library
Index

Table of Contents

Introduction . . . .. . . . . . xxi

Part I From the Ground Up . . . . .. . . . . 1

Chapter 1 Welcome to the World of Shaders . . . . .. . . . . . . . . 3

Prerequisites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Vertex and Pixel Shader Pipelines and Capabilities . . . . . . . . . . . . . . . 6

Tool Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

RenderMonkey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

Microsoft Texture Tool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

NVIDIA Photoshop Plug-In . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3D Studio Max . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

Microsoft Effect Editor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

NVIDIA’s Cg Toolkit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

It’s Your Turn! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

What’s Next? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

Chapter 2 The Art of 3D. . . . . . . .  . . . . . . . . . . . 19

From the Ground Up. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

Looking at Our Universe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

Translation Matrix. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

Scale Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

Rotation Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

Viewing It from a Camera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

Under the Hood . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3D APIs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

OpenGL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

DirectX and Direct3D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

Which One Is Better? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

Hardware Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

Shaders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

It’s Your Turn! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

What’s Next? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

Chapter 3 RenderMonkey Version 1.5 . . . . . .. . . . . . . . 37

Introduction to RenderMonkey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

Our First Look at RenderMonkey . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

Autopsy of a Shader . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

It’s Your Turn! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

What’s Next? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

Chapter 4 Getting Started, Your First Shaders. . . .  . . . . . 51

Your First Shader . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

Texturing Your Object . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

Seeing Double . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

It’s Your Turn! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

Exercise 1: ANIMATING A TEXTURE . . . . . . . . . . . . . . . . . . . . . . . 64

Exercise 2: BLENDING TWO TEXTURES . . . . . . . . . . . . . . . . . . . . . 64

What’s Next? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

Part II Screen Effects. . . . .. . . . . 65

Chapter 5 Looking Through a Filter . . . . . . . . . . . . . . . 67

Rendering to a Sketchpad. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

Texture Coordinates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

Finally Rendering Your Render Target . . . . . . . . . . . . . . . . . . . . . 74

Don’t Adjust Your TV! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

Black and White, Like in the Old Times . . . . . . . . . . . . . . . . . . . . 75

Generalizations Are Good! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

Things Are Not Always Linear . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

Blurring Things Up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

Bring on the Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

Motion Blur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

Building the Motion Blur Shader . . . . . . . . . . . . . . . . . . . . . . . . . 86

It’s Your Turn! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

Exercise 1: OLD TIME MOVIE . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

Exercise 2: GAUSS FILTER . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

What’s Next? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

Chapter 6 Blurring Things Up. . . . . .. . . . . . . . . . . 89

What Is Depth of Field? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

It’s All About Faking It! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

Blurring Things, Take Two . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

Depth Impostors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

A Note About Z-Buffers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

Using the Alpha Channel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

A Note About Multiple Render Targets . . . . . . . . . . . . . . . . . . . 106

Doing It Twice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

What About the Z-Buffer? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

Special Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

It’s Your Turn! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

Exercise 1: MULTIPLE IMPOSTORS. . . . . . . . . . . . . . . . . . . . . . . . 113

Exercise 2: USING A LOOKUP TEXTURE. . . . . . . . . . . . . . . . . . . . 113

Exercise 3: USING INTERMEDIATE BLUR TEXTURES

TO CREATE A SMOOTHER TRANSITION . . . . . . . . . . . . . . . . . . . 114

What’s Next? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

Chapter 7 It’s Getting Hot in Here . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

What Is Heat Haze?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

Uses for Heat Haze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

It’s All About Distortion Maps . . . . . . . . . . . . . . . . . . . . . . . . . . 118

Putting a Background to Your Shader . . . . . . . . . . . . . . . . . . . . 120

Hitting the Pavement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

Looking Above the Flame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

It’s Your Turn! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

Exercise 1: YOUR OWN REFRACTION SHADER . . . . . . . . . . . . . . 132

Exercise 2: MAKING IT MORE LIVELY . . . . . . . . . . . . . . . . . . . . . 132

What’s Next? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

Chapter 8 Making Your Day Brighter. . . . . . . . . . . . . . . . . . . . . . . . . 133

What Is High Dynamic Range? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

Glare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

Streaks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

Lens Flares. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

A Few HDR Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

What About Floating-Point Textures? . . . . . . . . . . . . . . . . . . . . 136

Exposure Control: The First Step. . . . . . . . . . . . . . . . . . . . . . . . . 136

A Note on Automatic Exposure Control . . . . . . . . . . . . . . . . . . . 139

Time for Some High Dynamic Range Effects . . . . . . . . . . . . . . . . . . . 139

Your First HDR Shader: The Glare! . . . . . . . . . . . . . . . . . . . . . . . 139

Time for Some Streaking! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

Lens Flare Free-for-All. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

Putting It All Together . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

Solutions for Today’s Hardware. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

It’s Your Turn! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

Exercise 1: USING A BIG FILTER . . . . . . . . . . . . . . . . . . . . . . . . . . 152

Exercise 2: STREAKING ON TODAY’S HARDWARE . . . . . . . . . . . 152

What’s Next? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

Part III Making It Look Real . . . . . . . . . . . . . . . . 153

Chapter 9 May There Be Light . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

Of Light and Magic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

What Makes Light in the First Place . . . . . . . . . . . . . . . . . . . . . . 156

Types of Lights. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162

Directional Light . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162

Point Lights . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164

Spot Lights . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

Area Lights . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

Let’s Get Shading. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

Ambient Lighting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168

Diffuse Lighting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169

Specular Lighting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171

Putting It Together . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174

It’s Your Turn! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

Exercise 1: DIRECTION LIGHTS. . . . . . . . . . . . . . . . . . . . . . . . . . . 177

Exercise 2: ANIMATING LIGHTS . . . . . . . . . . . . . . . . . . . . . . . . . . 177

What’s Next? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

Chapter 10 Shiny Little Pixels. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

Why Isn’t Vertex Lighting Enough?. . . . . . . . . . . . . . . . . . . . . . . . . . 179

Basic Pixel Lighting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180

Diffuse Lighting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

Specular Lighting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184

Putting It All Together . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187

Giving You Goose Bumps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189

Bumpmapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190

Tangent Space. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191

Normal Maps. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

It’s Your Turn! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197

Exercise 1: DIRECTION LIGHTS. . . . . . . . . . . . . . . . . . . . . . . . . . . 197

Exercise 2: MULTIPLE LIGHTS. . . . . . . . . . . . . . . . . . . . . . . . . . . . 197

What’s Next? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197

Chapter 11 Mirror, Mirror, On the Wall . . . . . . . . . . . . . . . . . . . . . . . . 199

From Reflections to Refractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199

Reflections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203

Refraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206

Walking Hand in Hand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209

Building Dynamic Environment Maps . . . . . . . . . . . . . . . . . . . . . . . . 212

It’s Your Turn! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213

Exercise 1: DOING IT ALL PER-PIXEL . . . . . . . . . . . . . . . . . . . . . . 213

Exercise 2: COLOR-BASED REFRACTION . . . . . . . . . . . . . . . . . . . 214

What’s Next? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214

Chapter 12 Not All Materials Are the Same. . . . . . . . . . . . . . . . . . . . . 215

BRDFs Are Your Friends . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217

Soft and Velvety . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218

Determining BRDFs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222

Oren-Nayer Velvet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224

It’s Your Turn! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227

Exercise 1: USING LOOKUP TEXTURES . . . . . . . . . . . . . . . . . . . . 227

Exercise 2: MULTIPLE BRDFs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228

What’s Next? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228

Chapter 13 Building Materials from Scratch . . . . . . . . . . . . . . . . . . . . 229

Turning Up the Noise! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230

Clouds, Clouds in the Sky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236

Wood and Marble. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237

Using Noise to Move Things Around . . . . . . . . . . . . . . . . . . . . . 240

It’s Your Turn! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

Exercise 1: ANIMATING CLOUDS . . . . . . . . . . . . . . . . . . . . . . . . . 242

Exercise 2: RENDERING STRATA . . . . . . . . . . . . . . . . . . . . . . . . . 242

What’s Next? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243

Chapter 14 Why Does It Always Need to Look Real? . . . . . . . . . . . . . 245

Just Like a Television Cartoon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246

Outline Rendering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246

Other Outlining Ideas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250

Toon Shading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252

Real-Time Hatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256

It’s Your Turn! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259

Exercise 1: DEPTH-BASED OUTLINE. . . . . . . . . . . . . . . . . . . . . . . 259

Exercise 2: SILHOUETTE AND TOON SHADING . . . . . . . . . . . . . . 260

What’s Next? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260

Part IV Advanced Topics. . . . . . . . . . . . . . . . . . 261

Chapter 15 Watch Out for That Morning Fog . . . . . . . . . . . . . . . . . . . 263

The Basics of Fog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263

Hardware Fog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265

Not Just Your Everyday Fog . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269

Giving Your Fog a Little Depth . . . . . . . . . . . . . . . . . . . . . . . . . . 271

Rendering the Atmosphere. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277

It’s Your Turn! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279

Exercise 1: ROUND FOG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279

What’s Next? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279

Chapter 16 Moving Objects Around . . . . . . . . . . . . . . . . . . . . . . . . . . 281

Light, Camera, Action! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281

Object Metamorphosis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283

Of Skin and Bones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287

It’s Your Turn! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290

What’s Next? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290

Chapter 17 Advanced Lighting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291

Outdoor Scene Lighting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292

Some General Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292

Hemisphere Lighting Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294

Polynomial Texture Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297

Combining BRDF and Bumpmapping . . . . . . . . . . . . . . . . . . . . . 297

Building the Shader . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299

Spherical Harmonics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301

The Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302

Lighting with Spherical Harmonics . . . . . . . . . . . . . . . . . . . . . . . 304

It’s Your Turn! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306

Exercise 1: PER-PIXEL SPHERICAL HARMONICS . . . . . . . . . . . . . . 306

What’s Next? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306

Chapter 18 Shadowing. . . . . . . . .. . . . . . . . . . . . 309

The Basics of Shadows. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310

Shadow Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312

Shadow Volumes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320

Taking Advantage of the Hardware . . . . . . . . . . . . . . . . . . . . . . 323

It’s Your Turn! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325

Exercise 1: SOFT SHADOW MAPPING . . . . . . . . . . . . . . . . . . . . . 325

What’s Next? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326

Chapter 19 Geometry Tricks .. . . . . . . . . . . . . . 327

Level of Detail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328

Static LOD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328

Progressive LOD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331

Re-Creating Lost Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334

Displacement Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336

It’s Your Turn! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337

What’s Next? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338

Part V Appendixes . . . . . . . . . . . . . . . . . . . . . . 341

Appendix A High-Level Shader Language Reference . . . . . . . . . . . . . . 343

Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344

Scalar Types. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344

Vector Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344

Matrix Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345

Structure Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346

Predefined Types. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346

Typecasts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347

Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348

Statements. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349

Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349

Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349

User-Defined Functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351

Built-In Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352

Appendix B RenderMonkey Version 1.5 User Manual . . . . . . . . . . . . . 379

Installation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380

Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380

Installing RenderMonkey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381

Using RenderMonkey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381

Application Toolbar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381

Application Menu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382

Workspace View . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385

Application Preferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394

Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395

Where Do We Go from Here? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401

Appendix C What’s on the CD. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403

Source Code. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403

RenderMonkey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404

High Resolution Illustrations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404

DirectX 9.0 SDK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404

NVIDIA Texture Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404

NVIDIA Photoshop Plug-In . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405

Appendix D Exercise Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407

Appendix E Shader Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451

Basic Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451

Object Transformation and Projection . . . . . . . . . . . . . . . . . . . . 451

Basic Texturing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452

Color Modulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452

Depth Encoding and Decoding. . . . . . . . . . . . . . . . . . . . . . . . . . 452

Screen Effects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453

Rendering to a Full Screen Quad . . . . . . . . . . . . . . . . . . . . . . . . 453

Color Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454

Basic Filtering Pixel Shader . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454

Box Blur Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455

Gauss Blur Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455

Edge Detection Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456

Lighting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457

Diffuse Lighting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457

Specular Lighting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457

Tangent Space Lighting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458

Per-Pixel Bumpmapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459

Polynomial Texture Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . 460

Spherical Harmonics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461

Reflection and Refraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462

Reflection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462

Refraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462

Materials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462

Velvet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463

Oren-Nayer Lighting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463

Basic Perlin Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464

Marble and Wood Noise Materials . . . . . . . . . . . . . . . . . . . . . . . 465

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467

  ●▬▬▬▬▬❂❂❂▬▬▬▬▬●

●▬▬❂❂▬▬●

●▬❂▬●

●❂●

═════● ●═════

Alex Varanese

Premier Press, a division of Course Technology

Publisher: Stacy L. Hiquet
Marketing Manager: Heather Hurley
Acquisitions Editor: Mitzi Koontz
Series Editor: André LaMothe
Project Editor: Estelle Manticas
Copy Editor: Kezia Endsley
Interior Layout: Bill Hartman
Cover Designer: Mike Tanamachi
Indexer: Kelly Talbot
Proofreader: Sara Gullion

Game Scripting Mastery

Acknowledgments
It all started as I was standing around with some friends of mine on the second day of the 2001
Xtreme Game Developer's Conference in Santa Clara, California, discussing the Premier Press
game development series. At the time, I'd been doing a lot of research on the subject of compiler
theory—specifically, how it could be applied to game scripting—and at the exact moment I mentioned
that a scripting book would be a good idea, André Lamothe just happened to walk by.
"Let's see what he thinks," I said, and pulled him aside. "Hey André, have you ever thought about
a book on game scripting for your series?" I expected something along the lines of "that's not a
bad idea", or "sure-- it's already in production." What I got was surprising, to say the least.
"Why don't you write it?"

That was literally what he said. Unless you're on some sort of weird version of Jeopardy! where the
rules of the game require you to phrase your answer in the form of a book deal, this is a pretty
startling response. I blinked, thought about it for about a nanosecond, and immediately said
okay. This is how I handle most important decisions, but the sheer magnitude of the events that
would be set into motion by this particular one could hardly have been predicted at the time.
Never question the existence of fate.

With the obligatory anecdote out of the way, there are a number of very important people I'd like
to thank for providing invaluable support during the production of this book. It'd be nothing
short of criminal if this list didn't start with Mitzi Foster, my acquisitions editor who demonstrated
what can only be described as superhuman patience during the turbulent submission and evolution
of the book's manuscript. Having to handle the eleventh-hour rewrites of entire chapters
(and large ones at that) after they've been submitted and processed is an editor's nightmare—
and only one of the many she put up with—but she managed to handle it in stride, with a consistently
friendly and supportive attitude.

Next up is my copy editor, Kezia Endsley; if you notice the thorough grammatical correctness of
even the comments in this book's code listings, you'll have her to thank. Granted, it'll only be a
matter of time before the latest version of Microsoft's compilers have a comment grammar checking
paperclip, dancing monkey, robot dog, or ethnically ambiguous baby, but her eye for detail is
safely appreciated for now.

Lastly, rounding out the Game Scripting Mastery pit crew is Estelle Manticas, my project editor
who really stepped up to the plate during the later parts of the project, somehow maintaining a
sense of humor while planet Earth crumbled around us. Few people have what it takes to manage
the workload of an entire book when the pressure's on, and she managed to make it look easy.
Of course, due to my relatively young age and penchant for burning through cash like NASA, I've
relied on others to provide a roof over my head. The honor here, not surprisingly, goes to my
parents. I'd like to thank my mom for spreading news of my book deal to every friend, relative,
teacher, and mailman our family has ever known, and my dad for deciding that the best time to
work so loudly on rebuilding the deck directly outside my room is somewhere around zero o'clock
in the morning. I also can't forget my sister, Katherine—her constant need for me to drive her to
work is the only thing that keeps me waking up at a decent hour. Thanks a lot, guys!
And last, and most certainly least, I suppose I should thank that Lamothe guy. Seriously though—I
may have toiled endlessly on the code and manuscript, but André is the real reason this book
happened (and was also its technical editor). I've gotta say thanks for letting my raid your fridge
on a regular basis, teaching me everything I know about electrical engineering, dumping so many
free books on me, answering my incessant and apparently endless questions, restraining yourself
from ending our more heated arguments with a golf club, and of course, extending such an
obscenely generous offer to begin with. It should be known that there's literally no one else in
the industry that goes out of their way to help people out this much, and I'm only one of many
who've benefited from it.

I'd also like to give a big thanks to John Romero, who took time out of his understandably
packed schedule to save the day and write the book's Foreword. If not for him, I probably
would've had to get my mom to do it.

Oh and by the way, just because I think they'll get a kick out of it, I'd like to close with some horrendously
geeky shout-outs: thanks to Ironblayde, xms and Protoman—three talented coders,
and the few people I actually talk to regularly online—for listening to my constant ranting, and
encouraging me to finish what I start (if for no other reason than the fact that I'll stop blabbering
about it). You guys suck. Seriously.

Now if you'll excuse me, I'm gonna wrap this up. I feel like I'm signing a yearbook.


About the Author
Alex Varanese has been obsessed with game development since the mid-1980's when, at age five,
he first laid eyes—with both fascination and a strange and unexplainable sense of familiarity—on
the 8-bit Nintendo Entertainment System. He's been an avid artist since birth as well, but didn't
really get going as a serious coder until later in life, at around age 15, with QBASIC. He got his
start as a professional programmer at age 18 as a Java programmer in the Silicon Valley area,
working on a number of upstart B2B projects on the J2EE platform before working for about a
year as both a semi-freelance and in-house graphic designer.

Feeling that life in the office was too restrictive, however, he's since shifted his focus back to game
development and the pursuit of future technology. He currently holds the position of head
designer and systems architect for eGameZone (http://www.egamezone.net), the successor venture
to André LaMothe's Xtreme Games LLC. He spends his free time programming, rendering, writing
about himself in the third person, yelling at popup ads, starring in an off-Broadway production
of Dude, Where's My Car? The Musical, and demonstrating a blatant disregard for the posted speed limit.
Alex Varanese can be reached at alex@amvbooks.com, and is always ready and willing to answer any
questions you may have about the book. Please, don't hesitate to ask!


Introduction

If you've been programming games for any reasonable amount of time, you've probably

learned that at the end of the day, the really hard part of the job has nothing to do with illumination

models, doppler shift, file formats, or frame rates, as the majority of game development

books on the shelves would have you believe. These days, it's more or less evident that everyone

knows everything. Gone are the days where game development gurus separated themselves from

the common folk with their in-depth understanding of VGA registers or their ability to write an 8-

bit mixer in 4K of code. Nowadays, impossibly fast hardware accelerators and monolithic APIs

that do everything short of opening your mail pretty much have the technical details covered.

No, what really make the creation of a phenomenal game difficult are the characters, the plot,

and the suspension of disbelief.

Until Microsoft releases "DirectStoryline"—which probably won't be long, considering the

amount of artificial intelligence driving DirectMusic—the true challenge will be immersing players

in settings and worlds that exert a genuine sense of atmosphere and organic life. The floor

should creak and groan when players walk across aging hardwood. The bowels of a ship should

be alive with scurrying rats and the echoey drip-drop sounds of leaky pipes. Characters should

converse and interact with both the player and one another in ways that suggest a substantial set

of gears is turning inside their heads. In a nutshell, a world without compellingly animated detail

and believable responsiveness won't be suitable for the games of today and tomorrow.

The problem, as the first chapter of this book will explain, is that the only solution to this problem

directly offered by languages like C and C++ is to clump the code for implementing a peripheral

character's quirky attitude together with code you use to multiply matrices and sort vertex

lists. In other words, you're forced to write all of your game—from the low-level details to the

high-level logic—in the same place. This is an illogical grouping and one that leads to all sorts of

hazards and inconveniences.

And let's not forget the modding community. Every day it seems that players expect more flexibility

and expansion capabilities from their games. Few PC titles last long on the shelves if a

community of rabid, photosensitive code junkies can't tear it open and rewire its guts. The problem

is, you can't just pop up an Open File dialog box and let the player chose a DLL or other

dynamically linked solution, because doing so opens you up to all sorts of security holes. What if

a malicious mod author decides that the penalty for taking a rocket blast to the gut is a freshly

reformatted hard drive? Because of this, despite their power and speed, DLLs aren't necessarily

the ideal solution.

This is where the book you're currently reading comes into play. As you'll soon find out, a solution

that allows you to both easily script and control your in-game entities and environments, as

well as give players the ability to write mods and extensions, can only really come in the form of a

custom-designed language whose programs can run within an embeddable execution environment

inside the game engine. This is scripting.

If that last paragraph seemed like a mouthful, don't worry. This book is like an elevator that truly

starts from the bottom floor, containing everything you need to step out onto the roof and enjoy

the view when you're finished. But as a mentally unstable associate of mine is often heard to say,

"The devil is in the details." It's not enough to simply know what scripting is all about; in order to

really make something happen, you need to know everything. From the upper echelons of the

compiler, all the way down to the darkest corners of the virtual machine, you need to know what

goes where, and most importantly, why. That's what this book aims to do. If you start at the beginning

and follow along with me until the end, you should pick up everything you need to genuinely

understand what's going on.

How This Book is Organized

With the dramatic proclamations out of the way, let's take a quick look at how this book is set up;

then we'll be ready to get started.

This book is organized into a number of sections:

• Part One: Scripting Fundamentals. The majority of this material won't do you much

good if you don't know what scripting is or why it's important. Like I said, you can follow

this book whether or not you've even heard of scripting. The introduction provides

enough background information to get you up to speed quick.

• Part Two: Command-Based Scripting. Developing a complete, high-level scripting system

for a procedural language is a complex task. A very complex task. So, we start off by setting

our sights a bit lower and implementing what I like to call a "command-based language."

As you'll see, command-based languages are dead simple to implement and

capable of performing rather interesting tasks.

• Part Three: Introduction to Procedural Scripting Languages. Part 3 is where things start

to heat up, as we get our feet wet with real world, high-level scripting. Also covered in

this section are complete tutorials on using the Lua, Python and Tcl languages, as well as

integrating their associated runtime environments with a host application.

• Part Four: Designing and Implementing a Low-Level Langauge. At the bottom of our

scripting system will lie an assembly language and corresponding machine code (or bytecode).

The design and implementation of this low-level environment will provide a vital

foundation for the later chapters.

• Part Five: Designing and Implementing a Virtual Machine. Scripts—even compiled

ones—don't matter much if you don't have a way to run them. This section of the book

covers the design and implementation of a feature-packed virtual machine that's ready to

be dropped into a game engine.

• Part Six: Compiling High-Level Code. The belly of the beast itself. Executing compiled

bytecode is one thing, but being able to compile and ultimately run a high-level, procedural

language of your own design is what real scripting is all about.

• Part Seven: Completing Your Training. Once you've earned your stripes, it's time to

direct that knowledge somewhere. This final section aims to clear up any questions you

may have in regards to furthering your study. You'll also see how the scripting system

designed throughout the course of the book was applied to a complete game.

So that's it! You've got a roadmap firmly planted in your brain, and an interest in scripting that's

hopefully piqued by now. It's time to roll our sleeves up and turn this mutha out.

Screenshot

Purchase Now !
Just with Paypal

Product details

Price
File Size	53,251 KB
Pages	1273 p
File Type	PDF format
ISBN	1-931841-57-8
Copyright	2003 by Premier Press

Contents at a Glance
Introduction
Part One
Scripting Fundamentals
Chapter 1 An Introduction to Scripting
Chapter 2 Applications of Scripting Systems
Part Two Command-Based Scripting
Chapter 3 Introduction to Command-Based Scripting
Chapter 4 Advanced Command-Based Scripting
Part Three
Introduction to Procedural Scripting Languages
Chapter 5 Introduction to Procedural Scripting Systems
Chapter 6 Integration: Using Existing Scripting Systems
Chapter 7 Designing a Procedural Scripting Language
Part Four
Designing and Implementing a Low-Level Language
Chapter 8 Assembly Language Primer
Chapter 9 Building the XASM Assembler
Part Five
Designing and Implementing a Virtual Machine
Chapter 10 Basic VM Design and Implementation
Chapter 11 Advanced VM Concepts and Issues
Part Six
Compiling High-Level Code
Chapter 12 Compiler Theory Overview
Chapter 13 Lexical Analysis
Chapter 14 Building the XtremeScript Compiler Framework
Chapter 15 Parsing and Semantic Analysis
Part Seven
Completing Your Training
Chapter 16 Applying the System to a Full Game
Chapter 17 Where to Go From Here
Appendix A
What’s on the CD?
INDEX


Table of Contents

Introduction..................................xliv

Part One Scripting Fundamentals...............1

Chapter 1 An Introduction to Scripting..........3

What Is Scripting? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Structured Game Content—A Simple Approach. . . . . . . . . . . . . 6

Improving the Method with Logical and Physical Separation . . 10

The Perils of Hardcoding. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

Storing Functionality in External Files . . . . . . . . . . . . . . . . . . . . 14

How Scripting Actually Works. . . . . . . . . . . . . . . . . . . . . . . . . . . 15

An Overview of Computer Programming . . . . . . . . . . . . . . . . . . . . . . . . . . 16

An Overview of Scripting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

The Fundamental Types of Scripting Systems . . . . . . . . . . . . . . 20

Procedural/Object-Oriented Language Systems . . . . . . . . . . . . . . . . . . . . . . 21

Command-Based Language Systems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Dynamically Linked Module Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

Compiled versus Interpreted Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

Existing Scripting Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

Ruby . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

Lua. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Chapter 2 Applications of Scripting Systems.......29

The General Purpose of Scripting . . . . . . . . . . . . . . . . . . . . . . . 30

Role Playing Games (RPGs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

Complex, In-Depth Stories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

The Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

Non-Player Characters (NPCs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

The Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

Items and Weapons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

The Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

Enemies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

The Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

First-Person Shooters (FPSs) . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

Objects, Puzzles, and Switches (Obligatory Oh My!) . . . . . . . . . . . . . . . . . . 51

The Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

Enemy AI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

The Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

Part Two Command-Based Scripting ..........61

Chapter 3 Introduction to Command-Based Scripting.......................63

The Basics of Command-Based Scripting. . . . . . . . . . . . . . . . . . 64

High-Level Engine Control. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

Commands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

Master of Your Domain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

Actually Getting Something Done . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

Command-Based Scripting Overview. . . . . . . . . . . . . . . . . . . . . 69

Engine Functionality Assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

Loading and Executing Scripts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

Looping Scripts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

Implementing a Command-Based Language . . . . . . . . . . . . . . . 74

Designing the Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

Writing the Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

Basic Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

Execution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

Command and Parameter Extraction. . . . . . . . . . . . . . . . . . . . . . . . . . . 81

The Command Handlers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

Scripting a Game Intro Sequence. . . . . . . . . . . . . . . . . . . . . . . . 90

The Language. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

The Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

The Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

Scripting an RPG Character’s Behavior . . . . . . . . . . . . . . . . . . . 95

The Language. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

Improving the Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

Managing a Game Character . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

The Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

The Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

The Demo’s Main Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

Concurrent Script Execution . . . . . . . . . . . . . . . . . . . . . . . . . . 109

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

On the CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

Chapter 4 Advanced Command-Based Scripting.....113

New Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

Boolean Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

Floating-Point Support . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

General-Purpose Symbolic Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

An Internal Constant List. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

A Two-Pass Approach. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

Loading Before Executing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

Simple Iterative and Conditional Logic . . . . . . . . . . . . . . . . . . 125

Conditional Logic and Game Flags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

Grouping Code with Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

The Block List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

Iterative Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

Nesting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

Event-Based Scripting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

Compiling Scripts to a Binary Format . . . . . . . . . . . . . . . . . . . 137

Increased Execution Speed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

Detecting Compile-Time Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

Malicious Script Hacking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

How a CBL Compiler Works. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140

Executing Compiled Scripts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

Compile-Time Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

Parameters. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

Basic Script Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

File-Inclusion Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

Part Three Introduction to Procedural 

Scripting Languages ..153

Chapter 5 Introduction to Procedural Scripting Systems ..............155

Overall Scripting Architecture . . . . . . . . . . . . . . . . . . . . . . . . . 156

High-Level Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

Low-Level Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158

The Virtual Machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

A Deeper Look at XtremeScript . . . . . . . . . . . . . . . . . . . . . . . 161

High-Level Code/Compilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162

Lexical Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164

Parsing/Syntactic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164

Semantic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

Intermediate Code Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

Assembly Language Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

The Symbol Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

The Front End versus the Back End . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

Low-Level Code/Assembly. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

The Assembler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

The Disassembler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

The Debugger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

The Virtual Machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168

The XtremeScript System . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169

High-Level . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

Low-Level . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

Runtime. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171

Chapter 6 Integration: Using Existing Scripting Systems ................173

Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174

Implementation of Scripting Systems. . . . . . . . . . . . . . . . . . . . 179

The Bouncing Head Demo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

Lua (and Basic Scripting Concepts) . . . . . . . . . . . . . . . . . . . . . 185

The Lua System at a Glance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

The Lua Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

The luac Compiler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

The lua Interactive Interpreter. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186

The Lua Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187

Comments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188

Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188

Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191

Tables. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

Advanced String Features. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197

Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198

Conditional Logic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200

Iteration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201

Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203

Integrating Lua with C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205

Compiling a Lua Project. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206

Initializing Lua . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207

Loading Scripts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208

The Lua Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209

Exporting C Functions to Lua . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215

Executing Lua Scripts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219

Importing Lua Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221

Manipulating Global Lua Variables from C . . . . . . . . . . . . . . . . . . . . . . 226

Re-coding the Alien Demo in Lua . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228

Advanced Lua Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241

Web Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

The Python System at a Glance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

Directory Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243

The Python Interactive Interpreter . . . . . . . . . . . . . . . . . . . . . . . . . . . 243

The Python Language. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244

Comments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244

Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244

Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246

Basic Strings. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247

String Manipulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248

Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251

Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254

Conditional Logic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256

Iteration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258

Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261

Integrating Python with C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263

Compiling a Python Project . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263

Initializing Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265

Python Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265

Re-coding the Alien Head Demo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277

Advanced Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286

Web Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286

Tcl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287

ActiveStateTcl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288

The Distribution at a Glance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288

The tclsh Interactive Interpreter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289

What, No Compiler? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290

Tcl Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290

The Tcl Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291

Commands—The Basis of Tcl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291

Substitution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292

Comments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297

Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298

Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301

Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303

Conditional Logic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306

Iteration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308

Functions (User-Defined Commands) . . . . . . . . . . . . . . . . . . . . . . . . . 310

Integrating Tcl with C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312

Compiling a Tcl Project . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312

Initializing Tcl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313

Loading and Running Scripts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314

Calling Tcl Commands from C. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315

Exporting C Functions as Tcl Commands. . . . . . . . . . . . . . . . . . . . . . . 316

Returning Values from Tcl Commands . . . . . . . . . . . . . . . . . . . . . . . . . 319

Manipulating Global Tcl Variables from C . . . . . . . . . . . . . . . . . . . . . . . 320

Recoding the Alien Head Demo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322

Advanced Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330

Web Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330

Which Scripting System Should You Use? . . . . . . . . . . . . . . . . 331

Scripting an Actual Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333

On the CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334

Chapter 7 Designing a Procedural Scripting Language..................335

General Types of Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . 337

Assembly-Style Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337

Upping the Ante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340

Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344

Object-Oriented Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346

XtremeScript Language Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349

Design Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349

Syntax and Features. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351

Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351

Operators and Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354

Code Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358

Control Structures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358

Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361

Escape Sequences. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363

Comments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363

The Preprocessor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363

Reserved Word List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365

Part Four Designing and 

Implementing a Low-Level Language .............367

Chapter 8 Assembly Language Primer ..............369

What Is Assembly Language? . . . . . . . . . . . . . . . . . . . . . . . . . . 370

Why Assembly Now? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371

How Assembly Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372

Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372

Operands. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372

Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373

Jump Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375

Conditional Logic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377

Iteration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380

Mnemonics versus Opcodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383

RISC versus CISC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386

Orthogonal Instruction Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388

Registers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389

The Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389

Stack Frames/Activation Records. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392

Local Variables and Scope. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395

Introducing XVM Assembly. . . . . . . . . . . . . . . . . . . . . . . . . . . . 397

Initial Evaluations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398

The XVM Instruction Set. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399

Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399

Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 400

Bitwise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401

String Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402

Conditional Branching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402

The Stack Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403

The Function Interface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403

Miscellaneous. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404

XASM Directives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404

Stack and Data. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405

Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406

Escape Sequences. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407

Comments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407

Summary of XVM Assembly . . . . . . . . . . . . . . . . . . . . . . . . . . . 408

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409

Chapter 9 Building the XASM Assembler ...........411

How a Simple Assembler Works . . . . . . . . . . . . . . . . . . . . . . . . 413

Assembling Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414

Assembling Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416

Assembling Operands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420

Assembling String Literals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422

Assembling Jumps and Function Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423

XASM Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428

Memory Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429

Input: Structure of an XVM Assembly Script . . . . . . . . . . . . . . . . . . . . . . . 430

Directives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431

Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439

Line Labels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440

Host API Function Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440

The _Main () Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441

The _RetVal Register . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441

Comments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442

A Complete Example Script. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442

Output: Structure of an XVM Executable . . . . . . . . . . . . . . . . . . . . . . . . . 444

Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444

The Main Header. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445

The Instruction Stream . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447

The String Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451

The Function Table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453

The Host API Call Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454

Implementing the Assembler . . . . . . . . . . . . . . . . . . . . . . . . . . 455

Basic Lexing/Parsing Theory. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456

Lexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457

Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459

Basic String Processing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462

Vocabulary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462

A String-Processing Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464

The Assembler’s Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469

The General Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470

A Structural Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470

Lexical Analysis/Tokenization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495

The Lexer’s Interface and Implementation . . . . . . . . . . . . . . . . . . . . . . 496

Error Handling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525

Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527

Initializing the Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528

Directives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 529

Line Labels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 542

Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543

Building the .XSE Executable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 552

The Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 552

The Instruction Stream . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553

The String Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555

The Function Table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 556

The Host API Call Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557

The Assembly Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558

Loading the Source File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558

The First Pass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 559

The Second Pass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 560

Producing the .XSE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563

On the CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564

Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564

Part Five Designing and

 Implementing a Virtual Machine..................565

Chapter 10 Basic VM Design and Implementation ..567

Ghost in the Virtual Machine. . . . . . . . . . . . . . . . . . . . . . . . . . . 568

Mimicking Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 569

The VM’s Major Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 570

The Instruction Stream . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571

The Runtime Stack. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571

Global Data Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571

Multithreading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573

Integration with the Host Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573

A Brief Overview of a VM’s Lifecycle . . . . . . . . . . . . . . . . . . . . 574

Loading the Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574

Beginning Execution at the Entry Point . . . . . . . . . . . . . . . . . . . . . . . . . . . 576

The Execution Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576

Function Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578

Calling a Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578

Returning From a Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 580

Termination and Shut Down . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 581

Structural Overview of the XVM Prototype. . . . . . . . . . . . . . . 582

The Script Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583

Runtime Values. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583

The Instruction Stream . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584

The Runtime Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585

The Frame Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 586

The Function Table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 587

The Host API Call Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 587

The Final Script Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588

Building the XVM Prototype. . . . . . . . . . . . . . . . . . . . . . . . . . . 589

Loading an .XSE Executable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 590

An .XSE Format Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 590

The Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594

The Instruction Stream . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595

The String Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599

The Function Table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601

The Host API Call Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 602

Structure Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 603

The Instruction Stream . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604

The Runtime Stack. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 616

The Function Table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621

The Host API Call Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 622

Initializing the VM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624

The Execution Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627

Instruction Set Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 628

Handling Script Pauses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633

Incrementing the Instruction Pointer . . . . . . . . . . . . . . . . . . . . . . . . . . 634

Operand Resolution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 636

Instruction Execution and Result Storage. . . . . . . . . . . . . . . . . . . . . . . 637

Termination and Shut Down . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 648

On the CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 649

Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 649

Chapter 11 Advanced VM Concepts and Issues......651

A Next Generation Virtual Machine . . . . . . . . . . . . . . . . . . . . . 652

Two Versions of the Machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 652

Multithreading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653

Multithreading Fundamentals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 654

Cooperative vs. Preemptive Multitasking . . . . . . . . . . . . . . . . . . . . . . . 654

From Tasks to Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 658

Concurrent Execution Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659

Loading and Storing Multiple Scripts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667

The g_Script Structure. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667

Loading Scripts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671

Initialization and Shutdown . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 674

Handling a Script Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 674

Executing Multiple Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 677

Tracking Active Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 678

The Scheduler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 679

The First Completed XVM Demo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 682

Host Application Integration. . . . . . . . . . . . . . . . . . . . . . . . . . . 682

Running Scripts in Parallel with the Host . . . . . . . . . . . . . . . . . . . . . . . . . . 683

Manual Time Slicing vs. Native Threads. . . . . . . . . . . . . . . . . . . . . . . . . 684

Introducing the Integration Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 686

Calling Host API Functions from a Script . . . . . . . . . . . . . . . . . . . . . . . 686

Calling Script Functions from the Host . . . . . . . . . . . . . . . . . . . . . . . . 687

Tracking Global Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 689

The XVM’s Public Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 694

Which Functions Should Be Public? . . . . . . . . . . . . . . . . . . . . . . . . . . . 694

Name Clashes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 695

Public Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 696

Implementing the Integration Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . 696

Basic Script Control Functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 697

Host API Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 700

Script Function Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 711

Invoking a Script Function: Synchronous Calls . . . . . . . . . . . . . . . . . . . 713

Calling a Scripting Function:Asynchronous Calls . . . . . . . . . . . . . . . . . 719

Adding Thread Priorities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 728

Priority Ranks vs.Time Slice Durations . . . . . . . . . . . . . . . . . . . . . . . . 730

Updating the .XSE Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 731

Updating XASM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 733

Parsing the SetPriority Directive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 734

Updating the XVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 735

Demonstrating the Final XVM . . . . . . . . . . . . . . . . . . . . . . . . . 739

The Host Application. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 739

The Demo Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 739

Embedding the XVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 741

Defining the Host API . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 742

The Main Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 742

The Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 745

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 746

On the CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 746

Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 747

Part Six Compiling High-Level Code .......749

Chapter 12 Compiler Theory Overview ................751

An Overview of Compiler Theory. . . . . . . . . . . . . . . . . . . . . . . 752

Phases of Compilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 753

Lexical Analysis/Tokenization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 755

Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 760

Semantic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 764

I-Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 765

Single-Pass versus Multi-Pass Compilers. . . . . . . . . . . . . . . . . . . . . . . . 766

Target Code Emission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 768

The Front and Back Ends . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 768

Compiler Compilers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 769

How XtremeScript Works with XASM . . . . . . . . . . . . . . . . . . . . . . . . . . . 769

Advanced Compiler Theory Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 771

Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 771

Preprocessing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 773

Retargeting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 778

Linking, Loading, and Relocatable Code . . . . . . . . . . . . . . . . . . . . . . . . 779

Targeting Hardware Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 780

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 782

Chapter 13 Lexical Analysis ............................783

The Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 785

From Characters to Lexemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 785

Tokenization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 787

Lexing Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 787

Lexer Generation Utilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 788

Hand-Written Lexers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 788

The Lexer’s Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 793

Reading and Storing the Text File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 793

Displaying the Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 795

Error Handling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 797

A Numeric Lexer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 797

A Lexing Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 798

State Diagrams. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 799

States and Token Types. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 800

Initializing the Lexer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 800

Beginning the Lexing Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 801

The Lexing Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 802

Completing the Demo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 809

Lexing Identifiers and Reserved Words. . . . . . . . . . . . . . . . . . . 811

New States and Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 812

The Test File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 813

Upgrading the Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 814

Completing the Demo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 819

The Final Lexer: Delimiters, Operators, and Strings . . . . . . . . 822

Lexing Delimiters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 822

New States and Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 822

Upgrading the Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 823

Lexing Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 827

New States and Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 827

Upgrading the Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 828

Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 831

Breaking Operators Down. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 832

Building Operator State Transition Tables . . . . . . . . . . . . . . . . . . . . . . . 836

New States and Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 840

Upgrading the Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 841

Completing the Demo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 849

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 855

On the CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 855

Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 856

Chapter 14 Building the XtremeScript Compiler Framework.............857

A Strategic Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 858

The Front End . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 859

The Loader Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 860

The Preprocessor Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 861

The Lexical Analyzer Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 861

The Parser Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 862

The I-Code Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 862

The Back End . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 863

The Code Emitter Module. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 863

The XASM Assembler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 863

Major Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 863

The Source Code. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 863

The Script Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 864

The Symbol Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 864

The Function Table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 865

The String Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 866

The I-Code Stream . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 866

Interfaces and Encapsulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 866

The Compiler’s Lifespan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 867

Reading the Command Line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 867

Loading the Source Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 867

Preprocessing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 867

Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 867

Code Emission. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 868

Invoking XASM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 868

The Compiler’s main () Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 868

The Command-Line Interface. . . . . . . . . . . . . . . . . . . . . . . . . . 870

The Logo and Usage Info. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 870

Reading Filenames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 871

Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 872

Reading Options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 874

Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 875

Elementary Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . 880

Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 880

The Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 881

Stacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 888

The Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 888

Initialization and Shutdown. . . . . . . . . . . . . . . . . . . . . . . . . . . . 890

Global Variables and Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 890

Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 891

Shutting Down. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 892

The Compiler’s Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 893

The Loader Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 895

The Preprocessor Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 897

Single-Line Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 898

Block Comments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 899

Preprocessor Directives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 902

Implementing #include . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 902

Implementing #define. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 903

The Compiler’s Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 904

The Symbol Table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 905

The SymbolNode Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 905

The Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 907

The Function Table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 910

The FuncNode Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 911

The Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 911

The String Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 915

Integrating the Lexical Analyzer Module . . . . . . . . . . . . . . . . . 916

Rewinding the Token Stream . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 916

Lexer States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 917

A New Source Code Format. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 919

New Miscellaneous Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 922

Adding a Look-Ahead Character . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 922

Handling Invalid Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 923

Returning the Current Token . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 925

Copying the Current Lexeme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 926

Error-Printing Helper Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 927

Resetting the Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 928

The Parser Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 928

Error Handling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 928

General Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 928

Code Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 928

Cascading Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 930

The I-Code Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 932

Approaches to I-Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 932

A Simplified Instruction Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 933

The XtremeScript I-Code Instruction Set . . . . . . . . . . . . . . . . . . . . . . 935

The XtremeScript I-Code Implementation . . . . . . . . . . . . . . . . . . . . . . . . 935

Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 936

Jump Targets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 938

Source Code Annotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 940

The Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 942

Adding Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 943

Adding Operands. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 944

Retrieving Operands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 945

Adding Jump Targets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 946

Adding Source Code Annotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 947

Retrieving I-Code Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 948

The Code-Emitter Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . 949

Code-Emission Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 949

The General Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 950

Global Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 951

Emitting the Header. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 952

Emitting Directives. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 953

Emitting Symbol Declarations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 955

Emitting Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 958

Emitting a Complete XVM Assembly File . . . . . . . . . . . . . . . . . . . . . . . 966

Generating the Final Executable. . . . . . . . . . . . . . . . . . . . . . . . 969

Wrapping It All Up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 972

Initiating the Compilation Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 972

Printing Compilation Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 972

Hard-coding a Test Script. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 975

The Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 976

The Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 976

The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 977

The Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 980

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 981

On the CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 981

Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 982

Chapter 15 Parsing and Semantic Analysis .........983

What Is Parsing? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 985

Syntactic versus Semantic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 985

Expressing Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 987

Syntax Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 987

Backus-Naur Form. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 988

Choosing a Method of Grammar Expression . . . . . . . . . . . . . . . . . . . . 989

Parse Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 989

How Parsing Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 993

Recursive Descent Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 994

The XtremeScript Parser Module . . . . . . . . . . . . . . . . . . . . . . 996

The Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 996

Tracking Scope. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 996

Reading Specific Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 997

The Parsing Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1000

Parsing Statements and Code Blocks . . . . . . . . . . . . . . . . . . . 1001

Syntax Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1002

The Implementation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1004

ParseSourceCode () . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1004

Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1005

Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1007

Parsing Declarations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1008

Function Declarations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1008

Parsing and Verifying the Function Name . . . . . . . . . . . . . . . . . . . . . . 1010

Parsing the Parameter List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1011

Parsing the Function’s Body . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1015

Variable and Array Declarations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1017

Host API Function Declarations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1021

The host Keyword . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1022

Upgrading the Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1022

Parsing and Processing the host Keyword . . . . . . . . . . . . . . . . . . . . . 1023

Testing Code Emitter Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1026

Parsing Simple Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . 1028

An Expression Parsing Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1028

Parsing Addition and Subtraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1028

Multiplication, Division, and Operator Precedence . . . . . . . . . . . . . . . 1030

Stack-Based Expression Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1031

Understanding the Expression Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . 1033

Coding the Expression Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1037

Parsing Full Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1048

New Factor Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1048

Parsing Function Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1051

New Unary Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1053

New Binary Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1054

Logical and Relational Operators. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1054

The Logical And Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1055

Relational Greater Than or Equal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1056

The Rest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1058

L-Values and R-Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1058

A Standalone Runtime Environment . . . . . . . . . . . . . . . . . . . 1058

The Host Application. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1059

Reading the Command Line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1060

Loading the Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1061

Running the Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1062

The Host API. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1062

PrintString () . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1063

PrintNewline () and PrintTab () . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1063

Registering the API. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1064

Parsing Advanced Statements and Constructs . . . . . . . . . . . . 1064

Assignment Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1065

Function Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1073

return . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1075

while Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1079

while Loop Assembly Representation. . . . . . . . . . . . . . . . . . . . . . . . . 1079

Parsing while Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1081

break . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1086

Parsing break . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1088

continue. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1090

for Loops. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1092

Branching with if . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1092

if Block Assembly Representation. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1092

Parsing if Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1094

Syntax Diagram Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 1099

The Test Drive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1099

Hello,World! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1099

Drawing Rectangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1102

The Bouncing Head Demo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1106

Anatomy of the Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1107

The Host Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1109

The Low-Level XVM Assembly Script. . . . . . . . . . . . . . . . . . . . . . . . . 1116

The High-Level XtremeScript Script. . . . . . . . . . . . . . . . . . . . . . . . . . 1127

The Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1132

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1134

On the CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1134

Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1135

Part Seven Completing Your Training ........1137

Chapter 16 Applying the System to a Full Game..............1139

Introducing Lockdown. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1140

The Premise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1140

Initial Planning and Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1142

Phase One—Game Logic and Storyboarding . . . . . . . . . . . . . . . . . . . 1142

Phase Two—Asset Requirement Assessment . . . . . . . . . . . . . . . . . . . 1150

Phase Three—Planning the Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1155

Scripting Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1157

Integrating XtremeScript . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1158

The Host API. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1158

Miscellaneous Functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1159

Enemy Droid Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1159

Player Droid Functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1159

Registering the Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1160

Writing the Scripts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1161

The Ambience Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1161

The Blue Droid’s Behavior Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1162

The Grey Droid’s Behavior Script . . . . . . . . . . . . . . . . . . . . . . . . . . . 1163

The Red Droid’s Behavior Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1167

Compilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1171

Loading and Running the Scripts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1171

Speed Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1173

Minimizing Expressions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1174

The XVM’s Internal Timer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1174

How to Play Lockdown . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1175

Controls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1175

Interacting with Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1176

The Zone Map. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1176

Battle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1176

Completing the Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1176

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1177

On the CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1177

Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1178

Chapter 17 Where to Go From Here .................1179

So What Now? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1180

Expanding Your Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . 1181

Compiler Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1181

More Advanced Parsing Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1182

Object-Orientation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1182

Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1183

Runtime Environments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1184

The Java Virtual Machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1184

Alternative Operating Systems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1185

Operating System Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1186

Advanced Topics and Ideas . . . . . . . . . . . . . . . . . . . . . . . . . . . 1186

The Assembler and Runtime Environment . . . . . . . . . . . . . . . . . . . . . . . . 1186

A Lower-Level Assembler. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1186

A Lower-Level Virtual Machine. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1187

Dynamic Memory Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1189

The Compiler and High-Level Language . . . . . . . . . . . . . . . . . . . . . . . 1190

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1199

Appendix A What’s on the CD? ........................1201

The CD-ROM Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1202

Installation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1203

DirectX SDK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1203

INDEX .......................................1205

  ●▬▬▬▬▬❂❂❂▬▬▬▬▬●

●▬▬❂❂▬▬●

●▬❂▬●

●❂●

═════● ●═════