Go to main page
A journey into the programming realm
The point of no return
Leaping into the unknown
Video games development is extremely difficult, with strict deadlines and a huge amount of competition, so personally I would recommend it only for people who have a passion for it.
The following things are required if you’d like a career in gaming:
A sprite is a 2D graphic object (image) that contains multiple textures.
For example, the armor of a monster can be kept in one sprite (one image), which contains the arms, legs, and body of the character as separate elements.
If you ever played a game in which the enemies were moving from one point to another, while avoiding the walls and/or other obstacles, that was performed by using a pathfinding algorithm. Another example where this could be used is in tower defense games.
To implement such algorithm, you need to first simplify the search area.
The search area should be split into tiles (pieces of a specific size) - think of chess for example - we don’t have a huge space to move randomly, we have 8x8 tiles (1 tile = 10x10 pixels each, for example).
Therefore, we don’t care about a specific location in terms of pixels, but in terms of tiles.
What we also want is to keep two lists – a list for open positions and another one for closed positions.
The open list is for the squares that can be considered to find the shortest path, whereas the closed list is for the squares we don’t have to consider again.
The first step is to add the current position (let’s call it A) to the closed list, and all the adjacent tiles that are available / walkable to the open list.
In order to determine which options would be optimal in finding our path, we need to give a score to each square.
The squares receive a score S summed by two numbers: C1 and C2.
C1 is the movement cost (the number of squares) from the starting point (A) to the current square. Therefore the closest squares will be of value 1, and it will increase by 1 each time we get away from the starting point. We calculate C1 by adding 1 to the C1 cost of its parent (the square we came from).
C2 is the movement cost (estimated) from the current square to the destination point (Let’s call this B). We can use the Manhattan distance method, for example, which counts the number of horizontal and vertical squares remaining to reach the destination point, without taking obstacles into account.
The algorithm works as follows:
Let’s give an example.
First step is to calculate the score S for all adjacent points from the starting point.
We continue to do the same things until we reach the destination.
We see that there are two different shortest paths. Both of them are fine.
Next time we go to the adjacent squares, we will reach the destination point, so we can add it into the closed list and stop. We get the shortest path by reconstructing the steps we took, by going backwards from parent to parent until we reach the starting point.
A collision occurs when the shapes of two objects are intersecting, or in programming terms, when the distance between these two is below a threshold.
In order to optimize the collision detection process, we can split it in two phases, the broad phase and the narrow phase.
The broad phase will find pairs of objects that COULD collide with each other, and exclude all the others that we know for sure that are not colliding, based on the items visible on the screen.
This is the broad phase because the objects could have some complex shapes, and we optimize this step by providing them some bigger bounding boxes (which are easier to calculate the intersection of) such as squares.
eg. For an object of shape as follows:
xx xx
x xxxxxxx
xxx
xxxx
We will make the bounding box to be the minimum and maximum values for each axis.
Because our character is 4 rows long and of different cols in size, with the maximum of 4, the initial bounding box will be 4x4.
xxxx xxxxxxx
xxxx xxxxxxx
xxxx
xxxx
Now it’s easy to calculate if these two objects intersect each other.
Popular types could also be circles (2D) or spheres (3D). The simplest bounding boxes are axis-aligned bounding boxes (AABB).
A 2-D AABB box can be written as such:
struct {
float x;
float y;
} Vector2D;
struct {
Vector2D min;
Vector2D max;
} AABB;
The min field will be the location of the lower left corner of the box, and the max field will be the top right corner of it.
To test the intersection of two AABB objects, we need to check if they intersect on all coordinate axes:
bool collide(AABB* a, AABB* b) {
float distX_1 = b->min.x - a->max.x;
float distY_1 = b->min.y - a->max.y;
float distX_2 = a->min.x - b->max.x;
float distY_2 = a->min.y - b->max.y;
if (distX_1 > 0.0f || distY_1 > 0.0f) return false;
if (distX_2 > 0.0f || distY_2 > 0.0f) return false;
return true;
}
Once we find out which objects potentially collides, we add the pairs into another structure and start the narrow (refinement) phase.
Now, our requirement is to find out if these objects collides, based on their real bounding boxes - which is more complex and more computationally expensive.
The command pattern is a replacement for callbacks.
Each game probably has a piece of code that reads user input (mouse clicks, keyboard events etc.) and translates them into game actions.
void Input::handle() {
if (isPressed(BUTTON_W)) MovePlayer(Moves::Forward);
if (isPressed(BUTTON_S)) MovePlayer(Moves::Backwards);
if (isPressed(BUTTON_A)) MovePlayer(Moves::Left);
if (isPressed(BUTTON_D)) MovePlayer(Moves::Right);
}
The alternative is to create an interface that handles any command.
class ICommand {
public:
virtual ~ICommand() {}
virtual void execute() = 0;
};
And implement classes for each specific command.
class JumpCommand : public ICommand {
public:
JumpCommand(IPlayer* _player) : player(_player) {}
virtual void execute() {
player->jump();
}
IPlayer *player;
};
class MoveCommand : public ICommand {
public:
MoveCommand(IPlayer* _player, Moves _where) : player(_player), where(_where) {}
virtual void execute() {
player->move(where);
}
IPlayer *player;
Moves where;
};
Then, the input delegates the action to the command. We can always rebind the buttons with whatever we’d like.
class Input {
public:
void handle();
private:
ICommand* BUTTON_W;
ICommand* BUTTON_S;
ICommand* BUTTON_A;
ICommand* BUTTON_D;
};
void Input::handle() {
if (isPressed(BUTTON_W)) BUTTON_W->execute();
if (isPressed(BUTTON_S)) BUTTON_S->execute();
if (isPressed(BUTTON_A)) BUTTON_A->execute();
if (isPressed(BUTTON_D)) BUTTON_D->execute();
}
Assuming we have different classes for different enemies in a game:
class Enemy {};
class BadGuy : public Enemy {};
class ToughGuy : public Enemy {};
The idea of this pattern is to be able to spawn other instances similar to itself.
Any objects of a type can be used as a prototype to generate other objects of that type.
class Enemy {
public:
virtual Enemy* clone() = 0;
};
class BadGuy : public Enemy {
public:
BadGuy(int _health, int _speed) :health(_health), speed(_speed) {}
virtual Enemy* clone() {
return new BadGuy(health, speed);
}
int health;
int speed;
};
Now, we can create a new class that can clone any other enemies.
class Spawner {
public:
Spawner(Enemy* type) : type(_type) {}
Enemy* clone() {
return type->clone();
}
private:
Enemy* type;
};
We can use the Spawner class to clone any other object of type Enemy.
Enemy* someBadGuy = new BadGuy(100,20);
Spawner* badGuySpawner = new Spawner(someBadGuy);
Enemy* anotherBadGuy = badGuySpawner->clone();
If we have one instance and we want to create thousands of identical objects, we can use this clone method, sure.
But each object will contain a bunch of data associated, such as polygons that define the shape of it, textures, location, orientation, or other parameters such as size, etc. so they all look look different.
Therefore, the class would look like this:
class SomeObject {
private:
Mesh polygons;
Texture head;
Texture legs;
Texture body;
Vector position;
double size;
Color materialColor;
//...
};
The most important thing to know is that these things look similar, and all objects will use the same mesh and textures - most of the data will be the same between instances.
Therefore, we should split this in two classes - the ones that are common can be moved separately.
class SomeObjectModel {
Mesh polygons;
Texture head;
Texture legs;
Texture body;
};
Now we’re left with what is specific for each instance:
class SomeObject {
private:
SomeObjectModel* model;
Vector position;
double size;
Color materialColor;
//...
};
This is helpful because we reduce the data we have to push to the GPU.
This is already supported in video engines such as Direct3D or OpenGL, and it is called ‘instanced rendering’.
The engine receives two streams of data, the common data, that will be rendered multiple times, and the list of instances.
Double buffering is a technique for drawing the bytes on screen, solving problems of stutter, tearing, and other artifacts.
This happens when we have two surfaces, the primary and the secondary buffer.
All the drawing is performed in some region in RAM (on the second buffer) and when everything is complete, the whole region is copied into the video RAM (The primary buffer).
Similar to double buffering, we have two surfaces.
The implementation is the same, but when the drawing is done, we interchange the two pointers (primary and secondary buffer).
Both in double buffering and page flipping case, the copy / interchange is done during the monitor’s vertical blanking interval (the blank period when there’s no video data being drawn) to avoid tearing.
The game loop decouples the progression of a game time from user input, and from processor speed.
A simple game loop looks like this:
while (true) {
Event* event = WaitEvent();
dispatch(event);
}
The game is waiting for user input - mouse clicks, key presses.
This is not working for video games, in which we have animations, visual effects, basically the time is still moving even if we don’t provide any input to the game.
In video games, we process the user input, but we don’t wait for it.
Therefore, we can handle other things, just as updating the time and animation on screen.
while (true) {
processInput();
updateLogic();
renderGraphics();
}
processInput function will handle any input, the updateLogic function will advance the game simulation (AI, physics, audio), while render() will draw the graphical elements.
Based on the number of game loop cycles in terms of real time, we will get the game’s frames per second (FPS).
Basically, if we call render 30 times per second, we will have 30 FPS.
There are two factors that determine the frame rate.
First one refers to how much work has to be done per loop.
If we have complex physics and many detail on screen, that keeps the CPU and the GPU busy, it will take longer to complete a frame.
The second one is the speed of the platform.
We are affected by the number of cores, by the GPU, by the OS’s scheduler, and so on.
The problem with our game loop is that we have no control over how fast the game is running.
If the machine is slow, the game will be slow, if the machine is very fast, the game will be very fast.
We would like our game to run at 60 fps.
We need to calculate how much time we need per frame, and then do our game processing / rendering in less time than that.
while (true) {
double start = getCurrentTimeInMilliseconds();
processInput();
updateLogic();
renderGraphics();
sleep(start + MillisecondsPerFrame - getCurrentTimeInMilliseconds());
}
Once that’s happening, we can process a frame and wait until it’s time for the next one.
The sleep assures that we will not process frames too quickly.
If it takes longer to update and render a frame, it will be negative, so it will be ignored.
This pattern provides a global point of access to a service, without coupling the classes.
We need this because there are some objects that should be everywhere in the game (memory allocator, logger, audio system).
These objects can be seen as services that need to be available everywhere.
We could use a static class, or a singleton, but we have a better solution.
Service locator decouples the code that needs this service from who it is (concrete implementation) and where it is (how we get the instance).
All the game can use the service, through its interface, while we can find the appropiate provider in only one place.
class ServiceLocator {
public:
static Logger* getLogger() {
return pLogger;
}
static void provide(Logger* obj) {
pLogger = obj;
}
private:
static Logger* pLogger;
};
Logger* loggerInstance = ServiceLocator::getLogger();
loggerInstance->log("random message");
Now we can use it from everywhere, we only need to show the Locator what’s the instance it should use.We only need to show the Locator what’s the instance it should use:
Logger* logger = new ConsoleLogger();
ServiceLocator::provide(logger);
Because someone could use the logger before we provide it, it will dereference a null pointer and crash the game.
Therefore, we could use the “Null object” pattern to solve this.
class ServiceLocator {
public:
static void init() {
pLogger = &nullLogger;
}
static Logger* getLogger() {
return pLogger;
}
static void provide(Logger* obj) {
if (obj == nullptr) {
pLogger = nullLogger;
}
else {
pLogger = obj;
}
}
private:
static Logger* pLogger;
static NullLogger nullLogger;
};
The null object provides no implementation, but doesn’t crash the software.
Object pool reuses the objects from a fixed pool, instead of allocating and deallocating them constantly, helping against memory fragmentation.
This is performed by allocating a big chunk of memory when the game starts, and freeing it when the game closes.
Basically we have a pool object class that maintains a collection of reusable objects.
For each object, we know if it’s in use or not, and when we need a new object, we grab the first one available.
When the object is no longer needed, it is set back to the unused’ state.
This is similar to Flyweight, but we reuse the instances that are already there instead of cloning (thus allocating memory) when we need one
Another good thing of this is that we make use of the data locality pattern, which says that we should keep objects close to each other.
Therefore, the objects will be in cache when we iterate through them to draw them and act on the instances.
In gaming, you’ll have many challenges, such as packing as much data in each frame, breaking one animation to start another, managing resources (loading and unloading GB of resources dinamically, etc).
The most important thing to remember is that games are all about user experience.
In the beginning, the games were networked peer-to-peer, meaning that two or more computers were directly exchanging information with the other ones.
The basic idea is to have a set of commands (move player, attack player, construct building) and then send over the network the same set of commands on each player’s machine.
The problem is that this will be a complete mess, and the game will be desynchronized over time.
A limitation we can add, to assure that the game will be identical on all machines, is to wait until all player commands for a turn are received - but then each player in the game will have the same latency as the one with the highest one.
Instead of communicating with each other, each player was connecting as a client and they all communicated with one machine called the server.
All the inputs (key pressed, mouse clicks) etc. were sent to the server, and the server updates the state of each character in the world.
The state is then sent to everyone, and all clients simply interpolate the updates to provide an illusion of smooth movement.
Now, the quality was much better, because it depended on the connection between the client and the server.
With this change, it was also available for players to join in the middle of the game.
The big problem that was still up was the latency.
In order to reduce the latency, the code will be run on client side - to predict the movement of your character locally.
If you press the button to move forward, the character will move immediately, and not wait for a client-server package to be sent.
We cannot simply let the client send his position constantly, because this will be a problem with the hackers (dodge bullets, teleport).
Therefore, the server also have to keep the state and correct the player position when they disagree with the location.
When there’s a disagreement, the client must accept the update for the position received by the server. Due to latency, the correction is obviously happening in the past.
In a multiplayer game, a cheater will make the experience bad for all the other players.
The most important and obvious thing to do is to not trust the player, and assume the worst.
We can let the server have the control, and the client will only send inputs (key presses, commands) to it, and then return results back to the clients.
This means that the server will not trust the clients with their position, but will keep their position in the world and the client will only tell what actions wants to do.
e.g.
Server knows that Player location = (x, y).
Client requests to move to the left.
Server sends info to the client: You’re at position (x-1, y).
So the server is reading client input, update the game state, and then send it back to the clients.
When we have multiple clients that send inputs simultaneously, updating the game for each input received from each client will consume too much CPU and bandwith.
An approach here is to queue the client inputs, and update the game world periodically.
If the game is updated at 10 times per second, the server time step is 100 ms.
In every update loop, all the queued inputs from the clients are processed, and the new game state is broadcasted to clients.
If we move a character with 10 steps per second, after 1 second we know it will be 10 steps ahead of where it started. This is not quite an exact computation, because the player could have stopped or turned a bit.
If we have a server that sends updates once every 100 ms, the clients will have a dead zone of 100 ms between updates.
The client will still display that the character is moving, by assuming that everything is constant, and update the logic (physics, animation, etc) accordingly.
When the server update arrives, the position is then corrected.
In cases where the direction or speed of a player can change directly (such as in 3D shooters, where the players run, stop, turn corners and so on) the predictions no longer work that good. If we update player positions, we’ll see them teleport short distances every time.
What we want is to show to the player what happened during this time, so we will show the other players in the past relative to the current player.
If we receive the player’s location at time T = 100, we know that last time we received a location for it was at T = 0.
Therefore, we know where the player was at T = 0, and where it is at T = 100.
From T = 100 up to T = 200, we show to the current player what everyone did from T = 0 to T = 100.
In other words, we show to the current user, the movement of other players, but we show it 100ms too late.
With this technique, every player will see the world differently - each player will see itself in the present, but all the other entities are seen in the past (100ms prior).
Most of the input received is valid (the rest is due to hackers) and the game will update as expected. (e.g. for location {X, Y} and left arrow press, the new location will be {X-1, Y}).
This is useful because the game is deterministic, or in other words, given a state and some inputs, the result is predictable.
Therefore, we can assume that the inputs will be executed successfully, so we can update the state for the client while we wait for the server to confirm the state, which will happen in most situations.
Due to lag issues, you want to avoid killing characters until the server confirms it, even if we see that its health dropped below zero. It could be that he healed himself right before dieing, but the server has not notified you about it yet.
You hit another player, but you miss - although you weren’t supposed to.
Because of the client-server architecture, you aim to where the player was 100ms before you shot.
The best solution is the following:
Due to all that, the server knows exactly where you were pointing to - it was the past position of his head, but it was the actual position of his head in your present.
Therefore, the server can process the shot at that point in time, and update the clients – thus killing your enemy.
Artifacts are anomalies that are present during the visual representation of a graphical object. Can appear due to software bugs, overclocking the video card, driver-related issues, temperature of the hardware, etc.
Null object pattern/idiom is used when working with pointers. Instead of setting the pointer to null and verifying if it’s null, or doing a null pointer dereference by mistake, we provide a default implementation that does nothing when functions are called.