A Glimpse into Tiny Dungeons Architecture

I haven’t written a game programming related article in a while, so here we go. We’ll look into some architectural aspects of tiny dungeons. I’ll not show the full blown code, but reduce things to a bare minimum. Also, while i myself like what i have so far, it by no means is the end all be all to game code design. Since this is a spare time project (1-2h/week), i take a lot of short cuts and try not to make everything as generic as possible. YMMV.

High Level Architecure

I’m a big fan of the model-view-controller (MVC) architecture. There are many variations of this architecture. The beauty of it is that you can combine it with other popular ways to lay out your game code, e.g. entity systems. My take on MVC is extremely simplistic and not a 100% pure. I try to be pragmatic instead of an architecture astronaut.

The model consists of a bunch of plain old Java objects (POJOs), that only contain data, and convenient getters and setters. The model has no idea how to render (view) itself or use its data to implement things like enemy behaviour. It just sits there for the other parts of the system to be consumed and modified. Common objects found in the model are monsters, tile/collision maps, decoration, the hero and so on.

The view is a bit more complicated. Based on the model, it must load any resources it needs to render the model. Additionally, it should preprocess those resources such that rendering the model is optimal in terms of batching and the number of render state changes. My views generally do not contain state. Instead, i provide methods that take a model of a level and spit out a sort of bundle or package that contains loaded resources and acceleration data structure specific to the model. Rendering the model then means to pass this bundle to the view. The bundle must somehow keep track of changes in the model that necessitate changes in acceleration structures.

The controller(s) are a bunch of classes that reference the model and know how to act on it. E.g. a monster controller might be responsible for moving around a monster in the world, let it seek and attack the hero and so on. Controllers are also responsible for implementing things like the camera following the hero, reacting to user input and so on. All of these things generally update the model but usually do not inform the view of any changes. Either the view can figure out that the model changed, or the model takes note that something changed, which the view can query for.

Model – A Simple Object Representation

Tiny Dungeons is a sort of action RPG, meaning that there will be many different types of things. These things can be grouped into 5 broad categories: heroes, monsters, items, decoration and chests. There may be hundreds of different monsters, items and decorations, but within one category, the attributes pretty much stay the same.

All things have at least 3 attributes in common:

  • A type, specifying something like the genome of a thing, be it it’s maximum velocity, graphical assets, strength, hitpoints and so on. Multiple instances of the same type of say a monster share these type attributes.
  • A position, given as 2D coordinates in the x/z plane (Tiny Dungeons is 2.5D)
  • An active flag

The corresponding class is called FloorObject. A Floor is a single level within a dungeon, that potentially leads to another floor deeper down the dungeon.

class FloorObject {
   private final T type;
   private final Vector2 position = new Vector2();
   private boolean active;

   public FloorObject(T type) {
      this.type = type;
   }
   // ... trivial setters/getters here, booh Java
}

The type of an object is expressed as a generic parameter, so i can later get the concrete type of an object, instead of having to mess around with tons of instanceof expressions (they are still there, just not as many :)).

Before diving into the subclasses of this (yes, i subclass…), let’s have a look at the Type class required by FloorObject:

class Type {
   private String name;
   private String graphics;

  // fugly setters/getters here
}

Just as FloorObject, Type is a base class for concrete type implementations. The name is an identifier that is unique across all object types. The graphics field is an arbitrary string that encodes what graphic resources are used. This is likely to get extended later on. For now it points at a file or directory that has a specific layout depending on the concrete type. E.g. for monsters and heros, the graphics string points at a PNG containing the animation frames for objects of this type. For decoration, the graphics field might point at a 3D model file and so on. It’s the responsibility of the view classes to interpret this field when constructing the graphical representation for this model object. The same mechanism is used for audio effects used by an object.

FloorObject is subclassed by AliveFloorObject. Alive objects do not just sit there, like decoration or items, but have behaviour. Here’s the corresponding class:

class AliveFloorObject {
   private State state;
   private float stateTime;
   private final Vector2 acceleration = new Vector2();
   private final Vector2 velocity = new Vector2();
   private final Vector2 direction = new Vector2();
   private Array path;
  
   // setters/getters/constructor
}

On top of the FloorObject attributes, i add a state (an extenable enum), the time the object’s been in this state in seconds, the current acceleration and velocity, a normalized direction vector (velocity can be zero, but we still need to know which direction the object is heading for rendering it) and an optional path.

The Floor instance simply holds all the objects in a dungeon floor. It might be used to query nearby entities, find paths and so on. We won’t discuss it further as it’s basically just a list of objects alongside the collision map of the floor (a simple 2 dimensional boolean array). The object parameter is the object to apply the behaviour to, the delta time is the amount of seconds elapsed since the last update.

These four base classes form the foundation for lightweight subclasses for each of the object groups mentioned before (heroes, monsters, decorations, items, chests) as well as specific behaviours. Let’s look through the subclasses of type first:

public class ChestType extends Type {
}
public class DecorationType extends Type {
}
public class FloorType extends Type {
}
public class ItemType extends Type {
}

These types are for non-living objects, like chests, decorations and so on. At the moment they do not contain additional fields ontop of the basic Type fields, this is about to change in the near future. E.g. ItemType is likely to be extended to describe the properties of an item such as it’s attack points and so on.

public class AliveType extends Type {
   private float speed;
   private String behaviour;
   private transient Behaviour behaviourImpl;
}
public class HeroType extends AliveType {
   private int attack;
   private int hitpoints;
}
public class MonsterType extends AliveType {
   private int attack;
   private int hitpoints;
}

An AliveType is base class for types of AliveFloorObjects. In addition to the Type attributes, we get the maximum speed and a String naming the Java class that implements the Behaviour for this type. This class is later loaded via reflection and instantiated and assigned to the in-memory representation of the Type. A Behaviour is like a state-less script that knows how to update the model of an object based on its environment. E.g. the behaviour of a monster would be to check if it can see the hero, seek a path towards the hero, and if it is in range, attack the hero. The Behaviour interface looks like this:

public interface Behaviour {
   public void update(Floor floor, AliveFloorObject object, float deltaTime);
}

For each of these concrete types exists one JSON file enumerating all the different instances of these types. Here’s an excerpt from the heroes.json file:

[
   {
      "name": "warrior",
      "graphics": "sprites/hero.png",
      "hitpoints": 10,
      "attack": 1,
      "speed": 3,
      "behaviour": "WarriorBehaviour"
   }
]

Similar files exist for each of the other types, e.g. monsters.json, decorations.json and so on. These files are loaded into a TypeStore, which can be queried for a Type instance by name and concrete Type:

MonsterType monsterType = typeStore.get("skeleton", Class monsterType);

Loading of these files is super easy with our nice Json class:

private  ObjectMap readFile(FileHandle file, Class arrayClass) {
   ObjectMap map = new ObjectMap();
   Json json = new Json();
   T[] entries = json.fromJson(arrayClass, file);
   for(T entry: entries) {
      map.put(entry.getName(), entry);
   }
   return map;
}
ObjectMap monsterTypes = readFile(Gdx.files.internal("types/monsters.json", MonsterType[].class);

Adding a new object type boils down to 1) creating a new Behaviour implementation, like WarriorBehaviour above and 2) adding an entry in the corresponding JSON file. Writting a UI app that lets me visually modify these files is trivial. An additional benefit of using these types is that i can change the behaviour of all monsters of a specific type by just overwritting the behaviourImpl field in the corresponding MonsterType at runtime. This lets me balance things more easily. Finally, i can serialize any changes i make to the Java Types back to the JSON files after a round of tweaking.

The last class in all of this is the Floor class. As said earlier, it’s basically just a list of objects. On top of that it also stores a 2D boolean array that encodes whether a tile in the world is a wall or a floor, which is later used by behaviours and controllers for path finding via A*.

Folks among you using entity or component systems might cringe at this simplicistic class hierarchy and non-modularity. However, full blown entitiy and component systems come at a cost in runtime performance as well as ease of debugging. For this project, i decided against using a component system simply because i can bang out things faster the way i do it now. I do not dispute that a proper entity system is a better solution, and my decision will most likely bite me in the ass later on :)

To construct a floor with a hero and a few monsters i can do the following:

TypeStore types = TypeStore.instance;
floor = new Floor(types.getFloorType("floor01"), 64, 64);
floor.setTiles(1, 1, 16, 16, true);
floor.setTiles(1, 8, 5, 1, false);
floor.setTiles(2, 3, 5, 1, false);
floor.setTiles(2, 6, 5, 1, false);
floor.setTiles(10, 5, 2, 2, false);

Hero hero = new Hero(types.getHeroType("warrior"));
hero.getPosition().set(4.5f, 4.5f);
floor.setHero(hero);

for(int i = 0; i < 25; i++) {
   monster = new Monster(types.getMonsterType("skeleton"));
   monster.getPosition().set(MathUtils.random() * 14 + 1, MathUtils.random() * 14 + 1);
   floor.getMonsters().add(monster);
}

Of course my placement of skeletons is not exactly correct, but you get the general idea.

These classes describe the entire state of a dungeon floor. I can save and load this with a nasty Persistence class that uses DataInputStreams and DataOutputStreams to write all of the class instances to a binary file. Types used by objects are stored at the beginning of the file in a sort of look-up table, type references in objects are replaced with ids into that lookup table. A persisted floor is thus a complete serialization of all the information needed to reconstruct it. I can also take a snapshot of a floor at any given point in time, since all the mutable state is in my model. Behaviour implementations use the fields inside the model to store state, controllers do not have any state at all, and the view is simply rebuild from the floor model on reload.

View - Of Packs and Renderers

Once a Floor is constructed, i build something called a FloorPack for it. The FloorPack contains:

  • A FloorMeshesPack, which holds Mesh instances for 16x16 tiles of the floor. These are quads the build the floor and wall tiles as well as any static 3D geometry for decorations. All the meshes are stored in a simple grid of bounding boxes so i can easily perform frustum culling
  • An DecalsPack that stores one DecalPack per FloorObject. A DecalPack contains a Decal (see DecalBatch), and a list of Animation instances for each state of the FloorObject. These Animation instances point at TextureRegions in an atlas, more on the atlas in a bit

Remember the graphics field in the Type class. When i hand a Floor to a FloorPack, it will go through all the Types referenced in the objects within the floor, pick out their graphics field and merge all the PNGs for decals into a single atlas via the PixmapPacker class on the fly. No messing with TexturePacker all the time, PixmapPacker is fast enough. This is easily possible, as all decals/sprites are only 16x16 pixels wide. You can fit a lot of animation frames into a 1024x1024 texture, in a very small amount of time, even on low-end Android devices :)

For decorations that use a 3D model and for the floor walls and floor tiles a different mechanism is used: i simply generate a mesh for the walls and floor tiles based on the 2D boolean array in the Floor. Each floor type's graphics field points at a PNG containing a set of 16x16 tiles for walls and floors which form another texture atlas. For 3D decorations i identify in which 16x16 batch of tiles they are located, and generated a single mesh for all decorations within that batch. Of course, a decoration can overlap 4 batches at once, in which case i just live with the geometry duplication instead of cutting up the model on the batch boundries. Textures of all decorations are merged into a single atlas again.

What i end up with is three texture atlases (decals, walls/floors, decorations), a list of decals for 2.5D objects like monsters, heroes etc, and a list of meshes per 16x16 batch on the floor. Each texture atlas is composed of a single 1024x1024 texture, thanks to the low resolution of all textures (16x16 pixels). This makes rendering extremely efficient.

With my FloorPack at my disposal i can simply hand it to a FloorRenderer which takes all the decals and meshes in the pack and renders them appropriately.

Three challenges remain:

  • how to deal with changing states of objects
  • how to deal with dynamically added objects that weren't in the floor when the pack was created, e.g. arrows, etc.
  • how to deal with changes to the walls/floors, e.g. within an editor

The first problem is easily solved: For an alive object, i simple check it's state and direction in its model and select the appropriate frame from the animation for that state, e.g. walking, attacking, dying.

The second problem is solved as follows: The FloorRenderer iterates through all objects in a Floor in every frame. If it encounters an object for which there is no DecalPack, it simply creates one on the fly. Chances are that the image containing the frames for the object's type are already in the texture atlas. If that's not the case, no problem: PixmapPacker can simply load and add that image on the fly. I expected there to be hiccups, but to my surprise, this worked seamlessly even on my Nexus One. This could be optimized, but so far it works brilliantly without any lag during rendering. For objects that got removed, i simply keep track of which DecalPacks have been used in this frame. If a DecalPack wasn't used, i simply remove it (actually, i put it pack into a Pool so the GC doesn't get mad at me).

The last problem is solved in a similar way. In the floor editor, i can tear down and build up walls at will. The FloorPack has to know about this. If i modify the boolean array in the Floor, i set a changed flag for those batches that need to be rebuild by the FloorPack in the Floor model. Each frame, the FloorRenderer checks if there are any changes to batches in the Floor, and if that's the case, it instructs the FloorPack to rebuild those batches. Again, this works like a charme, without any hiccups.

The best thing about this system is that everything is contained in the FloorPack. The renderer itself doesn't care about any state, just simply hand it a FloorPack and it does the right thing. The FloorPacks themselves are also trivial classes. The most "involved" thing is merging the meshes for batches and decorations, but even that is no more than 40 lines of code.

By having one pack object per floor object, i do not have to send and messages from the model to the view if something changes (apart from the batches, which is a compromise). The renderer operates on the current state of each object, which makes things really simple and easy to debug.

At the end of the day, using this is rather simple. Once i have my Floor constructored or loaded, i create a FloorPack and a FloorRenderer:

FloorPack pack = new FloorPack(floor);
FloorRenderer renderer = new FloorRenderer();

If i want to render the pack i do this:

renderer.render(pack);

And if i want to get rid of all resources, i simply dispose the pack and renderer. These are the only native resources i have in the game (apart from the skin atlas for the UI and background music).

pack.dispose();
renderer.dispose();

As a small aside: sound and music are also handled by the renderer. This part is not done yet, i'll likely add a tiny event system for this, as i also generate sound effects from user input, e.g. touching an icon, tapping on the floor etc. Events for things like a monster dying will be scheduled by controllers and behaviours.

Controller - Everyone gets Input

The controllers are responsible for executing the behaviours on alive objects, translating user input like taps and so on. Controllers are really really simple and generally only take a Floor object to work on. They may or may not proces user input, and as such implement the InputProcessor interface. Controllers are executed in a specific order, e.g. a CameraController that reacts to pinch zoom is executed before the HeroController which is responsible to let the hero move to a target position, or attack a monster. All controllers are managed by a ControllerManager (FactoryEntpriseBeanFactoryBean). Controllers have a simple interface:

public interface Controller {
   public void update(float deltaTime);
}

All they do is update something every frame, given the delta time to the last frame (which is actually fixed, you should fix your timestep too!). Here's the code for the manager in all it's glory:

package com.tinydungeons.controllers;

import com.badlogic.gdx.InputMultiplexer;
import com.badlogic.gdx.InputProcessor;
import com.badlogic.gdx.input.GestureDetector;
import com.badlogic.gdx.input.GestureDetector.GestureListener;
import com.badlogic.gdx.utils.Array;
import com.badlogic.gdx.utils.IdentityMap;

public class ControllerManager {
   private final InputMultiplexer multiplexer;
   private final Array controllers;
   private final IdentityMap detectors;
   
   public ControllerManager(InputMultiplexer multiplexer) {
      this.multiplexer = multiplexer;
      this.controllers = new Array();
      this.detectors = new IdentityMap();
   }
   
   public void addController(Controller controller) {
      controllers.add(controller);
      if(controller instanceof InputProcessor) {
         multiplexer.addProcessor((InputProcessor)controller);
      } else if(controller instanceof GestureListener) {
         GestureDetector detector = new GestureDetector((GestureListener)controller);
         detectors.put(controller, detector);
         multiplexer.addProcessor(detector);
      }
   }
   
   public void removeController(Controller controller) {
      controllers.removeValue(controller, true);
      if(controller instanceof InputProcessor) {
         multiplexer.removeProcessor((InputProcessor)controller);
      } else if(controller instanceof GestureListener) {
         GestureDetector detector = detectors.get(controller);
         detectors.remove(controller);
         multiplexer.removeProcessor(detector);
      }
   }
   
   public void update(float deltaTime) {
      for(Controller controller: controllers) {
         controller.update(deltaTime);
      }
   }
   
   public void dispose() {
      for(Controller controller: controllers) {
         if(controller instanceof InputProcessor) {
            multiplexer.removeProcessor((InputProcessor)controller);
         } else if(controller instanceof GestureListener) {
            GestureDetector detector = detectors.get(controller);
            detectors.remove(controller);
            multiplexer.removeProcessor(detector);
         }
      }
   }

   public InputMultiplexer getInputMultiplexer () {
      return multiplexer;
   }

   public void clear () {
      for(Controller controller: controllers) {
         if(controller instanceof InputProcessor) {
            multiplexer.removeProcessor((InputProcessor)controller);
         } else if(controller instanceof GestureListener) {
            GestureDetector detector = detectors.get(controller);
            detectors.remove(controller);
            multiplexer.removeProcessor(detector);
         }
      }
      controllers.clear();
   }
}

The manager has an InputMultiplexer. If i add a Controller, and if it implements the InputProcessor interface, it's added to that multiplexer. The manager's InputMultiplexer is set via Gdx.input.setInputProcessor() as usual. I can remove and add controllers at will. Here's a controller that updates all objects in the floor:

public class FloorController implements Controller {
   private final Floor floor;
   private float accumulator;
   private final static float TICK = 1 / 60f;
   
   public FloorController(Floor floor) {
      this.floor = floor;
   }
   
   @Override
   public void update (float deltaTime) {
      deltaTime = MathUtils.clamp(deltaTime, 0, 0.030f);
      accumulator += deltaTime;
      
      while(accumulator > TICK) {
         accumulator -= TICK;
         for(FloorObject object: floor.getObjects()) {
            if(object instanceof AliveFloorObject) {
               AliveFloorObject aliveObject = (AliveFloorObject)object;
               aliveObject.updateStateTime(TICK);
               aliveObject.getAcceleration().set(0, 0);
               aliveObject.getType().getBehaviour().update(floor, aliveObject, TICK);
               aliveObject.integrate(TICK);
            }
         }
      }
   }
}

This is not the real controller as implemented in Tiny Dungeons, but it should give you an idea. All alive objects are controlled via steering behaviours, hence the integrate() call.

Controllers are composable as well, e.g. i can create a controller that wraps the InputController to record all user input for later playback. I can also switch out controllers if i wanted this game to be networked and so on.

Conclusion

The architecture is far from being perfect, but this is a very small side project which i dedicate 2-3 hours to per week. Where appropriate i chose convention over configuration and for now it works out rather well.

Seperating things into MVC makes it also easier to unit test certain things. Once big feature i want to add are deterministic playbacks and maybe synchronous multiplayer via lock-step simulation. Both features require a deterministic simulation. At the moment i'm using floats all around, which will likely not work (strictfp is not available on all my target platforms). Apart from this, everything else like the order of objects in collections and so on, is deterministic, and initial tests on my CPU, where floats don't hit me (as hard), work exactly as imagined.

The lightweight class hierarchy also allows me to easily tweak and add new object types. The architecture of the renderer which is no more than 350 lines of code makes it easy to do custom things like the nice point light shader that gives the scene a more lively feeling.

On top of all, everything is very easy to debug (no event system to unfuck) and maintain so far. The only really ugly part is serialization, see http://pastebin.com/wvVXuuCE. I chose this route as i need to have control over the size of serialized things, down to the byte level. Server storage and bandwidth still costs money :)

Tiny Dungeons – Steering and Pathfinding

I’ve spent a few hours today and yesterday adding behaviour to the hero and monsters. The biggest challenge is keeping monsters apart, having them follow the hero and not tunnel through walls.

For path finding i use a rather simple and unoptimized implementation of A* on a tile grid (though it’s generic enough to work on any graph really). Path finding is only used to guide the hero to the point on the map the user tapped on.

For keeping monsters separated i give them a simple separation steering behaviours. To avoid walls, i implemented simplified obstacle avoidance which exploits the fact that the entities are moving on a tile grid. The monsters follow the hero by simple seeking. Those three steering behaviours (separate, wall avoidance, seeking) actually make for a passable overall experience. Each steering behaviour has a weight, so i can control the contribution of individual steering behaviours to the overall direction a monster takes. E.g. wall avoidance is weighted higher than seeking or separation. This (kinda) guarantees that monsters will prefer overlapping with each other more than tunneling through a wall.

I tried doing A* for every individual monster, but wasn’t happy with the result. Steering behaviours can’t resolve deadlocks resulting from paths that overlap in space and time, which creates stalemates among monsters. There might still be a way to make this work, however, for the simple dungeon maps the seek behaviour should suffice.

There’s a nice paper by Vavle on how they solved similar problems in Left 4 Dead. It’s a bit overkill, but some principles i could apply to my scenario as well. Haven’t had time to look into it yet, reactive path following looks pretty much what i had before i killed A* path finding for monsters. Thanks to Dave (@redskyforge) for pointing me at the presentation.

Here’s the obligatory screenshot, green lines show the velocity/direction, red lines show the steering force/acceleration. Blue tiles are the path nodes the hero follows.

You can try the desktop version here. Press ‘d’ to toggle the debug renderer.

You can try the Android version here. Alternatively you can use this QR code:

Tiny Dungeons – WIP

I’ve started working on a game again. Haven’t done one in ages, hope i have the stamina to pull it off. It’s going to be a light-weight Diablo kinda thingy. Kinda sorta, with a twist. I’ll try to release it on the desktop, Android and iOS eventually.

Here’s a screenshot. I’m happy to announce that Pascal from OrangePixels is doing the amazing pixel art.
tiny-dungeons

I’m actually taking timelapse videos for all the time i spent on the game. It’s gonna be a glorious 2 weeks timelapse once i’m done with this :)

The game is “data-driven”, in the sense that there are no real entity types in the code. Pretty much everything is specified in a bunch of JSON files. I keep things very simple by using conventions-over-configuration where possible. E.g. all sprite sheets for monsters/heroes etc. have the same layout. Adding a new “entity” boils down to dropping a PNG file with the animation frames into a folder, and adding a JSON descriptor for it in a file. I have not started implementing behaviour for entities, but the plan is to provide a couple of pre-build Java classes that i can reference by name from within an entities JSON descriptor. It’s not exactly a full-blown entity system, but it sure smells like one.

I guess what i want to get across is that i keep things as small and simple as possible, while making it very easy to add new content on the fly. I try to limit flexibility where i think i won’t need it, short-cutting my way through things :)