Copyright © University of Cambridge. All rights reserved.

- 1 Introduction
- 2 First Person Shooters
- 3 Strategy Games
- 4 Simulation Games
- 5 Conclusion
- 6 Answers
- 7 Interesting Web Pages

The purpose of this article is to have a look at how mathematics is used in computer games. I'll use examples from computer games you've probably already played. There are lots of different types of computer games, and I'll talk about how maths is used in some of the following examples:

The First Person Shooter (FPS) is a type of game where you run around 3D levels carrying a big gun shooting stuff. Examples of this sort of game include Doom , Quake , Half Life , Unreal or
Goldeneye . There are other games that look very similar, but aren't first person shooters, for instance Zelda: Ocarina of Time or Mario 64 .

The Strategy games are divided into two main types, Real Time Strategy (RTS), and Turn Based Strategy (not usually called TBS for some reason). These games usually involve building and managing a city or civilization and also fighting wars by controlling troops. Examples
of real time strategy games are Age of Empires , Command &; Conquer , Tiberian Sun . Examples of turn based strategy games are Civilization and Alpha Centauri .

Simulation games are games that try to make something as realistic as possible. For instance, Flight Sims are computer games which try to realistically simulate flying an aeroplane or helicopter. Two games of this sort are Microsoft Flight Simulator and Red Baron . Space sims are like flight sims, but with spaceships instead of planes. For instance, Wing Commander or X-Wing vs. Tie Fighter . Racing games are games which simulate driving different sort of
cars. For instance, Need for Speed , NASCAR Racing , Gran Turismo or Driver .

There are some exercises which you can do (if you want) throughout this article. The answers are at the end of the article, but do have a go at solving them on your own first.

.

If you find any of the article patronising, I apologise, my excuse is that the article is aimed at people of many different ages so there might well be bits you already know. If you already understand one bit, you can just skip through until you get to something more interesting.

The most amazing things about FPS are their incredible graphics. They look almost real, none of this would have been possible without the use of advanced maths. Here are some pictures from the early games (Wolfenstein) to the most recent games (Quake III Arena). All of the following screen shots are from games by iD software.

To begin to explain how these games work, you need to know a bit about *geometry* , *vectors* and *transformations* .

*Simple geometric figures*

If you have a line and a plane, you can find the point where the line cuts through the plane. In fact, sometimes you can't find the intersection, because they don't meet and sometimes the line is inside the plane so they meet at every point on the line , but this doesn't happen in the cases we're interested in. We call this the intersection of the line and
the plane. Here is a picture of what this looks like.

*Intersection of a line and a plane*

A vector is a mathematical way of representing a point. A vector is 3 numbers, usually called $x$, $y$ and $z$. You can think of these numbers as how far you have to go in 3 different directions to get to a point. For instance, put one arm out pointing to the right, and the other pointing straight forward. I can now give you a vector and you'll be able to
find the point I'm talking about. For instance, if I say $x=3$, $y=1$, $z=5$, you find the point by walking 3 metres in the direction of your right hand, then 1 metre in the direction of your left hand, and then getting a ladder and climbing up 5 metres. Here is a picture of a vector.

*Picture of a vector and directions*

Vectors are written as $(x,y,z)$, for instance $(1,2,3)$ means move 1 in the x-direction, 2 in the y-direction and 3 in the z-direction.

One confusing thing about vectors is that they are sometimes used to represent a point, and sometimes they are used to represent a direction. The vector $(1,0,0)$ can mean both ``the point you get to if you move 1 unit in the x-direction from the starting point'', or it can mean ``move 1 unit in the x-direction from where you are now''.

**Exercise 1** *[Adding Vectors]*

*If I start at the point represented by the vector $(0,0,0)$, then I travel along the vector $(1,2,3)$, and then I travel along the vector $(4,5,6)$, where will I be? This vector is called the sum of the two vectors, $(1,2,3)+(4,5,6)=(?,?,?)$.*

*Translations and rotations*

**Exercise 2** *[Translations]*

*If I translate the vector $(1,2,3)$ by 5 in the y-direction, what is the vector afterwards? In general, if we write a translation as $T$ and a vector as $\mathbf{v}$, then the new vector if written as $T\mathbf{v}$. For example, if $T$ is ``translate 1 unit in the x-direction'' and $\mathbf{v}=(0,0,0)$, then $T\mathbf{v}=(1,0,0)$.*

The basic idea of 3D graphics is to turn a mathematical description of a world into a picture of what that world would look like to someone inside the world. The mathematical description could be in the form of a list, for instance: there is a box with centre $(2,4,7)$ and sides of length 3, the colour of the box is a bluish grey . To turn this into a
picture, we also need to describe where the person is and what direction they are looking, for instance: there is a person at $(10,10,10)$ looking directly at the centre of the box . From this we can construct what the world would look like to that person.

Imagine there is a painter whose eyes are at the point $P$. Imagine that he has a glass sheet which he is about to paint on. In the room he is painting, there is a wooden chest. One of the corners of the chest is at point $A$, and the painter wants to know where that corner of the chest should be on his glass sheet. The way he works it out is to draw a line $L$ from his eyes ($P$) to the
corner of the chest ($A$), then he works out where this line goes through the canvas, $B$. He can do this, because the glass sheet is a plane, and I mentioned that you can find the intersection of a line and a plane above. This point $B$ is where the corner of the chest should be in his painting. He follows this rule for every bit of the chest, and ends up with a picture which looks exactly like
the chest. Here are two pictures, the first one shows the painting when he has only painted the one corner of the chest, the second one shows what it looks like when he has painted the entire chest.

*Projection on to a plane*

What I just described above is similar to what the computer is doing (50 times a second!) every time you run around shooting hideous monsters in Quake , although the details are slightly different. In computer games (at the moment) the description of the world is just a list of triangles and colours. The newest computer games are using more complicated
descriptions of the world, using curved surfaces, NURBS and other strange sounding things, however in the end it always reduces to triangles. For instance, a box can be made using triangles as illustrated below.

*Box made from triangles*

Here is a much more complicated example, using thousands of triangles. The first picture shows the triangles used, the second picture is what it looks like with colours put in.

*Viking Helmet*

The reason for using triangles is that they are a very simple shape, and if you make sure that everything is made from only one type of shape, you don't have to write a separate program for each type of shape in the game.

**Exercise 3** *[Making triangles] Draw a picture of a box with a smaller box stuck to the top of it, using only triangles.*

Each time the computer draws a picture of the world, it goes through the following steps: Firstly, it transforms the world (by rotating and translating), so that the person is at position $(0,0,0)$ and the centre of the glass sheet (the centre of the screen in computers) is at $(1,0,0)$. This makes the rest of the calculations much easier. Secondly, it removes all the triangles you can't see so that it can forget about them, for instance the triangles that are behind you or the ones that are so far away that you can't see them. Thirdly, for every remaining triangle, it works out what it would look like when painted on the glass sheet (or drawn on the screen in computers). Finally, it puts the picture it has drawn on the screen. Nowadays, computers are so fast that they can draw hundreds of thousands of triangles every second, making the pictures more and more realistic, as you can see from the pictures at the beginning of this section.

Of course, there is a lot more to it than just that: there is lighting, fog, animation, textures and hundreds of other things. Most of these use maths and physics to a large extent, but what I have described so far is the most important part of making 3D graphics look right.

*Graph with directed edges*

To complicate things even further, we sometimes want to add something called a cost to each edge. The idea of a cost is that it indicates how much it would cost to travel down that edge. A simple example of this is shown below.

*Graph with costs*

In this graph, most of the people in city $A$ want to get to city $C$, whereas only a few want to get to city $B$. Unfortunately, both roads are the same size, this means that there are long traffic jams on the road from $A$ to $C$, it takes about 30 minutes to get there. To get from $A$ to $B$ is much easier as most people are going to $C$, so it only takes 5 minutes. The numbers written next to
the edges indicate how long it takes to travel along that edge. Here is another (much more complicated) example.

*More complicated graph*

**Exercise 4** *[Shortest Path] Work out the lowest cost way to get from* A to *K* .

Now you know all you need to know to be able to understand path finding. If you did the last exercise, you'll have already solved one example of the sort of problem computers have to solve to guide troops through complicated maps.

How does all this stuff about graphs help the computer guide troops around levels? It makes a graph where every interesting point is a node on the graph, and every way of walking from one node to another is an edge, then it solves the problem you solved above to guide the troops. There are some complications. For starters, what are the interesting points? You might think that every position
on the entire level is interesting, but for most games this would lead to hundreds of thousands of interesting points, and finding the path would take years. Instead, the people making the game decide where the interesting points are. For instance, if there is a wide open expanse (a big field perhaps), you don't need a node at every point on the field, because the troops can walk in a straight
line across the field. Basically, you only need nodes around obstacles. Here is an example of a map of a level seen from above.

Once you have chosen your interesting points, you need to connect them up with edges, you can only connect up those nodes which don't have an obstacle between them.

**Exercise 5** *[Make your own graph] Place nodes at the interesting points on the example map above, then connect up the nodes with edges, remembering that you can only connect up nodes with straight lines, and the straight lines cannot go over obstacles.*

Once you have created a graph for a given map, the computer has to go through the following steps to guide the troops. Firstly, it has to work out what the nearest node that he can walk to in a straight line. This node is his starting node. Secondly, he has to work out the node which is nearest to his destination is (making sure he can walk from that node to the destination in a straight line of course!). This node is the destination node. Thirdly, he works out the shortest path connecting his starting node to his destination node. Now, all the troops have to do is walk to the starting node, then walk along all the nodes between the starting node and the destination node, along the connecting edges, then they walk from the destination node to the final destination.

To make things a bit more interesting, we can add costs to all of the edges. For instance, if there is a crocodile pit in the space connecting two nodes, the cost of crossing this crocodile pit is very high, so it might be a better idea to go the long way round even though crossing the crocodile pit is shorter. Of course, if the long way round would take the troops 3 days, and crossing the crocodile pit only took 15 minutes, they might decide that it would be better to take the risk and get there before the battle has moved elsewhere. You have to choose the costs carefully to make sure this sort of problem is solved in the best possible way. Here is an example of a map with edges with costs.

I haven't actually talked about how to get a computer to find the best path from one node to another yet. The total cost of getting from $A_1$ to $A_m$ via $A_2$, $A_3$, ..., $A_{m-2}$, $A_{m-1}$ is found by adding up the cost of going from $A_1$ to $A_2$, $A_2$ to $A_3$, ..., $A_{m-1}$ to $A_m$. The problem is to find the right choice of nodes that this total cost is as small as possible. One way of doing it would be to find all possible ways of getting from one node to the other, work out the total costs of each, and choose the smallest one. Unfortunately, this would take even the fastest computers much too long to do. There is a way of working this route out very quickly, but it is a bit complicated to explain here. However, if you're keen, you can look it up on the internet (search for the A* Algorithm - A* is pronounced A star), or you can check out the references at the end of the article.

**Exercise 6** *[Vectors]*

*(a) What is (1,2,3)+(3,2,1)?*

*(b) What is 10x(9,5,2)?*

*(c) What is the length of (4,2,4)?*

Every object has a position , which is a vector $\mathbf{x}$. It also has a velocity , which is the direction it is travelling in, it is also a vector $\mathbf{v}$, sometimes written as $\mathbf{\dot{x}}$. Every object also has something called an acceleration , this is
how fast the velocity is changing, and it is also a vector $\mathbf{a}$, sometimes written as $\mathbf{\ddot{x}}$. Finally, every object has something called mass , this is basically how heavy the object is, and is usually written $m$, but this is not a vector. If an object starts at position $\mathbf{x}$, and has a velocity $\mathbf{v}$ which doesn't
change, then after $t$ seconds, the position of the object is $\mathbf{x}_t=\mathbf{x}+\mathbf{v}\times t$. In case you're wondering what $\mathbf{x}_t$ means, it just means the position at time $t$. Similarly, $\mathbf{v}_t$ means the velocity at time $t$. If an objects starts with velocity $\mathbf{v}$ and has an acceleration $\mathbf{a}$ which doesn't change, then after $t$ seconds, the
velocity of the object is $\mathbf{v}_t=\mathbf{v}+\mathbf{a} \times t$.

Here is an example of how to use this to work something out. Suppose Billy-Joe Bob is floating in space, his position is $(100,150,150)$ and he throws a rock with velocity $(5,2,0)$. Where is the rock after 10 seconds? To work this out, we use the formula above: $\mathbf{x}_t=\mathbf{x}+\mathbf{v}\times t$. In this case (after 10 seconds) the rock is at $(100,150,150)+(5,2,0)\times
10=(100,150,150)+(50,20,0)=(150,170,150)$.

**Exercise 7** *[Throwing Rocks in Space] Billy-Joe's mortal enemy, Arthur Blenkinsop is at (240,640,143), reading his newspaper, unaware that Billy-Joe is watching him. Billy-Joe decides to throw his rock at Arthur. Billy-Joe is slightly obsessed with the number 7, so he wants the rock to take exactly 7 seconds to reach Arthur, what velocity should he throw the rock
at?*

If Billy-Joe wasn't in space, the problem would be much harder, because every object on Earth is pulled downwards by an acceleration caused by gravity . This acceleration is the same for every object on Earth, and if the y-direction is upwards, then the acceleration is $\mathbf{g}=(0,-9.81,0)$. The reason the problem is now harder is that the velocity changes, so you can't use the equation above to work out the position at different times. If we have a computer, we can work out things like this, but not exactly. The way we do it is by saying that the velocity is only changing very slightly over very small amounts of time. For instance, the velocity only changes by a very small amount in 0.02 seconds. So, we can work out what happens for very small amounts of time, if $s$ is very small, maybe $s = 0.02$, the equation $\mathbf{x}_{t+s}=\mathbf{x}_t+\mathbf{v}_t \times s$ is very close to being correct. In that equation $\mathbf{x}_{t+s}$ is the position at time $t+s$, $\mathbf{x}_t$ is the position at time $t$, $\mathbf{v}_t$ is the velocity at time t which we can work out because the acceleration doesn't change. By doing this repeatedly, we can get a computer to work out where the rock will be at any time, by working out where it will be after 0.02 seconds, then after 0.04 seconds, then after 0.06 seconds, and so on until we get to the time we want.

**Exercise 8** *[Throwing Rocks on Earth] Billy-Joe is at position (0,0,0), he throws a rock with velocity (0,4,0), where will the rock be after 1 second? To answer this question, the acceleration on the rock is (0,-9.81,0), and you should use* s = 0.2, you will need to use the method above 5 times to work it out. You might like to see if you can work out how long it takes
for the rock to hit him on the head.

How is all this stuff actually used in computer games? Here's a simple example. Every time you fire a bullet from your plane in your favourite flight simulator, the computer has to work out its position using calculations like the ones above with Billy-Joe throwing rocks around. The computer has to do these calculations 50 times a second for every bullet in the sky, and on top of that it has
to do much harder calculations for the planes as well. Unfortunately, things are not as easy as working out where Billy-Joe's rocks are. It is much more complicated, because in the real world, there are things like wind and friction because of the air. Here is how you might include wind in the calculations. Suppose the wind causes the bullet to have an additional acceleration of $\mathbf{w}$, and
the wind is blowing at a constant rate (the wind speed isn't changing). Now we have the acceleration on the bullet is $\mathbf{g}+\mathbf{w}$, which isn't that much more complicated than before. Friction in the air is much more complicated though, because the amount of friction depends on the speed of the bullet. In fact, the friction causes an additional acceleration of $-k\mathbf{v}$, where $k$
is some positive number and $\mathbf{v}$ is the velocity. So now the acceleration is $\mathbf{g}+\mathbf{w}-k\mathbf{v}$: in other words, the acceleration is changing as well as the velocity! This problem can be solved using the method above, where you assume that things don't change in small periods of time.

For the plane, things are even more complicated. If you fly your plane as high as it will go and then go into a nose dive, you might find that the wings of your plane rip off (if you are playing a flight simulator with new planes this might not happen, because planes are better now than they used to be). This happens because the air pushes the wings very hard, and they are not attached
strongly enough to the rest of the plane, so they just rip off.

Physics is one of the hardest bits in making computer games. Few games have accurate physics, most games only have something about as complicated as what I described above. It is such a hard problem that people are researching into how to simulate realistic physics in computer games even now, and they're quite a long way from the solution. So if you're interested in programming games and
you're interested in physics, then you might even find yourself working on this problem in years.

**Answer to Question 1** *[Adding Vectors]*

*The answer is $(1,2,3)+(4,5,6)=(5,7,9)$. This is because $1+4=5$, $2+5=7$ and $3+6=9$. The reason the answer is those sums is because to find out how far we go in the x-direction, we work out how far we have gone in the x-direction from the first vector, and add on how far we have gone in the x-direction from the second vector. We do the same for the y- and z-directions. In general,
$(x,y,z)+(u,v,w)=(x+u,y+v,z+w)$.*

**Answer to Question 2** *[Transformations]*

*The answer is $(1,7,3)$ because we add the vector $(0,5,0)$ to move 5 in the y-direction, and $(1,2,3)+(0,5,0)=(1,7,3)$. In general, a translation $T$ is something like ``add $(u,v,w)$ to the vector'', to $T(x,y,z)=(x,y,z)+(u,v,w)=(x+u,y+v,z+w)$. If you haven't done matrices and vectors at school, ignore the next bit.*

To rotate a vector by an angle $\theta$ about the x-axis, the matrix is

\mathbf{M}_{\theta} = \left( \begin{array}{ccc} \cos(\theta) & -\sin(\theta) & 0 \\ \sin(\theta) & \cos(\theta) & 0 \\ 0 & 0 & 1\\ \end{array} \right)

So$\mathbf{M_{\theta(x,y,z)}}=(x\cos(\theta)-y\sin(\theta),x\sin(\theta)+y\cos(\theta),z)$.

**Answer to Question 3** *[Making triangles] Here is one way of doing it, but not the only way:*

Two boxed attached, drawn with triangles

**Answer to Question 4** *[Shortest Path]*

*The shortest way to get from $A$ to $K$, is to go $A B C H G J K$.*

**Answer to Question 5** *[Make your own graph] Here is one way to do it, but this isn't necessarily the only way to do it.*

Level map with graph

If you are creating random levels in a game, you can't decide on where the interesting points are, so you need to think of a way to instruct the computer to decide where the interesting points are. There are lots of ways of doing this, think about how you might go about doing this. Some things to consider are (a) can you get to every point on the map by walking in a straight line from some node? You need to make sure you can. (b) Do you have any silly situations, like the one below where you can get from A to B, but only by taking a very silly route.

**Answer to Question 6** *[Vectors]*

*(a)* $(1,2,3)+(3,2,1)=(4,4,4)$.

*(b)* $10\times (9,5,2)=(90,50,20)$.

*(c)* $|(4,2,4)|=\sqrt{4^2+2^2+4^2}=\sqrt{16+4+16}=\sqrt{36}=6$.

**Answer to Question 7** *[Throwing Rocks in Space]*

*Write Billy-Joe's position as $\mathbf{x}$ and Arthur's position as $\mathbf{y}$. If Billy-Joe throws the rock with velocity $\mathbf{v}$, then after $t$ seconds, the rock will be at $\mathbf{x}+\mathbf{v}\times t$. He wants it to hit Arthur, so he wants $\mathbf{x}+\mathbf{v} \times t = \mathbf{y}$. Rearranging this equation, we get $\mathbf{v}=\frac{\mathbf{y}-\mathbf{x}}{t}$. So, the
velocity should be the position of Arthur minus the position of Billy-Joe, divided by the time taken, 7 seconds. So $\mathbf{v}=\frac{(240,640,143)-(100,150,150)}{7}=\frac{(140,490,-7)}{7}=(20,70,-1)$.*

**Answer to Question 8** *[Throwing Rocks on Earth]*

*Because the x- and z-directions are 0 in all the vectors, we can ignore them and just look at the y-directions. At time $t=0$, the rock is at position 0, with velocity 4 (with vectors, the rock is at position $(0,0,0)$ with velocity $(0,4,0)$). Therefore, at time $t=0.2$, the rock will be at position $0+4 \times 0.2=0.8$. At time $t=0.2$, the velocity will now be $4+0.2 \times -9.81 =
2.038$. So, at time $t=0.4$, the rock will be at position $0.8+2.038 \times 0.2=1.2076$. At time $t=0.4$, the velocity will be $4+0.4 \times -9.81=0.076$. So at time $t=0.6$, the rock will be at $1.2076+0.076 \times 0.2 = 1.2228$. At $t=0.6$, the velocity will be $4+0.6 \times -9.81 = -1.886$, so at $t=0.8$ the position will be $1.228-1.886 \times 0.2 = 0.8508$. At $t=0.8$ the velocity will be
$4+0.8 \times -9.81 = -3.848$, so at $t=1.0$ the position will be $0.8508-3.848 \times 0.2 = 0.0812$. So, after 1 second, the position of the rock will be $(0,0.0812,0)$.*

For the last part of the question, you work out the velocity at time $t=1.0$ is $4-9.81 \times 1.0 = -5.81$, so the position at time $t=1.2$ is $0.0812-5.81\times 0.2=-1.0808$, so somewhere between $t=1.0$ and $t=1.2$, the rock hits Billy-Joe on the head.

For people interested in learning to program, you can download a free C++ compiler called DJGPP at:

There is also a special ``library'' for making games which you might find useful, called Allegro, at:

http://www.talula.demon.co.uk/allegro

Here are some links on programming games:

This is a brilliant page on path finding:

http://www-cs-students.stanford.edu/~amitp/gameprog.html

Here are some very comprehensive notes on 3D graphics (very hard!):

http://www.cc.gatech.edu/gvu/multimedia/nsfmmedia/cware/graphics/toc.html