Download the Game

Introduction

Game Idea and Gameplay

I am a fan of Air Strike trilogy and I also like these kind of arcade games therefore I wanted to create a game with the same concept.

My game idea is quite simple; there is a spacecraft named LandShark fighting against asteroids and trying to save the world. LandShark has two kinds of guns; primary and secondary, which is powerful but can be activated in ten seconds, to fight against the evil asteroids. Primary gun can become stronger during game play by collecting the present boxes. There are three kinds of present boxes these are; Speed Box; increases the attack speed of the primary gun as well as the LandShark’s speed but it also decreases the range of the primary gun. The limits for the maximum speed and the minim range for the spacecraft are declared in the ‘Game-variables.txt’ file. Multi Box; increases the number of bullets (particles) by two of the primary gun until reaching a maximum limit which is declared in ‘Game-variables.txt’. Power Box; increases the attacking power be increasing the strength of the bullets and also cures the LandShark. The maximum strength limit for the bullets is also declared in ‘Game-variables.txt’.

By collecting these presents LandShark becomes stronger but at the same time, size of the asteroids and also the number of asteroids increases depending on time. This increase rate makes the game difficult the since the strength, speed as well as the accuracy of the particles increases depending on the difficulty. This difficulty change is a sinusoidal behaviour which means first increases and after the maximum point it decreases. This maximum point is also defined in ‘Game-variables.txt’.

LandShark can only be controlled with mouse. Left mouse button assigned to primary attack, right mouse button is the secondary attack and the mouse wheel is the spreading factor for the primary gun. The main reason for choosing the mouse to control the spacecraft is, these kinds of games usually are playing with mouse and provides a better gameplay.

Special Feature

According to the game idea LandShark has different kinds of guns and the behaviour of these guns needs to be changed easily. On the other hand to show the explosion of the asteroids, the particle system is ideal however creating thousands of particles may slow down the rendering. Additionally the collision detections between the gun particles and asteroids is one of the biggest time consuming calculation during the game since the secondary gun, for example, needs to create more 256 particles in one game loop. In normal ways, if we put these particles to the physics calculations for the collision tests with fifty asteroids the cost for the collision detection increases dramatically because the basic collision detection algorithm complexity is O(n²). Another problem of the particle system is the memory allocation/de-allocation time. In a short time interval the particle system needs to create thousands of particles and also free them which will definitely cause memory fragmentation.

As a result, to overcome these problems I tried to create a more efficient and easy to program particle behaviour system structure to prevent unnecessary collision detection calculations, memory allocations/de-allocations; I also use the classic multi-buffering method to send the particles in chunks to the graphics card to be rendered.

General Structure

The figure shown above is possibly the most simplified view to understand the outline of the programme. I tried to create a mini game engine to respond my needs to build the game on. There is no abstraction between the 3D API, which is DirectX, and the game which means all the parts of the engine dependent to DirectX even to DirectX 9.0c.

The main class for the game is the Core. Every game has to be a child class of the GameBase class which is also a child class of Core. This GameBase class is provided for future work actually to create an abstraction between the 3D API and the game. There is only one constructor of the Core class, which the HINSTANCE should be provided for the Core to create a windows application. After that Core initializes all the devices, managers and runs the message loop. In this message loop the previously created instance of the SceneManager class is being called each time. That is the actual running mechanism of the game engine.

Briefly Core is responsible of creating and initialising all the devices including the audio device, IO devices as well as the direct3D9 device; all the managers and systems; SceneManager, ParticleSystem and SpriteManager. After that it hands over all the control to the SceneManager instance by calling the run function of the SceneManager in each message loop. So the Core is pretty much abstracted from the game logic.

Second important structure is the SceneManager. It is responsible of the game object storage and calling all the necessary parts of the game in a constant order. Such as the sky box needs to be called at first, game panel should be rendered at the end etc.. SceneManager has four main duties; first: creating the necessary objects for the game such as camera, skybox and setting the necessary RenderStates. Second: registering/unregistering all the renderable objects, cameras, and frame listeners. Third: unregistering and deleting the unused renderable objects such as dead renderable objects. According to the game rules, camera never moves or even never changes its direction (always looking on +Z direction); therefore the SceneManager also clears the objects behind the camera location in every one second. This approach is dedicated to the game that means the SceneManager class is not really abstracted from the game. Fourth: calling all the listeners’, the renderable objects’ (which needs to be registered) and Particle Systems’ necessary functions to run them.

Basically all the objects to be rendered and all the listeners to be called needs to be registered the SceneManager and it will take care about calling their render or run functions.

The LandShark game class is also derived from the GameBase class and has two listeners; GameControlListener and GamePlayFrameListener.

GameControlListener is a listener responsible for movement of the SpaceShip and also shooting of the space ship according to the spaceships attributes.

On the other hand GamePlayFrameListener is responsible for creating the evil asteroids as well as the present boxes.

Code Organisation

Since the code organisation is quite complicated compare the game itself I prefer to split up the parts to provide a better understanding.

SceneManager

This figure is more detailed than the previous figure and shows the position of the SceneManager. Apart from the previous explanation of the SceneManager, to be more explanatory, SceneManager has three different storages instead of one for the listeners which are; KeyboardListener, MouseListener and the FrameListener. The main reason for dividing the listeners into three is to prevent unnecessary calls of the listeners. For each loop SceneManager checks the devices if there is an event happened or not. If so, calls all the necessary listeners’ necessary functions. To give an example; SceneManager checks for the mouse, if there is an event happened, such as a button clicked, than calls every mouse listener’s necessary function with the event information, according to the status of the mouse. If there is no event happened than it skips all the mouse listeners. Different from the classical approach to frame listener structures, this FrameListener has a priority variable which gives the frequency information of the FrameListener. For instance, if a frame listener has a priority of ‘1’ that means it will be called for every 1 frame. If the priority is ‘9’ than it will be called in every ‘9’ frames. Although the implementation and the logic of that priority attribute is quite simple, it saves lots of times for heavy operations such as physics calculations with a little precision loose.

Physics Engine

The most important three questions about the physics engine are; how to integrate the physics into the game loop, how to handle the visual objects as physical objects (since some visual objects may not be physical) and how to create a call-back structure (for example if a collision happens what to do).

The first problem is solved by creating a PhysicsFrameListener which calls the physics engine’s run function. The speciality of this frame listener is changing its own priority depending on time consumed by the physics engine. This may cause some precision loose but the minimum priority is once in ten frames which is not a big deal compare to the saving time.

The second problem solved by creating separate interfaces for the physics object model. In the figure above, there are three types of physical objects which mean to register an object to the physics engine the object should be derived from either of them. Since only collision detections handled in this physics engine, these interfaces have pure virtual function to provide the collision detection information to the engine. For example an object needs to provide the radius and position information by overriding the necessary functions, to be a physical sphere.

Just like the other problems, there are several solutions for the last problem as well. However, I preferred to put a function into the PhysicsObject , whenever a collision event happens between two objects, it calls this function for each of these two objects.

After solving these major problems, I faced with other problems about preventing unnecessary collision tests. For example according to the game specification, PowerBox, SpeedBox and MultiBox shouldn’t be affected by the spaceship’s attacks however these boxes should be able to collide with the spaceship. In this case collision tests between the bullets and the present boxes are unnecessary, so I put a CollsionGroup attribute into the PhysicsObject. If the and operation results with true between two objects, it tests if they collide or not.

The collision test between two spheres is very fast but the collision test between hundreds of particle and tens of spheres is not so fast since the complexity for the collision test is O(n²). The solution for this problem will be explained in the special feature section.

Sound

A 3D sound system is implemented in this project. There are two main classes; Audio and Sound. Audio class is the main class which creates the loader and performance objects and initializes the DirectSound and the DirectMusic. Sound is storing the actual data (Direct3DSoundBuffer) inside. Whenever we want to play a sound we need to create an instance of the sound object with the given filename. But the problem is, during the gameplay each time creating sound objects from wav files is not a good solution. To solve this problem, programme first scans for the files in the working directory and loads them into memory and maps them with their name. In addition I hide the constructor of the sound object to control the sound object creation. If the sound is registered in the sound map, the static function for creating sound objects, directly gives sound which is already created. So without any IO operations we can provide sound to the game with a static function. This structure is pretty much seems like a sound-bank approach.

The 3D sound properties used for the gun sound as well as for the score up/down sound. Depending on the LandShark’s speed and distance to the camera, the attack sound changes. For the score up/down, if the player gets a big amount of points in a short time the score up sound gets closer. The LandShark’s gunfire sound updating in the GameControlListener since the position of the LandShark also updating in this class.

DirectInput

The IODevice class is the mother class for the Keyboard and for the mouse, which mainly contains the DirectInputObject, virtual update function and the acquire function. Implementing the Keyboard class is not so difficult because there is not efficiency problem since the game is playing with mouse. Therefore Mouse implementation was a bit problem. Since DirectInput holds the mouse button information in eight bytes, it is not efficient to look for eight bytes. That’s why I created my own mouse event structure which stores all the mouse button information in one byte. With his structure, with an AND operation we can find out if any key pressed or released besides, with an EX-OR operation we can determine the released keys. That’s why I preferred to create my own mouse state structure.

SpriteManager

The explosions, game menu, game panel they are all sprites and are using frequently in the game. The most basic approach for creating the sprite is to read the texture file whenever asked for creating a sprite. This approach also causes lots of IO operations plus if the texture file is compressed (such as jpg) need to time extract this information. Instead of doing that I preferred to create a builder class; SpriteManager. With this structure to create a sprite, firstly we need to register it by providing the information about the texture such as name of the texture, width of the texture, number of vertical frames in texture etc. After providing this information to the SpriteManager, it creates a SpriteLayout which stores the common information for one kind of sprite. After that to create a sprite we need to call the createSprite function of the manager with a name to indicate which layout should the manager use to create the sprite. By this method, we only allocate one texture memory area for all same kind of sprites which also prevents unnecessary file IO operations.

However, in the game I use the sprites for only creating the menu, game panel and the numbers on the game panel. At first I used the explosion stripe for the explosion effect but, all the stripe files I found are in jpeg format and didn’t seem good. So I ended up with disabling the explosion stripes.

Tools

Tools mostly used for logging, fast square root, storing render states within a stack structure and reading the game variables from the files at the beginning of the game.

Putting all the parts together

To sum up, the main game class; LandShark is a child class of GameBase. So it initializes the Spaceship, registers it to the both SceneManager and to the Physics Engine, plays the opening sound, sets up the scene, registers the sprites and creates the two frame listeners; GamePlayFrameListener which creates asteroids and present boxes with different attributes and throws them through the spaceship with an accuracy and speed depending on the game difficulty, and GameControlFrameListener which handles the mouse moves, clicks and finds the new position and orientation of the spaceship.

Inside the GameControlFrameListener; when a mouse clicked, it calls the fire function of the SpaceShipGun. In the fire function of the spaceship gun, it sets the distance and the velocity of the sound.

So the game object creation and controlling of the spaceship works on the frame listeners, the rest is done by the provided data structures. The only point that needs to be explained is the special future; Particle System.

Special Feature: Particle System

Problems:

After deciding the game idea, I realise that for the gun as well as for the explosion effects I need the particles system. Actually creating 3D objects for each bullet is another way however the speed of the SpaceShip’s is quite high therefore this method doesn’t seem appropriate for this game.

Particle system fits like a glove the game but at the same time it brings lots of problems to the programming side. The first major problem is creating hundreds of particle in a short time and updating their position, velocity etc. which is a time extensive operation. In addition to these CPU side time consuming operations, sending these particles to the graphics card and drawing them to the screen is also a time consuming event for GPU. Another important problem is memory fragmentation; allocating hundreds of particles and freeing them in a short time interval causes memory fragmentation which also slows down the system. Besides the fragmentation issue, allocating unnecessary memory for the particles is also a big problem. In this game particles have some defined behaviours and these behaviours requires some other data apart from the particle data. For example according to the game scenario, the gun particles fired by the spaceship, has some common attributes such as texture, life length etc. These common attributes shouldn’t be allocated for each particle but at the same time these information need to be exist somewhere. Another major problem is collision detection. As the numbers of the particles increases linear, the time consumed for the collision detections increases parabolic.

Apart from the efficiency problems, creating a generic and expandable structure and integrating it with the game is a vital programming difficulty.

In this section all the solution against the bottlenecks will be explained clause by clause.

Implemented Solutions:

The figure above may seem complicated but involves the answers for the mentioned problems.

Creating hundreds of particles in a very short time (needs to be less than 5ms to not the slow the game down), updating their attributes and sending them to the graphics card to be rendered is really the first problem to be tackled. In this system classic multi-buffer method has implemented. The principle of this method is allocating a vertex buffer area and dividing it into small chunks after that filling up these chunks with data. Whenever a chunk gets fulfilled, program sends the data to the graphics data to be rendered. With this method; while the data being send to the GPU and also while being drawn, program will continue filling other chunks or continue doing other operations. But also in this design there is a problem; determining chunk size. In this particle system chunk size as well as the buffer size are constant. I tried to find the best chunk size for my system however this may vary according to the bandwidth of the bus or the memory speed of the GPU. This will be discussed in the critic section.

To prevent memory fragmentation as well as reducing the allocating/freeing time of the particles, this particle system uses pooling. At the beginning of the mini-engine, Core creates the ParticleSystem and the particle system creates thousand particles and puts them into the deadParticles vector. Whenever any particle needs to be created, ParticleSystem first looks at the dead particles pool. If there aren’t enough particles, than allocates the particles from the memory, otherwise gives the particles from the deadParticlesPool. However as shown in the figure above, there is no aliveParticlesPool. To explain why, the design of this particle system needs to be explained more; the ParticleSystem is a singleton structure which means can be created only once and can be called by any part of the program. At the same time this ParticleSystem is a builder means; ParticleSystem responsible for creating particles, putting them into necessary storages with the given information. This information is represented by the ParticleGroupLayout. Apart from the required information for the particle group to be created, this layout structure has two methods; init and update. Init function is using for giving the initial values to the particles and update function is for updating the particles. So the behaviour of the particles is completed abstracted from the ParticleSystem. The totally hidden structure from the other parts of the engine is ParticleGroup structure. ParticleGroup is a special class which contains all the particles’s pointer addresses, remaining life, texture and the layout object. The ParticleSystem has a pool structure for the ParticlesGroups as well. The main reason for not having an alive particles pool is all the particles to be processed in the system must be a member of the particle group which is constructed with the information coming from the ParticleLayout.

Best example to understand this structure is the gun mechanism. As seen from the figure, spaceship has two guns and each gun has its own ParticleLayout; PrimaryGunLayout, SecondaryGunlayout. When left mouse button clicked, the GameControlListener calls the SpaceShip’s gun’s fire function. After, this function wants the ParticleSystem to create a group of particles with the given information which is PrimaryGunLayout. ParticleSystem checks for the pools and if there is not enough particles in the deadParticlesPool creates new particles and fills a ParticleGroup structure with the particles as well as with the provided information. ParticleSystem also have a map for textures, once a particle texture is created, it is stored in the map and won’t be read from the file for the next time.

Another important reason for using ParticleGroup structure is the improving the collision detections. There are two gains for the collision detections. Let’s think that there are twenty ParticlesGroup registered in the physics engine which are all created by the SpaceShip’s gun and each group has ten particles, to sum up there are two hundred particles waiting for the collision test. In this case we shouldn’t test the collisions between these particles but how can the physics engine manage to do it? If there weren’t any ParticleGroups, it needs to check for each particles’s CollisionGroup flag which means 19900 (200*199/2) check operations needed to be done. With the ParticleGroups structure the number of the check operations is only 45 (10*9/2). This improvement is quite satisfactory to create and use such kind of structure. In addition to this magnificent improvement there is another gain for using that structure in terms of collision detection; creating bounding box for the particles registered to the ParticleGroup. But what do we gain by doing that?

Let’s assume that there are 63 objects waiting for the collision test with 256 particles. In that case, without the grouping method, the number of the checks between the all objects (since all the objects in one vector in the physics engine and we need don’t want to test the collision between two particles); 319 * 318 / 2 = 50721 type checks and 256 * 63 = 16128 collision tests; with single grouping method; 64 * 63 / 2 = 2016 type checks (25 times faster) and 56 * 63 = 16128 (same amount of collision tests). Even though the improvement is very good, still the number of collision tests is too much. Because in the game scene, secondary gun particles are moving altogether in the same direction but we are testing all the particles with all the objects in the scene even if they are far away. To prevent this unnecessary calculations ParticleGroupLayout structure provides an option for creating the bounding rectangle for the particles. This is only optional and can be enabled during runtime (actually just a Boolean flag named m_CreateRectengle). This bounding rectangle needs to be refreshed according to the precision desired. In the SecondaryGunLayout, it is refreshing in each update of the particles which is in every 20ms.

The physics engine decides if the object needs to be tested by just checking the borders and the location of the objects. If the object is not out of the ParticleGroup rectangle, tests the object with each particle. As a result in the same scenario; first type checking cost is the same; 64 * 63 / 2 = 2016 but the number of collision tests is; 63 inside/outside check (which is just a single if comparasion) + for each object inside the borders of the ParticleGruop test the collisions between the particles and the objects; in the figure there is only one object inside so 256 collision tests.

Instead of 2016 collision tests with the help of the bordering improvement the number of collision test reduces to 256 + 63 + 256/5(we need to find the maximums and minimums of the particle group in every 20 ms, so the assumption is physics engine runs in every 4 ms) = 370.

As a result, my special feature actually involves; easy code integration of the particle system to the mini-game engine, creating a conceivable relation between the game objects (SpaceShip,Gun,Particles relation), reducing memory as well as IO usage, preventing fragmentation by using pools, parallel processing between the GPU and the CPU by dividing the vertex buffer into chunks, giving a reasonable solution for representing the particles to the physics engine, reducing the time using for collisions between the objects and the particles, preventing unnecessary checks for collision tests.

Critical Appraisal

Physics/Collision Detection

As mentioned before, PhysicsEngine class is only responsible for collision detections. This is one of the main concerns about this structure. Instead of creating a PhysicsEngine class all the collision detections could be done either by the SceneManager class or by a frame listener.

Apart from the particle grouping there are no other methods used to improve the collision detection. All the objects in the physics world are being stored in a std::vector data structure even if the objects are from different groups which causes O(n²) complexity. To reduce the complexity; instead of one vector eight vectors (one vector for each group) could be used.

Another problem about the physics part is creating a relation between visual objects and the physical objects. In the implemented solution, a visual object can represent only an only one physical object. For example the spaceship is represented by a PhysicsSphere in the physics world. Apparently this structure is not flexible. For instance with this structure to divide the spaceship into small parts; a complex structure needs to be created. An alternative solution is having storage (e.g. std::vector) for physics object and adding the physical primitives in to this storage. To give an example, let’s assume there is a spaceship as a visual object and three physical (primitives) cubes to represent this object. In this case the physics world should provide a storage physics object and the cubes should be added to the main object with the local orientation and position respect to the main object. This structure also avoids multiple inheritances.

SceneManager

SceneManager is not only responsible for visual objects but also for the physical objects. This is one of the biggest weaknesses of the system. For example whenever an object gets removed from the list of visual objects, it needs to be removed from the physical list as well and vice versa. This is a big consistency problem since if the system removes the visual object in the SceneManager, the physics engine will crash because actually the memory addresses for both the objects are the same. The first solution for this problem is using flags to provide the information if the object still exist in visual world. Since there is no non-visual physical object implemented this solution works. To give an example; if an asteroid collides with the spaceship and explodes, the flag for the visual existence will be set to false and firstly the SceneManager will remove the object from the physics world and after from the visual world. In that case the SceneManager still needs to know the physical part. Another solution for problem is; creating an cleaning interface to provide the consistency and to abstract these two parts from each other.

SceneManager clears the objects behind the camera. This approach is really dedicated to the game itself however the scenemanager should be abstracted from the game rules.  The abstracted cleaning layer will also provide the abstraction between the game and the managers.

RenderableObject

In the implemented solution, RenderableObject represents the visual object with mesh structure which involves index and vertex buffers. Obviously creating the same structure each time for all the asteroids is not a good way. A better solution is creating storage and reading all the meshes for just once and whenever the system needs that mesh, creating the visual object with the same mesh and materials. This problem is one of the biggest performance issues for the current system.

Critic for Particle System and Its Implementation

Implementation of the particle system was one of the most difficult parts during in all the development process since there shouldn’t be any memory leak, a different way should be followed for the collision detection, integration of the particles to the game logic should be flexible as well as shouldn’t be too much confusing for the developer and the hardware capabilities should be taken into account more than other parts of the system because of the high usage, creation and deleting frequency.

The current implantation of the particle system is not very flexible since all the particle behaviours needs to be hardcoded however the integration of the particle system is easy. For example there is no structure such as particles emitters and the only way to attach a particle group any object can be done by passing the object’s word matrix to the particle group which also needs to be done by the programmer of the particle group.

On the other hand particle system designed not for flexibility but for low resource usage. Using pool system for the particles as well as for the particle groups and the fast collision detection improvements can be considered as successful point of the implementation. After the first implementation without the pooling improvement, the particle system was using 5% of the game loop time for two hundred particles in a current system with an empty memory space but as the free memory space becomes less the process time gets longer. After the improvement the process time for the particles reduced to 2% under same conditions and this percent never changes during game play. However there is a weak point of the pooling; the particles never gets deleted from the pools. For example let’s assume that at a certain moment the system reached a peak point of five thousand particles and the particle system allocated the necessary memory for these particles, after these particles are collected by the particle system and put to the dead particles pool. In this case after the peak time, the total amount of the memory allocated for the particles never changes, and system will have five thousand particles until the game ends.

As a result personally I am quite happy to create such kind of particle system with all the improvements and I am quite confident about implementing complex data structures.

Conclusion

Creating a game has some common point with IT development processes such as; they both needs to be designed first otherwise the complexity of the system will increase and in most cases the system won’t be consistent. To give an example while building up the special feature I haven’t taken the physical representation of the particles into account and I created the physics part without the particles since I wanted to put all the particles as spheres into the collision detection loop. This approach cost me two days. There were two problems about this approach; removing and adding the particles to the physics world one by one and the calculation cost of hundreds of particles. Thankfully the particle group structure was suitable to integrate to the physics world otherwise I would have lost more time to overcome with these problems.

The way that I wanted to do this coursework was not trying to create a realistic game but understanding the game logic as well as understanding the general approach about creating a mini game engine. Therefore first of all I tried to create the mini game engine which involves all the requirements. I apparently inspired from Ogre3D game engine and tried to implement a fully object oriented structure.  At the beginning I didn’t have a game idea but it wasn’t matter at all since my goal was creating a mini engine. After creating the base, I started thinking about the game idea. I chose a spacecraft game because the game design and the gameplay is quite easy as well as I like these kind of casual games. During the implementation of the game, I needed to change the mini game engine for several times but the main concept of the core never changed.

One of the most important time saving things that I have done was creating the log since sometimes debugging can be a big deal and it causes wasting too much time to find a small mistake.

To sum up personally I am very happy of being successful about creating a small game and implementing all the structures required for the game. After doing this project, now, I am more confident about understanding some of the structures to build up a game. The most important thing behind the success is creating the object oriented structure before starting the implementation. Finally I am glad to say that I like playing my own game J