Technical Design Document
This document outlines the high level functionality of all the major systems in Team Purple's Populous 2. It serves as a reference point for the functionality of code, as well as how it might be used and adapted to build upon the existing game.
Team Purple aims to develop both a PC (64 bit) and Arcade Machine (32 bit) build for the game.
Memory Usage: 100mb
Program Size: 267mb
We are using C++ 14 and DirectX 11 for this project. DirectX 11 was chosen because DirectX 12 uses a new standard and is still not fully recommended by Microsoft. The Scarle Engine is set up with C++ 14 so to avoid potential issues we are staying with this version.
DirectX Toolkit - The DirectX Toolkit is a collection of helper classes and methods for DirectX. Using this library allows us to start developing the game quicker as it provides a lot of base functionality.
A Simple ECS - In this project we decided to go for an data oriented approach. This starter code allows us to quickly implement a solid backend that we can build upon.
ECS (Entity Component System) is a way of programming which separates the logic from the data. It aims to speed up execution by reducing cache misses and therefore is ideal for projects where a large number of objects need to be simulated simultaneously. The primarily example of this in Populous 2 is the large number of NPCs wandering about the game world. In the original game lag is even a problem once the number of NPCs gets too high, so in this remake Team Purple aims to mitigate this issue through the use of an ECS.
In order to create a fast system, one of the things we want to do is reduce the amount of times the CPU has to go and check the RAM for data.
- CPU -> L1 Cache: 3 cycles
- CPU -> L2 Cache: 20 cycles
- CPU -> RAM: 200 cycles
While these numbers may not be perfectly accurate, the point still stands that going to the RAM is considerably slower (at least in CPU time) than checking the cache. The CPU knows this, and therefore tries to predict what data is being commonly used and store it in the cache. However, the cache is very small and so only a limited amount of information can be stored in it.
- L1 Cache: Very small
- L2 Cache: A little bigger, but still tiny compared to...
- RAM: Very large
Furthermore, to transport data between the caches and ram to the CPU buses are used. These are the 'transport links' data travels down to reach the CPU to be executed. In order to speed up execution, we want to fit more data on these buses so that it takes less trips back and forth between the cache / ram and the CPU.
So to solve this problem we want to have data structures with small memory footprints, so more of them can be stored in the cache and be carried at the same time on the CPU buses, so therefore can be accessed quicker by the CPU. But how do we do this?
A good example is a Sprite. Using a traditional Object Oriented Approach, a Sprite would have both its data (e.g. texture, scale, rotation) and its functions (e.g. init, setScale, setOpacity) in the same class. But all this functionality bloats the size of the class and therefore reduces the amount of sprites that can fit in the cache or onto a bus, meaning that the CPU has to check RAM more often, which slows down execution.
A data oriented solution is to split up the sprites data from its functions. Instead the sprite just contains its texture, scale, etc and a SpriteSystem has the functions for, e.g., initializing the sprite. A Sprite is probably only going to be initialized once, so therefore it doesn't really need to 'carry around' the init function everywhere it goes. Instead, we can simply pass the sprite into the SpriteSystem when we want to perform an action on it.
Because we have now slimmed down the size of our class we can pack more data into the cache and onto the buses, and the CPU optimisation will notice that the System is being commonly used and store it nearby on the cache. Therefore more data will be able to processed in a shorter time as less trips back and fourth will be needed.
This was a very basic outline of why ECS can increase performance and doesn't cover many nuances of the system. For a more detailed overview we highly recommend you watch Mike Acton's "Data-Oriented Design and C++" talk on YouTube.
A further benefit of data oriented design is that when you want to add more functionality, you just add more data.
For example, if an entity has a Thrust component with added velocity on the x axis and suddenly you wanted the entity to be affected by gravity as well, you could create a Gravity component which adds velocity on the y and add it to the entity.
This makes debugging easier as systems can be enabled and disabled easily. For example if your entity was now behaving unexpectedly you can just disable the GravitySystem to check the behaviour and isolate the problem.
Furthermore, it modularises your code so functionality can be quickly used between entities and promotes decoupling. Any number of entities could easily have the Gravity component added to them if the behaviour was desired.
For all these reasons Team Purple chose to adopt a data oriented approach for the Populous 2 game.
The driver is a static class that sits between the DirectX and Scarle Logic and the rest of the game code. It adds a layer of separation so that the backend logic can be accessed anywhere in the code. It sets up some DirectX variables such as the GameData and DrawData2D and initialises the handlers for example the LoadHandler.
It updates the handlers and manages operations regarding rendering the game, for example clearing the DirectX buffers and handling the swap chain.
The syntax for retrieving the driver is Engine::Driver::get[Driver/AudioHandler/etc].
Scenes act as a base class to derived scenes, granting core functionality required within all different game scenes. Scenes contain a data struct holding all information required, with the scene handler assessing this data and acting accordingly. Scenes can be paused through calling the function SetPauseState, and receive input through the virtual onKey and onMouse methods.
There are four handlers:
LoadHandler
AudioHandler
SceneHandler
InputHandler
Each handle specific functionality and are instantiated in the static Driver class so can be accessed from anywhere in the codebase.
LoadHandler is responsible for loading resources from external files. It takes the information from the Resources folder and it can be accessed with LoadHandler.getResource([ResourcePath])
AudioHandlermanages the initialisation and playing of sounds. A sound can be played with AudioManager.playSound([SoundData])
SceneHandler handles changing scenes, as well as updating and rendering the current scene. Scenes can be changed through SceneHandler.setCurrentScene([Scene])
InputHandler handles both keyboard and mouse input. It forwards the information to the current scene through the virtual onKey and onMouse functions.
Primarily composed of the MoreMath class, HelperMethods contains a collection of functions to carry out common operations. For example randomRange and rad2Degree.
Entities are represented by unsigned ints, and components can be added to them via addComponent to add specific behaviours. Depending on the components an entity depends on which systems iterate over them.
The entity limit is set in the Types.h script, and by default is 10,000.
The ECS supports entities becoming children and parents to one another, if the destruction of a parent is called, the ECS also calls the destruction of all children, and recursively the children of the children and so on. Two entities can enter a relation after creation or an entity can be directly created as a child to another.
Components contain data which systems manipulate to provide functionality. All components must be registered first in the initComponents function. A reference to a component on an entity can be fetched with getComponent, and removed with removeComponent.
Systems iterate through entities with the desired signature. They are used to add functionality to the data holding components. All systems should inherit from Engine::System and be registered in the scenes initSystems function. They are set with a signature, the components that an entity needs to be iterated over by the system, and initialised by passing in any relevant information, for example a reference to the scenes coordinator.
First the components are registered, followed by the systems. The system's signature dictates what entities will be iterated over by it.
Some systems store a pointer reference to another system to allow for easy communication and transferring of important data.
Entities can then be created through ecs->createEntity() and then components can be added to it via addComponent.
The coordinator provides a ‘getComponent’ method, allowing systems to grab relevant data structs from entities containing the components.
Entities can be destroyed with destroyEntity() or destroyEntityAtEndOfFrame(), resetting the entity. It's important not to delete an entity while other systems are iterating through it, so removing the entity at the end of the frame, after all the systems have iterated through it, can be used if this is a problem.
Creates entities with Ability Spawner components that are used to create ability effects at their locations by another system. The system has a timer used to wait in-between casting. When the timer is up, the system selects an ability from it's list of abilities by calculating a weight for each ability then randomly selects one, the higher the weight, the higher the chance the ability will be picked. The weight can be influenced by each settlement and unit owned by the team the AI is assigned to, and each other settlement and unit, it's up to each ability to define it's relation to each. The system then divides the tile map into segments that are minimum one tile by one tile, then counts a weight for each segment and similarly picks a random segment. Within the selected segment an entity is created on a random tile with the chosen ability. The system also supports the AI casting quicker when it's past a mana threshold. Overall the map weight works similar to a heatmap and the segmentation can add potential inaccuracy on precise abilities like the wall of fire or accuracy on wide range abilities like the firestorm.
Creates ability effects at the location of entities with the Ability Spawner component, then calls for their destruction.The system takes input from the Ability AI System in a form of an entity (using the aforementioned Ability Spawner component) that serves as a 'beacon', marking the location and the ability the AI wants to use. The component can also store a delay timer which also needs to be handled: the ability is only used when the timer reaches zero. Once the ability is used, the system takes care of the removal of the entity.
Adds watches / timers to the settlements through a Settlement AI Watch component if they are above a certain threshold. Capable of supporting multiple AIs, one for each team. In the original work, the player was capable of employing the help of a Sprogging AI and change it's behaviour between a more aggressive expansionist, a more reliable, patient one and a balanced one. The system is capable of replicating these different styles depending on how it was initialized, but the changing behaviour feature was cut while making both teams capable of having an AI.
Creates a chance to alert the Settlement Spawner System through the Settlement component to spawn a new unit at the settlement's position with the settlements team.
The autoscale system instantiates with the current screen dimensions, every update this is compared with the current screen dimensions and when a change is seen, entities containing a transform are scaled and positioned to their new relative screen position.
Moves a background sprite behind the map, every second time the sprite appears it is flipped to make it look less repetitive. It's the shape of clouds.
Destroys units that are off the tile map using their tile position, this is for powers like the tornado and to stop errors if pathfinding doesn't see the nodes the unit is connected to if the said unit moved off the map through any means.
Similar functionality to base directX camera, a single entity contains a camera component with FOV, near and far plane, etc. This information is then passed into the draw_data camera which renders from the camera entities view point.
Checks every entity with a collision component against every other entity in the list, does a check to see if they collide, if they do, then it calls the collider's respective collision function.
Creates and updates (Manages?) a UI element that shows the player a rough estimation of power between the different teams.
Decreases the energy of the units relative to the time elapsed, calls for their destruction when they've ran out of energy.
The system is responsible for creating, updating and removing the emitter entities. The system uses the Emitter component on the entities, that
stores all the important data to create an emitter, which can then emit the appropriate particles over a set period. The emission can be vertical,
radiant, or filling an area with particles. The emission can happen using either local or global space.
Adds energy to any settlement based on the elapsed seconds. Never allows them to go over the max energy limit.
Goes through the list of settlements and checks if they are assigned a flag entity yet. If a settlement does not have a flag entity yet, it handles the creation of the entity as a child, then saves the entity inside the component for other systems to see this link from the component, so they won't need to go through the list of children of settlements to find their flag.
Goes through the list of settlements, identifies their flag through their Settlement component, then calculates how high the flags need to be in relation to the ratio of current energy to maximum energy, finally it updates their positions, so the player can tell how much energy each settlement has.
A fairly simple system that works in cooperation with the Emitter system: the Particle system is responsible for updating, and once the lifetime
of the particle runs out, remove the particle entity from the system. The particle system is not responsible for creating the particles, this
task is delegated to the Emitter system. To identify a particle, the system looks for the Particle and Lifetime components.
Goes through the list of entities with rigid bodies and moves them according to their velocity. It also goes through the list of their children and moves them even if they do not have a rigid body, this is useful to make additional sprites follow a character, a crown for the leader, a sword if the unit's weapon is upgraded, a ship for naval transportation, ...
Renders every sprite attached to the entities and is responsible for ticking animations as well as handling operations such as z ordering. Furthermore, the RenderSystem implements a resource loading system that ensures that textures are only initialised once.
Creates a leader from one of the list of units if the team does not have a leader yet. This system also handles the creation of heroes.
A system that goes through the list of settlements and checks if any of them have been sprogged by either player input or by an AI. The settlement has it's energy reduced to zero and a new unit is created at the settlement's position with the settlement's energy.
Goes through all the units, each have individual timers that are randomized, when the timer ticks down, the system checks if the location the unit is at can be settled on, if it is possible to settle on it's current tile, it creates a settlement entity and destroys the settling unit.
Acts similarly to the Render System, provides text initialisation and updating with functionality planned to grant unique font creation. Text is rendered every frame through the ‘update’ function. Text in DirectX requires draw data to be cleared every frame unlike 2d objects.
The UnitSystem is one of the largest in the project. It handles a variety of operations that all units need, such as pathfinding, movement and fighting as well as merging. New units can be created through its initUnit function.
Requires the registration of team controller entities to work. The entities need to have the Team Controller component and the Mana Pool component The system adds mana to their mana pool for every house matching their team based on the elapsed time since the last update.
A component storing a type of ability and a timer to potentially delay the casting of the ability. Used by the AI Ability system and Ability AI system.
Heavily based on the Scarle camera, the camera component is simply encapsulates the data needed to render a viewport. For example, field_of_view and aspect_ratio. Note that every scene must have a an entity with the camera component to be used as the 'main camera', and that the header file is Cam.h to avoid conflicts with existing code.
The cloud component is just a tag to differentiate the cloud sprites from others.
Component storing pointers to functions to be called upon the entity's collision, the size of the collider and another value that allows it to be toggled on-off, so it does not need to be removed every time the collision needs to be turned off temporarily, for example shortly after a collision give a window of invulnerability. Used mainly by the Collision system.
A tag to differentiae the spectator from other entities with sprite and transform components.
Handles the creation of, managing, and deletion of entities with the ColosseumSpectator component. Creates an effect were entities of both teams fill up a grid as the number of units per side increases.
Empty component, used as a tag. It's used to optimise the project by helping systems filter out entities easier or helping systems find, assign and manage a specific entity in a wider range. Used by the Particle and Emitter Systems to create damaging particles and emitters.
Component that stores particle data on emitters, a timer and an emission speed that define the speed at which it creates the particles. Used by the Emitter and Particle Systems. The component stores a data struct called Emitter that is also used in the Ability manager to store the emitter system data for each ability that has a particle system component.
Component storing, current, minimum and maximum energy for units. Used on settlement entities, intended to be used on unit entities as well. Used by various systems managing energies, such as Settlement Spawner System or Flag Raising Systems.
Component that defines the rate an entity's energy is falling. Units lose energy over time, and certain abilities could add this component even to settlements. Used by the Energy Decay System.
Stores the maximum offset the flag can rise to, the current offset and it keeps track of the building it's bound to, in case any system wants to affect the building through it's assigned flag. Used by the Flag Creation and the Flag Raising Systems.
Empty component, used as a tag. It's used to optimise the project by helping systems filter out entities easier or helping systems find, assign and manage a specific entity in a wider range. Used by the Leader System.
Empty component, used as a tag. It's used to optimise the project by helping systems filter out entities easier or helping systems find, assign and manage a specific entity in a wider range. Used by the Leader System.
A timer component that defines a lifetime for an entity, then a system calls for the destruction of the entity when the timer reaches zero. Used by the Particle and Emitter Systems.
Component with a pointer to a variable that systems can access. Since only team controllers have mana pools, it could have been integrated together.
This component is essentially a tag to mark the entities that the Particle system has to manage. Stores the particle damage value and damaging
property if it is applicable.
Managed by the UnitSystem, the pathfinder component holds data needed to create an entity with can traverse the grid based world. For example, the entities path, speed and sensitivity (the distance to the destination node the entity needs to reach before a new path is calculated).
Stores the velocity and acceleration of an entity, has a gravity scale to change how much the entities are affected by gravity. Used by the Physics System.
Contains a timer and variables for resetting the timer, as well as a minimum energy required for the entity to become a settlement. Used by the Settling System.
Component that also functions as a tag. It stores the team it belongs to, the type of building, the energy regeneration and the building's attached flag entity. Used by various systems such as the AI Sprog System or the Worship system.
Timer component for the AI Sprog System, used for knowing when to roll to see if the AI wants to sprog the entity/settlement. Used by the AI Sprog System and the AI Settlement Watch System.
Holds the texture needed to render the sprite, as well as some other data such as an Animator component and source rect.
Started as a tag. The game controller entity was split into team controllers for more flexibility. Stores the team it belongs to. Used by the Worship System and Ability AI System.
Stores the location data of the entity. Used by various systems, such as the Flag Raising System and the Physics System.
Acts as a tag for the UI manager along with storing an enum type for the UI type
Inherits from UI, contains an enum type for the button type. Additionally stores a map to aid in text instantiation of main menu buttons and the main menu button role.
Inherits from UIButton, contains a map of button textures along with the buttons selection state. Additionally uses AbilityData.h to store an enum ability type for the button.
Inherits from UIButtonGroup, stores an int to the ability level
Component also working as a tag for filtering out entities. It stores the team the entity belongs to, it supports the entity having different max energy just like the energy component for creating stronger leaders and heroes and a standard timer for an invulnerability window after fighting or merging. Used by various systems such as the Leader System or Settle System.
A basic A* pathfinder that uses a single dimensional array to improve memory efficiency. Has the option to create the cost map with straight and/or diagonal connections.
Pathfinding is dependent on its ability to interact with the tile map. Units pathfinding component will calculate cost and path towards target destination. To do so the pathfinder must be able to find world space positions of tiles and the height of tiles the unit traverses. To do this a node map is created that mimics the size of the tile map. The node map stores information from each tile in the tile map and retains this information along with extra information pertinent to the pathfinding system, including data regarding where the unit has already traversed and the units target traversals.
Tile maps are inherent to the design of the game. The tilemap is responsible for the terrain and the perspective of the terrain using height values. Below is a description of the technical attributes and maths required to generate an isometric tilemap and utilise it in this tool kit.
The benefit of isometric design is the ability to create a 3D perspective. This is done with assets in a diamond shape with the width being twice the height. This allows the sprites to be drawn in a perspective where the camera is looking down and across the map. Using this Populous II is able to demonstrate differing depths and heights across a level map. The appearance is as if an orthogonal maps camera was swung 45 degrees to one side and 30 degrees down. This angle allows the user to see 3 sides of a cube. The dimensions also contribute to the perspective as if they were equal instead of width being double it would seem as a rotated orthogonal view which would not seem 3D.
A simple orthogonal tile map would have a very simple lay out. From the width and height values we increment through rows then columns and place each tile using the size of the tile to distance them.
(Bellanger, 2022)
isometric layout requires the map to appear as if it has been rotated. Each increment in each axis now changes from horizontal and vertical to diagonal. Two tiles could have the same position in the Y axis but entirely different Y values within the map as now the width increments right and down in a diagonal and the height incrementing down and left. We also now use half the width of each tile as we draw these.
(Bellanger, 2022)
The maths to do so is as following where screen is a point on a 2D screen and map is a value from a table of tiles as illustrated above:
screen.x = map.x * TILE_WIDTH_HALF - map.y * TILE_WIDTH_HALF;
screen.y = map.x * TILE_HEIGHT_HALF + map.y * TILE_HEIGHT_HALF;
This can be further simplified to:
screen.x = (map.x - map.y) * TILE_WIDTH_HALF;
screen.y = (map.x + map.y) * TILE_HEIGHT_HALF;
Further to this capability to find a tile from screen space coordinates or vice versa. This is necessary for using any on screen cursor and using a tile map in hand with other systems. To do this we have to rearrange our previous formula to solve for map coordinates from screen coordinates. We can resolve these as:
map.x = (screen.x / TILE_WIDTH_HALF + screen.y / TILE_HEIGHT_HALF) /2;
map.y = (screen.y / TILE_HEIGHT_HALF -(screen.x / TILE_WIDTH_HALF)) /2;
Furthermore, when converting screen coordinates to map coordinates the truncation of decimals can cause issues. To account for this 0.5 is added to screen values to account for loss of accuracy. The above formula in implementation must also account for the offset of the tile map or the screen position of a tile will not translate to the map coordinates of the same tile.
CppCon (2014). CppCon 2014: Mike Acton "Data-Oriented Design and C++". YouTube [video]. 30 September. Available from: https://www.youtube.com/watch?v=rX0ItVEVjHc [Accessed 05 April 2022].
Bellanger, C. (2022) Isometric Tiles Math. Available from: https://clintbellanger.net/articles/isometric_math/ [Accessed 3 March 2022].