The Use of Mathematics in Computer Games
Contents
1 Introduction
The purpose of this article is to have a look at how mathematics is used in computer games. The article will refer to some examples of popular computer games which you may have played. Generally we will be talking about 3D games. but the same ideas are used in 2D games occasionally as well. There are three aspects of games which we'll explore:
Geometry - the shapes that make up the world you move around, and all the characters within it.
Pathfinding - the basis for finding routes around the game world.
Physics - making the world behave in a way which is believable.
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.
2 Geometry
The virtual world you encounter in a computer game is basically made up of a space occupied by polygons with decorations on. 3D artists can spend days creating an object with tens of thousands of polygons. These polygons can be decorated in a number of ways to make them look better, but in this section we focus on the geometry and the process of rendering it (drawing the polygons). Computer graphics have improved vastly over the past 40 years, and the main reason for this is the improvement in processors which allows more polygons to be rendered.
A screenshot from Zelda: Breath of the Wild by Nintendo
Overwatch
To begin to explain how these games work, you need to know a bit about geometry, vectors and transformations.
2.1 Geometry, Vectors and Transformations
Geometry is the study of shapes of various sort. The simplest shape is the point. (It's quite difficult to explain what a point is, it is basically just a position, for instance, the very end of your nose is a point). Another simple shape is a straight line. A straight line is just the simplest shape joining two points together. A plane is a more complicated shape, it is a flat sheet, like a piece of paper or a wall. There are more complicated shapes, called solids, like a cube or a sphere. Here are some pictures of these things.
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)=(?,?,?)$.
A transformation moves a point (or an object, or even an entire world) from one place to another. For instance, I could move it to the right by 4 metres, this type of transformation is called a translation. Another type of transformation is rotation. If you take hold of an object (a pen for instance), and twist your wrist, you have rotated that object. Here are some pictures of rotations and translations.
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)$.
2.2 Rendering
Projection on to a plane
The game will have a camera somewhere in the world, which takes on the role of the painter in the paragraph above. The camera might be positioned as if it is looking out from a character's eyes, in which case the player will see as if through their eyes, or it might be positioned high up to give an overview of what's happening.
In order for a game to move at a smooth and enjoyable speed, the computer needs to go through this process for everything the player can see at least 50 times a second. When you consider that every polygon also has to respond to light sources appropriately, you start to realise how many calculations need to be performed. Modern GPUs (graphics processing units) can do around 15 Tera FLOPS per second... in other words 15 trillion floating point operations, or calculations, every second. How many can you do?
A typical box in a game would be made using triangles, something like this:
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.
3 Pathfinding
The computer often needs to move character or vehicles from one place to another. For example, you often have enemies that need to run toward the player when they become spotted. The enemies should take the quickest route, but obviously can't walk through trees or crates. In some PC or tablet games, the player doesn't control the player character directly, but indicates a spot that they would like the player character to move to. If this takes a long time by traversing an inefficient route, it will be noticeable and annoying to the player. But walking through walls or over water would spoil the sense of realism in the game.
What happens inside the computer? How does the computer know how to make the character get from their current position to the destination? Remember, computers can't think for themselves (yet!), they need to be told exactly what to do. So you can't just say, ''look at the map and work out the best route to wherever you are going'', the computer needs to decide on exact instructions at every stage of the journey. This process is called pathfinding and it relies on network theory.
3.1 Nodes, Edges and Graphs
To explain how the computer works out the best route, you need to know what nodes, edges and graphs are. You may have heard of graphs before in maths, but they mean something slightly different here. The simplest example of nodes and graphs is a map of some cities, and the roads between them (or an underground map). Each city is a node, usually drawn as a circular blob. Each road is an edge, and connects two nodes (cities), these are usually drawn as straight lines. The whole collection of nodes and edges (cities and roads) is called a graph. Sometimes there is a one way road, called a directed edge, and we draw an arrow on it to show which way you can travel along it. For instance, if there are two cities $A$ and $B$, and a line with an arrow from $A$ to $B$, then we can travel from $A$ to $B$, but not from $B$ to $A$. Here is an example of a graph, you can't travel from $B$ to $A$, but you can travel from $A$ to $B$. You can't travel from $C$ to $A$ or from $A$ to $C$, but you can travel from $B$ to $C$ and from $C$ to $B$.
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.
3.2 Finding a route
A map of a level in a game, the green areas are the ground, the grey areas are the buildings
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.
4 Physics
A virtual world in a computer game needs to convince us to believe it, by having things move around in a way similar to our own. Solid objects must collide with other solid objects, and sometimes rebound from them. Explosions should push things around, gasses should float through the air, things should float or sink in water. Games use simplified models of physics, although they are still complex! And in a similar way to cartoons, games will often exaggerate or distort the laws of physics to make events more dramatic.
4.1 More on Vectors
Physics used in computer games uses vectors. There a few more things you need to know about vectors. Firstly, instead of writing $(x,y,z)$ every time we talk about a vector, we'll just write $\mathbf{v}$ for a vector, this is the same as writing $(v_x,v_y,v_z)$. When I write $v_x$, that just means the distance you have to go in the x-direction to get to $\mathbf{v}$. We can add two vectors $\mathbf{v}+\mathbf{w}=(v_x+w_x,v_y+w_y,v_z+w_z)$. We can multiply a vector by a number, $a\mathbf{v}=(a v_x, a v_y, a v_z)$. For instance, $3 \times (1,2,3)=(3,6,9)$. The length of a vector is the length of the line from $(0,0,0)$ to the vector, the length is written $|\mathbf{v}|$, and you can work it out using the formula $|\mathbf{v}|=\sqrt{v_x^2+v_y^2+v_z^2}$. For example, $|(1,2,2)|=\sqrt{1^2+2^2+2^2}=\sqrt{9}=3$. The length of a vector multiplied by a (positive) number is the number times the length of the vector, so $|a\mathbf{v}|=a|\mathbf{v}|$.
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)?
4.2 Physics
Exercise 7 [Throwing a stone] Billy-Joe wants to throw a stone at a drink can at position (240,640,143). Billy-Joe is slightly obsessed with the number 7, so he wants the stone to take exactly 7 seconds to hit the drinks can, what velocity should he throw the stone 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 harder in these circumstances 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. 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 stone 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 stones on Earth] Billy-Joe is at position (0,0,0), he throws a stone with velocity (0,4,0), where will the stone be after 1 second? To answer this question, the acceleration on the stone 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 stone to hit the drinks can.
4.3 Projectiles
5 Conclusion
These are a few common examples of where maths is used in making computer games, there are many, many more examples. In fact, it is almost impossible to make any game without using maths, even Pacman uses some maths (although it is far simpler).
The number of calculations involved in a modern game are absolutely staggering, and developers often have to try to use clever ways to avoid performing totally overwhelming numbers of them. If a simplified approach can be taken without deterioration of the player's experience, it's often worth taking it.
6 Answers
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
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.
A very silly choice of graph
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 stones in space]
Write Billy-Joe's position as $\mathbf{x}$ and the position of the drinks can as $\mathbf{y}$. If Billy-Joe throws the stone with velocity $\mathbf{v}$, then after $t$ seconds, the stone will be at $\mathbf{x}+\mathbf{v}\times t$. He wants it to hit the drinks can, 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 the drinks can 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 stones 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 stone is at position 0, with velocity 4 (with vectors, the stone is at position $(0,0,0)$ with velocity $(0,4,0)$). Therefore, at time $t=0.2$, the stone 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 stone 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 stone 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 stone 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 stone will hit the drinks can.
7 Interesting Web Pages
For people interested in writing some code to explore these topics, it is worth looking into Python:
https://wiki.python.org/moin/GameProgramming
Here are some good general game programming sites: