Author Topic: OOP, ECS, Roguelike, and definitions  (Read 7066 times)

Omnivore

  • Bishop
  • ***
  • Posts: 152
    • View Profile
OOP, ECS, Roguelike, and definitions
« on: February 11, 2016, 03:51:49 PM »
These days we're bombarded with one liners, "OOP is bad!", "ECS is the way!", "New Roguelike game!".   Definitions, its all about definitions. 

OOP.. which OOP?  which part of OOP?  which application of OOP?  Like any other part of programming, there are good and bad uses.  I'm not even going to try to enumerate them here, much less address them.  OOP has a place, it fits some things, doesn't fit others.  Misuse of pattern classifications and concepts are a similar, related, even coupled, issue - to me, patterns are for review and refactoring purposes, *not* for up front design.  But hey, good uses, bad uses.

ECS... again which ECS?  The ECS as used in Unity3D?  The ones described here: http://entity-systems.wikidot.com/?  Maybe the one in this paper http://www.dataorienteddesign.com/dodmain/?  None of them are the same.  Some include OOP concepts, some are rabidly anti-OOP.  Which variant fits which problem space?  What are the costs and benefits?  Good uses, bad uses.

Roguelike - fooled you, not even going to touch this one. :)

Personally, I recall years ago, in another conversation, practically another lifetime, saying "it's all about the data", and when it comes to OOP, ECS, and Roguelikes today, I'm saying "it's all about the data".  As an experiment or proof of concept I'm taking 50+ years of relational database theory and practice and using that - I mean if they haven't gotten it right after all this time, no one has.  No, not sticking SQLiteDB ::memory:: in my game and running SQL against it, but organizing, structuring and accessing my game data in an equivalent manner.  Advantages, disadvantages, we'll see.  No, I'm not calling it ECS, its RDM if you need three letters (Relational Data Model).  And *gasp* it uses OOP in places!!

Anyhow, just had to hop on the bandwagon,
Have a good one,
Brian aka Omnivore




« Last Edit: February 11, 2016, 04:45:59 PM by Omnivore »

Krice

  • Troll
  • Protector of the @
  • *****
  • Posts: 2147
    • View Profile
    • Email
Re: OOP, ECS, Roguelike, and definitions
« Reply #1 on: February 11, 2016, 05:34:09 PM »
I think it doesn't matter that much if you are able to create a game. But I think in generic programming things like modular and data-driven designs are very clever in large scale programs which a major roguelike can be. OOP happens to be more modular by design than procedural languages, but it doesn't prevent "less" modular programming, at least in C++. There really isn't one perfect way to do things, otherwise we would be all doing exactly the same thing.

Kyzrati

  • High Priest
  • ****
  • Posts: 447
    • View Profile
    • Grid Sage Games
    • Email
Re: OOP, ECS, Roguelike, and definitions
« Reply #2 on: February 14, 2016, 02:33:56 AM »
Roguelike - fooled you, not even going to touch this one. :)
I love this part.

And I completely agree with you--that's how I approach it, too. Data is what matters most, and on top of that whatever works for a given situation goes, e.g. OOP, composition, etc. Really though, anyone who can take whatever they've chosen to use and make a complete game with it is "right."
Cogmind - Sci-fi Roguelike (devblog) | X@COM - The X-COM RL | REXPaint - ASCII art editor

Omnivore

  • Bishop
  • ***
  • Posts: 152
    • View Profile
Re: OOP, ECS, Roguelike, and definitions
« Reply #3 on: February 15, 2016, 04:31:00 AM »
Thanks Kyzrati :)

The last few days have found me waffling a bit around different languages and various configurations, and at one point I found myself back in Python doing some refactoring of the data representation I use in that language.  It struck me, that it might be of some interest to those who have completed the Python tutorial, and/or those who have wondered about how data is modeled in an ECS or similar approach.  So, here goes.

It is really easy to run into the 'god' object when you are representing your player, mobs, items, and other things in a roguelike game.  I don't believe I need to convince anyone that, in anything other than the simplest games, the 'god' object is going to cause you problems.  However, let's set aside all those problems, and just look at the data.

The 'god' object just throws all the data into one place, it has 'slots' for every single type of data in the game.  The Python RL tutorial introduces you to the concept of composition.  Composition is, as far as the data is concerned, grouping related data together into manageably sized chunks.  Another concept that you quickly recognize the value of, is assigning a unique number to each entity in your game, makes it easy to decouple entities from each other and use hashtables and such to map from your unique id number to the entity you want.  Lets stop here and look at what we have.

Open up your favorite spreadsheet program.  Create a blank worksheet.  Now imagine that each column in that worksheet is a type of component holding related data.  Down the sides (the rows) are your entities.  Let's make the first column a special component called EntityID, that holds a unique number.  Now every cell won't have data in it for every entity.  Some are going to be empty.  Lets call empty cells nulls. 

Again, looking at the columns in the worksheet, think about how those are your components, your groups of related data.  Each column is probably represented in your code by a class, or maybe a struct, doesn't matter which really.  We can say that we have (or should have) a type corresponding to each column.  Examining the data requirements, we can pretty quickly realize that we shouldn't have (and really don't need) more than one column of the same type per entity.  Even if we did, or maybe if we need more than one instance of a particular data item inside a component, we'd just use an array or some other collection for that item.

For anyone who has any database experience, there's probably a light dawning.  Being able to represent our data model in a flat spreadsheet means that really we're just looking at one big table full of records in a relaxed first normal form.  Relaxed because we have nulls (empty cells).  You could, if you wanted, organize your data into a higher normal form, and you'd start to see something similar to a class hierarchy form.  But it gets complex rather quickly, we soon need special columns to hold the ids of things in other tables, and so on.

The OOP approach (not using composition) could also be done, but runs into the same problems or worse, depending on what language you use and how you structure things.  So lets go back to that simple spreadsheet model, keep things simple.

At this point, we have entities and we have components.  Some people more or less stop here, maybe even back up a step and create a small hierarchy of classes to hold mostly non-overlapping collections of components.  Well, we've been talking about the data, but we've been leaving out how we manipulate it.  Looking at how we manipulate the data, even without getting into details, we can see we've got a couple problems.

The two biggest problems you run into at this point both boil down to the same thing, while we've expressed the primary relationships of our data, we haven't addressed the secondary ones.  Consider, with our behavior in our components, or maybe still some in the entity even, we run into problems where one component needs to talk to another.  This is actually harder to deal with than talking to a component on another entity.  Mainly because we either have to be able to go from component -> entity -> component without getting tied up in circular references or storing a copy of the parent entity's id everywhere. 

I'm not going to tell you you can't keep your behavior in your components, maybe turning your entities into switchboards or mailmen, but I am going to tell you it will likely create non-trivial problems.  It gets worse when you find yourself wanting to modify the component mix on your entities at run time.   Throw events into that, and we can quickly get ourselves into a snarl.

So what's the solution?  Realize that many of the problems you are running into with methods from one component calling into another (or grabbing data from properties on another), would be solved completely if you had access to everything you need at the start of the method.  One way to do this is to turn your entity into a switchboard, but.. there's another approach.

Systems.  Horrible name really.  Better would be Processes.  Take the troublesome behavior code out of components and put them in a separate function, even a static function (or free function) completely outside your entity/component model.  Reorganize your program flow so that you are passing the necessary data into each process in turn.  Yes you're violating the heck out of a bunch of theoretical OOP constraints at this point.  But, many have found this to be a viable solution.

Now, not trying to be a salesman, just an explainer (and probably a bad one), however i am going to say "But wait!  There's more!" :)

Once you've moved the code outside of your components, you can start to work on organizing your program's flow so that you reduce the need for much of the event wiring.  Realize that the existence or non-existence  of a component type on an entity can change program flow.  It quickly boils down to individual use cases so explaining it is difficult for me.  An example I read elsewhere that made sense, was consider a healthy mob.  There's no reason for it to have a health component.  It isn't wounded, so its automatically at full health.  Since our natural healing process only runs on entities which have a health component, it'll automatically skip the ones at full health.  It'd be pointless to process them anyhow, but without a health component, its an automatic de-selection. 

What do you do when the mob gets wounded?  Simply add a health component to the entity that represents the mob.  You can apply the same general ideas to command flow, to effect calculation, and so on.  It gives a nice, well defined, clear step by step route through your code.  That is the Systems part of ECS.

Wrapping this up, I hope the above explanation helped someone understand the concepts better.  It isn't the only way of course, but I think it is worth taking a look at depending upon your game's needs.

Have a good one :)
Brian aka Omnivore



reaver

  • Bishop
  • ***
  • Posts: 207
    • View Profile
Re: OOP, ECS, Roguelike, and definitions
« Reply #4 on: February 15, 2016, 09:33:05 AM »

  An example I read elsewhere that made sense, was consider a healthy mob.  There's no reason for it to have a health component.  It isn't wounded, so its automatically at full health.  Since our natural healing process only runs on entities which have a health component, it'll automatically skip the ones at full health.  It'd be pointless to process them anyhow, but without a health component, its an automatic de-selection. 

What do you do when the mob gets wounded?  Simply add a health component to the entity that represents the mob.  You can apply the same general ideas to command flow, to effect calculation, and so on.  It gives a nice, well defined, clear step by step route through your code.  That is the Systems part of ECS.


That sounds like premature optimisation to me, and actually not well defined at all. Actually sounds like a terrible, terrible idea! :)

1) What if you need to check if an entity has health? Do you keep another variable for that? Otherwise, if a mob doesn't have a health component, it's either invulnerable, or at full health.
2) Do you think the cost of creating a component and defining its data is computationally more efficient than N Processes iterating over the component?
3) What do you do if a monster goes back to full health? delete the component? Again, you think that creating and deleting components would be cheaper than iterating and checking for a condition?

Krice

  • Troll
  • Protector of the @
  • *****
  • Posts: 2147
    • View Profile
    • Email
Re: OOP, ECS, Roguelike, and definitions
« Reply #5 on: February 15, 2016, 10:10:39 AM »
What do you do when the mob gets wounded?  Simply add a health component to the entity that represents the mob.

That is your idea of "simple"? You are clearly overthinking and need to stop. If you take OOP as an example I think incredibly many people don't really get it properly. You can see it often in use of composite classes when they substitute inheritance - boom, you failed. Then again there is nothing wrong with classes (objects) as part of a class when they are data types which don't try to substitute inheritance. OOP is a difficult concept so if you don't understand it right away it's not embarrassing, but you need to understand what you don't yet know about it. C++ is even more difficult because it allows you to break OOP (which in some cases may be useful).

Omnivore

  • Bishop
  • ***
  • Posts: 152
    • View Profile
Re: OOP, ECS, Roguelike, and definitions
« Reply #6 on: February 15, 2016, 10:40:54 AM »

  An example I read elsewhere that made sense, was consider a healthy mob.  There's no reason for it to have a health component.  It isn't wounded, so its automatically at full health.  Since our natural healing process only runs on entities which have a health component, it'll automatically skip the ones at full health.  It'd be pointless to process them anyhow, but without a health component, its an automatic de-selection. 

What do you do when the mob gets wounded?  Simply add a health component to the entity that represents the mob.  You can apply the same general ideas to command flow, to effect calculation, and so on.  It gives a nice, well defined, clear step by step route through your code.  That is the Systems part of ECS.


That sounds like premature optimisation to me, and actually not well defined at all. Actually sounds like a terrible, terrible idea! :)

1) What if you need to check if an entity has health? Do you keep another variable for that? Otherwise, if a mob doesn't have a health component, it's either invulnerable, or at full health.
2) Do you think the cost of creating a component and defining its data is computationally more efficient than N Processes iterating over the component?
3) What do you do if a monster goes back to full health? delete the component? Again, you think that creating and deleting components would be cheaper than iterating and checking for a condition?

It may well be premature, though the example came from a highly optimized C++ implementation (not a rogue-like).  We're speaking of code that includes optimizations like data transforms to avoid branching and minimal branch state machines, and a few other things that frankly were over my head.

1) No you need no other variables.  The absence of the health component indicates, in the original, a mob at full health.  The value of full health came from elsewhere, perhaps even a calculated value.

2) Yes, again in the example case, we're merely talking about a struct in a sparse array.  No memory allocation involved.  I believe the implementation also sets a bit field in a mask that used to determine what components an entity has. 
In any event, when the health was modified from the original full health state, it would require modifying that data anyhow.
 
3) Yes, though its simply clearing the slot in the array, depending on implementation it may clear a bit field as well. 

Realize that in the original case, we're speaking of large numbers of mobs that don't have to have associated data loaded into cache in order to calculate and apply the correct health restoration rate.   Evidently the performance gains outweighed the costs. 

I would have preferred to have a different easy to explain example at hand that was more germane to rogue-like games, but the other uses of the technique that I'm currently aware of tend to be in more complex cases.  I have made use of the technique to apply lasting effects, but describing how that works would take longer than this entire answer :)  I also use it in command routing, but unless you understood the entire process, it wouldn't make sense.  In both of those cases, the costs of creating and discarding a handful of objects per second seems a small price to pay for the problem simplification, convenience and stability guarantees.

Really though, it was a minor part of the information presented.  The most important part was, in my opinion, taking the time to look at how your data is structured, manipulated, and processed.  That has value whether no matter what model you choose to use.

Hope that answered your questions,
Brian aka Omnivore

PS:  Didn't remember it until I'd finished the above, but the same ability to transform a mob's data representation (swap out components) makes it very easy to transform the mob from one state to another - including polymorphing and dying (turning into corpse).  The changes automatically route the processing of the mob to the correct systems, in addition to eliminating the need for fixing up any references. 

@Krice: Yes, it is a very simple example.  In fact, thinking it over again, I think it was a very good example as it illustrated the method involved.  Now we can argue all day long if the goal achieved was worthwhile, but in the end, that doesn't matter.  Simply that the example shows how a change in the mix of components belonging to an entity can be used to modify how the entity is processed.  It is a very valuable, powerful, and useful capability.
« Last Edit: February 15, 2016, 10:49:29 AM by Omnivore »

reaver

  • Bishop
  • ***
  • Posts: 207
    • View Profile
Re: OOP, ECS, Roguelike, and definitions
« Reply #7 on: February 15, 2016, 10:59:20 AM »
Don't get me wrong, I'm all pro ECS (especially for RPGs/roguelikes), and I've been using it already. Ok, if the implementation is indeed very optimized, it's rather unlikely that they would have done a bad job at this. I guess my problem is that the creation/deletion of a component to prevent a process from accessing is nonsense nowadays, but if conditions A, B, C etc apply (optimised implementation, simple initialisation, cache limitations, etc), then it could have some foot to stand on. But if you don't include this context along with it, it's bad idea and bad advice I think.

Omnivore

  • Bishop
  • ***
  • Posts: 152
    • View Profile
Re: OOP, ECS, Roguelike, and definitions
« Reply #8 on: February 15, 2016, 11:10:27 AM »
Don't get me wrong, I'm all pro ECS (especially for RPGs/roguelikes), and I've been using it already. Ok, if the implementation is indeed very optimized, it's rather unlikely that they would have done a bad job at this. I guess my problem is that the creation/deletion of a component to prevent a process from accessing is nonsense nowadays, but if conditions A, B, C etc apply (optimised implementation, simple initialisation, cache limitations, etc), then it could have some foot to stand on. But if you don't include this context along with it, it's bad idea and bad advice I think.

Well I agree that it would be a bad idea to apply to a roguelike, and I probably should have noted that.  On the other hand, it did serve to show a simple example of the technique - just not a good application of it where roguelikes are concerned.  The ability to transform entitys on death probably would've made a better if substantially more lengthy example.  As for the other uses I've found for the technique, you'd pretty much have to look at the source where they were used and have the context explained before it would make any sense, it still may not make good sense, but there ya go :).

A part of what I was attempting with that post was to show just how wide and varied the ECS topic is.  There are four people I speak to on a regular basis who all use ECS in one form or another, but no two of us use the *same* form.  In fact, the representation I have in C# I don't even call ECS, even though well technically it is - just became tired of all the confusion.  I was hoping my post would clarify things a bit, but eh, better luck next time I suppose.

Twisting in the wind,
Brian aka Omnivore

Omnivore

  • Bishop
  • ***
  • Posts: 152
    • View Profile
Re: OOP, ECS, Roguelike, and definitions
« Reply #9 on: February 15, 2016, 11:20:35 AM »
OOP is a difficult concept so if you don't understand it right away it's not embarrassing, but you need to understand what you don't yet know about it. C++ is even more difficult because it allows you to break OOP (which in some cases may be useful).

This just takes the cake.  I was doing commercial OOP in C++ in the Win32s days and for quite a few years afterwards.  Setting humility aside, I was damn good at it, and I have a thorough understanding of OOP.  Your assumptions are asinine and insulting.

Omnivore

Krice

  • Troll
  • Protector of the @
  • *****
  • Posts: 2147
    • View Profile
    • Email
Re: OOP, ECS, Roguelike, and definitions
« Reply #10 on: February 15, 2016, 04:31:23 PM »
I was doing commercial OOP in C++ in the Win32s days and for quite a few years afterwards.  Setting humility aside, I was damn good at it, and I have a thorough understanding of OOP.  Your assumptions are asinine and insulting.

It's hard to say. Being a "commercial programmer" tells nothing about the skills of the person. OOP can be very well understood only in superficial level. It happened to me also, so even I wasn't clever enough in my early days.

CaptainKraft

  • Priest
  • **
  • Posts: 60
  • I make nerdy stuff
    • View Profile
    • GamesKraft
Re: OOP, ECS, Roguelike, and definitions
« Reply #11 on: February 24, 2016, 06:54:35 PM »
I came to see what Krice had to say and stayed for the great explanation by Omnivore. I like your approach to your ECS, primarily because you actually took a minute to look at the data and make a decision based on what you saw. To me, it seems like most people just pick some system that they heard was good and then assume it is what they need for their own solutions.

Also, I'm curious how you implement the database model. It sounds like there is a lot of wasted space due to the sparse nature of the table I'm imagining. And how do you keep your searching efficient with such a table as well? (I'm genuinely curious because I've never implemented a database myself. I've only used them and been unhappy with their performance)

Thanks
Build a man a fire and he'll be warm for a day.
Set a man on fire and he'll be warm forever.
GamesKraft

Omnivore

  • Bishop
  • ***
  • Posts: 152
    • View Profile
Re: OOP, ECS, Roguelike, and definitions
« Reply #12 on: February 24, 2016, 10:21:33 PM »
Also, I'm curious how you implement the database model. It sounds like there is a lot of wasted space due to the sparse nature of the table I'm imagining. And how do you keep your searching efficient with such a table as well? (I'm genuinely curious because I've never implemented a database myself. I've only used them and been unhappy with their performance)

A pure database solution, even using something like a SQLite3 ::memory:: database, spends a lot of extra time on things most games don't need: transactions, interpreted SQL, etc.  They are also optimized for use with a different level of data normalization than what I used in my explanation.  Note that the more typical normalized database representation in part trades speed for data compaction.  For a database, which is usually i/o bound, this is a good tradeoff.  For a game, not so much.

The model I have come to prefer is more of a spreadsheet model.  It is still a relational database, just at a different level of normalization.   This leads to, as you've noticed, a sparse memory layout for many columns.  There are a number of ways to implement a sparse memory array, but before I get into them, let me address the other portion, that is querying (or searching).   

There are effectively two keys required to get to any individual piece of data, namely the row id (entityId) and the column id (component type id).  If you use integers for both ids and represent your entire model as a 2d array, you have 2 dereferences minimum to reach any piece of data.  Of course, this results in a lot of wasted space, which may or may not be a problem.

If the wasted space is a problem, there are at least two directions to go in discovering a solution.  The first is, use hash-maps.   This is a simple solution, has an average lookup cost not much worse than a 2d array, and is far more space efficient.  It probably isn't going to be as cache friendly but in a roguelike that's not typically a concern.  The second method I've seen is sparse arrays, in particular the multilevel variant (rather than the trie based ones).  By splitting an array into an array of arrays, you double the lookup cost but replace gaps in the sparse array with single null entries in the primary array.  In the end though, for a rogue-like (and for that matter as first draft in any implementation), use hash maps (dictionaries/tables/whatever they are called in your language of choice) because they are simple to use.

So recapping, the model I use is still technically a relational database, but in practice most resembles a spreadsheet.  Any piece of data can be found from its row id (entityId) and its column id (component type information).  A simple hashmap of hashmaps can efficiently represent this model and still has an average cost of O(1) for random access.

There is a situation that can arise with fine grained components (fine grained meaning broken down to the level of one or two variables per component), where you want to only process rows which have non null entries in multiple columns.  While not strictly necessary, if you find this to be a bottleneck in performance you can add a 'key-fits-lock' column (typically a bitset) which allows you to quickly answer questions like: does this row have non-null entries for columns a, d, g, s, t, and w.  It is an optimization so rather than implementing it to start with, just encapsulate the question so that you don't prevent easy refactoring later.

Typically though, your access should be centered around the columns.  For instance, I can access all of my actors by iterating through the key-value pairs of my energy_state column.  The set of active actors who also have commands to process then becomes iterating through the energy_state column entries and checking to see if, for each actor key for a positive energy_state, a corresponding next_command column entry exists.

Hope this helps,
Brian aka Omnivore

Krice

  • Troll
  • Protector of the @
  • *****
  • Posts: 2147
    • View Profile
    • Email
Re: OOP, ECS, Roguelike, and definitions
« Reply #13 on: February 24, 2016, 10:33:22 PM »
Can someone explain what the fuck am I reading?

Omnivore

  • Bishop
  • ***
  • Posts: 152
    • View Profile
Re: OOP, ECS, Roguelike, and definitions
« Reply #14 on: February 25, 2016, 05:52:30 AM »
Can someone explain what the fuck am I reading?

Dude, it is simple, it is just modeling your data as a tessellation of n-dimensional Euclidean space by congruent parallelotopes

Hope this helps,
Brian aka Omnivore