Toni Westbrook dot Com

The Joy of Computer Science and Engineering

Before we get started, I feel the need to point out that this entry will in no way even begin to approach the territory of being comprehensive in the study of video game physics. This is targeted toward those who have little background in physics and is very much a starter tutorial. In general, the better and more realistic the game physics, the closer you’re getting to actual physics - and that’s a lifetime study in itself. However, there are some basic tips and tricks to know when dealing with intro action and arcade style games.

Newton and his Mechanics

While games have gone from simple squares on the screen to 2D sprites to 3D-super-rendered-polygon-ray-traced-blammo-wow objects, the actual science behind their movement on the screen has stayed relatively the same - mainly because their movement is based on the movement we’re used to, what we see all around us every day. We reproduce it in our video games (for the most part) because it’s natural and makes sense to us. We’re mirroring physics! Specifically Classical (or Newtonian) Mechanics. We generally don’t need to take into account relativity or quantum mechanics when making Mario jump from one green pipe to another.

So to understand how the pod in Lunar Lander works, we need to understand how a real lunar lander would work. But let’s start out more simply.

Mass and Position

What is mass? This is a large, fundamental question that involves inertia, resistance to movement, the amount of force necessary to move the object, etc. But we don’t need to get that deep into it. Mass is physical stuff. You have mass, a ball has mass, the planet has mass, your dog has mass, Catholic churches have Mass, etc. (ba-dum-dum). Anything physical has mass. It doesn’t start moving for the most part, it stays where it is until something pushes it (in the case of a person, your muscles). If it’s already moving, it doesn’t stop moving unless something stops it (a wall, friction, a large rope, etc). It basically keeps doing whatever it’s already doing.

Reproducing an object that sits there and does nothing is very easy to do in a video game. Simply create a representation of an object, whether it be a colored square (Pong), a bitmap graphic (Mario), or a polygon object (Lara Croft) and put it on the screen. The actual way to do this is outside this tutorial (Check out Creating a Blackberry Game if you’d like to see how to do it in Java). Just as in the real world an object has a position, in the video game world, the object will have a position too - a coordinate on the screen. In the below example, we use a simple object that is 1 pixel in size for a pong-like game.

The green pixel is our pong ball

When programming this, we would need to store the dot’s X coordinate and Y coordinate into variables, in this case, store a 6 in X, and a 2 in Y. If we wanted to use the arrow keys to move this object, we would simply add or subtract from the coordinates as the appropriate key is pressed (e.g. pressing up -> Add 1 to Y, pressing down -> Subtract 1 from Y, pressing right -> Add 1 to X, pressing left -> Subtract 1 from X). Then redraw the object in its new location. Our drawing routine would always just take the values and of the X and Y variables and draw a pixel at those coordinates on the screen.

While this would be enjoyable for 2-3 seconds, it would overall be a fairly boring game. We would be doing physics’ job in this case, telling the object how to move every step of the way. We want physics to carry its load. So let’s program in another property.

Onto Part 2

I remember the first time I formally encountered recursion - it was sophomore year of high school and I was watching as my CS teacher, Mr. Kendall Chun, was explaining how instead of using loops, a function could repeatedly perform an action by calling itself. The concept at the time just completely blew me away. It seemed to me, like I think it does to a number of people when they first learn about it, almost magic. I used it on more of a faith basis until I became more comfortable with it - and now, like any programmer, it is a standard part of my arsenal.

What is Recursion?

While recursion is a powerful technique, there is definitely nothing mystic about it. Simply put, recursion is when a function uses itself in it’s own definition. It can be a little easier to demonstrate by showing an example.

Non-Recursive Function

First off, remember that a function is a dependence between two values - or in plain terms, it’s a “machine” where input goes into it, and output comes out. Usually that output is generated by doing something to the input.

Take f(x) = x+3. This is a simple function that says whatever I put in, I get that plus 3 out - so if I put 7 in, I get a 10 out. f(7) = 7+3 = 10. No biggie, the function is defined in terms of x - we put a 7 in for x, we got a 10 out - no recursion yet.

Recursive Function

The most classic example of a recursive function is the factorial function. For those unfamiliar, the factorial function multiplies all integers less than or equal to itself, and is represented by an exclamation mark. So 5!, or 5 factorial, is equal to 5 * 4 * 3 * 2 * 1, or 120.

Why is this recursive? Check it out:

• 5! = 5 * 4 * 3 * 2 * 1
• 4! = 4 * 3 * 2 * 1
• 3! = 3 * 2 * 1
• 2! = 2 * 1
• 1! = 1

So I’ve listed the factorials of each of these numbers out, so what? Well, if 4! = 4 * 3 * 2 * 1, then we could say:

• 5! = 5 * 4!
• 4! = 4 * 3!
• 3! = 3 * 2!
• 2! = 2 * 1!

As can be seen, any factorial is the number going into it times the factorial of one less that number. This means that factorial uses itself as its definition -

f(x) = x * f(x-1)

Factorial is the number going into it (variable x) times the factorial of the number minus 1. So factorial of 5, or f(5), is 5 * f(4). What’s f(4)? 4 * f(3). f(3) = 3 * f(2), and f(2) = 2 * f(1).

The Base Case

The issue is that for recursion to be useful, it has to STOP somewhere. In the factorial example, nothing stops it. We would say f(1) = 1 * f(0), f(0) = 0 * f(-1), f(-1) = -1 * f(-2), ad infinitum. Endless loops are no fun (unless the basis of annoying pranks), so we need a way of saying STOP! This is where the “Base Case” comes in. It is simply a point during execution, or in the definition of the function, that says “no more calling yourself, stop the looping madness”.

In the case of factorial, it’s f(0). f(0) = 1. Period. It doesn’t involve itself any longer, it just returns 1 - it’s a static value, an axiom, a solid rock, where the buck stops. Every recursive function needs a base case.

Full Execution

So the full definition of our factorial function is

f(0) = 1
f(x) = x * f(x - 1)

That means, if we call f with 0, we get 1, otherwise we perform the second operation. Let’s try it out with 4. We should get 4 * 3 * 2 * 1 = 24.

• f(4) = 4 * f(3)
• f(3) = 3 * f(2)
• f(2) = 2 * f(1)
• f(1) = 1 * f(0)
• f(0) = 1

Now we know what each function returns, we can fill in the unknown values

• f(1) = 1 * f(0) = 1 * 1 = 1
• f(2) = 2 * f(1) = 2 * 1 = 2
• f(3) = 3 * f(2) = 3 * 2 = 6
• f(4) = 4 * f(3) = 4 * 6 = 24

It worked! And is very easy to implement in whatever programming language you happen to be using. Once you become comfortable using recursion, you’ll find it’s useful all over the place, because the world around us uses recursion constantly - it is a large part of math and our Universe.

Other Fun Examples

Looking for some more examples of recursion?

• The Fibonacci Numbers - 0, 1, 1, 2, 3, 5, 8, 13, 21, etc. Each number is defined by adding the two numbers before it - so f(x) = f(x-1) + f(x-2). Double recursion - it makes use of itself twice! Our base cases are f(0) = 0 and f(1) = 1.
• Any Geometric Series - The powers of 2 for example - 1, 2, 4, 8, 16, 32, 64, 128, 256. Each number is the previous number times 2. We could define this using exponents, but let’s do it with recursion! f(x) = 2 * f(x-1). Base case f(0) = 1.

Recursion rocks, so try finding some situations where loops are used that you could use recursion instead - it’s a lot more fun!

Whether you’re completely new to programming, or have been out of the game for so long that you’re completely lost, an important first step in becoming a coder is choosing your first language. While it is true that learning the principles behind Computer Science is what is truly important, in practice one needs a way of implementing these important concepts, converting theoretical into reality, and a trusted language is necessary for this. There are thousands of programming languages at the disposal of the modern day programmer, and making a choice of which one to use can be a little daunting. Coupled with this, there is no one language that fits all situations, each language has its own strengths and weaknesses in different areas.

What Platform Will You be Programming For?

The first question to ask is what system are you creating software for? This isn’t simply a question of Windows vs OS X vs Linux. You could be programming console systems like your Playstation 3 or Dreamcast. You could be interested in creating applications for your smart phone, such as a Blackberry or Treo. Or perhaps you want to write a small program to run a microcontroller in a robot you’ve built.

If you are indeed completely new to programming, you may want to start by writing programs for your computer. Programming for unique architectures can often have their own slew of hiccups and peculiarities that will detract from learning core ideas. The goal is to become comfortable with the idea of programming in general, get the general concepts under your belt, then move on to the more advanced stuff as you feel more confident.

Okay, So What Language Do I Choose?

Even after making the decision of starting with your PC as a platform, the choices aren’t over yet. Most languages can be used to create programs on your desktop. The ones we tend to hear a lot about are BASIC/Visual Basic, C/C++/C#, and Java. Once you have chosen a language, you need a program called a “compiler” which converts your code into machine code the computer can understand. Below I’ve posted links to a few popular choices.

BASIC / Visual Basic

BASIC has typically been used as a beginner’s language. It’s easy to learn and quick to implement. However, the same simplicity that makes it a great language to start with also limits its potential as projects get bigger and more complex. In comes Visual Basic (especially modern day VB.NET). It combines the simplicity of BASIC’s syntax with the power of .NET and object oriented programming. While you may not be familiar with these concepts, VB.NET paves the way of making life easy until you’re ready to tackle these advanced topics.

For those looking to start with BASIC, especially one geared toward game development, Dark BASIC (http://darkbasic.thegamecreators.com/) is an excellent choice. Though it is not free, there is a trial version, and the full version is only $39.99 (at the time of this article).

If you’re looking to go with Visual Basic, which is this author’s suggestion, Microsoft currently offers Express editions of all its products, completely for free. The entire product family is incredibly powerful and a very good deal (free!). Check out Visual Basic Express 2008 (http://www.microsoft.com/express/vb).

C / C++ / C#

The C family of languages are definitely less fluffy than Visual Basic. However, this fits their purpose - less of beginner languages, and more powerful as projects get larger and more involved. This is not to say it is impossible or even a bad idea to learn programming using C - there are many concepts central to Computer Science and computer architecture in general that can be demonstrated much more clearly with C than with VB, such as memory management.

C/C++ have been around for a while and are the preferred languages in many different environments - because of which a large number of tools can be found. Again, Microsoft offers Visual Studio Express versions of their C++ compiler. The far most well known compiler, however, is the GNU compiler, which can be found on countless platforms, including UNIX, Linux, OS X, etc. For more information, check it out here (http://gcc.gnu.org/)

C# is a creation of Microsoft and tied much more closely to the .NET framework. While it may be not the perfect choice for a beginner language, it is a great language for both web application work as well as creating applications for Pocket PCs and Windows Mobile powered smart phones. Visual Studio Express also contains a C# module.

Java

Java is another interesting choice - it looks similar to C++ at first glance, but offers something quite different. Java is geared toward true cross platform portability. When you write and compile Java code, it is turned into what’s called “Byte Code” which actually runs on a virtual machine on top of your real machine. What’s neat is that while the real machine underneath can be different, each machine will run the same virtual machine, so the code you write for one platform will theoretically work for another. Java, for this reason, is an excellent choice for client side web applications and mobile applications on cell phones. When I write applications for my Blackberry, I always use Java. Sun offers its official (and free) Java compiler as a part of the Java SDK (JDK) - you can find it here (http://java.sun.com/javase/downloads/index.jsp).

You’re On Your Way

The language you begin with is important - it is your first companion as you explore the sights and wonders that are Computer Science. Don’t be too worried about picking the perfect language though - if you’re fairly comfortable with your choice you’ll be fine, and once you’ve built up some programming skills, you can easily branch out and try new languages, especially ones that might suit your needs in the particular project you’re working on. Good luck!