Immortius' Forge

[immortius]

Voxel Physics

This post looks at some of the common approaches to integrating physics with a voxels I've seen and used, as well as the approach I settled on for Terasology.

Before that let me clarify what I mean by voxel physics: supporting collision and hit detection of a voxel world, including individual voxels. This does not touch on voxel dynamics such as having floating voxels fall or detecting unsupported structures.

Integrate an Existing Physics Engine

This is an obvious path to take, particularly if already using a game engine with built in physics integration like Unity. Full physics behaviour with a variety of shapes is a complex area, so using an existing and hopefully well supported implementation is enticing.

The vast number of voxels as usual puts some constraints on how to approach this. Adding a collider per voxel will consume vast amounts of memory and perform poorly. A better approach is required.

One method that works reasonably well is to generate one or more collision mesh for a voxel chunk. Multiple mesh will be required if there are multiple collision behaviours - perhaps some voxels are solid, while others can be passed through but still can be targeted. Often this can reuse much of the mesh generation code used to render the world - but generally cannot be the same mesh due to differences between what is displayed and what can be collided with.

There are a few downsides to this technique:

Generating and updating the collision mesh takes time. This can be done on a background thread, but there will be a delay.

In some engines the mesh will be set up for rendering even though that is not required for your usage. This means it will use video memory and take longer to build.

Mesh colliders are paper thin, which means you have to be careful about objects passing through them. In particular when the collision changes due to a voxel being added, any object inside that space will fall into the collider.

The mesh use some amount of memory.

Extra work needs to be done after colliding with the world to determine which voxel was hit.

Another technique is to add colliders for each voxel, but just in the immediate area around players or other actors of interest. This has some immediate advantages:

Per-voxel collision with whatever collision shape best fits each voxel.

Can update immediately with voxel changes.

Small memory footprint, if the number of actors requiring collision is small.

The downside is the limited area in which collision works - you cannot do long-ranged ray traces, nor have objects bouncing around everywhere. Velocity can also be an issue, as a fast moving actor could exceed the collision area in a single tick. Still, this can work well for character movement and can be combined with other techniques.

Roll Your Own

Having seen the options for integration with a physics engine you may be thinking you could do better. After all, your voxel world is composed of a axis-aligned grid of primarily cubic objects - you can easily work out what grid cells are involved in any ray trace or potential collision. And this is correct to an extent.

Ray tracing is pretty straightforward. The ray trace need only step through the voxel cells - you can work out which cell is next from the side of the cell it exits from. Some care is needed for traces along the edge or passing through the corners of cells - these may need to hit all the cells they touch for correct behavior. Supporting non-zero extent traces (where the ray has a diameter) may also be useful.

After determining a cell is involved the ray can be tested against the shape of the contents. Axis-aligned boxes and spheres are simple, but more complex shapes are possible too.

The advantages of rolling your own are:

Can hook directly into world data, so little memory cost or delay in collision availability.

Performs well by taking advantage of the voxel structure.

Per-voxel collision info is easily available.

The problem with rolling your own physics is when to stop. Beyond ray tracing is convex sweeps, collision between moving objects, rigid body simulation, constraints... If you are primarily interesting in creating an engine then this may be ok, but if you have some other goal like creating a game then producing and maintaining a physics engine is a poor use of your time.

Extend a Physics Engine

This is the solution I went with in Terasology - take an existing physics engine and build in support for voxel structures. These structures can link directly to voxel data, providing all the benefits of rolling your own engine, but can take advantage of the collision algorithms and features of the existing engine.

The restriction is that you need access to an open source physics library or one with an api that supports the necessary extensions.

For Terasology I extended JBullet (a Java port of Bullet) and named it tera-bullet. The extension is a new Shape called a VoxelWorld. This shape provides the ability to request information on the collision shape of each voxel. The collision algorithms for VoxelWorld work out all the voxels involved in a collision and delegate the collision processing to their shapes.

[immortius]

An Approach To Events For Entity Systems

One experiment that has proven very successful in Terasology is our event system. It works like this:

A system creates an event - say, OnDamagedEvent. This is just a class implementing Event that holds whatever data is related to that event (damage, instigator, etc).

The event is "sent to" an entity. Entities don't have any logic though, so what this really means is...

The event is forwarded to every system subscribing to that event, filtered by components of interest.

The filtering is important here. It means that the behavior of an entity in response to an event is effectively determined by what components it has.

For modding, this also allows mods to hook into existing events either on existing components, new components or combinations of both.

In Terasology this is annotation driven, so the health system may have a method that looks like:

@ReceiveEvent(components = {HealthComponent.class}) public void onDamaged(OnDamagedEvent event, EntityRef targetEntity) { // Decrement health }

Or

@ReceiveEvent public void onDamaged(OnDamagedEvent event, EntityRef targetEntity, HealthComponent health) { // Decrement health }

That method will be called whenever an OnDamagedEvent is sent to an entity with a health component.  Another system may play a sound or generate some particles based on other components present.

This technique is great for some use cases in particular - an excellent example is a player using an object in the world. Rather than having to know about the types of things the player can interact with or have systems explicitly registering themselves with a central 'use' system, a use event can be sent to the entity. If it has some combination of components that make it usable, then that will be triggered. This loose coupling also means that non-players can also use objects just by sending a use event.

[immortius]

On Entity Systems

Currently I'm working on Terasology - an open source voxel engine with a focus on modability and graphics. My primary area is the core architecture and mod support. Central to both of these - the beating heart of Terasology - is an Entity System. I know there is a fair bit of interest in entity systems out there so I thought I'd take the opportunity to share some my experiences and learnings.

For this first post I will be covering in brief the reasoning behind using an entity system and what one is, and then in future posts I will delve into more specific topics. For further information I would recommend Richard Lord's What is an entity system and Why use an entity system articles, and T=Machine's blog.

What is an Entity System

To start off, an entity system is a composition based approach to describing game objects, as opposed to an inheritance based approach. When someone relatively comfortable with Object Oriented programming starts to write a game they generally begin with a GameObject class with some common behaviors. Then they create subclasses like "Monster" and "Door" with more specialized behaviors. This works fine until you need a door that is also a monster - it might sound trite but there are many aspects like whether a game object has a location, moves, is rendered, casts light, can take damage... and if you split this up across subclasses then you will end up in this situation. One approach is to lump all these common features down into the base GameObject - this works, but you end up with a gigantic class with all sorts of features and attributes, many of which you don't need for a given object.

Entity Systems on the other hand have Entities that are meaningless on their own but can be composed of Components. These components describe the behavior of the entity through the types of component (e.g. Location, Mesh, Physics) and the data they contain. Essentially each component correspond to a feature an entity can have as listed above. This way you can pick and choose which features each entity should have, and reuse features as desired.

Now at this point there are two approaches that can be taken. One is to put the logic that drives each component in the component class itself. This has the advantage of keeping the logic with the code - which sits with with the Object Oriented paradigm. However there are a number of disadvantages:

Components will need to access each other (e.g. a physics component will need to access the location component), and thus will need to know the entity they are on, which complicates the data model.

To call update() methods and send events to components, every component needs to be registered individually for these calls. This adds overhead to the instantiation and manipulation of entities and forces them to reside in memory so they can be hooked up.

There are some things that simply cannot be done through logic in components, such as physics updates (typically physics systems tick all objects together as collisions involve multiple objects)

Entity Systems take a different approach - they split out the logic into separate systems that work with all entities with a type of component or combination of components.  A rendering system for instance may render everything with a Location component and a Mesh component. It is these systems that receive update() calls and other events. By centralizing processing you can do things that are otherwise difficult, like batch rendering of every entity using the same shader and material, or physics processing. Your components also don't need to know which entity they belong to - the system knows which entity it is working on - which simplifies things. Since entities and components are pure data in this model they can be store out of memory and streamed into memory as necessary, which is great in low memory environments.

The entity system in Terasology follows this second model. This sits well with supporting mods, as a mod can introduce new systems that work on existing components. But more on that later.

One or Multiple of a Component

One decision that needs to be made early on when creating an entity system is whether an entity can have multiple of the same type of component or not. For instance, should it be possible for an entity to have multiple mesh components?

My opinion is you should stick to only one of a type of component per entity. For the majority of components, it doesn't make sense for a single entity to have multiple of a components - what does it mean to have multiple locations? To have multiple physics components?

For components where it makes sense that can be reflected in the component itself - have the mesh component contain a list of mesh to be rendered. Alternatively what you may actually want is a set of entities that reference each other - to have multiple mesh you could have a second entity that is "attached" to the main entity, perhaps through the location component, with the second mesh - then you can manage the offset of the second mesh through the location of the second entity.

[immortius]

Continuing to make progress with NightBlock. Demonstrated in the video are doors, which are an example of player interaction with the world - in their closed state they are just world blocks backed by a controller entity that handles the interaction. When opened they become an entity proper, allowing the door mesh to sit across block boundries.

Also demonstrated is weapon switching and some extra effects like attached lights, particle effects and sounds.

[immortius]

In my spare time I've been tinkering with creating a game called Nightblock.  The core idea is a shadow-based stealth game with strong support for user content and possible procedural generation. The player will sneak through mansions, castles and towns, stealing loot and evading guards.

I came up with the idea while messing with setting up a basic block world engine - I noticed that as a result of calculating lighting information for every block of the world, it is easy to make use of that information for stealth calculations. 

The game is written in java, on top of JMonkey Engine. So far I have working:

Basic world structure and updates

A world lighting system with shadow projection

A basic collision system for player movement

The core of an entity/component system to drive game logic.

Other bits and pieces

[immortius]

Adding Tileset Rendering to Goblin Camp (part 4)

So in Goblin Camp all the buildings, items, NPCs and plants are defined in configuration files, which can be modified or extended by mods. These definitions are loaded up as prefabs, and then every entity that exists in the world is tied to the prefab that defines it. I wanted a way to be able to link tiles to the prefabs, without requiring the existing configuration files to be changed, without having them need to know about the existence of the the tileset renderer, and with minimal impact in general. But at the same time it had to be performant.

In the end I did two things. First, I added a graphicsHint attribute to the prefab classes. This attribute can be populated with an integer by the renderer, and then used to lookup the sprite used to render an entity. Secondly I added a graphicsFallback string to each prefab.

At this point I started reading tileset configuration from a file. This file mapped various elements, such as the terrain types and water, to the tile in a texture used to render them. For items, buildings, NPCs and plants the tile is given a name. Then the tileset renderer looks through each entity and checks if there is a suitable tile who's name:

a) matches the entity's name

b) matches the entity's graphicsFallback

OR

c) for items matches one of the item's categories

If none of these conditions are met a default tile is used instead.

With this the basic rendering was complete.

[immortius]

Adding Tileset Rendering to Goblin Camp (Part 3)

With a method for rendering tiles determined, the next step was to work out how to integrate it.

The way Goblin Camp does ASCII rendering is that each entity knows how to draw itself, keeping track of the character and colours used to represent it.  Then the main class iterates over all the entities (or at least the ones appearing within the viewport, where that information was available) asking them to draw themselves.

A simple approach might be to just add an extra tilesetDraw() method to each entity, with a flag to determine which method is used - but then the tileset rendering would be mixed in all over the place, and if more renderers were added later things would get quite messy.

Instead I created a new Renderer interface, which each rendering technique implements to handle drawing the game however they desire. One of these is registered with the main game class, and called each frame to do the rendering. The first Renderer class I created was for the existing ASCII rendering, which became the new home for the code that iterated over the entities asking them to render themselves. I otherwise left the existing code alone - I could have moved all the draw functions out of the entities, but that wouldn't have helped create a tileset renderer.

Next I created a copy of the ASCII renderer and started replacing the the ASCII rendering with tileset rendering in a layered way, keeping the ASCII rendering for the unhandled elements. To fit in with the ASCII the initial implementation allowed only 8x8 pixel tiles, had no configuration support, only scrolled in 1 tile leaps and was generally quite basic. By keeping the ASCII rendering for other elements it was easy kept the game in a playable state, making it easier to test the changes as I went.

First terrain...

Then water...

And then plants, items and NPCs - but with only one tile for each of these items. Before things could continue I needed to work out how to map each type of these entities to different tiles.

[immortius]

I've been doing some more work on the house builder prototypes.  Part of this has been fiddling with the various commands, seeing what makes them easier to use. In particular the stairs tool now shows the slope of the stairs being created, reveals the floor the stairs will reach as the user extends them, and is overall zoomed out compared to the other tools.  This gives the player a much better feel for what they are doing.

The other major piece of work has been added detection and removal of house parts that do not connect to the ground.  This was done by maintaining a connectivity graph of the house parts, which can be traversed to determine if a part touches the ground.

[immortius]

House Building Prototype

Started work on a prototype house builder based on the fictional game Sburb in Homestuck. The principle is a simple click-and-drag editing tool with some high level commands like "Extend" and "Reduce", possibly along with some finer-grained tools for fiddly details.

For the prototype I'm paying no attention to performance (which is fine thus far anyhow), and instead am focusing on the building commands and how they interact. There are some tricky cases to consider. For instance, the extend tool is used to grow a room - if you click inside a room and drag it out of house, then the walls move to encompass the new area and the ceiling and floor with it (as shown).  But what is considered a room? What should happen if you extend from outside the house inwards? What if you have a room inside another room and extend into it? What is the most intuitive behavior for a player?

These are the questions I'm trying to focus on with the prototype - basically to get a feel for the problem space. I've been doing this in Unity 3D - I find it really easy to throw things together with it, partially because I have a library of relevant math and other scripts to fall back on.

Try the prototype.

[immortius]

Adding Tileset Rendering to Goblin Camp (Part 2)

Goblin Camp uses Libtcod, a roguelike framework that provides a lot of useful features - path finding, configuration file support and ascii rendering are just some of them. Rendering is done using a Libtcod console, which tracks the character, a background color and the color of the character for each tile to render to the screen. The console is then rendered to the screen using either SDL software rendering or OpenGL (with or without shaders), depending on how it is configured.

Both the world and UI were being rendered using Libtcod originally. I decided early on that I did not want to rewrite the UI - doing so would be a large task on its own, and too many opportunities to introduce bugs. Luckily Jice, the creator of libtcod, had posted in the tileset thread about the hook he had added to allow libtcod's sdl rendering to be combined with custom world rendering. He even gave a few examples of how to use it.

The basic idea was this:

1. Render the world to a SDLScreen.

2. Let libtcod render the UI to the screen, with unrendered areas colored Magenta.

3. When Libtcod went to flush the screen, it would provide the screen to a custom rendering function.

4. Have the custom renderer blit the screen over the world's SDLScreen, with Magenta as the key color so that it isn't copied.

4. Render the world's SDLScreen to the screen.

5. Flush the screen.

There were two major problems this technique. The first one was that libtcod is clever and only renders tiles that have changed to the screen - however the Magenta tiles always need to be rendered so that they can be made transparent. This was easily solved by marking them as dirty manually.

The bigger problem was performance. Reading from the screen is very slow. It was actually faster to copy the screen to a SDLScreen and then render that screen with magenta as transparent over the world's SDLScreen than to do it directly from the screen to the world. Ultimately I changed libtcod so that when a custom SDL renderer was installed it would render to a SDLScreen and provide that along with the screen to the custom renderer to do with as it saw fit.  This performed much better, and also removed the need to mark magenta tiles as dirty as well.

[immortius]

Adding Tileset Rendering to Goblin Camp (Part 1)

I wanted to start of this blog by describing what I've been working on recently - adding tileset rendering to Generic Container's Goblin Camp.

First a bit of history. Goblin Camp is an open source city management game in the vein of Dungeon Keeper, Caesar 3 or Dwarf Fortress. In Goblin Camp you loosely direct a tribe of orcs and goblins in setting up a camp and defending it.  The first release of Goblin Camp was mid-2010, and the game is still very much in an alpha state.

In the initial release the graphics of Goblin Camp were ASCII - that is everything in the world was represent via letters on a grid - a goblin was a 'g', and an orc was a 'o' and so forth. Graphics like these have been the staple of an entire genre of games (rogue-likes) and they simplify development, however they do make it harder for the majority of people to get into a game. Especially real time games like Goblin Camp.

Very early on (three days after the original release) a thread started on the Goblin Camp forum discussing adding a tileset support and what features would be nice. At its most basic tileset support would render each game element with its own tile, but a number of other features were mooted.  A few people even started working on it, but not much came of it.

Then early 2011 a friend of mine who reads the Something Awful forums alerted me to the existence of Goblin Camp.  After checking to see where things were at, I decided to have a go at adding tileset support myself.