Jump to content
  • Advertisement
Sign in to follow this  
Rainweaver

Flyweight... sort of

This topic is 3074 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello everyone,
Question: how do you manage data for thousands of entities?

1) Many entities start with the same set of stats. It makes no sense to duplicate data.
2) However, data is bound to change very early in the life of the entity...
2a) or at least very often, once it begins to change.
3) Entities can also spawn or be killed very quickly.

In my mind, it'd go like this:

* request attribute value ("hp")
* no value is found in the entity instance
* look it up in the entity "prototype"
* return this value

Despite the technical issue of storing different data types without boxing etc (thinking .NET here, but I may have a solution for this), is it worth it going through all of this nowadays?

I don't like the idea of wasting time optimizing prematurely (and I know some will say I am), but I believe there must already be an "ideal" solution. I like best practices.

For instance, how about muds? How do they (allegedly) deal with a similar scenario?

Thanks for any input. Hope it makes a bit of sense.

Share this post


Link to post
Share on other sites
Advertisement
I wouldn't consider it a premature optimization, but rather an appropriate approach for factoring out data that is common to all instances. The downside is that if most of your data really can't be static for whatever reason, then you don't gain much by using the flyweight pattern. If you're feeling adventurous, you might try implementing copy-on-write, which is basically the process you described -- the prototype maintains the values until the entity changes them, at which point it makes a local copy and uses that from then on. Optionally, you can tell the entity to "reset" the value and have it start using the prototype again.

Share this post


Link to post
Share on other sites
For a case like this you might want to look at smart-pointers with copy-on-write.

Say you have some asset that starts out the same for all of your entities, they will then all have this prototype smart-pointer. However, when an entity tries to write to the smart-pointer, that entities smart-pointer gets automatically detached from the prototype and a new instance of the smart-pointer with the new data is created.

All this will happen behind the scenes and the programmer won't have to worry about the details.

Share this post


Link to post
Share on other sites
I was messing with something like this a while ago. It started out as this, a sort of vtable for data which allowed a structure to contain an arbitrary subset of fields with constant-time lookup and constant amortized space overhead.

A small but serious modification to that is to give each struct a prototype pointer, and each field's vtable record a parent-count. What this gives you, essentially, is prototype-based structures. A struct may hold a given field, or it may delegate the value of that field to its parent, or its grandparent, etc. If it holds the field itself, it can change it. This doesn't allow you to decide dynamically which fields you get to edit after creation time, but AFAICT that's not very important functionality (I'll leave the reasoning out here, let me know if you want me to go into that). Additionally, cloning an entity is as simple as a memcpy. There's no pointer fixups required.

That's a really dense description. Let me know if you want me to go into more detail on anything.

Share this post


Link to post
Share on other sites
Amazing, thanks a lot for all your replies. I'll be sure to digest every bit of info and come back with some feedback.

Share this post


Link to post
Share on other sites
class MonsterType:
name = "Goblin"
max_hitpoints = 10
colour = "green"

class MonsterInstance:
type = getMonsterType("Goblin")
name = "Jim the " + type.name
hitpoints = type.max_hitpoints


Every goblin instance refers back to the goblin MonsterType. It's ad-hoc prototypal inheritance. Some attributes are copied at creation time, others are calculated based on or relative to the prototype values during gameplay. You can formalise this into different types of properties later if you want, but in practice I've never had to.

I'm always surprised that this comes up a lot, and outside of this thread, people tend not to spot this obvious division between types and instances. The Flyweight pattern seems to be a bit of a hack to try and pretend that no specific 'type' class exists.

Quote:
For instance, how about muds? How do they (allegedly) deal with a similar scenario?

MUDs are almost all open source. Open up a DIKU derivative (Envy 2.2 is fairly clean, as far as they go) and look for MOB_INDEX_DATA (the prototype of an NPC) and CHAR_DATA (an instance of a NPC or player).

Share this post


Link to post
Share on other sites
Thanks, everyone.

@Kylotan:
Quote:
I'm always surprised that this comes up a lot, and outside of this thread, people tend not to spot this obvious division between types and instances. The Flyweight pattern seems to be a bit of a hack to try and pretend that no specific 'type' class exists.

I think Flyweights solve a different problem. They can coexist with Prototypes. The way objects are composed is not the way their data is stored.

Your example is crystal clear - prototypes are pretty and powerful. Thanks for the link.

@Zipster:
Quote:
The downside is that if most of your data really can't be static for whatever reason, then you don't gain much by using the flyweight pattern

And that's my biggest gripe. I might as well just copy the fields I need and be done with it. It would also keep me from creating a copy-on-write .NET surrogate for instance fields. That won't be pretty.

@nem123: thanks for the explanation of copy-on-write.

@Sneftel:
V8: Their solution to avoid dynamic lookup makes perfect sense. I'm curious how they store property data, since that's something I'll have to deal with as well. However, I guess it'll be native code, likely not applicable to my problem. Had a brief look at OSTRUCT, but will consider it for inspiration.

@Antheus:
I'd have to modify V8 pretty heavily to make it fit in my current project... :)
As for javascript: I think that the language, right now, is just a façade for lower-level operations I expose through the library I'm working on. Still, it was my first choice as a scripting language. I don't like its scoping rules, but it's a damn cool language.

Share this post


Link to post
Share on other sites
Quote:
Original post by Rainweaver
I'm curious how they store property data, since that's something I'll have to deal with as well.

Pretty much the same way: The fields in a structure are packed. Because V8 uses compacting GC, they already need a way to be able to move an object in memory and have it still be the same object, with references updated properly; this allows them to move the object around when it needs to get bigger, so they can store all the fields together (and the hidden class remembers the offset for each field). My guess is that they double the size of the allocation each time, for amortized constant-time field additions.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!