ARM Assembly: The ARM Architecture

The history of the ARM architecture is quite interesting, though we will only be looking at it very briefly.  ARM started with a company named Acorn Computers.  It initially produced simple computers, during the time when all computers were pretty simple.  Acorn Computers produced several machines that were successful in Europe, including the BBC Micro series.  The primary focus of the company was on processors though, and due to the unsuitability of other processors at the time, it decided to create its own processors, in the Acorn RISC Machine project, to go with the BBC Micro for more business oriented applications.  Early ARM processors compared quite favorably to early Intel processors, with the ARM2 outperforming the Intel 80286 at the same time as using less power.  In the end, the ARM processor line was turned into its own company, Advanced RISC Machines.  The unique thing about ARM as a company is that it does not manufacture processors.  It designs and licenses processor architectures for other companies to manufacture.  The consequence of this is that ARM processors are ubiquitous in the mobile device industry, because it is far cheaper to license designs and manufacture them than it is for companies to design custom processors themselves.  This is especially valuable in an industry that is constantly trying to push technological boundaries to keep up with competition.  In this business model, one company does all of the design work, often working with larger clients to include valuable new features, and the entire mobile device industry licenses and uses the designs to produce all sorts of different mobile devices.  In addition to mobile devices, there are some companies that are attempting to use the ARM architecture to produce server processors.  They believe that the lower power consumption and higher performance that may be possible with RISC processors could be very popular in a market that values processors that run cheaper and cooler but need plenty of processing power.

Instruction Sets

The specific part of the ARM architecture that is important to us is how the ARMv7 architecture works.  ARMv7 is broken up into 3 divisions.  There is an A series, an M series, and an R series.  The A series is general purpose.  The M series is mostly low power consumption processors designed for use in embedded applications and lower powered mobile devices.  The R series is designed for real-time embedded applications, where responsiveness and performance are extremely important.  We are mostly going to focus on the A series, with a little bit on the M series.  The main difference between A and M with respect to this series is that the M series only supports ARM's 16 bit Thumb/Thumb2 instruction set (possibly with support for the few 32 bit Thumb2 instructions), while the A series supports both the 32 bit ARM instruction set and the mostly 16 bit Thumb2 instruction set.

Later in this series we will also learn about another instruction set the processor in the Pi 2 supports.  This is the Neon/VFP instruction set that provides instructions for floating point math as well as parallel integer and floating point math.  We will discuss this more later.

Registers

Pretty much all processors need some sort of memory to operate on.  Modern processors use several levels of memory.  The lowest level is registers that each can store one value.  The size of the value is generally the word size of the processor.  The word size of the ARMv7 architecture is 32 bits, meaning that each register can hold a 32 bit value.

The ARMv7 architecture claims to have 16 general purpose registers, but this is not strictly true.  No less than 3 of these registers have  dedicated purposes, and attempting to use them for anything else is likely to cause problems.  Some programs may use a 4th register for a dedicated purpose as well.

ARM generally names its general purpose registers as rx, where x if the register number.  Thus, ARMv7 processors have registers r0 through r15.  We never use any registers above r12 for general use though, nor do we use them by their designations r13, r14, or r15.  Instead, we use sp for r13, lr for r14, and pc for r15.

The pc register is the program counter or instruction pointer.  It contains the memory address of the next instruction to be run.  With a few exceptions, whenever an instruction is executed, the instruction pointer is updated to point at the instruction after it.  Modifying the instruction pointer will change where the program is executing.

The sp register is the stack pointer.  It contains the memory address of the last entry on the stack.  It is often used as a reference point for accessing data stored on the stack.  Modification of the stack pointer should be done carefully and predictably, because otherwise the top of the stack can be lost, which can be disastrous.

The lr register is used to store the return point for a function.  When a function is called (there are some instructions for this), the address of the instruction directly after the function call is stored in lr, so that the function being called knows where to return to when it is done.  Technically, if the address stored in lr is saved somewhere else and restored later, lr can be used as a general purpose register, though I have not found this to be terribly common.  The most important thing to remember about lr is that if you are going to call a function from inside of another function, you need to store the value in lr somewhere else first, because it is going to get overwritten.  Don't worry to much about this right now though, as we will discuss it again when we start calling functions.

In partially compiled C programs, you may also see an fp register.  This is the frame pointer register, and when used, it is r11.  The frame pointer can be really handy for certain kinds of debugging, and it can be used as an alternative reference to sp, however it is not strictly necessary.  In fact, you will never find it in partially compiled C programs with any level of optimization.  It can only be found in unoptimized, partially compiled C code.  We won't be using it, however it is good to be aware of, as you may see it in assembly code generated by GCC.

Memory

One fairly unusual thing about ARM is that it does not have any instructions that directly operate on data in memory.  In fact, the only memory access instructions ARM has are a few for loading data from memory into registers.  Most modern processor architectures allow at least a few instructions besides load and store instructions to access data from memory directly.  ARM does not, and this means that if you want to operate on a value stored in memory, you must first load it into a register, and if you want to put the result of an operation in memory, you have to save it to memory after the operation is complete.  This keeps the instruction set fairly simple, and despite the fact that it means you have to use more instructions when accessing data in memory, ARM processors still have excellent performance.

The general workflow in 32 bit Intel processors involves a lot of memory accesses, because they have a very limited number of registers (8 general purpose registers, except that some have special purposes as well, which often limits their usefulness).  Consequently, instructions that can access memory directly have been seen as essential to good performance.  ARM, however, has plenty of registers, which means that intermediate values rarely ever have to be stored in memory.  Thus the value of instructions that access memory directly is very limited.  Historically, this has been such a significant strong point of ARM that it has been able to outperform Intel and other processors with significantly lower power consumption, despite the fact that RISC processors are defined by the fact that they maintain smaller instruction sets of simpler instructions.  In fact, this is such a potent strength that modern Intel 64 bit architectures have doubled the number of registers from 8 to 16 (comparatively though, 64 bit ARM processors now have 31 general purpose registers, and the pc and sp registers are dedicated registers, meaning that it more than doubled the number of usable registers).  The general workflow with ARM programs should take advantage of the copious amount of general purpose registers to avoid unnecessary memory accesses.

Peripherals

Peripherals won't matter much here with respect to processor architecture, because we will be accessing them through the operating system, not directly.  That said, it is still worth spending a paragraph on.

Peripherals for ARM processors are memory mapped.  This is the most common way of handling peripherals.  Memory mapped peripherals are mapped to unused memory addresses by the processor (the Pi 2 processor can address up to 1TB of memory, but it only has 1GB, which leaves a huge number of memory addresses free).  In many systems, they are hard coded to specific memory addresses, but in some (desktops and laptops, for example), they are mapped by the BIOS during boot based on a number of factors.  The Pi has its memory mappings hard coded, since its hardware is not changeable.  It can be accessed by reading and writing the memory addresses associated with the peripheral you want to control.  The catch here is that this is handled by Linux on the Pi, and we don't have direct access to the device's memory.  We access memory through a memory manager that is managed by the operating system.  We will look at this more later, but the important thing is, no matter what memory we attempt to modify in our programs, we cannot directly access memory that is mapped to peripherals.  We must go through the operating system.  This is for security reasons and because an operating system running multiple processes simultaneously has to implement some kind of access control to prevent programs from stepping on each other's toes.


Now that we have a basic understanding of the processor architecture in our Pi 2, we can get back to writing assembly code!

ARM Assembly

Preface

I recently designed a course on the subject of ARM assembly programming, which I am now teaching.  During the design of the course, I spent a great deal of time struggling to find information on certain topics within the subject.  I found a distinct lack of good resources on many things.  The biggest problem was finding information about the interface between assembly level code and the operating system.  On one occasion I even taught my students something totally wrong, because I had been forced to learn it myself through reverse engineering, and it turns out that the operating system and the debugger don't behave the same way.  Of course, I corrected myself two days later, and I used the incident as a teaching opportunity.  What I learned from all of this is that assembly programming, especially for the ARM architecture, is very poorly documented at the interface between OS and user space programs.  I am writing this series with an aim to fix this problem.

Introduction

This series will teach ARM assembly programming, using ARMv7 assembly running on the Raspberry Pi 2.  The Pi 3 should also work fine for a vast majority of this, however some parts will not work for the original Pis.  I will do my best to identify these where I am aware of them.

This series assumes that if you have a Raspberry Pi, you either already have everything you need to use it, or you can figure out what you need and obtain it.  The essential things you will need are internet access for your Pi, at least briefly for the first chapter, and some way to input text and view text output.  This can be a USB keyboard and a monitor that will work with the Pi, it can be an SSH connection to the Pi over a network, or it can be a serial to USB adapter that gives you direct terminal access through the GPIO pins (Adafruit sells these).  There are plenty of resources online for each of these methods.

The operating system used for this series is Raspbian.  At least one of my students is using Arch Linux successfully, so this may also be a viable option.  Raspbian can either be installed using the NOOBs installer that comes on most SD cards sold specifically for the Pi, or you can download a Raspbian image and install it directly.  The second option is recommended, as it will give you the most recent version of Raspbian.  In addition, you may be able to avoid certain issues some of my students have run into with Raspbian installed through NOOBs for another assembly project you might be interested in that is currently outside the scope of this series.

Additionally, this series expects you to already have a basic understanding of the concepts of processor registers and assembly instructions.  I am sure many people will be able to figure these things out as they go along, but if you start this without that understanding and find yourself struggling to understand even the basic concepts, perhaps you should take a break and spend a little bit of time learning about modern processor architectures and how they work.  (I will probably write a short article on this in the future, but right now this series takes higher priority.)

Table of Contents

This will be populated with links to each chapter as they are published, in order of publication.

1. Setup
2. The ARM Architecture
3. Basic Math
4. Math with Small Data Types
5. Type Casting
6. Advanced Integer Math
7. Memory Architecture
8. Integer Division
9. Ditching GCC
10. The Stack
11. Pointers and Global Memory Access
12. Function Pointers
13. Branches
14. Conditional Branching
15. Loops
16. Indexing Modes
17. Arrays and Structs

Index

This will be populated with links to the chapters sorted by topic.

ARM Assembly: Setup

Setup

Before we can start writing assembly programs, we need to do some basic setup.  If your Pi is not already setup and running, stop here and do that.  Once it is running, login to the terminal.  You won't need the graphical interface for any of this, and it is honestly easier to just work completely in the terminal for most of the chapters in this series.  If you are an experienced user and you feel you cannot do without the GUI (both of these in one seems unlikely), feel free to use the GUI, but understand that I won't be using the GUI, and this series will assume that you are working purely from a terminal as well.

Once you have logged into a terminal, you will need to check what version of GCC is installed.  This is important, because the assembler that comes with versions of GCC older than 4.8 does not have support for some ARMv7 instructions that we will be using on our Pi 2.  (The original Pi processor is ARMv6, and thus it does not have these instructions.)  Check your version of GCC by running gcc -v.  This will spit out a lot of information.  At the bottom you will find the version information.  My Pi 2 says it's GCC version is 4.6.3.  This is what it came with.  If your version is lower than 4.8, you will need to run sudo apt-get install gcc-4.8.  Note that this will not change the default version.  If you run gcc -v again, it will still say the old version.  For compatibility reasons, installing GCC 4.8 won't replace the old version.  Now though, you should be able to run gcc-4.8 -v, and it will give you the version information about the new GCC you just installed.  If you want to compile with GCC 4.8, you will have to run gcc-4.8 instead of gcc.  Installing GCC 4.8 will replace the assembler though, which is all we really care about here.

I should add a note here, if the version of GCC says 4.8 or higher (recent versions of Raspbian now come with 4.9.2), then you can just use gcc, instead of specifying the version.

Writing a Simple Program

This part is not so much about learning assembly as it is about learning to use a terminal editor.  You have two options by default.  They are Nano and Vim.  In my opinion, Vim is the better of the two, however it has such a steep learning curve that am not even going to try to teach you how to use it (besides that, I am not even that proficient with it yet).  If you prefer Emacs, it is not installed by default, but you probably already know how to install it.  I am going to use Nano for this series.  You can run nano in the terminal to start Nano and create a new file.  You can run nano filename to open an existing file.  When you are in Nano, you will see a list of controls at the bottom.  The important ones are Ctrl+R to open a file, Ctrl+O to save a file, and Ctrl+X to exit (I have never actually used Ctrl+R...).  You can also use Ctrl+W to search, Ctrl+K to cut a line of text, and Ctrl+U to paste the last text that was cut.  If you expect to use these last few, I would suggest experimenting with them a bit to get familiar with how they work.

Let's start by writing a simple program that compiles with C.  You will probably want to create a directory to do all of this in.  I'll leave that up to you (in Linux, use the command mkdir directory_name to create a new directory in the current one, and use cd directory_name to move into that directory; if you did not know this already, you may want to find a Linux command line tutorial before continuing).  Once you are in your new directory, start Nano.  I ran nano num.s, to create a new file named num.s.  (The file extension for assembly files is ".s".)  You can instead specify the file name when you use Ctrl+X to save it the first time, if you prefer.

The first thing we need in the file is a line with the text .text.  .text is the section of your program with executable code, and it is generally called the text section (less commonly the "code section").  Since we are compiling with GCC, we need a "main" function.  Assembly does not have functions in the same sense as other languages, though we generally treat it like it does.  Instead, assembly has labels that are references to memory addresses.  These can be the addresses of data or instructions.  To create a "main" function, we need to do two things.  First, we need to create a label named "main" that references the instruction in our code where the program should start.  This is done by typing main:, on its own line.  The second thing we need to do is make our "main" label visible outside of our assembly file (so that the C library can see it; more on why this is necessary later).  Directly above the "main" label, add a line, .global main.  In the future, we will type the global directive before we create the actual label.

As this point, your program should look like this:

.text
.global main
main:

Now, the C compiler knows where our program starts (the instruction directly following the "main" label).  Next we need to write the actual code.  To keep things simple, our program is going to return an error code.  The convention is for functions to put their return values in the register r0.  When we return from main, the value in r0 is going to be used as the error code returned by our program.  Normally you don't get to see what error codes are returned by programs, but I'll show you a way to do it when we get there.

To put a value in r0, we will use the mov instruction.  This instruction can copy a value in one register to another, or it can take an immediate value (a number encoded in the instruction) and put it in a register.  There are some limitations to this, but we don't need to worry about them yet.  Underneath the "main" label, press tab once to indent, and then type mov r0, #27.  This will put the value 27 in the register r0.  Immediate values must generally be preceded with a # symbol.

Now that we have put our return value in r0, we can return from the main function.  This is done with a special branch instruction that takes a memory address to branch to.  By default, the program will run one instruction after another sequentially.  Branches are instructions that tell the processor to go to some other instruction and continue from there.  This is how we do things like calling functions and skipping instructions in false if statements.  We also use a branch instruction to return from a function.  In this case we will use the bx instruction, which takes a register that contains the memory address of the instruction we want to go to.  We will discuss ARM registers more in a moment, but for this instruction all we need to know about is the lr register, which contains the address for the return point when a function is called.  To return from the main function, we will use the instruction bx lr.  This will go back to whatever code C used to call the main function, allowing C to shut down anything it did before the program exits.

Our program should now look like this:

.text
.global main
main:
    mov r0, #27
    bx lr

All this program does is to return the exit code 27.  Here we need to save our program (Ctrl+O).  Now, exit Nano (Ctrl+X).  At the command line again, run gcc num.s.  This will compile our program and create an executable with the default name a.out.  We can run our program with ./a.out.  Disappointingly, it does nothing.  Like I said before, normally, we don't actually get to see the error codes.  We can display the error code of the last program that ran by running echo $?.  This should print out the number 27.  (Note that if you run echo $? again, it will print out 0, because that is the error code returned from the first time you ran it.)  You can edit your program and change the number put into r0, but there are two things to keep in mind.  First, negative numbers won't work.  The error code is an unsigned byte, so a negative number will print out as its unsigned representation.  Second, an unsigned byte can only fit in the range of values from 0 to 255 inclusive.  If you put in a number outside of this range, it will only print out whatever the unsigned representation of the lower 8 bytes are.  Additionally, due to limitations we will discuss later, some numbers outside of this range won't even allow your code to compile.  If the compiler gives you an error like "invalid constant (8888) after fixup", it means that the number you are trying to put in the register cannot be encoded in the instruction you are trying to put it in, so you will have to find another way.

The main point of this exercise was to become familiar with the editor and make sure everything works the way we expected.  An important thing to note is that we did not use the GCC 4.8 that we installed earlier, but we did use the assembler installed with it.  From here on out, most of our programs will not be compiled with GCC.  GCC adds some overhead to pretty much everything it compiles.  It adds startup and shutdown code that we really only care about if we are using C functions.  So, for the most part, the only time we will use GCC to compile our programs is when we are using C functions.

Video Game Development: Multi-threading

Multi-threading is a complex enough subject to warrant an entire course on its own, so we are not going to go into extensive detail here.  Multi-threading does have some very valuable benefits in the realm of game development though.

Multi-threading allows different parts of a program to run at the same time.  In modern multi-core computer systems, this can mean managing the game physics on one core, rendering graphics on another core, and handling audio on a third.  It could also mean updating one game unit on one core and another on a different core, though doing this is significantly more complex.

There are two things that are essential to understand when discussing any kind of parallel programming.  The first is concurrency.  Concurrency is when the program is doing different tasks at the same time.  The second is parallelism.  Parallelism is when the program is doing the same thing to different sets of data at the same time.  An example of concurrency with respect to video games is rendering graphics in one thread while processing physics in another.  The two tasks are different, but they are happening at the same time.  This can often be beneficial, even on systems that do not have multiple processor cores, because graphics rendering spends a lot of time waiting for the video card to be ready for more data.  During that wait time, other processing, like game physics, can take place without slowing down the rendering.  Parallelism requires hardware designed for multi-threading, like multi-core processors.  With parallelism, a set of data is broken up into smaller sets, and these sets are worked on at the same time, using the same algorithm.  For example, if my game has 100 game entities that need to be updated, instead of updating each one, one at a time, I could break the list into two lists of 50 each.  Then, I could process 50 entities in one thread and 50 in another, at the same time.  This could reduce the time required to update all of the entities by up to 50% (in practice, the benefit is a bit smaller than this, due to overhead of multi-threading).

In games, we generally stick to concurrency, due to certain issues with multi-threading.  When multi-threading we have to share memory between threads to allow communication.  In a game, we might be sharing animation frame data between the rendering thread and the physics thread.  When an entity updates, the physics engine might also update that entity's animation frame.  For example, a character in the game might be walking, and when the character steps forward, the physics engine sets the animation frame to show the step being taken.  The rendering thread also needs to use this data when it actually renders the animation frame on the screen.  So, what happens if the rendering thread starts to render the animation frame, but then halfway through, the physics thread changes it?  The result is that we have the top half of the frame as one image and the bottom as another, and we can probably see a horizontal seam in the middle where the change happened (this is called tearing, though it does not generally happen in this way).  You can also run into problems where two threads load something from memory at about the same time, both change it, and then both write it back.  This results in what is called a "race condition," because whoever writes second wins.  An example of this is a variable that is incremented each game loop, by two different threads.  If the variable is an 8, and then both threads load it (both getting 8s), and then both increment it (now both are 9s), and then both write it (still 9s), the result will be a 9, even though it should be a 10, because it was incremented twice.  These bugs can be incredibly hard to find, and there is no easy way to prevent them, except not sharing anything between threads, which defeats the point.

There are a lot of complications with multi-threading, and they all come down to making sure that memory accesses are carefully managed to avoid unexpected problems.  This is usually done by "locking" memory accesses.  A function that needs to modify some memory will lock that memory, read it, modify it, and write it, and then unlock it, and since it is locked while in use, nothing else can use it.  These locks take time to set and remove though, which reduces the efficiency of the program and can even eliminate the benefits of multi-threading if too many have to be used.  The best strategy is to avoid the need for locks in the first place, and minimize their use when they are absolutely necessary.  Even with locks though, you can run into issues.

This is a very complicated topic.  More information can be found on Wikipedia and other resources on the internet.  The takeaway here is that multi-threading can be extremely valuable in optimizing video game performance, but it requires a great deal of care and complete understanding to avoid running into very difficult problems.

Video Game Design: Player Generated Content

Player generated content is anything creative within a game that was created by one or more players.  It generally requires a high level of flexibility within the game, even if that flexibility is only within a limited scope.  For example, allowing players to design their own flags in a game would be player generated content.  Of course, it can also be far more broad than this.  Games like Minecraft and Terraria allow players to build custom structures and even complex logic constructs from basic building blocks.  Most Blizzard real-time strategy games (including the Starcraft and Warcraft series) include map editors that allow players some degree of ability to create custom maps and other custom in-game content.  This allows for large scale player generated content far beyond anything the developers could imagine (and they can imagine a lot).

Player generated content can also go outside the game.  For example, there is an entire YouTube series built around the Halo games.  They use video captures from the games, and then they add voices.  There are also millions of "Let's Play" videos for all sorts of games, with Terraria and Minecraft being some of the most popular, which also qualify as player generated content.  Even written fan fiction can be a form of player generated content.

Player generated content serves several purposes.  The first is to give a game increased replay value.  Replay value is the value a game has in continuing to play it even after you have beaten it.  Some games add replay value by adding a multiplayer mode so players can play with their friends.  Others do it by randomizing maps and adding such huge amounts of content that no one can experience it all the first time through the game.  Player generated content can add almost unlimited replay value to a game though.  When players are able to add their own content to a game, they can create replay value themselves.  A few flexible options can turn into practically infinite combinations, and that helps a game to avoid ever really getting old.

Player generated content also helps the game creators more directly.  You could create a game with huge amounts of content, or you could give your players the ability to make content for you.  Spend some time looking for epic things built in Minecraft, and you will find an enormous amount of free advertising for Mojang.  When people make mods for Minecraft, they are creating their own content that players can optionally add to their game.  If you start to get bored with Minecraft, just add a few mods.  Even the 5 most popular mods have almost more content than a single person can every experience completely, and Mojang, the creators of the original game, did not have to many any of that.  Some mods add more content to the game than it has in the first place, and some people put together packages with many mods all put together.  All of that keeps people playing and brings new people into the game, at no cost to the developers.  In short, player generated content is essentially free labor for the game creator, and even though the game creator does not legally own the player generated content, it does not matter, because it still benefits them just as much as if they did.

Allowing player generated content in a game can be tedious and difficult, but it is generally well worth the time and effort.

Video Game Design: Educational Game Psychology in a Nutshell

Game psychology, in a nutshell, is about reward and punishment.  The Paranoia XP rulebook says it best.

If you reward players for doing something you like, they will do more of that.

If you punish players for doing something you don't like, they will do less of that.

 Applied to video game, this generally means, if you want your players to keep playing your game, reward them for it.  Applied to educational games though, the meaning is much less clear.

In educational video games, the above psychological truth is applied to only one facet of the game.  "something you like" is construed to mean learning and solving problems related to the educational goal of the game.  "something you don't like" is applied only to failure to correctly solve the problems presented.  The game generally rewards success with points, a good grade, some visual recognition of the student's success, or even actual game play in a non-educational element of the game.  The reason educational games are, for the most part, an epic failure is that they miss at least two other facets.

In non-educational games, the reward/punishment psychology is applied to the game itself, to encourage players to keep playing the game.  You reward the player for playing the game and progressing in the game, because you want the player to keep playing your game.  Most educational games miss this motivational facet entirely, putting great effort into rewarding players for success in the educational element of the game, but ultimately not motivating them to actually want to play it in the first place.  An educational game that cannot keep players engaged is worthless, no matter how good the educational aspect of the game is.

The educational aspect of an educational game is always viewed by the game designers as the "something" in the above quote.  From the point of view of educators and parents, education is the "something" that they want to encourage students to do more of, but educators and parents are not the target audience of educational games.  Students are the target audience, and designing a game without focusing on the target audience almost always ends in failure.  If you don't believe this, look at educational games.  The fact is, the educational aspect of the game is not just the something we want players to do.  It is also a reward or punishment, and when we apply this to motivation to play the game, it becomes crystal clear why there are almost no decent educational games.

The educational aspect of most educational games is the "work" portion of the game, without any fun.  We hope to motivate students to work through the educational portion of the game, so that they can learn what is being taught and gain some skill in the subject.  We do this by rewarding them for their successes.  Unfortunately, this is not what the players see.  The players don't see the work as the thing that they have to do to earn the reward.  They see it as a punishment for playing the game.  When we punish people for playing our games, they don't want to play those games.  If we cannot see beyond our idealized version of how the game aught to be played, through the eyes of the players, our target audience, we will miss the fact that our games are awful, because we are using learning, which should be fun, to punish the players for playing the game, and in the end we will find that we have alienated our target audience and caused them to hate learning, which is the opposite of our goal.

When making a game for any purpose besides entertainment, it is essential to understand both our target audience as well as the psychological ecosystem created by our game.  If we lose sight of the primary goal of any successful game, to engage players and motivate them to continue playing, it does not matter how good or effective our game is at its stated goal, it cannot be successful, because a game that no one wants to play cannot have a positive impact on anyone.

There are three essential facets to the above quote when designing educational games:

1. Reward the players for playing the game.  This should be the first goal for every game.  If no one wants to play your game, it cannot benefit anyone (except, perhaps, as an example of what not to do).
2. Do not let the educational element of the game become a punishment for players.  If the educational element becomes a punishment, it won't matter if people play your game either, because it will just make them hate learning and hate the subject you are trying to teach.  It does not matter if your players come away knowing math or reading or anything, if they hate it so badly they never want to use it again.
3. Reward players for trying to solve your educational problems, and reward them more for success.  Don't punish them for failure.  The time lost on a failed attempt is already punishment enough, and one of the strongest motivators for playing games is that the cost of failure is low.  Don't make it worse, especially in a game that may already be less motivating than you might want it to be.

These are in order of importance.  A game that does not satisfy #1 has no value, because no one wants to play it in the first place.  An educational game that does not satisfy #2 harms the education of the student, instead of improving it.  An educational game that does not satisfy #3 probably does not satisfy #2 or #1, and even if it does, it is not going to be as effective as it could be, because it does not encourage the player's brain to consider the value of the information to be high enough to store.

This is educational game psychology in a nutshell.  Making effective educational games is not horribly difficult.  In fact, it only requires the same mentality that making successful non-educational games does, with a few extra priorities below the most important one.

Video Game Development: Scheduling

Scheduling is an essential part of game development.  It is how the game decides what subsystems and tasks to run, when, and in which order.  The three most common game subsystems are physics, graphics rendering, and input handling.  These three subsystems are what defines a video game, but they don't have to be everything.  Many games also have an audio subsystem and a networking subsystem.  Some of these, like the physics engine, must run at at least once per game loop.  Some have specific performance requirements to avoid problems, like the input handing and networking systems.  Some are less important but still need to be managed well to avoid annoyances, like the audio system.  Managing all of these is called scheduling.

Subsystems

The most important subsystem of a game is the physics engine.  This handles things like movement of game entities, state changes, and pretty much everything that happens in the game world.  It is sometimes split into multiple pieces, to make management easier, but generally all parts of the physics engine should run at the same speed, and there is usually some order of operations requirement for a good game play experience.  The physics engine does not have to run at a perfectly consistent rate, but it should never be allowed to get more that a few milliseconds behind or ahead, otherwise the game will run too fast or lag.

The second most important subsystem is input handling.  This is often grouped as event handling, which deals with input as well as intersystem communication within the game.  The important thing with input handling is that it happens often enough to keep the game highly responsive.  When a player clicks the mouse, presses a key, or presses a button, the effect on the physics engine should appear to be immediate.  Players can perceive very small amounts of input delay, and laggy input can easily make a great game unplayable.  The input handling system never needs to run more frequently than the physics engine, but it should generally run at least as fast as the renderer.

The third most important subsystem is rendering, often called the graphics engine.  The graphics engine shows the player what is happening within the game world.  The only reason it is less important than physics and input is that the graphics engine's performance requirements are much more flexible.  A game that renders slowly can still be playable if the physics engine and the input handling are running at an acceptable rate.  If the physics engine is too slow though, the game lags, and if the input handling is slow, the player loses the ability to respond quickly.  With a technique called frame skipping, it is acceptable to skip rendering to allow the game engine and input handling to catch up if they get behind.  There are two good rules of thumb for choosing a default frame rate.  The first is avoid going over around 60 to 75 frames per second.  This is because above about 50 frames per second, the human eye is not capable of transmitting data to the brain fast enough to see any difference.  This is also because most monitors have a refresh rate of 60Hz or 75Hz, which means that rending faster than this literally will not make any difference.  The other rule of thumb is to avoid frame rates lower than around 30 frames per second, and if the game is going much lower than 20 frames per second, the user is going to assume that his or her computer just cannot handle the game.

Other subsystems can depends on a lot of factors.  Networking generally needs to be very responsive, to keep things synchronized.  If the audio subsystem is not running frequently enough, it can end up with the sound not synchronized with the game, but it can always skip playing less important sounds if necessary.  If you are doing something like dynamic terrain generation in the background, you will want it to go fast enough that nothing important gets into an ungenerated area, but not so fast that the physics engine starts to get laggy.  In general, other subsystems are not as important as the top three, but when any of the top three rely on them, it may be necessary to give them higher priority.

Game Loop

The game loop is where most of the scheduling occurs.  Unless you are multithreading to put graphics or networking in another thread, the game loop decides when to call all of the various subsystems.  The order subsystems are called in does matter, though it typically matters the most when you have more than the main three.  The input handling should happen directly before the physics, so that the physics is working with the most recent input.  This is important for minimizing input delay.  The graphics engine should generally render directly after the physics engine runs, to display the new game state to the user as soon as possible.  If the game is networked, that may need to happen either right before or right after the the input handling or the physics (depending on the details of the protocol).

The game loop is responsible for timing.  This may mean that the game loop is responsible for making sure that the physics engine is kept above a minimum rate, or it might mean that it needs to keep it within a certain range.  It should make sure that input is handled regularly and that rendering happens without getting in the way of anything more important.  It also needs to deal with running other subsystems regularly.  The most important thing is managing priorities.  In some ways, a game loop is like the scheduling system in an operating system, though with rather less complexity.

Scheduling Algorithms

The scheduling algorithm is the strategy used by the game loop to keep everything running smoothly.  There are two popular scheduling algorithms that can be adjusted to fit most situations.

The first popular scheduling algorithm is time scaling.  Long ago, game loops did not do any scheduling.  They relied on the speed of the processor to maintain appropriate game speed.  This eventually lead to a problem.  When Intel's 80386 processor came out, a lot of people noticed that their games would run way too fast.  The games were designed on much slower 80286 or older processors, and these were slow enough that limiting speed had never had any value.  With the 80386 though, these games ran so fast that they were unplayable.  The initial solution was that most computer manufacturers added a "turbo" button to their 80386 and 80486 computers that would reduce the clock rate of the chips to make older games playable.  Of course, new games would also have this problem if the developers did not do something about it, and relying on the continued existence of the turbo button, as even faster computers appeared, was clearly not a wise option.  One of the solutions to this problem was to scale the speed of the physics engine to the time passing.

The time scaling scheduling algorithm is simple.  Any time any state change occurs in the game world, the magnitude of the change is scaled by how much time has passed since the previous game loop.  If a game entity was set to move at 10 pixels per second, and one tenth of a second had passed, the entity would move 1 pixel.  This provides a major advantage in two ways.  If the game is running extremely fast, the game world still runs at the expected rate, just with finer precision.  If the game is running very slow though, it still seems to run at the correct rate, and the slowness is only apparent in rendering and input delay.  In other words, for any given computer, the game physics appear to run at the same rate, and only the visual representation and responsiveness suffer.  There are also several costs to this scheduling strategy.  The first is that it requires many physics variables to be floating point variables, to deal with the very fine granularity of the game running on a very fast system.  This can degrade performance on slower systems.  The second is that floating point math is inherently inaccurate.  While these inaccuracies generally only occur on an extremely small scale, which will not be noticed by a player, they add up enough to make it quite difficult to keep networked games synchronized.  The problem is that floating point error adds up faster on fast machines than slow machines, which means that two networked machines doing the same math will probably not end up with the same cumulative results.  This problem can be mitigated, but another scheduling strategy exists that makes it unnecessary.

The fixed rate scheduling algorithm runs the physics engine at a fixed rate.  The physics engine does not need to do any time math, because it can assume that each time it is called, the same amount of time has passed.  The game loop typically handles this by keeping track of how much time a given loop has taken, and then sleeping for the remaining time at the end.  One problem with fixed rate scheduling is that if the operations in the loop take longer than the allotted time, the game will get behind and start to lag.  This makes it not very resilient to slower computers.  In addition, this can make collision detection more difficult, as game entities generally move in larger fixed distances than time scaling.  The problem arises when a game entity is moving fast enough that it traverses the distance across another entity in one frame, effectively moving right through it.  The benefits of fixed rate scheduling include the fact that it does not waste CPU cycles unnecessarily, and as long as the ends of a networked game are on the same physics frame, their state should be identical.

In modern games, fixed rate scheduling is generally preferred, because so many games are networked, and it is the best algorithm for networked games.  Its downsides are pretty serious though.  It does not scale down well, which can limit the game to only faster systems.  The length of intervals cannot be guaranteed, because no sleep function provides a 100% guarantee that it will sleep for exactly as long as requested.  These are some pretty serious problems, as they mean that the game can get behind or ahead at the whim of the operating system, and slow systems will just have to deal with chronically laggy games (which does not work at all for networked games).  Fixed rate scheduling comes with more serious problems than time scaled scheduling, but it turns out they are also easier to deal with.

The typical fixed rate game loop does more than just running all of the subsystems and then sleeping for the remaining time.  It also prioritizes subsystems, ensuring that the most important ones always get as much time as they need, at the cost of the less important ones.  In addition to this, it keeps track of how much time passes during sleeps, so that it can mitigate cases where a sleep takes longer than expected.  A fixed rate game loop in Python might look like this:

while(run):
    new_t = time.time()
    pending_time = pending_time + new_t - t  # Add time elapsed
    t = new_t

    input_handler()

    while (pending_time > 0.020):  # 20ms is 50 times per second
        update()  # A common function name for physics
        pending_time = pending_time - 0.020

    render()  # A common function name for graphics
    sleep(0.20 - (time.time() - t) - pending_time)

Here are some things to note:

We only get the current time to store once per loop.  There is no reason to do it more often, and in fact, if we do, we may end up frequently losing small amounts of time.  An important note is that time.time() is not a high precision timer, and thus it should not be used for real games.  Pygame has a Clock object that is much more suited to this purpose.  Likewise, sleep() is also too low resolution to be used for games, but Pygame's Clock object can manage this functionality as well.

Instead of keeping track of only the time elapsed since the last loop, we are keeping track of all time elapsed, and then we are subtracting the expected time per loop from that for each time we run the physics engine.  This ensures that if the OS sleeps for too long, we eventually get that time back when it adds up to enough to matter.

The physics engine runs in a while loop.  This allows us to catch up if we get behind.  If enough sleeps taking too long adds up to a full game loop of time, we will just run the physics engine an extra time during the next loop, which will catch us right up.

The render and input handling are outside of the while loop.  This essentially skips frames if the game is behind, and since rendering tends to take a long time, skipping a frame now and then can allow the game to run smoothly even on slower systems.  If the game has to skip a lot of frames, this may result in significant input delay though, so it may be better to put the input handler inside the loop as well, if you expect a lot of customers to be running your game on computers that can only barely handle it.

The while loop subtracts 20ms from pending_time each time it runs the physics engine.  This is the second part of what allows us to keep track of smaller amounts of leftover time.

The sleep function only sleeps for 20ms minus the time elapsed since we began the last game loop and the pending time.  The first part is there, because we only want to sleep for the remaining time.  It accounts for the part of the 20ms that has already been used running the various subsystems.  The second part is there to keep the time intervals as consistent as possible.  Ideally, this means that if there is any time pending, we only sleep just long enough that we have accumulated exactly 20ms.  In practice, this is unlikely to happen often, but doing this will help to avoid skipped frames as much as possible, by reducing the chances that pending_time will ever accumulate enough time to run the physics more than once a loop.


This example is fairly simple, and it does not include any extra subsystems.  Most subsystems will need to be included in the same priority level as the physics engine or renderer, but lower priority subsystems may need a new priority level.  This might be done by checking how much of the 20ms (or whatever period you give your game loop) is remaining after the first and second priorities have run, and if there is not enough time, skip them and go straight to the loop.  Even more complex priority systems can be created  as well, ensuring that the top priority subsystems run every loop, and then rotating through the lower priority subsystems, running or skipping a few each loop, depending on timing.  It is important to keep in mind though, that the game loop is the top level bottleneck for the game, and it is possible for a complex scheduling system to end up taking up more time than it ultimately saves.  You may need a complex scheduling system, if you have a lot of different subsystems, and if each subsystem needs a certain level of reliability to be guaranteed, but if you don't actually need this, don't do it.  The scheduling system's job is to make sure the game runs smoothly and responsively, and if the scheduling system itself becomes too heavy, it will get in its own way.

Good scheduling is an essential element in the development of a good game.  The scheduler budgets time, ideally making sure that everything gets as much time as it needs, but rationing time effectively when there is not enough to go around.  Choosing or developing a good scheduling algorithm for your game can be just as important as any other part of development, because it really does not matter how awesome your game is if it is unplayable.  In addition, a good scheduler can allow your game to run smoothly on a much wider range of systems, dramatically increasing the size of your market.