December 13, 2013

A Layered Game Architecture III - Scenes and Directors

Scenes and Directors

Apart from actor AI, states and physics as describe in the first backend post, there is much more to be controlled in a game like:
  • handling collision events
  • watching actor's life power
  • collecting visible actors for each player
  • using gadgets like invisibility, super speed, damage doubling, etc.
  • walking upon special tiles for powering-up
  • opening and closing doors
All this is controlled by various directors. A director is the controller counterpart in a MVC architecture. Its models are actors and scenes.




Scene directors control game scenes. A scene is the model of one part of a running game. Games can have one or multiple scenes.
Examples for scenes are:
  • a shop to buy new weapons 
  • the battlefield where the action takes place
  • a screen to switch levels 
  • a built in mini game
  • an underground dungeon as opposed to the day light world
Now, just like in the real world, directors like to delegate work. Here, there are various sub directors, each specialized for one kind of task. For all the listed tasks at the beginning of this post, there is one sub director.
There are two given abstract implementations of sub directors:
  1. Directors that operate on a (dynamic) list of actors of one defined type, like for example:

    BlackHoleDirector - for droids and bullets
    Loops through its actors and drags them into nearby black holes if applicable.

    ActorLifeDirector - for droids
    Removes droids with a power of zero.

    PhysicsDirector - for droids, bullets and level gadgets
    Listens for added and removed scene actors and notifies the physics module about it. Creates appropriate events for actor collisions.
     
  2. Directors for tasks that are not bound to given actor lists, like for example:

    BulletDroidCollisionDirector
    Does not work on a list of actors, but on incoming collision events between droids and bullets detected by the physics director.

    InvisibilityGadgetDirector
    Does not work on a list of actors either, but on incoming player requests to become invisible. Activates and publishes according looks and disables invisibiltiy after a given time span.

    VisibilityDispatchDirector
    Does not work on a list of actors but on the list of current players. Each player gets a personal list of currently visible actors.
If neither AbstractSubDirector or AbstractActorsSubDirector suits a given task, ISubDirector can be implemented and plugged in as well.

Some important characteristics of sub directors:
  • They allow to modularize game control into smaller maintainable tasks.
  • They are invoked one after another from the game loop.
  • They can be invoked for each game frame or after a defined time span, like every 100ms.
  • They realize a plugin concept for the whole game direction sub system.
  • They can be enabled and disabled at runtime.




December 11, 2013

A Layered Game Architecture II - Backend AI

The first part of A Layered Game Architecture gave an overview of frontend, backend and shared packages. Here, we continue with a look upon the backend components for actors and AI:
  



actor

Each interactable game object is represented as IActor. Actors are controlled, influenced, directed, moved, created and removed by states, goals, game physics and directors.
Actors are the central object in each game. To avoid dependencies to concrete behavioural implementations, each actor has only a IActorBehaviour reference and does not whether it is controlled by states, goals or in any other way. This allows to plug in, for example, your new sophisticated almighty AI controller instead of using goals, or to switch from Box2D physics to any home brewn physics algorithms without affecting other framework and game parts.

state

States offer separate representations of, for example, moving and waiting actors. Furthermore, game events of all kinds like input and collisions events can be sent and received. Typical events are BulletHit, BulletMissed, DesiredHeading.
States could also be used to implement a (primitive) AI. Then, actors would not get a GoalBrainAndStateBehaviour but a simpler StateBehaviour.

physics

The game physics makes sure that actors move and behave according to the physics rules of the game world. It takes care of collisions between multiple actors as well as between actors and the environment. Collision listeners get notified to initiate appropriate reactions. Velocity and acceleration is calculated from given player input and AI events.
Source and target for game physics is IMovable where data for positions, forces, velocities and acceleration is stored. Because a multiplayer client/server game architecture requires to move actors on server as well on client side, movables are parts of the shared base class ICharacter which resides on both client and server side.
The game physics takes desired actor movements as input and applies them to the game world model. Whether movement commands origin from player input or from AI thoughts is of no interest and simply unknown.

goals

Actors can try to achieve goals like finding level items, following and shooting the player or fleeing and hiding. A typical output of a goal is a new heading direction which is handed over to the physics components. Actor velocities or positions are not directly manipulated from goals to let the physics module handle and watch the complete game physics of all objects together once per frame.
Like states, goals can also send and receive game events of any kind.

Goals are a part of an actor's brain which is supported by its memory where recent observations, events and all kind of AI important information is stored and used for subsequent decision finding. Naturally, a brain has an assigned actor, but, to get back to the previously introduced behaviours, actors don't contain references to their brain.

The goal sub system was inspired by the great book Programming Game AI By Example from Mat Buckland.

August 12, 2013

A Layered Game Architecture I - Overview

This post shows an example for a layered game architecture as being developed for the game Biodrone Battle (abbreviated as BDB).
The most important requirements are 
  • being capable for single and multi player games running the same code base and only switching the used net implementation
  • platform independence, for targeting desktops and mobile devices with a common code foundation
  • abstraction and hiding of low level details from, for example, OpenGL and TCP
  • strong focus on dependency management, complete avoidance of cyclic dependencies, broken up into ~16 dedicated projects and accordingly built JARs
  • separation of 3rd party libraries usage into dedicated sub packages and projects
  • emphasis on interfaces for hiding implementation details and providing various implementations 
  • event driven communication overall
The following big picture shows three main components:



1. Libgdx as abstraction for the target platforms Windows, Linux, OSX and Android, as well as for OpenGL graphics, sound and game physics.
2. GameRoots as framework for game logic, ai, network, sprites, tile maps, actor and input handling, sound, etc. However, there is nothing related to any concrete game in there, thus no dependency is pointing up to the BDB component.
3. The game itself with its screens, implemented game rules, lobby and anything else uniquely required.

GameRoots

At the top level, GameRoots is separated into three packages:
  • frontend, the client, responsible for graphics, sound, input and client side movement. Always running on the player's machine
  • backend, the server, holding game logic and AI, controlling all player clients, receiving player input, sending world updates back. Either running on a dedicated game server, or for single player games on the player's computer. In case of the latter, without networking involved.
  • shared, anything needed from both frontend and backend. For example, sent and received events, actor movement, utilities like collections classes and math functions.
Naturally, there is no dependeny between frontend and backend. They must be physically separatable and a game server should be runnable on a headless machine.
Consequently, shared does not know frontend or backend but is used by both packages.


backend

scene
A scene is the place where all game actors live in. All dynamic game objects are actors, regardless whether they are living creatures or dead level items of any sort. Actors of the backend are a relatively abstract view of the game world, with little or no knowledge about graphical representations for example.
Scenes and actors form the model and representation of the game world with the highest number of incoming dependencies.

ai
The place where actors come to life. Actor have a brain which is driven by various goals. An actor brain is always in one state and takes decisions with the help of recorded memories of visited opponents, taken hits, known paths, etc. Typical states are for example MovingState and WaitingState, typical goals ShootGoal, DodgeGoal, WaitGoal, FindPathGoal.
The AI operates on scenes and actors. After taking decisions new events are sent to other actors, to directors and player clients. Events are received from players, directors and the game AI itself.

director
Similiar role like movie directors, only that there is not one but are many specialist directors at the same time. There are specialists for collision detection, building a field-of-view, using inventory and level items, watching health points, applying physics, etc.
Receives player input events and forwards them to addressed actors and responsible directors. Vice versa, directors send events to the AI, other directors and player clients.

navigation
For actors finding paths from point a to point b.

net
Event driven communication with all clients. Uses the "real" network for multiplayer games or an in-memory model for single player games. Does not know about scenes. Only receives events created by directors or AI classes.

management
The game rules and factories for creating new actors at runtime based on predefined build plans.

server
The game server for bringing together network services, connected clients and directors.

frontend

scene
The game world on the client side and the model of the applied MVC pattern. Inhabited by puppets, the client side representation of game actors. Puppets are controlled by server events and, for a responsive game feeling, immediately by player input.

controller
The controller of the applied MVC pattern. Moves puppets according to server events, player input and game physics.Works on received server events and sends player input back to the server.

view
The view of the applied MVC pattern. Home of view puppets, the visual representation of scene puppets. Each scene puppet can be shown in different and multiple ways, in 2d, 3d, as map point, etc.

input
Listens for player input and forwards it to controller classes.

net
For communicating with the game server. Sending and receiving events as well as downloading game resources. Concrete implementations allow to communicate directly by event queues inside a VM for single player games or by TCP for multiplayer games.

sound
Anything for the sonic game experience independent of any particular audio player implementation. Namely, loading and organizing of sound resources, setting volume and pan positions dependent on player positions.

gdx
This is the interface to the Libgdx game library. Usage of textures, lights, particles, playing of sound, etc. is encapsulated here and only here so that the main part of the frontend packages is independent of 3rd party libraries and would allow to switch to other libraries like Java2d for example.

shared

Everything that is required and useful for both client and server.
For example, actor movement and game physics are applied in the same way on both client and server side.
Naturally, events exchanged between client and server are located here as well.

May 1, 2013

A tabbed list or table for LibGdx

The TabbedList was derived from the original List widget of LibGdx.
It allows to split the list items into sub items which are positioned in individual virtual columns. Rows can be deleted and added by just modifiying the underlying data of the widget without creating or removing the widget itself or any of its child components.
Additionally, TabbedList is synchronized for a thread safe modification of the list items.



An example using the tab character as delimiter:

String[] items = {"12:00\tgame1\trunning", "13:00\tgame-2\tfinished"};
TabbedList list = new TabbedList(items, mySkin);
list.setColumnGap(20f);
list.setHeader("Time\tName\tState");


The items and the header are displayed like this:

Time  Name   State
12:00 game1  running
13:00 game-2 finished


Download at GitHub.

April 30, 2013

A virtual joystick for Android and LibGDX

Developing games for mobile platforms always involves the problem of finding a solution for the overall game control. For game programming with LibGdx, I created a virtual joystick modeled after classic hardware devices with the following features:
  • the knob can either be snapped to fixed directions (typically 4 or 8) or is freely movable
  • separate renderer classes ease the design of an individual visual appearance
  • around the center is the unresponsive dead zone
  • an adjustable tolerance allows to ignore very small knob position changes

a virtual joystick drawn with the circle renderer


An usage example:

1.The setup:

// create a joystick at point(123, 456) with a radius of 128 pixels
VirtualJoystick joystick = new VirtualJoystick(Gdx.input, 123, 456, 128);
joystick.setYUp(800) // view height=800 pixels, bottom-left is point 0,0
joystick.setPositionCount(8); // 8 snappable positions
joystick.setDeadZone(32); // inner dead zone circle with a radius of 32 pixel

// paint joystick with simple circles
ShapeRenderer shapeRenderer = new ShapeRenderer();
...
joystickRenderer = new CircleJoystickRenderer(shapeRenderer);
joystickRenderer.setDrawSnappedKnob(true);
joystickRenderer.setBoundsColor(Color.BLUE);
joystickRenderer.setKnobColor(Color.RED);
joystick.setRenderer(joystickRenderer);

1.1 Keep the direction vector as member which will updated by the joystick:

Vector2 joystickDirection = new Vector2();


2. Now polling the joystick's current direction in the game loop:

// update for touch pointer 0 and retrieve the current knob direction as unit vector
joystick.update(0);
joystick.getDirection(joystickDirection);



3. And finally rendering the joystick:

joystick.paint();

By default, created joysticks use a y-down coordinate system which requires a camera to be set up with the shape renderer, for example like this:

int viewWidth = Gdx.graphics.getWidth();
int viewHeight = Gdx.graphics.getHeight();


cam = new OrthographicCamera();
cam.setToOrtho(true, viewWidth, viewHeight);
cam.position.set(viewWidth / 2, viewHeight / 2, 0);
cam.update(true);

shapeRenderer = new ShapeRenderer();
shapeRenderer.setProjectionMatrix(cam.combined);



Currently, VirtualJoystick is digital, but a modification for analog position values is not a big deal.
The virtual joystick is published under the Apache License and hosted at GitHub.

April 18, 2013

Design Patterns in Game Programming (III): Visitor

First, an attempt of a short summary of the visitor pattern:
Create an interface to let objects process items collections of other objects.

Typically, a visitor setup looks similiar to this:

public class VisitorHost {
   public visitItems(ItemVisitor visitor) {
      ...
   }
   ...
}

public interface ItemVisitor {
   void processItem(Object item);
}

public class ConcreteVisitor implements ItemVisitor {
   void processItem(Object item){
      ...
   }
}

An important characteristic is that the internal treatment of the items is completely hidden. No visitor knows whether items are stored in lists, sets or arrays. Furthermore, visitors can not modify the internal item collection.
Another common way to operate on item collections is the iterator. However, as the typically Java iterator is created for using only once and gets handed over to the garbage collector afterwards, and because it is often still good in game programming to avoid object creation, iterators are only the 2nd or 3rd best approach.

Some important characteristics are:
  • The internal storage of the items is not exposed. No visitor knows whether items are stored in lists, sets, arrays or any other use case specific optimized collection class.
  • Visitors only have read only access on the item collection because they can not modify it, thus read and write access on the item collection of the visitor host can be optimized
  • In a concurrent setup, as the item collection is encapsulated, it must be synchronized inside the visitor host as well. Thus, the usage for visitors is simplified and synchronization is not spread among the code base.
  • Algorithms and functionality related to the host's items can be exchanged dynamically at runtime by just sending other visitors the the host.
Examples useful for game programming:


SpriteVisitor

Sprite rendering is invoked from within sprite visitors. Storing sprites can be optimized for read access, nameley rendering, which typically happens far more often than creating new sprites or removing old ones. The fastest collection class can be chosen, exchanged and benchmarked for each concrete game. For examples, lists could be used if the z-order is important or faster bags if not.

Example 1:

public class SpriteCollection {
   public visitSprites(SpriteVisitor visitor) {
      for (int i=0; i < sprites.size(); i++) {         
         visitor.visitSprite(sprites.get(i));
      }
   }  
   
   private Bag sprites;
}

public interface SpriteVisitor {
   void visitSprite(Sprite sprite);
}

public class SpriteRenderer implements SpriteVisitor {
   void visitSprite(Sprite sprite){
      ...
   }
}

Example 2, synchronized:

public class SpriteCollection { 
   public visitSprites(SpriteVisitor visitor) {
      synchronized (visitLock) {
         for (int i=0; i < sprites.size(); i++) {         
            visitor.visitSprite(sprites.get(i));
         }
      }  
   }

   private Bag sprites;
   private final Object visitLock = new Object();
}

Example 3, visitor operate on a second copied collection to keep synchronization lock time short. For most calls of visitSprites()which would be rather slow for rendering, no lock needs to be aquired. One thread creates and removes sprites, one or more other thread(s) visit sprites.
However, to find the fastest implementation of a sprite collection, benchmarking is needed.

public class SpriteCollection {
   public void addSprite(Sprite sprite) {
      synchronized (visitLock) {
         sprites.add(sprite);
         needCopy = true;
      }
   }

   public void removeSprite(Sprite sprite) {
      synchronized (visitLock) {
         sprites.remove(sprite);
         needCopy = true;
      }
   } 

   public visitSprites(SpriteVisitor visitor) {
      if (needCopy) {
         synchronized (visitLock) {
            visitorSprites = sprites.copyFlat();
            needCopy = false;
         }
      }

      for (int i=0; i < visitorSprites .size(); i++) {         
         visitor.visitSprite(visitorSprites .get(i));
      }
   }  


   private volatile boolean needCopy;
   private Bag sprites;
   private Bag visitorSprites;
   private final Object visitLock = new Object();
}

LightVisitor

The main screen renderer holds a collection of scene lights. However, concrete implementations of actually rendering lights are extracted into separate light renderer classes which appear as visitors of the screen renderer. Thus, the main renderer need no dependency to light renderer classes.

ActorVisitor

The game scene holds a set of game actors. Several parties - and threads - are interested in operating on actors:
  • The AI controls the actor's behaviour
  • The physics sub system is responsible for realistic movements
  • The network dispatcher sends actor states into the world
  • The renderer draws actors

April 3, 2013

Dreaded Optimization

Did you ever wonder why your brilliant scrolling algorithm causes a high cpu load for no apparent reason ? Why the scrolling is choppy ?
Then the cause of it might be a setting of the graphics card driver called "threaded optimization" for NVidia cards.
Just turn it off and enjoy smooth scrolling with almost no CPU load and most important: remember it after reinstalling the graphics card driver...

On my notebook (NVS 4200M), there is obviously another issue with the latest driver 311.35. The thread "optimization" is turned off, but still, the CPU load is significantly higer than with 310.90. After getting back to the old driver the load dropped down.

Addendum: After upgrading to a GTX 660 there are performance issues as well with the latest driver:
320.18: cpu load 25-30%
314.22: cpu load 5%

April 2, 2013

Box2D via Libgdx in a top-down Action Scroller Game

Recently I wanted to let the sprites of Biodrone Battle bounce whenever they collide with each other or hit any kind of wall tile. As Libgdx is already used and comes with a native binding to the physics library Box2D, it was an easy decision to make use of Box2D instead of doing it all by myself and reinvent the wheel.



Game physics, movement, collision detection, bouncing

Initially, the tile based game scenes needs to be set up as Box2D world. There are basically three kinds of tile groups:
  • floor tiles, always passable 
  • wall tiles, never passable 
  • door tiles, passable when open 
For all wall and door tiles are corresponding Box2D bodies created and added to the world. Note that bodies are positioned based on their centers instead of corners.

World settings:

Setting Value Comments
world gravity 0 rather useful in a sidescroller
pixelPerMeter 64 pixel matches the tile size of 64x64


From inside the game loop, the following three steps are executed.

1. Calculating the steering force for each sprite:

Each sprite holds its desired heading as unit vector, a current velocity vector, the maximum velocity as single float field, its acceleration as well as the corresponding Box2D body. The required force to speed up, slow down or to keep the maximum velocity is calculated as follows for each sprite: 

// input from sprite
Vector2 desiredHeading = sprite.getDesiredHeading();
Vector2 velocity = sprite.getVelocity();

float maxVelocity = sprite.getMaxVelocity()
float acceleration = sprite.getAcceleration();

// force to reach and keep desired velocity
steeringForce.x = desiredHeading.getX();
steeringForce.y = desiredHeading.getY();
steeringForce.mul(
maxVelocity);
steeringForce.sub(velocity.getX(), velocity.getY());
steeringForce.mul(
acceleration );

steeringForce.div(pixelPerMeter);

// apply steering force
Body body = sprite.getBody();
if (body.isAwake() || !desiredHeading.isZero()) {
    steeringCenter.x = body.getWorldCenter().x;
    steeringCenter.y = body.getWorldCenter().y;
    body.applyForce(steeringForce, steeringCenter);

}

The steering force derives from the delta vector between maximum (= desired velocity) and current velocity, multiplied by an arbitrary acceleration factor.
steeringForce and steeringCenter are vectors created once and reused for all calculations.
Because the game operates with pixels while Box2d prefers meters, all values must be converted accordingly.

2. After applying all forces to all sprite bodies, the world gets updated once for each game frame:

World world = getWorld();
world.step(deltaInSeconds, velocityIterations, positionIterations);
world.clearForces();


3. Finally, the new body velocities and locations can be retrieved from Box2D and used for rendering the scene:

Vector2 worldVelocity = sprite.getBody().getLinearVelocity();
Vector2 pixelVelocity = new Vector2(worldVelocity.x / pixelPerMeter, worldVelocity.y / pixelPerMeter);


Vector2 worldPosition = body.getPosition();
Vector2 pixelPosition = new Vector2(worldPosition.x / pixelPerMeter, worldPosition.y / pixelPerMeter);


The overall acceleration behaviour depends upon body density and shape, acceleration, damping and friction.
The following settings were found to give a nice movement behaviour for the Bionic sprites:

Setting Value Comments
linear damping 0 the higher the damping the lower the reachable velocity
density 60 heavier sprites accelerate slower
friction 0.2 sliding between sprites and walls
restitution 0.7 lets sprites bounce with each other as well as with solid walls
acceleration 150 gives a nice acceleration effect
if too high, the velocity will start to jitter
shape CircleShape
radius: 32 pixel = 0.5 meter
bigger sprites accelerate slower

And the settings for fast moving bullets:

Setting Value Comments
linear damping 0 no damping for flying bullets
density 10 lighter in relation to Bionics
friction 0
restitution 0 bullets do not need to bounce on collisions
acceleration 50 appropriate to nearly instantly get on maximum velocity
shape CircleShape
radius: 10 pixel ~ 0.15 meter
smaller in relation to Bionics


Field of View

Another nice use case of Box2d is for detecting the field-of-view of game actors. This is often necessary for implementing the game AI.
With Box2d this can be done with raycasting. Basically, for each game actor a ray is casted to all other actors. If the ray hits obstacles like a wall the other actor is not visible.

All we need is to call
World#rayCast(RayCastCallback callback, Vector2 point1, Vector2 point2);

with an appropriate callback interface like this:

public class VisibilityCallback implements RayCastCallback {

    private Actor targetActor;

    private boolean visible;

    @Override
    public float reportRayFixture(Fixture fixture, Vector2 point, Vector2 normal, float fraction) {
        if (fixture.getBody().getUserData().equals(targetActor)) {
            return fraction;
        }

        if (fixture.getBody().getUserData() instanceof Wall) {       
                visible = false;
                return fraction;           
        }

        return -1;
    }



    public boolean isVisible() {
        return visible;
    }
}


Beforehand, all body fixtures are equipped with game actors respectively environment objects like walls.
After each ray casting the visibility state can simply be queried by invoking isVisible().

To reduce the number of ray casts, only ray cast
  • once between each pair of actors
  • to actors relevant for the game AI
  • to actors inside the general range of view

February 17, 2013

Android gaming performance

Recently I started to port Biodrone Battle to the Android platform. Thanks to Libgdx the view part is quiet easy to manage, but all in all it still takes some time. On a Nexus 7 I get the following frames per second after loosing the breaks (Thread.yield() is called for each frame):
 
Thread FPS Tasks
server ~ 3.500 game logic, goal based AI, collision detection, A* path finding,
sprite movement, finite state machines,
field-of-view calculating with shadow casting,
game state & scores
client ~ 32.000  input handling, server event processing, managing sounds

view 58-60 painting sprites, tiles, particles, lighting and shadows,
tile map scrolling

Game and framework were designed for the desktop first in an object oriented way without considering the slower Dalvik VM. Some more technical facts:
  • data encapsulation, private fields, a lot of polymorphism, interfaces, immutable vectors, no static methods, floats for game locations.
  • 8 game actors for this benchmark
  • 1280x736 as display mode
  • Nexus 7 quad core, 16GB, Android 4.2.2
  • Dalvik launched with large heap (results in 384MB)