Alright, sorry about the questions. But I tend to ask for the abstract and concepts more than I ask for direct solutions.

First the premises. So after rewriting a good chunk of my engine, and successfully decoupling the rendering system from the main thread -WITH INTERPOLATION! YAAAAY- I now looked into threading my entities.

So... after doing the fork join method, I realized two things.

A: The entity component system did not suit my needs at all. I quickly swapped to a Component Object design, and am having far better results.

B: Threading Component Objects is more efficient than an ECS system.

But I came to a problem. How do you schedule dependencies effectively? I tried planning out two designs on a white board.

The first one was by heap sorting the entities by their dependency count. That... came with the problem of update order being from the previous frame.

The second came by using Graph Theory, which a lot of schedulers use. Which means that each task holds an adjacency list. Then figure out an algorithm that will detect branches and push them to separate threads. But... the problem is still... dependencies are known from the last frame.

The threading system is being implemented in Lua using LuaLanes and Torch Threads, (yes it's working out well).

I understand that a lot of implementations uses a preupdate to determine the scheduling. But the only example I could find was Intel's Nulstein, which had unchanging dependencies. At least as far as I could tell.

But how do you go about this preupdate if your game world is mutable? Or is it a matter that every object has three primitive functions to call?

PreUpdate, FixedUpdate, OnFrame

I suggest you look at this differently. What is it that causes dependencies in the first place? The code is not dependent on other code and does not require ordering, the problem is all about data access the code performs while running. It is obvious to state this, but have you ever really thought through the implications? Entity component systems 'can' be extremely fast and damned near optimal over n-cores in some use cases, so the real question is what is it about a component object model which made things better? I don't mean to suggest that component object models are better or worse, I find they both have general use cases where they excel and fail, so using one or the other is dependent on your goals.

But, specifically, your description of solution points out a common thought process which I, personally, don't agree with. Attempting to precompute some form of dependency graph is self defeating. It's like using a qsort on 'mostly' sorted data, a simple bubble sort would have been faster for the use case. The same thing generally applies to executing game code, normally order doesn't matter all that much and you only have to worry about dependency in a very few cases. So, instead of sorting objects up front, which have dependencies on other objects, simply allow objects to 'defer' themselves to be executed later. The idea is that you do one pass on all objects leveraging code/data cache coherency and all the good things of not worrying about dependencies and solve the expensive case of non-linear memory access only after you have reduced the problem to the point of having a hand full of remaining items to compute.

I'm not sure the above makes a lot of sense, the point is trying to say that sorting initially in a game is basically a waste of a lot of complicated time. Let the handful of objects with dependencies identify themselves in the first pass over all objects, wasting a minor bit of performance. Compared to a big sorting tasked once a frame, taking a small number of cache hits and such in a second (or third/forth) pass over just the remaining items will almost always out perform pre-sorts.

Hopefully this suggests other ways to look at the problem..

I suggest you look at this differently. What is it that causes dependencies in the first place? The code is not dependent on other code and does not require ordering, the problem is all about data access the code performs while running. It is obvious to state this, but have you ever really thought through the implications?

I am aware that code is not dependent on code. But code -is- dependent on data. And the accuracy and order of data can be a problem. And I am merely covering loose ends in certain situations, providing a general fix for future problems with a less naïve approach, and reduce problems I have noticed. I've had instances where items that should be updated last, have found their way in the beginning of the list while the entity it's dependent on is updated last. The item in question actually lags behind.

Since I threw out the scene manager, and allowed the actors to handle their transformations if they have the component, the update order does matter a lot now.

Entity component systems 'can' be extremely fast and damned near optimal over n-cores in some use cases, so the real question is what is it about a component object model which made things better? I don't mean to suggest that component object models are better or worse, I find they both have general use cases where they excel and fail, so using one or the other is dependent on your goals

The engine is being optimized for CRPGs. The problem I ran into for ECS is several reasons.

A. Speed isn't really a problem. But complexity did become a problem. ECS is great if the game is expected to be simple. But it absolutely sucked if you planned on implementing items with different features and functionalities. Especially if a quest was attached to it. Keep in mind I am using Lua for lua, so things work differently than C++ or big daddy languages.

With ECS, I pretty much had to be ridiculously specific. Components are just data. And Systems are what processes them. That's fine and dandy if I have potions with a healing property. You'd just have a component for healing that says +20 hp or something. But, if I planned on having a potion that boosted speed, cursed the player to forever walk upside down, and take damage everytime he swung would make things difficult.

With the component system I've got set up in Lua, Components are data. But also mutable systems that can be easily defined with a Lua file.

NewObject { 
    Name = "Fire_Balm",
    Components = {
        {
        Class = "Model",
        Path = ".../Potion",
        },
        {
        Class = "Item",
        Icon = ".../Icon",
        Description = "An alcoholic beverage that will make you spew fire!",
        onPickup = funtion(character){. . .}, -- Function is optional. Argument is the character whom picked it up.
        onDrop = function(character){}, --item is dropped as normal if emtpy. dropping the item is a global function.
        onUse = function(character) { 
                    Hapazardly spew out fire while stumbling over self 
                    },
        Price = 5000 --if -#, can not be sold or bought.
        
        },
        {
        Class = "Clickable",
        onClick = Item.highlight(this),
        Color = {.5,.5,.5}
        }
    }

}

Instances of this item honestly only needs to reference to this data table. ECS forces each entity to copy this data, when the reality is.. if it doesn't change, the only copy of data it needs is transform. So when the item is spawned, it merely grabs a reference of the table.

If the item is only instanciated, then it's not assigned an ID. It's just one table that holds a reference to the table, and then an array of transforms for the current level cell.

If the item becomes unique, then it treats the table as a base, generates an ID, and stores it.

It might be less efficient in memory access, but constantly allocating in Lua has severe drawbacks. Plus, the entity update is not so slow that it needs a speed boost.

Not to mention I found the architecture friendly for modding, and rapidly adding in elements.

But, specifically, your description of solution points out a common thought process which I, personally, don't agree with. Attempting to precompute some form of dependency graph is self defeating. It's like using a qsort on 'mostly' sorted data, a simple bubble sort would have been faster for the use case. The same thing generally applies to executing game code, normally order doesn't matter all that much and you only have to worry about dependency in a very few cases. So, instead of sorting objects up front, which have dependencies on other objects, simply allow objects to 'defer' themselves to be executed later. The idea is that you do one pass on all objects leveraging code/data cache coherency and all the good things of not worrying about dependencies and solve the expensive case of non-linear memory access only after you have reduced the problem to the point of having a hand full of remaining items to compute.

I thought about that... and I believe that is a case by case scenario. I see that argument a lot where the chances of dependencies are not that common. But... I'd like to call that out as just bogus. If you have a FPS game where each character is holding onto a gun that can be dropped when they die, and picked up by another player. Each one of those guns are entities.

With 60 players on a map at once, you suddenly have 120 entities running around in the map. If 60 of those entities are dependent on the world matricies for their parent's bones for their own position -not to mention the facing of the camera for aim- you suddenly have a strong dependency. If the gun is fired, you have two things that do not care about where the gun is... but for a smoking barrel, the particle system responcible for that must be updated after the gun's position, which must be updated after the player's position.

And what of a rocket with a homing missile?

And what about a western-esque rpg? Each character is holding a weapon that can be collected after it's dropped. Bows, if in first person, needs to have an arrow that tracks the position of the bow, that tracks the position of the player and his camera.

Objects may already be in order when created. That may always be true. But there is no guarantee it will stay in order.

Sides... sorting is only... a few microseconds of frame time?

I'm not sure the above makes a lot of sense, the point is trying to say that sorting initially in a game is basically a waste of a lot of complicated time. Let the handful of objects with dependencies identify themselves in the first pass over all objects, wasting a minor bit of performance. Compared to a big sorting tasked once a frame, taking a small number of cache hits and such in a second (or third/forth) pass over just the remaining items will almost always out perform pre-sorts.

Hopefully this suggests other ways to look at the problem..

Sort of? I'm thinking along the lines of entities that depends on the position of other entities or data, with the ability to change this field. So... not just items being held. But also as a method for AI to target other AI or receive data from other AI. Probably also remove items from the update that do not need to be updated yet. Doors, Items, etc. Though that last part is less of a concern.

There's nothing stopping you from having a component that has a reference to a function that can do whatever it wants using the game's object model. Like, a component with a script attached to it, which is called when the system processes those components.



Yes, that's "breaking out" of the ECS model, but no one ever said you must use an ECS throughout your game.

Yes that's why I am using a Component Object model. Uniquely, I hadn't had the need for everything to have an Update component. I allow the physics system to update an object's transforms. As Bullet has it's own scene for handling physics, and call backs.

But detracting from the point here... Task Scheduling?

Er... off track once again. And... I'm starting to wonder if I can get a direct answer on this forum without some sort of chiding about my current architecture that is working well, and the need for a refactor would mean to completely rewrite something I am already happy with.

My components are not updated one at a time. The entity as a WHOLE is updated. I threw out the ECS because I just couldn't care for it. ECS eventually just got messy to use.

I have one GameObject class that acts as a container, and then components that attach to that. Components can be disabled, enabled, and removed at runtime. Components also do not -have- to be updated every frame. But are controlled through basic callbacks and events. GameObject is what has transforms. As GameObject is a class used for specifically Objects that must be placed in the scene. Spector is a class I have for logic that is attached to either the world or the cell.

GameObject - The name specifically states for an object that can be seen in the game. Have some form of interaction, or what ever. Basically anything that exists in space and needs to be updated, or has function that is triggered by event. Lights are forced to implement this. Why? Because lights can flicker, may be snuffed out., change color, etc., Can be turned on and off. Concidering the engine is designed for CRPGs where this sort of element is needed. I am not changing it.

GameObjects are also clones of templates. Which makes them poor use for regular logic.

Spector - Or a ghost object. Something that does not exist in the mortal plane. Soul purpose is for all logical holding that is related to a specific level or the world. Logic for puzzles, logic for checking if a boss is dead, which tells doors to open. Logic that detects if three conduits across the continent have been activated successfully. It may not hold components, but it is allowed to receive and send events to other components.

Because all NPCs and the player's controller is just an AI, A global Spector manages callbacks to game overs, character death messages, and user input.

Physics is Bullet Physics (for the love of god I am using 3D), and each component is updated one at a time. Some precautions were taken to make interactions are efficient as possible. Certain features for items are automatically turned off until explicitly stated otherwise. If a Collision mesh was detected in the mesh file, then it automatically implements rigid body. But it defaults to dynamics being turned off.

The transform (managed by gameobject) is just for logic to have data for, and is pushed off to the graphics. The way bullet physics handles, is that you send data to it's world, and get new transform data. Graphics uses a double proxy, so it has current and old data. I don't see how you'd do otherwise with interpolation -.-;

Now can I -please- just get a response to the question that was asked.

I understand that a lot of implementations uses a preupdate to determine the scheduling. But the only example I could find was Intel's Nulstein, which had unchanging dependencies. At least as far as I could tell.

But how do you go about this preupdate if your game world is mutable? Or is it a matter that every object has three primitive functions to call? PreUpdate, FixedUpdate, OnFrame

My suggestion would be to not use them. Only have a regular fixed-time update step. Having a pre-update and post-update add complexity that can generally be avoided with a bit of design.

I don't see what you described as a scheduling problem or dependency problem.

While games often benefit from having multiple cores and parallel processing, generally the core functionality of the game needs to run on minimum spec, which often means you should be able to perform your work on a single core or dual core machine. You can take advantage of additional processor if they are present, but you generally shouldn't build your game with the assumption that you can always be parallel.

I've worked on several games where the engine had a pre and post update step, but we found in practice they were almost never used, and those few times they were used tended to be work that could have been accomplished just fine in the main simulation. In one particular in-house engine (used for a game and three sequels) we ended up disabling the pre/post update steps to recover the sliver of processing time.

What specifically are you attempting to do in your preupdate step? What is it that you cannot do with one round per simulation step?

I've worked on quite a few games that didn't follow that model, and I don't think it caused problems. I don't think the dependencies are are big as you are making them out to be. They might be for your specific game implementation, but I can't readily imagine them being so as a matter of course.

The Sims 3 had a thread model superficially similar to yours. Instead of threading each component, there were several game tasks that had their own threads (audio, rendering, etc) but critically all of the individual Sim characters lived in their own thread.

We didn't have threads per component, there were lots of components that could be added and removed, just threads per actor in the simulator, and some work threads in the engine.

The simulator behaved as though everything was serial. The simulator used the threads both as an organizational tool and as a safety tool. If something happened to a thread, either it stalled or crashed, the simulator that controlled the thread would reset the Sim associated with the thread and any objects they were using, then start a new thread setting the Sim to a safe idle position.

Some actions in the simulator threads were immediately run, but much of it was queued, hidden behind the scenes inside the engine and away from the simulator. Requests to move were exactly that, a request. As a wonderful side effect of the "every sim is a thread" model, when there were requests that required a bit of time, the individual thread could be suspended or otherwise worked around if it made a blocking request, the rest of the game could move on.

With all of that, there was never really a need for pre/post update steps in the simulator for the game. If code needs a delay for time there are many options available, including using clock tools where you can add a timestamp to test against, with both wall-clock times and simulator-clock times available. If you need something to take place in the next update set the alarm for now+1.

Basically anything that exists in space and needs to be updated, or has function that is triggered by event. Lights are forced to implement this. Why? Because lights can flicker, may be snuffed out., change color, etc., Can be turned on and off. Concidering the engine is designed for CRPGs where this sort of element is needed. I am not changing it.

I'm not so certain that these need their own threads. We had similar actions in The Sims. Flickering can be done by an animated texture that is handled by rendering, or by registering a timer with a callback alarm rather than requiring a full thread. Other changes to the light, such as being turned on or off or changing color, are caused be being interacted upon by an actor in the game (using the character's simulation update) or by the player directly (UI thread).

There may be a small number of items that require their own simulator thread, but we found in practice nearly everything can piggyback off callback alarms, character simulator updates, or the UI's direct interactions.

Sorry I am a bit loopy on my thoughts with this stupid medication from the doc.

The reason for my multi-tasking is that currently Quad Core systems are actually incredibly common. Programming for just a single core isn't quite targeting the common minimum specification. It would be more like targeting walmart computers built in 2005. Plus being mostly a hobby and learning experience, it'd be pretty counter intuitive to dial back a few steps.

I am trying to have my game-objects determine their dependencies before the scheduling pass to the task threads. That is to put data dependencies in the correct order, and all strongly dependent items in the same job. Similar to what was done in Shadow Fall.

Or at least figure out how they did it, and make the technique my own. I could just very well be seeing something idealistic or not there, because I can't actually see the video myself, nor afford the costs for GDC. So context to a concept is basically slimmed down to pretty pictures and bullet points.

The Sims 3 had a thread model superficially similar to yours. Instead of threading each component, there were several game tasks that had their own threads (audio, rendering, etc) but critically all of the individual Sim characters lived in their own thread.

So... instead of tasking... you had each character existing as an OS thread. That sounds ridiculously expensive. If memory serves correctly... you had approxmiately ninety somethin lots in the sims. And god knows how many characters.

Honestly, I'd consider it if my specification were CRPGs. Which basically meant I'm limited to what seems reasonable for that design. And everyone I talk to just basically beats their chests and chants "There are overheads to threads." But if it worked in the Sims... then dear lord.

I'm not so certain that these need their own threads. We had similar actions in The Sims. Flickering can be done by an animated texture that is handled by rendering, or by registering a timer with a callback alarm rather than requiring a full thread. Other changes to the light, such as being turned on or off or changing color, are caused be being interacted upon by an actor in the game (using the character's simulation update) or by the player directly (UI thread).

Er... why do these need their own threads?