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