Monday, 12 January 2009

More Entity Broken-ness

Haskell is weird.

Having dispensed with that, I got some great comments about ways to approach entity composition after my Doing it Wrong post a couple of days ago. Something which I'd given little attention was brought up, and I'm thinking I should give it a second chance: representing entities as name/value pairs.

A bit of stumbling around later, and I found this huge post by Steve Yegge talking about the same thing, with extra bonus links at the end for additional reading. I'm still digesting it.

There do seem to be some unique challenges attached, though, in addition to the inherent oddity that are types in such a scheme (I'd also like to take this opportunity to bitch about type erasure under the JVM: bitch bitch bitch whine hate hate).

For starters, entities want to be able to refer to each other. At the very least, many will want a reference to a 'parent' so I can implement a simple scheme for inheriting properties. That's all fine, apart from the fact that I can't actually store references to objects because they're immutable, constantly subject to being deleted and recreated with different data. So there must be some kind of handle or ID system built in - no big problem, it's a useful thing to have in the scheme of things. Except then you need to provide a some kind of reference to the list of current objects, somewhere, for the handle/ID to search within and produce an entity object when really needed. Urgh, OK, we can do that... a simple function which returns the current world state's entity list will do, and provided entities and their clients behave that should be kindof safe.

Except it's not, of course. When a given entity acts, several other entities may be changed in an indeterminate order (invalidating the old list), and the world itself might pass through several intermediate steps during the update process - I can't currently see a way to ensure that entities always deal with the correct list of entities. It's possible an implicit variable might be a way ahead in Scala, providing a kind of weakly dynamic scope for the entity list. That doesn't sound like a good solution though, it sounds like a hack.

Of course, there's also some unrelated bookkeeping attached to ensuring that entity handles/IDs are always valid, unique, and easily generated. Eww.

On the plus side, if I vaccillate back to wanting Lua scripting, it would probably integrate very nicely with Lua's solitary data structure (last I checked, anyway, everything was an associative array in Lua). But then, ensuring or even pretending immutability in the presence of Lua could be a whole different kettle of fish...

Do other roguelikes ever use a scripting language? Choosing to have one is a pretty big step for any game, even if you don't roll your own and produce a hideous abomination (I'm currently using some middleware at work that provides it's own scripting language, somehow combining the concision of VB with all the elegance of COBOL, speed of Ruby, rapid iteration capabilties of C++ and expressiveness of a wheelbarrow of dead badgers) and most roguelikes appear to be more amenable to being data- rather than script-driven.

Pfft. I should go write some code. This is all getting a bit abstract.


Enne Walker said...

For what it's worth, Dungeon Crawl Stone Soup uses Lua for scripting, but it's fairly limited and the only gameplay (loosely speaking) that it gets used for is in constructing vaults and running arbitrary vault-dependent code on level entry/departure. Past that, it's only used for interface code where players might want to configure something without recompiling.

Back to the rest of your post, it's really too bad that no language (that I know of) handles this particular design very elegantly. It certainly appears that if you want to extend immutability up to the entity list, then there's really no way around recreating that list when you modify any given entity. (Wouldn't any other entity design scheme bump up against this same problem?)

Also, why do you need to keep the parent entity around apart during the initial creation? Are you planning to allow for changes to the parent after child creation to subsequently propagate to that child? Or, were you planning to use it for type-checking of sorts? I'm mostly just curious, as this simplification doesn't solve the fundamental problem.

Snut said...

Thanks, I didn't know that Crawl used Lua! Always interesting to know, even if it's not used for any core features.

Why a parent entity? Well, the best reason is probably prototype-style inheritance. If a property is not present on an entity, you can check the parent/prototype for it. This means most entities can be very lightweight, especially if there is support for 'freezing' the parent entity to prevent changes. Random fiddling with the parent of an arbitrary number of entities sounds like a good way to add bugs, but maybe even that has uses.

And you're absolutely right, I've not found any immutable entity scheme that allows for simple entity references, without passing around the current list everywhere. Annoying, as it sounds like something that will cause subtle, insidious little bugs as you grab a reference to a slightly out of date entity and make some decisions based on it.

Snut said...

Erk, forgot to add that even absent a parent/prototype reference, there's a good chance entities will want to store entity references. Inventory and AI data (enemies, friends) seem like key places, although I'm sure there are others...

So the problem is still, well, a problem even without any kind of inheritance.

Knarkles said...

Regarding parents / property inheritance, in my entity system, entities don't have parents or children. However, there are some related systems in place.

First, I separate entity types from entities. Entity types are essentially prototypes for entities, and they can be subclassed. The Entity type itself is never subclassed, and is purely a container for components. You create entities by calling the create() method of an entity type (or the create() function in the entity module, which creates entities by entity type name, but I digress). The create() method then creates an Entity object populated with relevant components.

For example, in my current game project, I have the base EntityType, a Unit type which subclasses it, unit types (such as Artillery) which further subclass Unit, and then finally individual units.

In addition, there are currently two components which have a parent or children: LinkedTransform, which is what traditional scene graphs usually include in the entity itself, and Composite, which is purely a convenience component for grouping a group of entities together.

Snut said...

Hi Knarkles,

Just wondering, do you not find that a bit restrictive? The idea of properties (and associated prototypes) does seem to allow for a huge amount of flexibility. Of course you pay a cost for that in lack of type safety, syntax overhead, runtime errors etc. It feels a bit like placing stringent restrictions on the use of Entities as prototypes sacrifices a lot of the flexibility of a property system, but without bringing any advantages from conventional inheritance and statically constructed objects?

Just curious. I can certainly see why there'd be a temptation to do this, just not sure how I'd balance and weigh the advantages and disadvantages. In an almost related note, it's interesting to consider a completely free-form system where properties can be added and removed at any time, with a more rigid approach that has different syntax for adding properties to an entity, and updating them with new values.

It's certainly an interesting pattern, which many people seem to have used successfully in a wide variety of ways.

Knarkles said...

It hasn't been restrictive thus far, and if you think about it, at least in Python it isn't any more restrictive than entity prototypes, since you can create new types at runtime. Entity types are really just another convenience; you could create the exact same entities without them.

And btw, I'm currently allowing adding, deleting and replacing components after creation, and the code takes this into account. It's a bit of a hassle at some points though, and I haven't really decided yet if it's worth it.

Jotaf said...

Couldn't you use a double buffer? Read from list_objs(t-1) and write to list_objs(t).

Then just swap them! :)
Like double-buffering when blitting to the screen.

Jotaf said...

The thing with components vs. property bags is, IMO, that property bags are C and components are C++. In what way? Property bags provide no encapsulation, it's like a mess of "globals". The "timeout" for one thing is different from the "timeout" from another. You'd need to distinguish them with prefixes or something, like "foo_timeout" and "my_timeout". With this in mind, and all the problems it brings, you might as well just encapsulate a bunch of properties inside a neat component, with its own namespace.

The other thing is that a component often includes "callbacks". This would be a worthy addition to property bags also but most of the times its forgotten. They'd be simply properties whose values are function pointers. You could iterate through all objects and check for the "init_callback" property, then run it. Actually it would work better as an array of function pointers, so you can add behavior later on. For example, attach a "amount_poisoned" value, and add a poison update function to "update_callback".

Other than that they're pretty similar. I like encapsulation so I prefer components; both the amount of poison and the update function reside in a single object in my design.

Snut said...

I'd rather argue that property bags are Ruby and components are C++ ;)

There's nothing to stop you structuring properties in a heirarchical manner, except the extra syntax and complexity overhead. In many ways components are a better solution for statically typed languages, except they tend to beget multiple dispatch... and I think they also complicate the threading of data through the functional parts of a system, as functions tend to end up being written in terms of components rather than dealing with the essential data they contain. By contrast, property bags are just maps or lists, cuddly data structures very much at home in a functional setting.

I like both solutions, and neither, so I'm writing lots about them in the hope that this will miraculously cause my brain to get big enough to understand anything useful about them...

(WRT the double buffer, that's more or less what I'd like, but due to the fiddly nature of some steps in the update process it's more like a triple- or quadruple-buffer, and the correct one to read from is poorly defined at some points. I think that's a simpler and more fundamental problem with my architecture though)

Knarkles said...

The more I read that post by Stevey, the more I'm convinced I should use entity prototypes instead of entity types. However, I'm not sure I'm prepared to make yet another huge change to my entity system at this point... But I think I'll do that anyway before the game is far enough that making the change would be too much of a pain. Learning new, better ways of things always results in a lot of effort, especially since I'm a bit perfectionist ;)