ArchTypes, composition and code is data

For a long time I’ve wanted to do a write-up on the ArchType based model. It’s as old as dirt and shamefully simple. But simple is good. It scales well to different complexity needs. For example it works really well as a data reduction technique and can be appropriate for low complexity system that otherwise wouldn’t need anything beyond the native abstraction model. It’s a top level model that can work hand-in-hand with other top level models, such as Actor based. And even though my motivation is in an attempt to show something one can do instead of the component-based model…the two would actually work “well” together assuming you think component-based has some merit.

Now I’m going to attempt to talk at multiple levels of background knowledge. Plough ahead if something sails over your head.

NOTE: That all of my examples will be super basic and poorly designed…this is going to be long enough as it is. Also I’m going to break this up into parts and any only build on this (into a usable form) if there seems to be interest.

ArchType in overview
The ArchType model has many different names and is probably most frequently used without the programmer calling it anything. At its most basic it looks like the following:


public class ArchType
{
  // whatever
}

public class Entity
{
   ArchType archType;

  // whatever
}

That’s it. So simple that it will probably seem worthless if you’ve never used the model before.

The major role of the Entity class is to store the state-data specific of a given instance of an entity. The major role of the ArchType class is to store the data that “defines” what the entity actually is and does. Enough for now.

Java’s abstraction model, briefly, inexactly and with much hand waving
Java’s base abstraction model is class based object oriented. This basically means that the abstraction model manages two memory chucks. One for the class and another for an instance of that class. The instance memory chuck only stores a pointer to its class’s memory chunk (along with some bookkeeping info) and the remainder is all the instance variables (fields) of that class along with the instance variables that it inherited from its parent.

It is also “closed class” based, which means that all of it’s members (static & instance) are defined at compile time and none may be added or removed at runtime. (Yes, there are minor ways around some of this) Additionally methods are immutable…you cannot set a method to another compatible method at runtime.

To simplify the above, basically an instance only stores the state-data needed per instance (along with some bookkeeping). The remainder of the storage is placed with the class since all of this data is common among all instances of a given class.


public class A
{
  public static int sa;
  public int ia;

  public static void hello() { ... }

  public void world(...) { ... }
}

public class B extends A
{
  public static int sb;
  public int ib;

  public static void hey() { ... }

  public void you(...) { ... }
}

gets logically translated into the following memory chunks (in pairs):


class$A {
  class*  parent;       // Object's class
  method* sMethods;     // table of static methods
  method* iMethods;     // table of instance methods
}

instance$A {
  word   bookeeping1;  // hotspot internal magic
  word   bookeeping2;  // hotspot internal magic
  class* class;        // class$A
  int    ia;           // instances fields of 'A'
}

class$B {
  class*  parent;       // A's class
  method* sMethods;     // table of static methods
  method* iMethods;     // table of instance methods
}

instance$B {
  word   bookeeping1;  // hotspot internal magic
  word   bookeeping2;  // hotspot internal magic
  class* class;        // class$B
  int    ia;           // instances fields of 'A'
  int    ib;           // instances fields of 'B'
}

So when an instance method is called, such as: b.world(...). This gets translated into b.class.iMethods[slot of world](b, ...)

Compare this with the basic outline of ArchType above and you’ll see alot of things in common. An Entity has the same major role as an instance and an ArchType has the same major role as a class.

CODE IS DATA

In data driven design you avoid creating a new type (class) if two things only vary by data.


public abstract class SillyPotionClass extends SillyItemClass
{
  public abstract void onDrink(Entity drinker);
}

public class NoobHealingPotion extends SillyPotionClass
{
  public void onDrink(Entity drinker) { drinker.heal(1); }
}

public class SuperDuperHealingPotion extends SillyPotionClass
{
  public void onDrink(Entity drinker) { drinker.heal(50); }
}

// I refactor into:

public class HealingPotion extends SillyPotionClass
{
  private int healAmount;

  public void onDrink(Entity drinker) { drinker.heal(healAmount); }
}

But wait! CODE IS DATA. All potions work in the same way. You use them and they do something. But wait! Scrolls do the exactly same. Sure the animations, descriptions, models, etc. etc. are all different…but that’s just data…and so is the handling code.

A poorly designed example:


public class OnUse extends ....
{
  public static OnUse SINK = new OnUse();

  public void OnUse(Entity user, Entity item)
  {
    // default to a script error log
    Script.errorlog("Yo: " + user + " somehow triggered on OnUse on " + item + " and it ain't set-up...fix yo bug scripter!");
  }
}

public class OnUseEffect extends OnUse
{
  final Effect effect;
  final int    value;

  public OnUseEffect(Effect effect, int amount)
  {
    this.effect = effect;
    this.value  = value;
  } 

  public void OnUse(Entity user, Entity item)
  {
     user.apply(effect, value);
  }
}

public class SillySingleUseItem extends SillyItemClass
{
   OnUse onUse;
}

In fact the vast majority of Entities really behave in the exactly same way. The player or the computer causes some event to occur and the underlying code determines what the effect of that event causes on the world. In the above event handler example, constant data about the effect is moved into the event handling code. And note that the reference to the handler doesn’t need to be in the ‘entity’ at all. All idential items will (generally) have identical sets of event handlers…move it into the ArchType…along with all other common data.

That’s enough for now.

Ah, I did something similar for an MMORPG (yes, I was going through that phase) for my entity class. I didn’t really like it though, since in the end I might want an equipable item which also has a use effect (a throwing axe, for a concrete example), or a reusable item. It seems like this method suffers from the same problems as hierarchy based ones, so how would I solve such a problem? Have a general Item class which contains a Equipable ArchType (I’d call that a component, but whatever =S) which can be null and a Usable ArchType that can also be null to accomplish both? Maybe some items can stack in one inventory slot? I can think of solutions, but how do I know when to create a new subclass of SillyItemClass instead of adding an ArchType? I can’t see the benefits of not having a simple ArrayList components; and just dump in a Usable component, an Equipable component and so on. These components can of course have subclasses.

EDIT: Where’s the Appreciate button when you need it?!

I do this at work all the time, although in my sector it is more usual to refer to the meta-information as a metamodel. Of course the next logical step is to have a metamodel for the metamodel.

I have to say that this is interesting, but the last example isn’t terrible clear to me. I also look forward to responses to theagentd’s post.

[quote]I do this at work all the time, although in my sector it is more usual to refer to the meta-information as a metamodel. Of course the next logical step is to have a metamodel for the metamodel.
[/quote]
Yeah, it pops up all over the place and goes by many names. I’d imagine that it’s very common in “grab-bag” languages like JavaScript, LUA, etc. I used this model back in the late 70s/early 80s in Z80/6502 assem & Forth. Using modern OO based terminology I’d call it an open-class based model. And yes it could make sense for an ArchType to store a reference to it’s logical super ArchType…the usefulness of doing so depends on the other types of abstraction that are being applied and how data-storeage is managed.

Before attempting to answer theagentd’s questions let me take a step back. I tend to think of the entity-system as being the logical block of code that seperates the engine-side from the world-building/scripting side. As such I’ll typically have a wider notion of “entities” than most programmers and an entity is any potentially scriptable individual thing. So will include things like triggers, delayed events, factions, encounters, etc. etc…i.e. may things that have no visual representation. It may also include things like UI elements…this is game design specific. And an ArchType is something that defines what a specific entity is and what it does. The world-building/scripting side pretty much only cares about the external interfaces that ArchTypes, Entities and the Entity system define. The engine side hardly cares at all about the entity system, which feeds it the information it needs to do it’s black magic. Notions like this will be over-engineering for very simple games and should be avoided, but as the complexity increases you mimimzie your risk by have a reasonably well define system that cleanly seperates these three logical systems.

If you were to go this route (as these types of design decisions are not dicated by the model I’m describing) it still wouldn’t be component-based. There’s no dynamic look-up and the type is of a concrete supertype. Personally this isn’t a direction I’d head in. Also for these types of pseudo-mixins I’d tend to avoid nulls. I’d have composed elements directed to sinks which either do-nothing if legal or do-nothing and log an error if illegal. OR high-order logic handles depending on what exactly where talking about. My view is that scripting/world-building side should be as fault tolerant as possible and the game should (hopefully) continue to be playble even though some scripting portions are currently broken.

The overall goal is to lower complexity. Make scripting and world-build as easy as possible and spend as little time tinkering with the entity system itself and get onto actually creating a working (and hopefully fun) game.

I way I’ve always used this model in the context of entity-systems is a single ArchType instance uniquely describes an indiviual game thing.

I’m not sure that I’m understanding you here. Let me try to anwser your question. The game design tells you what kind of events you need to handle. For some uber-RPG-thing a partial list (off the top of my head) for items:

Receive item
Give away item
Add to inventory
Remove from inventory
Equip item in slot
Unequip item from slot
Use item (For consumables/single kind of usage items…but not nessisarly consumed on usage)
Active item (for other things…aka…it can be ‘used’ in multiple ways.
Item hits something
Item gets hit by something
Spawn this ArchType

The exact list of events and whom is responsible for dealing with them is game-design specific. And note that game-design specific includes not only the things that various “kinds” of archtypes need to handle…but equally how the process of world-building and scripting is going to be performed. World-building app vs. text-based (XML, JSON, whatever) plays a role. Scripting in Java? some DSL? Some other JVM language? Basic hard-coded lego blocks? Some combination of the previous? This plays a role as well.

Let’s take the first two “receive item” and “give away item”. It seems highly unlikely that these are something that each-and-every item should be able to handle as it seems like something that would be very uncommon. And the base entites and archtypes should only deal with thing that are common amoung their specific kind. Uncommon and exceptional things should be handled in a separate way. Since I’ve only scratched the surface of some the various possible abstraction models that can be combined…this isn’t obvious yet. One thing that might come to mind about “give away item” is the if game design doesn’t allow the player to give away a quest item. Have the item archtype have a isQuest flag and disallow in higher order logical…manually setting an OnAquireItem handler for each quest item would be a PITA (more work than clicking a check-box). Of course all quest items could come from a common template to solve this problem. It’s a design decision. I’d not have any archtype kind respond to an event I deemed to be uncommon as it would be simple to reverse my decision and add them in at a later point if I desired. Now it might be interesting to allow responses to these two events, but associate them with the “module” or “player” for instance…which could examine the item and determine if it needs to do something special…in the case that a player is the giver or reciever. What about some placeable thing getting or losing a specific item? Ah…I’d have placeable things respond to the two inventory change events for instance to handle this situation.

“Item hits something” & “Item gets hit by something”: Say for magic weapons & armour. I’d pass. Allow items to have list of attached properties. These property specify what the do and when they do it. Higher order logic deals with applying these effects to the appropraite entity at the correct time.

OK. Do these examples help?

Add and remove from inventory events OR stackable items are handled by higher order logic. For example an item ArchType could specific a maxStack value and could be handled at a higher level than events…game design specific.

I have a tendency to minimize my write-ups. It’s a combination of assuming that my attempted descriptions are clear and that extending the notion is obvious along with the pragmatic thought that if anyone doesn’t understand and need clairifcation then they will ask. Likewise I’ve have a tendency to ignore low-complexity situations for similar reasons.

So people ask questions if something isn’t clear.

I think the behaviors of the objects could be represented as objects and the the mapping of objects to behaviors could be data-driven. Rather than hard-coding the behavior of objects in subclasses, each object is a collection of behaviors and properties.

This is exactly what I’m saying…tempered with only adding specific abstractions if it lowers complexity for the given design.

Episode V: Composition Strikes Back!

Fake mixins by composition

The most common way to fake a mixin like structure is to use one or more composted elements and hide that behind forwarding methods:


// external code doesn't need to know this exists
abstract class Mixin
{
  int someStateData;

  abstract int someMixinMethod(...);
}

public class A
{
  private Mixin mix;
  
  public int getData()
  {
    return mix.someStateData;
  }

  public void setData(int value)
  {
    mix.someStateData = value;
  }

  public int someMethod(...)
  {
    return mix.someMixinMethod(...);
  }
}

Another way this can be used is for extendible state, either perm or transient:


// external code doesn't need to know this exists
class ExState
{
  int foo;

  boolean isRemovable()
  {
    // check if this instance is still needed
  }
}

public class A
{
  private ExState ex = null;

  private void insureEx()
  {
    if (ex == null) ex = new ExState();
  }

  private void maybeKillEx()
  {
    if (ex.isRemoveable())
      ex = null;
  }
  
  public int getFoo()
  {
    if (ex == null) return 0;
    return ex.foo;
  }

  public void setFoo(int value)
  {
    if (value == 0) {
      if (ex == null) return;
      ex.foo = 0;
      maybeKillEx();
      return;
    }

    insureEx();
    ex.foo = value;
  }
}

Remember these are minimal examples. “Hey, can’t I don’t this by XXX?” Probably. Design decision. “Hey, that’s boilerplate hell!” Yeap…that’s why you probably wouldn’t do it that way. No null, defaults to a SINK, setters pass in this, SINK returns default values for get and auto-magically replaces itself when needed on sets.



interface HasStateEx
{
  void setEx(StateEx ex);
}

public class A implements HasStateEx
{
  private StateEx ex = StateEx.NIL;
  
  @Override
  public void setEx(StateEx ex) 
  {
    this.ex = ex;
  }
  
  public int getFoo()
  {
    return ex.foo;
  }

  public void setFoo(int value)
  {
    ex.setFoo(this, value);
  }
}

Fake mixins by inheritance
Less commonly used (and for very good reason) is to fake by inhertiance. This requires using class loaders. Potentially useful for server-side (for hotswapping) and in adaptable libraries. Another game usage could be in over-ambitious engines that want to allow user-definable game-mechanic with higher performance than one would otherwise achieve. BEWARE! Requires solid knowledge of how classloaders work and you probably really don’t want to do this.


// Classes in this package is what the high level is aware of.  When creating instances, however, it uses the direct child of each class.
package some.base.package;

public class BaseA
{
  // fields and methods engine/library side is aware of
}

public class BaseB extends A
{
  // fields and methods engine/library side is aware of
}

// by changing the search path we can 'flip' between different versions of
// these classes. 
package some.other.package;

public class A extends BaseA
{
  // left empty by default
}

public class B extends BaseB
{
  // left empty by default
}

(EDIT: missed a return statement in the boilerplate aggressive transient state-data example.)

For some reason I am having trouble grasping exactly what it is actually going on with the archtype setup you are describing. Can we walk through a simple example?

Let’s say I have a game with a JetFighter that has the following state:

x,y position
health

The JetFighter can fire either a BigMissle or a SmallMissile which are essentially the same except for the amount of damage they cause.

It has the following “events”
FireBigMissile
FireSmallMissile
moveTo(newX,newY)
TakeDamage(Missile)

What would the archetype / entity set up look like for this scenario?

Very nice, thanks :slight_smile:

@actual: Once I’ve built-up more more building-blocks I’ll show a few different ways these (and similar) things can be connected together. The model itself is heavily data-driven so is way over-engineering if you don’t need it. The ArchType model is really nothing more than using a fake mixin (by composition) is a specific way. If simple design-by-inhertiance is sufficient for a given game design…go that route. If a dash of composition will make things work…go that way. This stuff is really not interesting…get it done and move on.

WRT your list of events. Events/messages are a way to communicate with semi-unknowns. So these may or may not make sense.

FireBigMissile: Highly likely this would be best handled by just a spawning entity from the AI
FireSmallMissile: Likewise.
moveTo(newX,newY): All entities that move are likely to do exactly the same thing for this…unless I’m not understand what this does.
TakeDamage(Missile): This might make sense if damage can be handled in a unique ways that wouldn’t be reasonable for a single method to handle.

SECTION D: Dynamic fields: OR Using dynamic lookups doesn’t mean you’re component-based.

Sometimes you just need extra state data that simply falls outside the norm. Attempting to have some ‘generic’ slots that can be used to service this need is usually an unmaintable solution. Enter dynamic lookup (I’ll ignore everything other than hash-maps…but other methods are possible)

Using strings as keys of these fields works really well for our little human brains and (reasonable named) makes not having usage conflicts pretty easy. A system that has worked well for me in the past is to use hash-tables which LOGICALLY maps a string in an entity to a small set of types: say integer, float, String and Entity. This might sound very limited, but remember you can do quite a bit with a String and storing an Entity means that you can indirectly store any information any entity can store.

This is what I meant by: “An entity IS an arbitrary container of ARBITRARY types.”? for component-based vs. “An entity MAY be an arbitrary container of a small set of types.” over HERE.

In the context of some entity-system there are a couple reasonable ways to handle this (that I can see). The first is to have all the types logically in a single map and act typeless. The second is to either use multiple maps (one per type) or <name,type> pairs as the actual key used for lookup and stored in a single map. Another consideration is where the map is stored. Either directly or indirectly inside the entity. OR they can be stored in a global map, where you’d use a key of <owner,string> for untyped and <owner,string,type> for typed. This second method is one example of a more general techinque of storing rarely present data outside of it’s logical owner. Of all of these choices…only the first is really important as it’s the only one the outside world is aware of. Another outside world aware choice is if variables act inside a namespace or are local only. In other words if you do:


public void SomeMethod(Entity e)
{
   if (e.getInt("numberOfPiesEaten")>10) {
     ....
  }
}

If “numberOfPiesEaten” is only looked at with ‘e’, or it will look further up the chain if ‘e’ doesn’t have a value set. Like examine the ArchType of ‘e’ (assuming ArchType based), followed by whatever else until the root of the namespace is reach if none is found along the way. If a namepaces are used, then it’s probably very wise to have two sets of look-ups…one for local only and another for the whole namespace.

For direct storage (reference in all entities)…using a proxy technique like the self creating and aggressive self deleting example above could be employed…then you only have a real hash-map when needed and don’t have a mess of boilerplate. Likewise it could be placed inside a composed element as it’s highly likely that any entity with extended variables will have some other extended over the norm data. But none of this really matters as it’s all hidden under the hood…do it easy and change only if you need to.

Component based kids: Hash-tables are expensive. If you use a hybrid system and can limit the set of components to some small fixed number (say <=32 or <=64) per kind of entity…then you can use the old flags/compressed array trick. Components are stored by name (integer index) which maps to a bit position, that bit and lower is a masked with the flag…population count gives the real array index.

Dynamic Methods: Pfffff
Using the same techniques as attaching fields to an object, one could attach dynamic methods. To be somewhat reasonable this would require having a signature (return type + parameters) as part of the look-up key. I can’t think of a game situation were this would be reasonable. However, it could potentially be reasonable to shove very rarely used events into such a structure…assuming a global map, then the key is <owner, event-type>.

When storing stuff in global maps, there are some potential gotchas to be considered. First reasonable hashing and second how the ‘owner’ info is stored. If it’s a reference…this means that an entity will need to delete all its variables (in the case of fields) when it dies or it will never become garbage (since the hash-map will store references to it). One way is to have unique id’s per owner and to use this value. This still leaves the problem of the actually variables not becoming garbage. However in the case of things like uncommon events where you can explicitly store a flag that indicates that you have a specific item stored in the map, then this problem disappears.

Assumming JDK5+, a simple creation ordering (should be reset on loading):


  private static AtomicInteger uidCounter = new AtomicInteger();
  ...
  {
    uid = uidCounter.getAndIncrement();
  }

Or the long version if you’re worried about overflow.

Light-weight events:
Or lego block programming.
Having explicit event handlers can be overkill as each unqiue one requires coding. A possible higher order mechanic is to have a list of properties, perhaps like this sketch:


public class LwEventEffect
{
  public static enum EVENT
  {
    // whatever event triggers are supported
    ;
  }

  // magic constants might at least make more sense here, as
  // target values will depend on the event in question.
  public static enum TARGET
  {
    // whom the effect is applied to when triggered
    ;
  }
   public final EVENT  event;   // triggering event
   public final TARGET target;  // whom gets the effect
   public final Effect effect;  // the effect to be applied
}

Which are applied automatically inside the entity system. Of course this techique and explict handlers are not mutually exclusive.

Effect filtering: Or less code (is yet again) better.
For more complex mechanics where what actually happens to the target when applying an effect depends on any “buffs”, innate abilities, physical properties, etc. etc. that the target has…then it’s probably useful to use filtering of effects.

In my first post, I hand-waving-ly changed:


// this: (method name changed..and item parameter added to match event notion)
public void OnUse(Entity drinker, Entity item) 
{ 
  drinker.heal(healAmount); 
}

// to this:
public void OnUse(Entity user, Entity item)
{
  user.apply(effect, value);
}

Doing this might or might not make sense. The idea here (in the case of healing) is how many ways can it be modified? Can the user be undead and cause damage instead? Can the user be non-living and have no effect? These two alone would be easy to explictly code, but if there were many potential modifers…then it could be troublesome. Remember that the entity will have health restored in different manners (resting, etc). I admit that “healing” is probably not a very good example here. Be that as it may, at least for some effects explictly coding for all the possible ways that the effect might be modified at each location where the effect is generated can be a big pain. If that’s the case, then one way to handing the problem is to simply pass off the effect unmodified and the effected entity walks through its list of “effect filters” which modify the effect before applying the final result.

O.K. That’s enough of this stuff…I’ll start getting to the heart of the matter next time.

I can imagine that a game involving magic might make use of dynamic methods - a spell might temporarily change the capabilities of an avatar or an object.

Opps…missed this reply.

There are a number of ways to handle temporary changes of behavior. What I really meant by dynamic methods would be something like this:


public void run(Entity self, Entity other)
{
  Boolean_EntityEnity foo = (Boolean_EntityEnity)self.getMethod("someMethodName");

  if (foo.run(self, other)) {
    ...
  }
  ...
}

A more practical way to handle extending methods is to have a user defined event with an event ID.

Design by inheritance
As has been mentioned here and elsewhere, classic design by inheritance can be a perfectly reasonable model. By this I mean: one unique entity = one class. A rough rule of thumb is when the total number of unique entity types is small. I’d strongly advice inexperienced programmers to start with a straight design by inheritance model. You have more than enough work ahead of you in creating a game and learning new stuff that you don’t need to go out of your way generating make-work. Over-engineering is an illness best avoided.

As the number of unique entity types increases, the straight inheritance model will begin to break down. In a wide range of cases the simple addition of a ‘dash’ of a data driven model will resolve the problem. From here there is a natural logical progression of increased generalization (more and more data-driven) where the ‘final result’ will be the common model of breaking entities up into “kinds” of things. Sticking to a FRPG example you might end up with: area, trigger, placeable, item, npc, pc, etc.

There are two “gotchas” of all data-driven models:

  1. Initialization of the data.
  2. Increased memory footprint.

Now the first is really a good thing in most people’s opinion. It means that having definitions of entities which are outside of the source code. And the second is rarely a direct concern. It can be an indirect concern as effectively you have a prototype-based model, which is to say that every entity is basically uniquely defined. This might be undesirable as you might want the easy ability to update all instance of a given unique type in one go rather needed to modify each individually. Of course the solution to this is simple…use a common composed type instead of repeating the data in each.

Typeless (or god-class)
From here on out I will only consider heavily data-driven models for supporting large numbers of unique entity types. Another possible design direction is to have a single Entity class that the outside world is aware of. This god class can logically do anything that collectively all entities can do, and as previously mentioned will perform some default thing (log an error or do nothing for instance) if the request is illogical. Under the hood of the entity system, this could be designed in exactly the same way as the previous…break up into kinds, or by composition of compound elements.

Now, of course, design pattern kids will tell you this is an anti-pattern and that you should avoid it at all cost. Me? I don’t care. I probably wouldn’t go this route unless I was using a dynamically typed language for scripting.

A quick and dirty implementation of dvars for playing purposes: UserVar and GameObject.