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

No comments:

Post a Comment