Game Programming Techniques

Game Programming Questions

Answers

How do I create a HUD?

A HUD or any UI components are normally 2D graphics and text displayed on top of the game view. A number of libraries help you to display 2D graphics, for OpenGL there is GLUI and GLUT and for DirectX there is the sprite and font interfaces. To do it yourself the standard way is to create a square made of two triangles defined in screen space (already transformed) and then to texture the square with the 2D graphic you wish to display. Text is normally achieved by creating a texture with all the characters in the font on it and then display a quad on screen for each character and use the texture co-ordinates to reference the correct letter in the font texture. Look at the way it is done in the DirectX SDK samples for an example of this.

Related notes: 2D Elements (Textures, Sprites, Text).

How can I move objects in a certain direction?

Use vectors. Normalised  vectors are great tools. They have a length of 1 so multiplying them by another vector leaves the other vectors size unchanged but alters the direction. If you  want to move an object to a particular place you calculate the vector between  the two positions, normalise it and add it to the current position.

e.g. If you want to move from position A to position B and both are described  with vectors: 

D3DXVECTOR3 direction=A - B;
D3DXVec3Normalize(&direction,&direction);

// to move the object from A you would then do something like:
D3DXVECTOR3 newPosition=A + (direction * movementAmount);

Since direction is normalised and has a length of 1 you multiply it by the amount you want the object to move during this calculation , in this case movementAmount.

How can I implement a 3rd person camera?

If you want the camera to  follow your character around the world you need to take into account the direction and position of the character to be followed.

You will probably want the camera to be a set distance away from the object  and facing the same direction as the object. So the first thing to do is obtain  the position and direction of the object. Once you have these you can position  the camera a set distance from the object by multiplying the inverse of the object direction vector by the set distance away you want the camera to be:

3rd person cameraApologies for the rather crude drawing - I am a programmer not an artist :)

In code this may look something like:

// objPos - is the position of the object in the world
// objDir - is the normalised direction vector of the object in the world
// cameraPos and cameraDir are the position and direction of the camera that we want to find

// Position the camera 5 world units (dx) away from the object:

D3DXVECTOR3 inverseObjDir = -objDir;

cameraPos= objPos + (5.0f * inverseObjDir);

// Camera direction is just set to the same as the object:

cameraDir=objDir;
 

The above will position the camera at the same height as the object, you  may want the camera to always be above the object looking down. In this case you  need to raise the camera position up and then calculate a new 'downward facing'  camera direction.

To do this you get the vector between the camera position and the object  position. This then gives you the correct direction vector.

3rd person camera Following on from the previous code you would add code something like this:

 // We want the camera to be 4 world units above the object it is looking at
 cameraPos.y+=4.0f;
 
 // We have to change the camera direction to look down toward the object
 D3DXVECTOR3 newDir=objDir-cameraPos;
 
 D3DXVec3Normalize(&newDir,&newDir);
 
 // now the newDir is the correct camera direction
 

Relates notes: Camera

How can I find out if a point is within a polygon?

Often you need to find out if a point is within a polygon. E.g. when doing collision you may have detected that a ray collides with the plane of a triangle and now you need to determine if the collision point is within the triangle. This is obviously in 2D. The  method I have used is from Gems IV. Note: there are a few other methods out there so do a Google if interested - you will find plenty. The description above the code is not mine:

/*
    The definitive reference is "Point in Polygon Strategies" by
    Eric Haines [Gems IV]  pp. 24-46.
    The essence of the ray-crossing method is as follows.
    Think of standing inside a field with a fence representing the polygon.
    Then walk north. If you have to jump the fence you know you are now
    outside the poly. If you have to cross again you know you are now
    inside again; i.e., if you were inside the field to start with, the total
    number of fence jumps you would make will be odd, whereas if you were
    outside the jumps will be even.
    The code below is from Wm. Randolph Franklin <wrf@ecse.rpi.edu>
    with some minor modifications for speed.  It returns 1 for strictly
    interior points, 0 for strictly exterior, and 0 or 1 for points on
    the boundary.  The boundary behaviour is complex but determined;
    in particular, for a partition of a region into polygons, each point
    is "in" exactly one polygon. 
   
    The code may be further accelerated, at some loss in clarity, by
    avoiding the central computation when the inequality can be deduced,
    and by replacing the division by a multiplication for those processors
    with slow divides.

    numPoints = number of points
    poly = array of vectors representing each point
    x,y = point to test
*/

bool pnpoly(int numPoints, Vector *poly, float x, float z)   
{
        int i, j, c = 0;     

       for (i = 0, j = numPoints-1; i < numPoints; j = i++)
       {
              if ((((poly[i].z<=z) && (z<poly[j].z)) || ((poly[j].z<=z) && (z<poly[i].z))) &&
                   (x < (poly[j].x - poly[i].x) * (z - poly[i].z) / (poly[j].z - poly[i].z) + poly[i].x))
              c = !c;     
       }     

       return (c==1);   
}

Vector can be your own vector structure / class or D3DXVECTOR3 if you are using DirectX.

How do I get an accurate timer for my PC game?

There are some issues with different processors relating to timing. Normally timeGetTime works fine on most computers however there are issues on some machines so often QueryPerformanceCounter is used instead. This is a high resolution counter but is not supported on older machines. So the best method is to check if this counter exists, if it does, use it otherwise use timeGetTime. I have a class I use to wrap all this and I have made it available, for reference, via this download: timeUtils.zip. You are advised to create your own so you understand what is going on.

Physics

Take a look at this link on Gamasutra which has a number of good articles: Game Physics

Related notes: collisions

How do I find the distance between two points / vectors?

Firstly be sure you know what you mean when talking about distance between vectors. Vectors have a direction and a length however vectors are also often used to represent a position only (point vectors). So finding the distance between two vectors normally refers to finding the distance between two points. You can subtract one vector from another and get a new vector but to get the distance between the points you need to determine the length of the new vector.

To find the distance between two points you use the Pythagorus theorem: 'the square on the hypotenuse is equal to the sum of the squares of the other two sides'. So if you have two points P0 and P1 the distance between them is:

float dx=p1.x - p0.x
float dy=p1.y - p0.y

float distance=sqrt(dx*dx + dy*dy);

Tip: often you just want to compare distances so rather than use the slow sqrt (square root) function you can safely compare the squared distances. It is wise to avoid sqrt where possible in game code.

How can I optimise my code?

This used to be a much easier question to answer. In the past I would have said unroll loops (to avoid the loop code overhead), create look up tables for sin, cos, tan etc. (these functions can be slow) plus many other nice tricks. However nowadays with the complexity of modern processors these methods are no longer always correct. PC processors like the Pentium are now better at handling loops and maths functions are very fast compared to what they were. You also have the issue of the graphics card working in parallel to the CPU, you want to try to maximise that parallel effect so neither processor is waiting for the other. On consoles the situation is the same and in some cases worse. The PS2 has two vector units that need to be kept busy in order to maintain high speed.

So nowadays you need really to look at your algorithm for increased speed rather than low level coding tricks. Most importantly you should profile the code to see where the slow points are. Often programmers are wrong about the place they think is slowing the code down and only when you run a profiler can you determine exactly where slow downs occur. You don't even need to buy a profiler you can use your own code to measure the time sections of code take. Of course the best way to optimise slow code is to not call it at all! If you can remove code by redesigning an algorithm this is the biggest gain.

I wrote a program not long ago which was spending ages creating shadows on a terrain. I profiled it so I knew exactly where the problem was and I worked at it for many days reducing the speed by 0.5 % at a time until after a week or two I had reduced it by about 5%. A few weeks later I suddenly realised I could change the algorithm used and use a completely different one which would be quicker, it took a few hours to change but did the same job as before but ran 500% faster! All that time I spent optimising for a few meagre percent would have been better spent redesigning the algorithm.

So my general suggestions for optimising slow code is:

  • Determine where the slow down is - it is often not where you expect. Use a profiler for this - there is one built into Viz but for .net you need to download one.
  • First look to see if you can change the algorithm or the way you do something to get a speed increase
  • If you are sure there is no algorithmic change possible only then start looking at the code line by line

If you get to the final step and really have to look at the code there are a few things to bear in mind:

  • Your basic type should be the bit size of an integer on the platform you use (on a PC it is 32 bits). So use signed ints or unsigned ints everywhere you can. Bool or BYTE or char are all 1 byte in size and inefficient. Float is 4 bytes but suffers from computation slow down and casting slow down (casting a float to an int is very expensive on a PC), double is slower than float.
  • The above applies to structures and classes as well. Try to align them to 4 byte (or failing that 2 byte) boundaries. This can often be achieved by rearranging the member variables so they add up to 4
  • Try to avoid too much memory allocation during game play. Often it is not completely avoidable but normally you can create all your class instances and other memory at level load time and not during game play.
  • Don't pass structures or objects to functions by value. This is a big no-no for a couple of reasons. Firstly you are passing all the data in the structure which gets shoved on the memory stack. Secondly a copy is made of this data in the function. If it is a class the constructor for the class also gets called which may cause memory allocation as well. Once the function ends all this memory is freed. This is really painful so instead pass a pointer to the data (if the function needs to change it) or a const reference if the function is just reading it.
  • For small member functions make them inline and define them in the header. It is tempting to make everything inline but this is not always a good optimisation on modern processors so limit yourself to inlining only small functions.
  • Pythagorus is used a lot to compute distances between things and it involves 2 or 3 squares and a square root operation. Square root is faster nowadays than in the past but is still relatively slow. Often you only need to compare distances so just avoid the square root and simply use the squared value in comparisons.
  • I said before that casting a float is very expensive, any sort of casting is expensive so try to avoid casting as much as possible. Use the painful to write static_cast C++ cast method, it helps to remind you where casts are occurring.:)
  • Cache results. If you have a piece of code that calculates something given some input and it takes a long time remember the previous input and result. If your code then gets called with the same input next time you already have the answer and have to do no work at all. It is surprising how often calculation code does get called with the same input. You can even cache a few inputs and outputs but don't let the overhead of searching the cache slow everything down to the point where it is no use any more.

There are more things you can do but basically the key is to make sure you know where the slow down is and then see if you can change the whole algorithm rather than resort to code level tricks.

How do I calculate the area of a 3D triangle?

The area of a 3D triangle defined by the vertex V0, V1, V2 is half the magnitude of the cross product of the two edge vectors:

0.5 * | V0V1 * V0V2 |

Why would you want to know this? Well it is useful if you want to calculate your Gouraud normals so large connecting triangles have more effect on the normal than the smaller ones. The standard way to calculate a Gouraud normal is to add up all the plane normals of the connecting triangles and divide by how many there were. This works fine in most cases but does not differentiate between large and small triangles - each is equally weighted. You often get a better effect by modifying the influence of each triangle to the normal based on its size.

How do I convert between degrees and radians?

Easy. 2PI radians = 360 degrees, or PI radians = 180 degrees. So 1 radian is 0.017453
The best thing is to set up a macro to do the conversions e.g.

#define PI (3.141592654f)
#define DEGTORAD(degree) ((PI / 180.0f) * (degree))
#define RADTODEG(radian) ((180.0f /PI) * (radian))


© 2004-2016 Keith Ditchburn