Wednesday, 17 December 2008

Entity Composition: Doing It Wrong

So, despite the lack of updates I've been working on this quietly. Unfortunately recent progress has been entirely on the game logic and architecture, rather than anything readily screenshotable, hence no real drive to blog.

But here I am, writing a new post. This can only mean one thing: rambling, waffly code-oriented braindump!

My current obsession is the structure of entities, going right back to basics. Entity is a deliberately ambiguous term, which I'm taking to mean any gameplay-relevant object that can be affected by the actions of agents in the game. Doors, monsters, AI, buffs... many things potentially fall under this umbrella.

I tried splitting the potential abilities of an entity into traits/mixins:

abstract class EntityAbility
trait HasPosition extends EntityAbility {
val position : Vector
val blocksTravel : Boolean
trait HasHealth extends EntityAbility {
val currentHealth : Int
val maxHealth : Int
abstract class Entity extends EntityAbility {
val id : Int

class Character(val id:Int) extends Entity with HasPosition with HasHealth {
val (position,blocksTravel) = ((2,2),true)
val (currentHealth,maxHealth) = (100,100)

This is nicer in many ways than a traditional hierarchy, allowing for more code reuse and less chance that required functionality will come with a bundle of meaningless state.

Unfortunately there are also some interesting problems with this approach. Mainly they concern the immutable update step. If only the position (say) is changed in a given timestep, objects can be dealt with as instances of the HasPosition trait. However this trait has no concept of the entity that it's being mixed into, and so cannot instantiate a copy of the entity with an updated position. Dropping the requirement for immutable world state allows for this easily, but that's no fun.

In addition, information about capabilities of an entity are defined at compile time, bound up in the type system. There's no way to define these things in a data file read at runtime. Whilst this isn't as big a concern for me (this is a small game and only needs a handful of basic types to define most of the game) it is an unfortunate restriction.

Another approach is to use actual composition...

sealed abstract class Position
final case class HasPosition( position: Vector, block: Boolean ) extends Position
final object NonPositional extends Position

sealed abstract class Health
final case class HasHealth( current: Int, max: Int ) extends Health
final object Invulnerable extends Health

final case class Entity( id: Int, position: Position, health: Health )

def move( e: Entity, newPos: Vector ) = e.position match {
case HasPosition( _, b ) => Entity(, HasPosition(newPos,b), )
case NonPositional => error("can't move nonpositional entities")

Well, changing entities becomes trivial (and supports using a Builder pattern or helper methods to remove those ugly constructor calls everywhere, plus enabling runtime construction of new entity 'types') but I end up having pattern matching all over the place. When you're operating on several components that becomes very messy, very quickly. There's also the issue that there seem to be vastly more potential runtime errors visible in the code, even if in practise I always check that a given component is of the correct type the compiler will whinge if pattern matching is not exhaustive (and correctly so).

I've fiddled with some other approaches such as conventional inheritance and a slightly COM-like abomination, but so far the above two feel most natural in Scala. I can't help but think that I'm missing some obvious alternatives though, as neither is particularly elegant when implementing common operations. Clearly I'm doing something wrong...


Knarkles said...

I don't know anything about Scala, but I like my solution in Python; it will very likely work with some effort in other languages.

Here it is in essence, with lots of practical details lefts out (formatting breaks in comments):

In practice, components are cached by the various subsystems using those specific components; that's why I have the observer pattern -based Signals in the Entity class, to detect new and deleted components. At runtime, you mostly don't need to check if an entity has a specific component.

Snut said...

Thanks, this kind of solution puts me in mind of COM (without a lot of the boilerplate and evil implied by that warty old system, of course). Requesting an interface from a composite/aggregate object via some ID or token and such, at least.

It can be translated to Scala relatively easily too, although it requires a bit of explicit casting in statically typed languages of course. That and the need to add a set of identifiers for each component or component type are really my only complains about the approach - I'd really like the type system to do that for me.

Perhaps I'll give it another shot starting from that very clean Python implementation *g*

With my crazed desire for immutability a few things become complicated, such as (meaningful) caching becoming impossible. I'll see how it goes.

Thanks again for the feedback, always good to get an insight into working systems.

Enne Walker said...

Another alternative might be to decouple the traits into a property bag of name->value pairs. The entity can then be instantiated from the base. Additionally, that gives you the flexibility to provide the same mixed in name from multiple traits.

I don't know if that maps to Scala very well, but I thought I'd suggest it as an idea.

James McNeill said...

I don't know that this is a problem that has been addressed very well by programming languages. I seem to recall some paper recently about polymorphic partial update of record types in a functional language, but I can't recall where I saw it. Perhaps on Lambda-the-Ultimate. I don't remember their solution being elegant.

Component architectures ring warning bells in my mind, having worked with game engines that did and didn't use them (albeit not in Scala). I try to write specifically and only add abstractions when they will clearly pay their way. They have a cost in understandability, and it's not generally clear up front which abstractions will be most useful.

Polymorphic dispatch, for instance, essentially hides "if" statements, refactoring the code so it's grouped by type rather than by function. This is a desirable organization sometimes but it does involve trade-offs about what is most understandable in the code.

Snut said...

Enne, using a sort of loose approach does work - and fits quite well using an immutable map type - but there are some problems. For starters in this case I'd need some kind of 'value' object, which typically leads to the same style of pattern matching code all over the place. It also has the issue that the key type is only checked at runtime, so there are some issues with how liberal to make the process of fetching the value. Not insurmountable problems at all, but I'm really trying to push as much validation back to the compiler as possible (without rewriting in Haskell, heh).

Snut said...

James, I think I know what you mean regarding component based architectures. Depending on the implementation, they can be ugly, brittle, and create a very high signal to noise ratio. I also saw some huge headaches created whenever there was any dependency or significant interaction between components. However I've seen them used well in small cases... at the moment I'm just trying to experiment with everything I can think off to find the least unpalatable of the very non-silver bullets.

I think the problem with multiple dispatch in this context is that it shines when you add new operations more often than you add new types. But at this point it's unclear that'll be the case with a roguelike game. I do think there's a problem with a lot of the code potentially being duplicated too, as often the same kind of pattern matching is performed when validating an action or actually executing it, at least in my test cases. Very ugly.

Thanks for the suggestions and helpful advice, to all who've shared comments. I love it when problems don't have a canonical solution, it's what programming's all about *g*