Jump to content

Entity-component-system and functional programming


special_ed
 Share

Recommended Posts

How many of you have experience developing games with an entity-component-system pattern? How about writing games in general with functional programming? It would be especially interesting to me if you have experience combining both.

TL;DR (this is back story, feel free to skip)

I have this very simple and crude frogger style game that I've been toying with. I have a plan for turning it into something a lot better, starting as the relatively simple and recognizable game that we're so used to and likely not interested in (all of this functionality is already finished) but then quickly ramping it up in weirdness (which I have well outlined to avoid creeping my own scope). However, some might say that I've been "sidetracked" in the development process because of my desire to experiment with and learn new things..

I've literally rewritten the game from scratch 5 times in the past week. It's sort of okay because it's still small, but it's also one of the first things people tell you not to do when writing games. I, on the hand, am more interested in these rewrites and what I'm learning from them than progressing in the game right away. Part of it is my inclination towards learning and experimentation, and part of it is knowing that it can have practical dividends that might not be apparent because I'm preventing problems that I might have when the project grows in size and complexity.

Object-orientation

My game started in a very typical ES5 object-oriented style where I used the "new" keyword. My first major revision was porting everything to ES6+ (for built-in module system with import/export, never ending a line with a semi-colon, object spread operator, etc). When doing that I started using ES6s new class syntactic sugar, but something about it reminded me of the idea spread by FP evangelists that we as JS developers should never use the "new" keyword and that class based inheritance is a bad idea.. I then rewrote everything to use functions that return objects (factories) instead of classes. Some object types needed their own custom prototype object and used Object.create() (ones that are created a lot and have shared functions), while others didn't and simply were created by my own function that returned an object literal. This caused me some headaches because of the general lack of consistency in the way I was creating objects and how they were actually structured and accessed. The ones which weren't made with Object.create(customPrototype) required getter functions for methods to access attributes which were block scoped within the factory function by let, while the others didn't and their methods could access similar values through "this".

Entity-component-system

I then stumbled on the ECS pattern while Googling about why the MVC pattern is rarely employed in games (in the web community, MVC is the only pattern that some people know and they try to religiously apply it to everything). The most interesting aspect of ECS to me is that it was originally devised as a solution to the problems introduced by classical inheritance (which many JS developers also see as a problem), but their solution was radically different than prototypal inheritance (also solving the problems that might be introduced by prototypal inheritance, such as a failed property lookup recursing down the entire prototype chain).

The gist of ECS is that an entity is what we might commonly think of as an object. They're really no more than a unique identifier (typically an integer). Despite being nothing more than a number, you can construct "classes", "templates", or "assemblages" for actually associating these numbers to data (components), and groups of related functionality (systems). An entities position, velocity, and acceleration within the game would each be a component. Rendering and physics systems would then operate on these values and more to draw them to the screen and calculate new state.

ECS is an abstract idea, and thus wherever you look at implementations, you'll see things understood and coded very different. One common idea is that systems are associated to only one component, such as the rendering system to a "renderable" component with "renderable" being a key in an object. The key could itself be an object with all the values the rendering system needs (thus giving a degree of data privacy if necessary), but others simply have it as a standalone value and require other ways of making sure that the rendering system has access to what it needs and not to what it doesn't (or the latter idea escapes people entirely).

Some people also let systems traverse the entire set of all entities each frame in a game loop to see if they have the component of interest. This in particular was disturbing to me, so I opted for the idea of simply adding/removing an entity to a register of entities that a system traverses. On top of cutting down on unnecessary operations, this also allowed me to discard the idea of components such as "renderable", "updateable", and "animatable". This bugged me because of the ambiguity about what their actual value should be and whether or not certain values (such as position) would need to be duplicated in the case that their values would be objects to which that system was restricted.

All of these issues hint at another big implementation ambiguity: How do you actually store all of this information, and where? I still haven't quite ironed this out. I also haven't quite ironed out where some of the related functionality will come from (such as having it abstracted to a part of the game engine). Since this is JavaScript, the data structure decision is between objects and arrays. Each has inconsistent performance tradeoffs because of the functions that operate on them and how this varies between browsers. On top of data structures and operational functions, there's also the question of just how many you'll actually need.. One article recommended a wide variety: one for just entities, one for just components, one for entity-component mappings, N (number of components) to store the actual values of the components, and then further ones for all "assemblages" and assemblage/component mappings. This seemed a little unnecessary to me, but after further thought it depends on the particular game and the resources available to the game. That author was coming from the world of MMORPGs, so it makes sense. Here's the article.

My game is single player and state, at the moment, is being stored entirely in memory. Regardless of how much further I progress the game, it will never reach the point where I'm dealing with even hundreds or thousands of entities. I'm therefore not too interested in having all of these data structures floating around. Keeping one for all entities and all components seems like a prudent thing to do even if they're unnecessary, and I'm currently thinking that it could be stored along with generalized entity and component functions within a part of my engine (in the same manner that I store cached resources in the engine itself).

What I'll almost certainly need access to frequently is a mapping of entities to components along with their values with the "primary key" being either entities or components (depending on everything else). Conceptually, to me this is a 2D jagged array: indexed by entity, with each index pointing to a list of component-value pairs. Of course, this is JavaScript, so an array would have an integer index making it more suitable for a component->entity:value type of arrangement (since entities will likely come and go while component definitions remain static).

At the moment, there's no need to query by entity to get all components, which would be slow if the entity weren't the primary key. This would slow down a systems ability to look up the value of a component if a quick way to access it isn't registered. I'm thinking that any given system should generally know what components it needs to access (exceptions to this are certainly possible). A general registration process should be capable of handling everything. For instance, a rendering system might require an entities "position" component, but how do we know it knows the right name and that the name is in fact the right name? This points towards the need for either verification in the process of creating an "assemblage" (good for larger projects, especially if they have a custom interface for non-technical people to compose assemblages, which was one of the original goals of the pattern), or through a process of registration with the system (good in my case). I could get away with doing neither by simply naming everything correctly, but since registration also gives me a form of data privacy for free, I think I'll do it.

Functional Programming

I'll write more here later, since I have to leave. I've been looking at various aspects of my code and asking myself, "how could I do this more functionally?" This generally means, "how can I store and access state such that I'm not mutating values?" Furthermore, it leads to, "how can I make sure that this doesn't drastically limit performance?"

General thinking now is to minimize the impact of state changes (which can be costly because of how often the game loop runs). One idea of mine has been to fragment state into discrete units (3-tuple or even just a pair) so that the common functional method of generating new values rather than mutating old ones is less expensive. Not sure if this will work yet or how to do it if it's possible, but my first guess is this: seed systems that operate on state with initial values during registration, then if there's a change later have them forward an entirely new value to the next iteration of themselves.

At first glance, I think this has issues. A 3-tuple might work, but pairs need to be associated. If the system is a single function, then even forwarding new pair values to the next iteration would mean mutating an array or object in which they get their association. I could always forward a new copy of the entire array or object, but that's what I'm trying to avoid. Maybe a creative reorganization of the system itself could work to make pairs possible.. My conception has always been of a system as a collection of functions that iterates through it's register of entities performing operations for each one. An alternative would be the registration process setting up an array of systems to operate. Egh. Gotta go.

 

Link to comment
Share on other sites

There is no such thing as truly functional programming that actually does something.   At some point you're going to need to take in some form of a messy state, then at another point you're going to need output some form of a messy state.   Whether it's in and out from a database, in from the previous step and out to the next step, or similar.    Even taking input from the keyboard is a very stateful action in the sense that over many many cycles of whatever type of process/threading/event manager where you're remember the state and where previous state affects the current state.

That isn't to say functional is pointless, it's actually really nice to do things that you can truly pin down to an in and out problem.

_____________________________

Though the platformer I'm currently working on does mess with functional and entity based programming a bit, though with the dumber JS objects (Though I've given few cares about purity, one person touches that code).   Basically each entity has an X, Y, a communication queue, preprocessing queue, and a processing queue.  first the objects preprocessing queue runs, followed by the processing queue.   To actually get stuff done the preprocessing and processing queue can access the communication queue and change X, Y location.  For instance if my player touches something it sends something to that objects communication queue (which gives it a chance to send a kill message back, or a forced movement request back).  Player physics are ran every tick in it's processing queue with some state stored in that semi-functional function.  If an object wants to be drawn it communicates to itself, then the part of the game loop that draws everything can see that communication.

There are some things that I like.   Each object is the same object just with different processing orders shoved inside them (If I cared a bit more at keeping at my style it would be pretty easy to allow the player control process to jump between entities and make stuff just work, and  even in it's current state I could see myself making the game multi player without an insane amount of work).   Likewise I have never found it so easy to write unit tests for a game, especially for the core entity protocol (even the messy stateful physics wouldn't be too bad).   Lastly all the actual gameplay logic, and core logic are pretty separate (I've only needed to change the core logic that I made before I started on the actual game with only a small handful of lines of code).  

I'm not particularly happy with some of the end results since I can get some pretty deep stack traces for even simple logic, you can also see a lot of areas where I'm struggling with not knowing JavaScript very well, and I'm generating way too much garbage at the moment.   though these issues haven't been such a bad effort that I'm keeping them till my next game.  

You can see my earliest showable build http://lostlocus.com/   (arrows/WASD, Spacebar, F/J) Though be warned there are plenty of dragons in there(old code).   Though everything is still separated out into different files for easier readability, all the ugliness of being an early build is still there, and the parts that actually make it more than a tech demo just aren't there (actual map loading, real assets, AD hooks, and similar).   Which is also why I'm not too concerned about it walking off (that and there are some polish issues that would embarrass even a thief like the GC stutter that that version has).   Though considering that it's only about 1000 useful lines of code for a usable start to a platformer I'm still happy with it.

EDIT:  If your intention is to make a game, I don't think you're being pragmatic enough.   Though you're making great strides to teach yourself it seems.

Link to comment
Share on other sites

3 hours ago, permith said:

There is no such thing as truly functional programming that actually does something.

You're joking right? That sort of sweeping (incorrect) statement really isn't helpful in the slightest. You're trying to suggest that anyone using Haskell, Idris, Elm or Ocaml has never produced anything that runs? Or does something? Thats blatantly ridiculous. Whether you think functional programming is suitable for games or not is another discussion but those functional languages (and others) exist and are popular because they solve problems inherent when coding in an OOP style.

If you've never spent hours trying to untangle and inheritance chain or debug a race condition that is killing your code then keep programming OOP, you'll run into it, and, I expect, you will loathe the whole process because its horrendous. Once you hit the point (or numerous other ones relating to the bad points of OOP) then you might understand how and why functional programming exists and you'll be in a better place to comment or where each style can be used and how aspects of each can work cooperatively.

3 hours ago, permith said:

it's actually really nice to do things that you can truly pin down to an in and out problem

What, like every programming problem you mean? That is simply how computers work, if you think computing problems differ in any way, then get reading up, current methods of computation (which inherently have not differed very much since Babbage and Lovelace started this endeavour) don't allow anything else.

On 20/11/2016 at 4:04 AM, special_ed said:

General thinking now is to minimize the impact of state changes...  I could always forward a new copy of the entire array or object, but that's what I'm trying to avoid.

Functional languages often go hand-in-hand with immutability (although they don't have to) which means you'll be creating and passing on new state object/s for every mutation, whilst handling this is a performant manner is usually a language-specific task modules like ImmutableJS exist to try and add this feature to JS. I can't see that a frogger game would ever have enough state to worry anything but old mobile devices, even with JS, but part of the idea is to have a minimal representative state of the system in any case and perform functions to move that state from its canonical state into its presentational or usable state, this is very often done in some kind of rendering layer although it forces you to really consider the use-cases for your data which is always a good thing.

From my personal experience of creating several fairly (to very) complex web applications almost entirely in a functional style I can tell you that performance often gets a boost, despite it sounding counter-intuitive, I'd attribute this to thinking more clearly about how data flows through the system as a whole and adopting stronger patterns. However, your typical web application and game differ, in this regard, in one very important way, and that is the frequency of mutations. Generally the frequency of state mutation in gaming is far far higher than other types of application and this is a real problem, I'd go so far as to say its likely insurmountable for some types of game.

If you're after more examples of a functional style or common patterns to adopt check out Elm, there are many theoretical articles and discussions on the site that explain what drove the development of the language. Those theories have been widely adopted in many JS libraries and even frameworks over the last year or so.

If you're asking for some reassurance that FP is a good style for JS programming then, yep, just check out the popularity of libraries such as React (and the many React-likes), redux, cycle, even cerebral, all lean heavily on FP patterns and theories. Not to mention FP libs like Ramda, even Lodash has jumped on-board and rewritten their entire suite of tools in an FP style.

Link to comment
Share on other sites

@Permith

I think your oppinion about functional programs having dirty intermediate states comes from the fact that you're using basic JavaScript Objects as variables. If you write things like player = player.setPos(100, 200), first the object's x will be set, then its y, then the same object with modified fields will be re-assigned to the player variable. Inbetween it will be in a dirty state, so async events, like input, might get either version (player before call, player with new x/old y, new y/old x, new x and new y).

In a functional language, first a new position object will be created, this will be attached to a copy of the player object, and then this new object will completely replace the player object. As even asynchronous calls will not find a global state to just pull some data "from exactly now", they will never be able to receive any intermediate, dirty objects. In a more relaxed approach, when global variables can be changed atomically, you'll still have valid objects, either from before or after the update, but never inbetween (think update locks the object until it's done, though that's not true, the concept applies).

To get this behaviour in JS, you'll need to use implementations of real immutable data, like Mori.js or immutable.js.

FP and ECS pattern

Years ago I implemented a platform game on Java using the ECS pattern. A basic entity did just provide position, an update, and a render interface, as well as a list of components and sub-entities (like, Player has a Weapon). Whenever a component was added, I had it added to the list and registered at a system (maybe it could fall, so it got a Gravity component that registered to the physics system, or some entity should be the player figure, so it got a PlayerControl component that registered with the input system, you get the point). Each time step the systems processed an update of their registered components, then the entities combined all update instructions from their components to update their positions. It looked very tedious in the beginning, but once the basic skeleton and all the first entities were finished, I was amazed at how easy I could introduce complex behaviour of anything by simply adding or removing some components from it.

Some time ago I began to learn functional programming, and for about two years I've only been writing OOP-style when forced at gunpoint, for some of the reasons MattStyles mentioned, and some more. For web games, I don't write JavaScript when I can avoid it, but write in ClojureScript and transpile to JS.I'll give you some basic points of my way of writing FP games (though writing pure JS/ES6, your experiences may be far different), which works well, though it may be inherently terrible.

  • My game loop models all game events as input queues, and it maps updates of the game world to them in reactive-fp style. That means, anything that requires any change to the game world starts an iteration of the game loop; be it a small change like "increase score", or a big update like "time step". So things like input or logic updates can be done immediately, without waiting for the next drawing loop to finish, while all rendering and global time updates will still have a consistent, finalised state (now, if we could easily delegate rendering to another thread in JS, we could have insanely fast and responsive games...)
    • FP doesn't mean you don't have a state. Every game loop iteration just receives the current world state, swaps out some values and returns an updated version. The point is, no one else does swap out values, especially no arbitrary keypress or anything
    • Yes, time is just a game event
    • User input, entity hit, level solved etc. doesn't do anything on its own, but just put another message to the event queue
    • One advantage: if objects moved so fast that collision locations can't be detected correctly, we still have the previous (input) state availiable and can move the objects back in time for fractions of the delta time until we get a clean situation to solve and output that state
  • Basic data in CLJS is organised in maps. That allows to swap single elements for freshly created ones with constant/linear time access (depending on implementation of the maps). The thought behind it might be similar to your tuple/triple idea. Once again I call out the words "Mori.js" and "immutable.js"
  • Some of the ways I created to update entities and all of their components in the past:
    • Chain all systems, make them act on all entities, but only if they have attributes that system acts on. Bit of slow-ish
    • Group entities by classes, make systems act on their relevant entities. Great until an entity has too much components and you can't decide where to group it
    • Factory style: genereate functions for entities that receive themselves as argument and return updated versions of themselves, chain all those functions on update. Put each entity's functions in a list/array inside itself. Actually working quite well
    • Chain all systems, but make the function calls multi-methods; applying different methods based on the registered components. Very similar to the first version, but more elegant to implement, don't know if that's possible in JS

After all, I agree - combining the Components with the immutable data set is the greatest challenge, and there is no canonical way to do that; as always it depends on what you're trying to achieve.

I'm not sure if it's of any help, but at least you'll know that it's quite possible to create FP/ECS games ;-)

Link to comment
Share on other sites

@mattstyles   I think my original intention would have been better stated like this:   In any programming paradigm that you follow, as long as you follow it well you'll be able to get work done easily.   But you'll have to break out of your paradigm at some point to eventually interact with other software and that is where it will get messy and frustrating.       (Annoyingly enough my original post did need some bashing though, though I hope my post didn't praise OOP though).    The game I showed also did a good job of all the bad that will happen when you badly try to mix different programming paradigms, even if you will get a nice advantage out of it here and there (I imagine badly since it does get pretty close to just being entity component pattern) .

Link to comment
Share on other sites

7 hours ago, permith said:

I think my original intention would have been better stated like this:   In any programming paradigm that you follow, as long as you follow it well you'll be able to get work done easily.   But you'll have to break out of your paradigm at some point to eventually interact with other software and that is where it will get messy and frustrating.

I'd disagree here (but not wholly), Redux is a prime example, it basically follows functional principles but not too strictly that you couldn't use it with some traditionally OOP structures.

I think part of the joy of using JS is that both functional and OOP can exist at the same time, there are many many aspects of functional programming that make perfect sense to mix in to an OOP architecture. Libraries extolling FP like Ramda, lodash/fp and Lazy work perfectly well in an OOP world. Going full-bore FP is very difficult for OOP-trained devs (which is most of us) but its relatively easy to dip your toe in and pull out FP techniques, later on you can learn more about true FP and see what other lessons you could learn there.

Conversely, if you're full-bore FP I'm not sure how many OOP techniques would be useful to you.

Libraries like Mithril and Cerebral use an mvc pattern but use many FP techniques to achieve their goals.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...