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.