When thinking about games and the creation process behind it, most of people think about the creative aspect of the process, but do you know much maths go into the process? In this article we will go over gaming with mathematics.
Table of contents Gaming with mathematics
The main objective of this article is to look at how mathematics are used in the process of making computer games. This guide and compilation of resources will try to give some examples of how mathematics are applied in different parts of the development process and how, they can make the difference between a great game or a mediocre one. We will try to give both examples applied to 2D and 3D games. We will look at three aspects of games:
- Geometry – the shapes that make up the world you move around in, and all the characters in it.
- Pathfinding- the basis for finding routes through the game world.
- Physics – the plausible behaviour of the world.
- Other Resources
In some of the points of the explanation, we will add some resources and references to other sources where you will be able to expand on the information.
The virtual world you encounter in a computer game is basically a space occupied by decorated polygons.
3D artists can spend days creating an object made up of 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 will focus on geometry and the rendering process (drawing the polygons).
Computer graphics has evolved a lot over the last 40 years, and the main reason for this is the development of processors, which allow more polygons to be rendered.
2.1 Evolution of videogames
You can also see how games look now a days with the below listed Screenshots from two AAA successful games.
To start explaining how these games work, we need to know a little bit about some aspects of how some assets in games are made and processed geometry and transformations, Vectors, and other elements.
2.1 Geometry and transformations
Geometry is the study of different kinds of shapes. The simplest shape is a point. (It is quite difficult to explain what a point is, it is basically just a position, for example the very tip of your nose can be considered a point). Another simple shape is a straight line.
A straight line is just the simplest shape that connects two points. A plane is a more complex shape, it is a flat sheet of paper, such as a sheet of paper or a wall. Some more complex shapes are called solids, such as a cube or a sphere. Here are some pictures of these things.
If you have a line and a plane, you can find the point where the line intersects the plane. In fact, sometimes you can’t find the intersection point because they don’t meet, and sometimes the line is inside the plane so they meet at every point on the line, but that 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.
In this 2013 GDC talk, Intel’s Stan Melax shares some useful tools for programmers to help render avatars that can interact with 3D Geometry in games.
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 reach a point. For example, extend one arm to the right and the other arm straight ahead. Now I can give you a vector and you can find the point I’m talking about. For example, if I say x=3, y=1, z=5, you can find the point by walking 3 metres towards your right arm, then 1 metre towards your left arm, then take a ladder and climb 5 metres. Here is a picture of a vector.
Vectors are written in the form of (x,y) for 2D vectors, and (x,y,z) for 3D vectors , for example (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 denote a point and sometimes a direction. A vector (1,0,0) can mean “the point you will reach if you move 1 unit in x direction from the starting point” or “move 1 unit in x direction from where you are”.
Video support- Vectors In games
4. Rendering or Math for 3d
The basic idea of rendering is to transform a mathematical description of the world into a picture of the world as it appears to someone inside the world. The mathematical description can be in the form of a list, for example: there is a box with a centre (2,4,7) and sides 3 long, the colour of the box is bluish-grey. To translate this into a picture, we also need to describe where the person is and in which direction they are looking, for example: 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 for that person.
Imagine that there is a painter whose eye is at point P. Imagine that he has a sheet of glass on which he is about to paint. In the room where he is painting, there is a wooden box. One corner of the crate is at point A, and the painter wants to know where one corner of the crate should be on the glass plate. He calculates this by drawing a line L from his eye (P) to the corner of the crate (A) and then calculating where this line crosses the canvas, B. He can do this because the glass sheet is a plane, and I mentioned above that the intersection of a line and a plane can be found.
This point B is where the corner of the box should be on your painting. You follow this rule for each piece of the crate, and you end up with a painting that looks exactly like the crate. Here are two pictures, the first showing what the painting looks like when he has painted only one corner of the crate, and the second showing what it looks like when he has painted the whole crate.
In the game, there will be a camera somewhere in the world, which takes the role of the painter in the paragraph above. The camera can be positioned as if it were looking out of a character’s eye, in which case the player sees as if through his eyes, or it can be positioned high up to give an overview of what is happening.
For the game to run smoothly and at an enjoyable speed, the computer needs to go through this process at least 50 times per second for everything the player can see.
When you consider that each polygon also has to respond appropriately to the light sources, you begin to realise how much computation is involved. Modern GPUs (graphics processing units) are capable of about 30 TeraFLOPS per second… in other words, more than 15 trillion floating point operations, or calculations, per second.
A typical box in a game is made using triangles, something like this:
Here is a much more complex example, using thousands of triangles. The first picture shows the triangles used, and the second picture shows what it looks like with the colours added:
The reason for using triangles is that they are very simple shapes, and if you make sure that everything is made from just one type of shape, you don’t need to write a separate program for each type of shape in the game.
Each time the computer draws a picture of the world, it goes through the following steps:
- first, it transforms the world (by rotating and flipping) so that the person is in position (0,0,0,0) and the glass plate (the center of the screen for computers) is in position (1,0,0). This makes further calculations much easier.
- Second, it removes all the triangles that you can’t see so that you can forget about them, such as triangles that are behind you or triangles that are so far away that you can’t see them.
- Third, for each remaining triangle, it calculates what it would look like if it were painted on a sheet of glass (or drawn on a computer screen).
- Finally, it places the image it has drawn on the screen. Nowadays, computers are so fast that they can draw millions of triangles per second, so the images are becoming more realistic, as you can see from the screenshots that we have posted at the beginning of this guide.
Of course, this isn’t the only things going around, there are much more: things that are being processed in real time like: lighting, fog, animation, textures and hundreds of other elements that are required to make a full blown modern game.
Going all the way from the bits of vertex coordinates to the rasterizing of pixels, let’s learn how rendering graphics works!
5 Finding your way around with Path-Finding
When you are trying to life your game, one of the most tasks, depending on your game style, is to either make your enemies move naturally around the level, or in case you have some game based on point & click movement, to have the character selecting the best path to reach its final objective.
For this to happen, the computer needs to move a character ( hero, enemy or NPC) or a vehicle from one place to another. For example, there are often enemies that need to run towards the player when they are spotted. Enemies have to take the fastest route, but obviously they can’t go through trees or crates. In some PC or tabletop games, the player does not directly control the player character, but indicates the location to which the player character wants to move. If this takes a long time to navigate an inefficient route, it will be noticeable and annoying to the player. But crossing walls or water would spoil the sense of realism of the game.
What happens inside the computer? How does the computer know how to get the character from their current position to their 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 where you’re going’, the computer has to give you precise instructions at every stage of the journey. This process is called pathfinding and relies on network theory.
5.1 Nodes, edges and graphs
To explain how a computer finds the best route, we need to know what nodes, edges and graphs are. You may have heard of graphs in maths, but here they mean something slightly different. 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), usually drawn as straight lines. A complete collection of nodes and edges (cities and roads) is called a graph. Sometimes there is a one-way road, called a directed edge, and an arrow is drawn on it to show which direction it can be travelled. For example, if you have two cities, A and B, and a line with an arrow leading from A to B, you can travel from A to B, but not from B to A. Here is an example of a graph, you cannot travel from B to A, but you can travel from A to B. You cannot travel from C to A or A to C, but you can travel from B to C and from C to B.
To complicate things further, sometimes we like to add a so-called cost to each edge. The point of a cost is to show how much it would cost to travel on that edge. A simple example of this is shown below.
5.2 Find a route
Now you know everything you need to know to understand route finding. If you have done the last exercise, you will have solved an example of the kind of problem that computers have to solve to guide operators on complex maps.
How does all this stuff about graphs help the computer guide teams through the levels?
It creates a graph where every point of interest is a node in the graph, and every path from one node to another is an edge, and then solves the problem solved above to guide the teams. There are some complications. First, what are the points of interest? You might think that every single position on the entire map would be interesting, but for most games this would result in hundreds of thousands of points of interest, and finding the route would take years. Instead, the people who make the game decide where the points of interest are.
For example, if you have a wide open area (perhaps a large field), you don’t need a node at every point on the field because teams can walk in a straight line across the field. Basically, you only need nodes around obstacles. Here is an example of a level map viewed from above.
A map of a level in the game, the green areas are the ground, the grey areas are the buildings.
Once you have selected the points of interest, you need to connect them with edges, you can only connect nodes that have no obstacles between them.
Exercise 5 [Make your own graph] Place nodes at points of interest on the example map above, then connect the nodes with edges, but remember that you can only connect nodes with straight lines, and straight lines cannot cross obstacles.
Once you have created the graph for a given map, the computer has to go through the following steps to guide the teams.
- First, it has to work out the nearest junction it can go to in a straight line. This node will be your starting node.
- Secondly, you need to work out which is the closest node to your destination (making sure, of course, that you can walk in a straight line from this node to your destination!) This node is the destination node.
- Third, it has to calculate the shortest path connecting the starting node to the destination node. All teams now 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, and then from the destination node to the final destination.
To make things even more interesting, you can add costs to all edges.
For example, if there is a shark pit in the space connecting the two nodes, the cost of crossing the shark pit is very high, so it might be a better idea to take the long way, even if the shark pit crossing is shorter.
Of course, if the long trip would take the troops 3 days and the shark pit crossing would only take 10 minutes, they might decide it would be better to take the risk and get there before the battle migrates elsewhere.
The costs associated with each path should be carefully chosen as to ensure that problems of this nature are resolved in the best possible way. Here is an example of a map with costs on the edges.
We haven’t actually talked about how to get the computer to find the best route from one node to another. Let’s get in some detail.
The total cost of getting from P1 to Pm via P2, P3, …, …, Pm-2, Pm-1 is found by adding up the costs of getting from P1 to P2, P2 to P3, …, Pm-1 to Pm. The problem is to find the right choice of nodes to make this total cost as small as possible. One way to do this would be to find all possible paths to get from one node to another, calculate the total cost of each, and choose the smallest one.
Unfortunately, this would take too long even for the fastest computers. There is a way to calculate this route very quickly, but it would be a bit complicated to explain here. However, if you want to, you can look it up on the internet (search for the A* algorithm – A* is pronounced A star) or check the links at the end of this article.
This is probably one of the best tutorials on youtube about path-finding and more specifically the A* algorithm by Sebastian Lague, that explains in a very detailed how the algorithm works with all the maths behind it.
The virtual world of a computer game should convince us to believe that things move in a way similar to our own. Solid objects must collide with other solid objects and sometimes bounce off them. Explosions must push things, gases must float in the air, things must swim or sink in water.
The games use simplified models of physics, but they are still complex! And like cartoons, games often exaggerate or distort the laws of physics to make events more dramatic and fun to play that is what they are made for.
6.1 More about vectors
The physics used in computer games uses vectors. There are a few more things you should know about vectors. First, instead of writing (x,y,z) every time you talk about a vector, you simply write v for the vector, which is the same as writing (vx,vy,vz). When we write vx, it just means the distance we have to travel in the x direction to get to v.
You can add two vectors v+w=(vx+wx,vy+wy,vz+wz). You can multiply a vector by a number, av=(avx,avy,avz).
For example 3×(1,2,3)=(3,6,9). The length of a vector is the length of the line from (0,0,0) to the vector, we write its length |v| and calculate it using the formula |v|=v2x+v2y+v2z———-√. For example, |(1,2,2)|=12+22+22———-√=9√=3.
The length of a vector multiplied by a (positive) number is the product of the length of the vector and the number, so |av|=a|v|.
Every object has a position, which is a vector x. It also has a velocity, which is the direction in which it is moving, also a vector, sometimes called an x˙ vector. Each object also has what is called an acceleration, which is how fast the velocity changes, and this is also an a vector, sometimes written as x˙. Finally, each object has what is called a mass, this basically means how heavy the object is, and is usually written as m, but it is not a vector.
If an object starts from position x and has a velocity v, which does not change, then after t seconds the position of the object will be xt=x+v×t. If you’re wondering what xt means, it just means the position at time t. Similarly, vt means the velocity at time t. If an object starts with a velocity v and its acceleration is a, which does not change, then after t seconds the velocity of the object will be vt=v+a×t.
This is actually a tricky answer in this case. Because in games you can create projectiles in two different ways:
- Physic Projectiles, in this case, there is actually a physic based object that is moving across the level emulating a real physic projectile, with a mass, a speed,, and the capacity to collide with other objects in the level. this has limitations for fast paced games where the projectile can miss a collision in between frames
- Physic raycasts, there isn’t any object with physics properties, only a mathematical check on all the objects along a line to see if they intersect and that could be considered as a hit. They have the advantage they work at any pace and independent of the frame rate.
Here is a very simple example that is constantly used in video games and which is the easiest and most commonly used solution.
Every time you shoot a bow and arrow or a fireball, the computer has to calculate your position using calculations similar to the ones that we have seen above.
The computer has to do these calculations 60 times per second for each moving projectile (amongst other physics enabled objects in the game), and then do even harder calculations to determine whether the projectiles hit anything.
We can make the simulation of the projectile as real as we want, but the more realistic it will be the more resources it will require from the computer, both in terms of CPU and Memory, as more variables will have to be used as to adjust the nature of the simulation to what would be expected in the real world. But we don´t have to forgot that games are not supposed to be ( in most cases) simulators of the reality, but rather a very fun simplification that emulates its behavior to certain limits, but that afterwards focuses more on the fun factor than in getting the physics correctly implemented.
So, the case we would implementing a project with physics in our game, we could basically avoid thinking about the wind and the friction of the air, and only consider a constant speed by adjusting the position of the object by a constant displacement in meters in each frame. We can already see part of the problem, the projectile will actually be somewhat teletransporting itself at very short distances, but that could move it without colliding any objects. Another problem with this solution, is that if you are shooting a lot of projectiles, you will be creating a huge overhead of calculations and could have a negative impact on the capacity for the computer to perform all the calculations required, which would in the end reduce the frame rate of the game.
This when using the second method with the raycasts could bring some advantages, as you don’t have actually physical objects moving in the game world, but just some intersection checks along a predefined direction, which will make it more efficient and less resource consumption. The problem of course is that you will not actually have bullets flying around, but just rather estimating their possible trajectory. But for projectiles that are very fast to move and very difficult to actually see, the simplification is actually ok.
Physics is one of the hardest parts of making computer games. Not many people have the expertise to do these calculations accurately enough, yet simplified enough, to run at an acceptable speed or frame rate. If the simulation is unreliable, even for a short period of time, it can result in objects passing through walls and disappearing. Game developers often rely on other people’s game engines, such as Unity or Unreal, rather than trying to implement a new physics system from scratch, which can be a very complex task.
GDC conference Math for Game Programmers: Predictable Projectiles
Linear Algebra concepts come into play whenever a character is moved on a screen. Matrices manipulate vectors, effectively transforming the coordinate system of the vector. In 3D Graphics, movement occurs when a character’s coordinate system is converted to another coordinate system.
A vector is an entity that possesses both magnitude and information about its direction. It represents the displacement between two objects. On the other hand, a matrix is an entity that holds the necessary information to convert one coordinate system to another.
Transformation involves converting the coordinate system of an object into a different coordinate system. A Transformation Matrix is employed to carry out this conversion. By multiplying a vector with a transformation matrix, the vector’s coordinate system undergoes the necessary transformation.
7.1 Linear Algebra Concepts
Every vertex of a character can be defined as a vector consisting of n components. These components correspond to displacements along the x, y, or z-axis. For instance, if a vertex is represented as a vector (2, 3, 1), it signifies a displacement of two units along the x-axis, three units along the y-axis, and one unit along the z-axis.
Position is not a factor in vectors. Two vectors positioned at different locations within a coordinate system are considered identical if they possess the same magnitude and direction.
In computer graphics, a matrix is highly valuable for its capacity to convert geometric data into various coordinate systems. It consists of elements organized in rows and columns. The dimensions of a matrix are determined by its rows and columns.
For example, a matrix with 2 rows and 3 columns is referred to as a 2×3 matrix. Dimensionality plays a crucial role in matrix arithmetic, as certain operations can only be performed when matrices have identical dimensions.
Vector rotation is a fundamental concept in linear algebra and is commonly used in various fields, including computer graphics, physics, and engineering. It involves transforming a vector’s orientation or direction in a coordinate system.
In the context of two-dimensional space, a vector can be represented as an arrow with a specific magnitude (length) and direction. When we talk about rotating a vector, we mean changing its direction while keeping its magnitude unchanged.
To rotate a vector, we typically use a rotation matrix. A rotation matrix is a 2×2 matrix that contains the necessary information to perform the rotation. The elements of the rotation matrix depend on the angle of rotation.
Let’s consider a vector represented by coordinates (x, y) in a two-dimensional plane. To rotate this vector counterclockwise by an angle θ, we can use the following rotation matrix:
[ cos(θ) -sin(θ) ] [ sin(θ) cos(θ) ]
To apply the rotation matrix, we multiply it by the vector [x, y]:
[ cos(θ) -sin(θ) ] [ x ] [ sin(θ) cos(θ) ] * [ y ]
The result is a new vector with updated coordinates (x’, y’), which represent the rotated vector.
In three-dimensional space, vector rotation becomes slightly more complex as we need to consider additional dimensions. We can still use rotation matrices, but they become 3×3 matrices. Each element in the matrix corresponds to the appropriate rotation axis (x, y, or z) and angle of rotation.
Vector rotation is a powerful tool that enables us to manipulate and transform objects in different coordinate systems. It finds applications in computer graphics, where it is used to animate objects, simulate 3D rotations, and create realistic visual effects. Additionally, it plays a crucial role in physics, robotics, and many other areas that deal with spatial transformations and orientations.
These are just a few common examples of where mathematics is used to make computer games, there are many, many more. In fact it is almost impossible to make any game without using mathematics, even Pacman uses mathematics (although it is much simpler).
The number of calculations involved in a modern game is absolutely staggering, and developers often have to try clever ways to avoid doing entirely too many calculations. If it is possible to take a simplified approach without degrading the player experience, it is often worthwhile to do so.
We hope that you have liked this content, if you want more, read our blog
We are also listing some added youtube videos that can help you moving forward understanding how maths can be applied to games
9. Other Resources
This video outlines what are some of the core principles you need to understand to make dynamic computer games, covering vectors, angles and motion. The video tries present it in such a way that highlights the relationships between these principles, so you can identify when to use one or the other, or combinations of them. It is by no means an exhaustive list, but gives the beginner/aspiring games programmer a place to start.
This is from the improvised tutorial stream on core math concepts in game dev! Timestamps at the bottom of the description.
00:00 – Intro
22:01 – Scaling & Ratios
46:04 – Vectors & Dot Product
1:54:45 – Trigonometry
2:30:05 – Degrees & Radians
2:52:32 – Cross Product
3:07:03 – Local vs World Space & Transformation
3:20:27 – Lerp
3:33:45 – Derivatives
3:46:35 – Frame rate Independence