Game Logic Layer

Games are real-time software applications designed by the logic layer which consists on a dynamic and interactive virtual environment that changes over time. The game engine loop is the overall flow control for the entire game program and is responsible to service every game subsystem in a single loop running at an optimal update rate for a human being. Game logic holds information of the entities, which they can be either static or dynamic, in the virtual world. These entities are updated by applying the game rules and represented in different game subsystems.

Game data. Any kind of game contains both static and dynamic actors which the engine groups in a single container and update them each game tick. Depending on the game, it may be necessary to implement more flexible and optimized data structures that allows the game to traverse the actors efficiently. The game engine uses the actor component system which is a very flexible and reusable architecture that define the game actor’s properties as components. In opposition to the inheritance system which are ambiguous and complicated hierarchies, this system encapsulates common data and behaviors in a generic way, called component. They are built up at runtime, that is, any entity can change by adding or removing components while the game is running. Actors can contain multiple components with different responsibilities but it can only have one class of a particular responsibility. Each actor component can derive the responsibilities to many subclasses, for instance, an AIComponent can be an interface for different kinds of behavior that we can change at runtime. In this model, actors don't have game methods embedded but instead they are containers of components. In the engine we have defined the most common components that are used by game actors. The TransformComponent represents the actor’s position, orientation and scale through a transformation matrix. The RenderComponent represents the graphical description of the actor which could be primitive shapes, complex meshes, skies, particle effects or lights. The PhysicsComponent represents any physical property of the actor which is created and simulated by the physics system. The AudioComponent allow actors to trigger sound effects. Whenever a system needs access to a component, it asks the actor for that interface and gets a pointer to the requested interface object.

eastl::shared_ptr<Actor> pGameActor(
GameLogic::Get()->GetActor(actorId).lock());

eastl::shared_ptr<TransformComponent> pTransformComponent(
pGameActor>GetComponent<TransformComponent>(TransformComponent::Name).lock())

The game actor is an object that represents a single entity in the game world with the only purpose of managing and maintaining components. The actor and its component are defined in an XML data file (see directory Assets/Actors) as it shows the following code.

<Actor type="Player" resource="actors\player.xml">
	<TransformComponent>
		<Position x="0" y="0" z="30"/>
		<YawPitchRoll x="0" y="0" z="0"/>
	</TransformComponent>
	<PhysicsComponent>
		<Shape>Controller</Shape>
		<Density>glass</Density>
		<PhysicsMaterial>Normal</PhysicsMaterial>
		<RigidBodyTransform>
			<Position x="0" y="0" z="30"/>
			<YawPitchRoll x="0" y="0" z="0"/>
			<Scale x="24" y="24" z="60" />   
		</RigidBodyTransform>
	</PhysicsComponent>
	<MeshRenderComponent>
		<Mesh>art\dwarf.x</Mesh>
	</MeshRenderComponent>
</Actor>

This XML file defines an actor with three components, a TransformComponent, a PhysicsComponent and a MeshRenderComponent. It is a template for a type of actor and we can create many instances of this actor with completely different sets of data within their components. The XML file is a data-driven template which has the advantage that we can modify the actor’s behavior by adding or removing components without changing a single line of code.

All actors are created using the ActorFactory class which are responsible for reading XML resources, parse them, and finally create them as instances. It returns a new actor instance along with their components initialized to their default values.

eastl::shared_ptr<Actor> GameLogic::CreateActor(
const eastl::string &actorResource, tinyxml2::XMLElement *overrides, 
const Transform *initialTransform, const ActorId serversActorId)
{
   eastl::shared_ptr<Actor> pActor = mActorFactory->CreateActor(
   ToWideString(actorResource.c_str()).c_str(), overrides, 
   initialTransform, serversActorId);
}

Events. We have seen that in an event-driven architecture, the events are changes in state that triggers the emission of notification. They will be processed by the Event Manager and later delivered only to listeners subscribed to the event. The events defined in the header file Core/Event/Event.h are sent out by the game logic and received by delegated functions. This delegated functions dictates how to respond to the subscribed events such as, create a new actor when an actor is requested, destroy actor when an actor is deleted, synchronize actor data in order to update actor’s transformation properties, load the environment when a new game is started, and send start game event to all views so they can load a game level.

// To define a new event - you need a 32-bit UID. 
// In Visual Studio, go to Tools->Create UID and grab the first bit.
const BaseEventType EventDataEnvironmentLoaded::skEventType(0xa3814acd);
const BaseEventType EventDataNewActor::skEventType(0xe86c7c31);
const BaseEventType EventDataSyncActor::skEventType(0xf1975ad);
const BaseEventType EventDataDestroyActor::skEventType(0x77dd2b3a);
const BaseEventType EventDataRequestStartGame::skEventType(0x11f2b19d);

Physics. Game physics involves the introduction of the laws of physics into a game engine for the purpose of making the game appear more realistic to the observer. Typically, game physics simulation is only a close approximation to actual physics and computation is performed using discrete values at optimal update rate for gameplay. As the processor speed is more important than the simulation accuracy, physics engines are designed to produce results in real-time at expenses of a real-world physics approximation. The simulation progresses at a timestep, that is the time interval between updates or delta time, which can be either fixed or variable. A variable timestep means that the game state is updated once per tick and the time interval is calculated from the previous update. A fixed timestep updates the game state a variable number of times per tick at the same time interval. The engine works with a variable delta time and physics simulation results may vary depending on the timestep rate, i.e. slow computers will experience undesired physics behavior.

Game physics implement collision detection systems for determining the intersection of two or more objects, which in a discrete system are often solved using very simple rules. However, such system ignores what happens between the previous and current steps, as some collisions might not be detected. In this case we use an expensive technique that attempt to find when two bodies collide between simulation steps, that is a continuous collision detection system. In order to optimize the collision detection process, we generally split it in two phases: broad phase and narrow phase. The broad phase limits the number of pairs that need to be checked for collision by sorting the bounding volume of each body. Bounding volumes are simple geometrical approximation that encapsulates an object for fast intersection calculations. This may be a bounding box, sphere, or convex hull. When the bounding volumes of two bodies overlaps, they are sent to the narrow phase to test their specific shapes, usually concave or convex, by a more precise and time-consuming algorithm. The convex meshes are used to improve the physics performance as they have properties that allow doing maths efficiently in physics system. The convex geometry must be completely closed and have no holes in it. During this phase, if any intersection is detected between collision meshes, the collision system calculates the time of impact (TOI), computes the contact points and reports the set of intersecting points (contact manifold) that will be used to solve the collisions.

Aside of reporting collision events, any collision system should be able to handle ghost triggers, support collision groups, and perform raycasting and shapecasting. In ray casting, it is traced an invisible line between two points in the game world, and the process will return collision information from objects that have been hit along the way. If we want more accurate collision information, we use shape casting which performs a more expensive calculations to check collision from a straight line using a geometrical shape. A ghost trigger is a volume with no collision response that any game can use to detect which dynamic objects entry and exit the area. A collision group allows to classify objects that can collide or not with each other’s. It also optimizes the simulation as we are grouping objects which can potentially collide against each other, and therefore reducing the geometry checking overhead.

Game physics use the Newtonian physics model to simulate the motion of physical objects within the environment. The foundation of dynamics is concerned with the study of forces and their effects on motion, that is, how the forces acting on the bodies affect the linear and rotational properties of the physical bodies in the simulation, and how it responds to collisions with other physical bodies. Any game physics engine use the dynamics of a rigid body system which is described by the laws of kinematics, specifically the application of Newton's second law (kinetics). The solution of these equations of motion provides a description of the position, the velocity and the acceleration of the individual components of the system and overall the system itself, as a function of time. The assumption that the bodies are rigid, which means that they do not deform under the action of applied forces, improves the simulation performance as it simplifies the analysis of the dynamics of solids.

Physical materials are used to define the response of a physical object when interacting dynamically with the world. After collision, the reaction depends on both properties; friction or resistance of the object that produce movement, and bounciness of the object. They are respectively known as restitution and friction coefficients which are usually expressed in a positive floating-point number. Restitution describes how bouncy is an object, static friction is used when an object is at rest on a surface, and dynamic friction is used when an object is in relative motion. The engine physics systems let us specify these coefficients on a material-by-material basis, which isn’t exactly the most accurate approach. The values can be found in the following file /Assets/Config/physics.xml:

<PhysicsMaterials>
    <PlayDough restitution="0.05" friction="0.9"/>
    <Normal restitution="0.25" friction="0.5"/>
    <Custome restitution="0.95" friction="0.7"/>
    <Bouncy restitution = "0.95" friction = "0.5"/>
    <Slippery restitution = "0.25" friction = "0.0"/>
</PhysicsMaterials>

We also define the density table, a measure of an object’s mass per unit of volume usually called specific gravity. They can easily be saved in an XML file, allowing the game objects to be described with something other than a number:

<DensityTable>
    <!-- custome -->
    <soft>0.004</soft>
    <heavy>50.000</heavy>
    <!--  specific gravity (these numbers are easier to find) -->
    <air>0.0013</air>
    <water>1.000</water>
</DensityTable>

Collision shapes determines the collision geometry of the object. The primitive shapes are best in terms of memory and performance but do not necessarily reflect the actual shape of the object as they are calculated based on the object’s bounding box. The most common primitive shapes are box, sphere and capsule. A more complex geometry is the mesh-based shapes which are accurate representation of the object but computationally expensive. The engine provides an abstraction class that any 3rd Party Physics SDK can implement. Currently we have implemented the physics interface making use of Bullet Physics external library which has been successfully tested for the demo application as well as the showcase game.

class BulletPhysics : public BaseGamePhysic
{
    friend class BspToBulletConverter;

    btDiscreteDynamicsWorld*		mDynamicsWorld;
    btBroadphaseInterface*		mBroadphase;
    btCollisionDispatcher*		mDispatcher;
    btConstraintSolver*			mSolver;
    btDefaultCollisionConfiguration*	mCollisionConfiguration;
    BulletDebugDrawer*			mDebugDrawer;

The most important component managed by Bullet is the btDynamicsWorld object. This object encapsulates the physics world and performs its simulation in discrete time stepping. It provides the main interface point to Bullet’s internal physics system that offers methods for setting the strength of the world gravity, manages motion constraints, objects and forces during the simulation and handle other components. One of those components is btBroadphaseInterface which Bullet creates for detecting collisions between pairs of bounding boxes in a scene. This phase is fast but inaccurate, using simple axis-aligned bounding boxes as placeholders for actual collision geometry. Once a possible collision has passed this test, it is sent to the narrow phase and dealt by the btCollisionDispatcher. The collision dispatcher handles very accurate collision detection of objects which have been passed by the broad phase. It finds the appropriate algorithm from a repository of intersection algorithms which are used for testing pairs of convex and concave shapes. Once the collisions are detected, this class is used for dispatching the collision pairs so they can be handled by other systems. The btDefaultCollisionConfiguration is a helper used internally for managing the allocation of memory for collision objects and for collision detection algorithms. The creation of the constraint solver btConstraintSolver relates to rigid body dynamics and is used for ensuring that all bodies in a scene are affected accurately by the scene’s pervading motions, collisions, and forces. It is also in part responsible for ensuring that objects behave appropriately, acting and responding according to physical laws.

void BulletPhysics::RenderDiagnostics()
{
    mDynamicsWorld->debugDrawWorld();
    mDebugDrawer->Render();
    mDebugDrawer->Clear();
}

The last object created is BulletDebugDrawer, which actually handles debugging tasks for the game engine. BulletDebugDrawer inherits from Bullets DebugDraw class and implements the drawing routines using the renderer system. The easiest way for debugging physics is to draw physics data as visible geometry which is carried out by the RenderDiagnostics() in the main loop. Before rendering diagnostics, it is important to setup some BulletDebugDrawer options in order to make visible rendering collision shapes, contact points, and contact normals. Collision hulls show up as wireframes around the objects, contact points and normals are drawn as lines, and forces are drawn as lines of different lengths in the direction of the force. There is also a reporting log system to inform any physics error through messages.

The physics subsystem initialization does the following tasks; Initializes the btDynamicsWorld and components’ members. Creates the internal tick callback, which is used to send collision events. Loads the physics materials and density tables using data driven XML file. These data structures are accompanied by some helper functions, LookupSpecificGravity and LookupMaterialData, which return data for matching a name with the density, restitution or friction value, respectively. It set up Bullet initialization parameters, read rendering options for customizing the BulletDegubDrawer class, and set the internal callback which is called once every internal time step for dispatching collision events.

The shutting down process consists on cleaning up all of the btRigidBody objects that have been allocated and added to the physics system, and delete the physics system components.

void GameLogic::OnUpdate(float time, float elapsedTime)
{
   if(mPhysics && !mIsProxy)
   {
       mPhysics->OnUpdate(elapsedTime / 1000.f);
       mPhysics->SyncVisibleScene();
   }
}

The physics stepSimulation method updates the simulation over 'timeStep', in seconds, which we pass through the GameLogic OnUpdate function. By default, Bullet uses an internal fixed timestep of 60 Hertz and if the time frequency is larger, it will subdivide the timestep in constant substeps. This is very important because it maintains the system stability by ticking the real-time simulation multiple times up to a maximum number of substeps. The trade-off is that this operation is very expensive and we can always disable it as long as we can keep the game timestep stable. After starting the simulation, Bullet automatically calls an “internal callback” once every internal time step. This callback is specified in the initialization function as BulletInternalTickCallback and dispatches collision events. First it collects all of the collision pairs from the physics system. A collision pair is any two objects whose physics shapes overlap in the physics world. The algorithm finds all the pairs of objects that are touching each other in the current tick. Next, it compares the collision pairs with the previous tick’s collision pairs. If there are any new ones, then an event is sent indicating that the two objects came into contact with one another. If there are any pairs that existed in the previous tick but no longer exist, an event is sent to tell the game system that the objects separated from each other. The final step that this internal tick callback does is to store a list of collision pairs which will be use to compare collision pairs during the next tick.

The other method called in the GameLogic Onpudate function is the SyncVisibleScene which is responsible for iterating through all the physics objects, check for any object motion state changes and send the appropriate event for the game system to update the graphics object transform matrices with new location and orientation. In Bullet, each physics actor has a btMotionState that is used to communicate position and orientation changes back to the game engine. The class ActorMotionState converts the Bullet’s transform matrices to the engine internal transform matrices. When the physics system detects differences between the actor’s motion state and the actor TransformComponent, it sends a data synchronization event to any game system that cares about the object transform. Bullet physics uses a physics system-specific vector class, btvec, and a transform matrix, btTransform. It is quite normal for a physics system to have its own data structures or classes for common fundamental mathematics: vectors, matrices, and so on. Notice that while the position and orientation of a physics object are related to the visual position and orientation, they aren’t necessarily the same. The position of an object in the physical world is always the center of mass, and that might not be the center point of the visible geometry. Therefore, the delegated function responsible for overwriting the actor’s transform will apply the transformation to get the correct position and orientation of the visible geometry from the orientation and position of the physics object.

void Scene::SyncActorDelegate(BaseEventDataPtr pEventData)
{
    Vector4<float> actorPosOffset = HLift(pPhysicComponent->GetPositionOffset(), 0.f);
    Vector3<float> actorTranslation = pNode->GetRelativeTransform().GetTranslation();
    Matrix4x4<float> actorRotation = pNode->GetRelativeTransform().GetRotation();
#if defined(GE_USE_MAT_VEC)
    actorTranslation -= HProject(actorRotation * actorPosOffset);
#else
    actorTranslation -= HProject(actorPosOffset * actorRotation);
#endif
    pNode->GetRelativeTransform().SetTranslation(actorTranslation);
}

Bullet represents all dynamic and fixed physical bodies with the btRigidBody class. The Bullet Physics library draws a distinction between a rigid body and a collision shape; the former refers to the actual object in the scene with its own position, scale, and orientation, and the latter refers to the bounding volume associated with that object. This volume will be used by Bullet when testing for collisions. A separation is made between a collision shape and a rigid body since all rigid bodies in the scene will have a unique position, scale, and orientation, but many of those bodies will share the same collision shape, being sufficiently similar in form and size. A collision shape is encapsulated in the btCollisionShape class which can be of different primitive types such as, btSphereShape, btCapsuleShape btBoxShape, etc... It is preferable to represent static environment with btConvexHullShape as its properties are optimal for collision detection. Otherwise the btBvhTriangleMeshShape is used for concave geometry on the level. The collision shape, its motion state and other properties which we show in the following code create a unique rigid body in the scene.

void BulletPhysics::AddShape(eastl::shared_ptr<Actor> pGameActor, btCollisionShape* shape, 
float mass, const eastl::string& physicMaterial)
{
   Transform transform;
   eastl::shared_ptr<TransformComponent> pTransformComponent = 
      pGameActor>GetComponent<TransformComponent>(TransformComponent::Name).lock();
   LogAssert(pTransformComponent, "no transform");
   if (pTransformComponent)transform = pTransformComponent->GetTransform();
   else return;

   ActorMotionState * const motionState = new ActorMotionState(transform);
   btRigidBody::btRigidBodyConstructionInfo rbInfo( 
   mass, motionState, shape, localInertia );
   rbInfo.m_restitution = material.mRestitution;
   rbInfo.m_friction    = material.mFriction;
   btRigidBody* const body = new btRigidBody(rbInfo);
   mDynamicsWorld->addRigidBody( body );
}

The ActorMotionState is initialized with the actor’s TransformComponent and encapsulates the world transform matrix for each unique and moveable rigid body in the scene. Bullet will internally update and apply transforms to this matrix on each step of the simulation. It can be accessed and modified using two interface methods: getWorldTransform and setWorldTransform.

Artificial Intelligence. AI is the creation of computer programs that emulate acting and thinking rationally like a human. This definition encompasses both the cognitive and the behavioral views of intelligence, but it differs when applied to videogames. Game AI is the code that makes computer-controlled opponents appear to make smart decisions when the game has multiple choices for a given situation, resulting in behaviors that are relevant, effective, and useful. The game AI interest is aimed to create the illusion of intelligence regardless of the methods which are used to produce it.

Modern computer games combine technology from graphics, physics and AI to produce realistic gameplay. Realistic gameplay is difficult to define, but it roughly translates to a sense of immersion in the game world and a sense of intelligence behind the Non-Player Characters (NPCs). In realistic play, objects behave and look much as they do in the real world, and NPCs act rationally. The goal of game AI is not to create unbeatable opponents, but to create intelligent NPC for a more immersive and interesting gameplay.

Every game is unique, and every game requires a unique AI that’s highly customized to fit their particular mechanics. However, there are many common features shared between different games that allow us to identify and describe the major AI components that nearly any game will feature. In this context, agent-based AI is about producing autonomous characters that take in information from the game data, determine what actions to make based on the information, and carry out those actions. It can be seen as bottom-up design; the first two elements of the AI model, movement and decision making, make up the AI for an agent in the game. The implemented AI is needed to support how each character will behave and the overall behavior of the game is simply a function of how the individual character behaviors work together.

• Movement refers to algorithms that turn decisions into some kind of motion. Movement algorithms can be very complex, a character may use navigation system in order to avoid obstacles on the way or even work their way through corridors. There are numerous ways to represent the relevant information of a level for an agent. The knowledge representation technique and the amount of information about the level directly affect the efficiency and quality of paths that an agent can find. Accurate representation of the search space comes to a price of memory space and CPU cycles.

  Waypoint graphs, and navigation meshes are abstract data structure used to aid agents in pathfinding through complicated spaces, each of which has its own advantages and disadvantages. The genre of a game, the type of levels, the number of agents, and many other constraints can make one scheme more appropriate than the others. A waypoint graph specifies the lines in the level that are safe for traversing. A waypoint node is a point along a path which is connected with other nodes through links. A link connects exactly two nodes together, indicating that an agent can move safely between the two nodes by following along the link. A navigation mesh is a collection of two-dimensional convex polygons (a polygon mesh) that define which areas of an environment are traversable by agents. The advantage of a convex polygon is that any two points inside it can be connected without crossing an edge of the polygon. This means that if an agent is inside a convex polygon, it can safely move to any other point inside the polygon without leaving the polygon. An edge of the polygon is either shared with another polygon, indicating that the two nodes are linked, or not shared with any other polygon, indicating that the edge should not be crossed.

  Now that we have seen different ways of representing a level, we will focus on the pathfinding algorithm that an agent can use for travelling. Within graph theory, pathfinding is closely related to the shortest path problem, which examines how to identify the route that best meets some criteria (shortest, cheapest, fastest) between two points in a large network. A path is a list of cells, points, or nodes that an agent has to traverse to get from a start position to a goal position. In most situations, a large number of different paths can be taken to reach the goal. One of the important criteria of a pathfinding algorithm is the quality of the path it finds. Algorithms that guarantee to find a path are referred to as complete algorithms, and algorithms that guarantee to always find the most optimal path are known as optimal algorithms. Pathfinding is a problem that has to be dealt with in about every game and is not a trivial task because the resources that a pathfinding system consumes can quickly get out of hand. One of the most important characteristics of the pathfinding system is that they consider a wide variety of paths. In fact, they keep track of numerous paths simultaneously, and if they have to, they will consider every possible part of the map to find a path to the goal. To do so, they use two lists known as the open list and the closed list. The open list keeps track of paths that still need to be processed. When a path is processed, it is taken off the open list and checked to see whether it has reached the goal. If it has not, it is used to create additional paths, and then placed on the closed list. The closed nodes (or paths) are those that do not correspond to the goal node and have been processed already.

  Breadth-First, Best-First, Dijkstra, and A* (AStar) are among the most common algorithms to choose for pathfinding. The main difference between them is how they handle the open list to process every iteration of the loop. Breadth-First always processes the node that has been waiting the longest, Best-First always processes the one that is closest to the goal, Dijkstra processes the one that is the cheapest to reach from the start node, and A* chooses the node that is cheap and close to the goal. Many game engines implement an A* (AStar) algorithm which in videogames is by far the most popular. A* pathfinding is a general-purpose search algorithm for finding the cheapest path through an environment. Specifically, it is a directed search algorithm that exploits knowledge about the destination to guide the search intelligently. By doing so, the processing required to find a solution is minimized. Compared to other search algorithms, A* is the fastest at finding the absolute cheapest path. It tends to use significantly less memory and CPU cycles than Breadth-First and Dijkstra. In addition, it can guarantee to find an optimal solution as long as it uses an admissible heuristic function. A* combines Best-First and Dijkstra by taking into account both the given cost (the actual cost paid to reach a node from the start) and the heuristic cost (the estimated cost to reach the goal). To guarantee that A* finds the optimal solution, the heuristic function used to compute the heuristic cost should never overestimate the actual cost of reaching the goal. In the engine, we have implemented the Dijkstra algorithm which means that the calculation is only based on the cost from the current path.

• Decision-making involves an agent working out what to do next. In most games, the purpose of AI is to create an intelligent agent, sometimes referred to as a nonplayer character (NPC). This agent acts as an opponent, an ally, or as a neutral entity in the game world. An agent has three key steps which are continually updated, commonly known as the sense-think-act cycle.

  1. Sensing. The game agent must have information about the current state of the world to make good decisions and to create action upon those decisions. Since the game world is represented entirely inside the program, perfect information about the state of the world is always available. This means that there is no uncertainty about the world, only accurate information of every entity state and location. It is important to use wisely that information and take only what is necessary to update the NPCs thinking process, that is, its self-awareness of the virtual environment to predict any potential opportunity or risk depending on their current believes. Abusing of this knowledge or using knowledge that the agent is not supposed to know will create disbelief on the NPCs intelligent behavior.
  2. Thinking. Once an agent has gathered information about the world through its senses, it evaluates the information and makes a decision. The AI Manager implements the stimulus interpreter which is the way the agent perceives the world by receiving and processing events, such as physics collisions events. This information will guide the decision-making system to update every agent believes and to determine the next course of actions. Generally, there are two main ways in which an agent makes a decision in games. One is for the agent to rely on predefined expert knowledge, typically handcrafted through if-then rules, with randomness introduced to make agents less predictable. The other is for the agent to use a search algorithm to find a near-optimal solution.
  3. Acting. The game agent’s sensing and thinking steps are invisible processes to the player. Only in the acting step is the player able to witness the agent’s intelligence. In order to show the hidden work several game subsystems are involved such graphics, animations, physics, audio, etc... They are used to reveal the sensing-thinking steps and to expose behaviors which enhances the game and the player’s perception of the agent. The adeptness and subtlety with which the agent carries out the actions will impact the player’s opinion of the agent’s intelligence.