-
-
Notifications
You must be signed in to change notification settings - Fork 881
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Some implementation Questions #53
Comments
Uhm... Did you close the issue because you found the answers in the meantime? |
oh i think i missunderstood another thread where you said how to contact you. yes i would love to hear you point of view should i reopen it ? |
Not a problem, it's fine. Just asking. So far, all what you can do is to create a bunch of factories to assign the right components to an entity when you create a concept. It's easier than this. 3 and 4. Honestly I can't help you with a components model based on hierarchies because it's not the way I do it usually and I'm not accustomed at working with hierarchies of components' types. |
ye this is a new thing for me i allways implemented a ecs on my own and it allways had logic in entities. i guess imma try this way out thanks for sharing |
You're welcome. Feel free to contact me if you need help. |
Hi there. Regarding question 2, I'm facing the same challenge. However, my problem isn't transformation but mapping the hierarchy. |
Maybe another solution to consider is having a 'parent' and 'depth' field in the 'transform' component that holds the id of the parent transform and then sort them by the depth before looping, so transformations are guaranteed to propagate from parent to child? Unless there's a fast way to loop all 'transform' components that don't have a 'parent' component on the same entity, that way it won't be necessary to store that data in the transforms at all |
I think I got it: a |
This may be of interest. Especially, the Transform Matrix System section. |
Thank you @Kerndog73. Yes, that's exactly what I meant with a new entity pool for each hierarchy 'depth'. However, I realized that has too many pitfalls, for example you have to copy components between registries what's not an easy task and currently not supported in entt. For a tech demo like that it doesn't really matter though, but that won't be a flexible solution for an actual game. |
@Alan-FGR
Copying components is straightforward actually:
But you've to ensure the mapping between the two registries in term of entities and it could be annoying.
Does it sound good? What other problems you encountered along this path? Do not hesitate to ping me with requests for features on the line |
@skypjack thank you for your reply. No worries, you're not late at all and it's great to see such a wonderful dev support here 😃... |
@Alan-FGR What i did (on that space battle article) is designed to work stupidly fast and fully multithreaded on an scenario where everything is dynamic. It was inspired by the paper "pitfalls of object oriented programming). Im dynamically generating a "scenetree" where each tree level is stored in a separated array. The whole thing is regenerated every frame, and then i do a parallel iteration to build the final matrix from depth 0 to the max depth. The thing is that you dont have to generate it dynamically every time. In a normal game, you have dynamic objects and static objects. Both ue4 and unity have this distinction. In planning for some even bigger tech demos i thought of having 2 transform types. A static transform, and a dynamic transform. The static transform would be just a reference to the scene tree, while the dynamic transform would get regenerated all the time. When rendering, first i would iterate over the entites with StaticTransform, and use that handle to get the (already calculated) final matrix to store it on the RenderTransform component. After calculating the static objects, i would do the whole "dynamic scenetree" on the dynamic objects to also calculate their RenderTransform component (dynamic objects as childs of static objects would work completely fine, but not in reverse). Then the render system just renders everything by sending the RenderTransform to the gpu. A thing to remember, is that you dont need to keep all your data in the ECS registry. There is nothing wrong with storing things in a specialized data structure (like a scene graph) for efficiency. Ive heard of people that just have a completely normal scenegraph as usual, and they have a "SceneNode" component that just holds a handle to the "actual" scenegraph node (wich has parent + child pointers) Of course, keeping data outside of the ECS itself means you cant use the snapshot features to serialize the ECS, but would need to augment it with your own. To help with this kind of things, the unity ECS has added "System State Components" wich are components that are linked to a system instead of an entity, and when the entity is destroyed, its system state components are not destroyed, but they are flagged as orphaned or similar, so the system can perform cleanup accordingly (you can use the events for this with Entt) |
@vblanco20-1 Thank you for your reply 😃.
I thought about that too, but even if you've static and dynamic transforms, without a dirty flag you still need to update the dynamic transforms in the correct order, and you get O(n²) anyway.
I've certainly considered some approach like that... keeping a separate tree of entities that simply maps their hierarchy, independently from the 'flat' entities registry. But that's not gonna be very performant. I have found this however, that describes an approach that I think is by far the best way to go. Basically each transform that's been updated is moved to the end of the registry and a 'dirtyStart' variable is decremented. Then these 'dirty' transforms at the end of the registry are sorted so that parents always come before children, but they're not completely sorted, it doesn't matter if there are other transforms in between as long as overall parents always come before their children. That way you just loop from 'dirtyStart' to the end of the registry and update the world matrices as usual. I don't know however if I'll face some problems implementing that in Entt, please let me know if there's anything I should be aware of 😉. @skypjack Since this discussion grew quite substantially, maybe I should open a new issue so other people will benefit from it too since my question is specifically about ordered data propagation... maybe you could tag these issues/questions with a "Q&A/FAQ" label too even if they're closed, so later on they can be linked from a Wiki or something... |
Not O(n²) in any way. You regenerate the tree and iterate it in top to down order. It is exactly O(n) Even the "sorting" to add the dynamic objects to the dynamic tree is still O(n) becouse you arent really sorting, just inserting into the level arrays. I havent tried the static+dynamic version, but the dynamic version ran at a seriously stupid high speed. My next tech demo is going to be a 2d shooter with time rewind mechanics i want to try to put on the browser, will write about it once i have it. |
@vblanco20-1 I'm sorry but I don't understand how it's O(n) unless you're caching the world transforms. Are you talking about looping the tree from roots to leaves and passing the parent transform as an argument? Other than that if you need it to be CPU-cache friendly by looping a flat list and not cache matrices internally I really don't see how it won't be O(n²) since you're recalculating the whole transformation chain aren't you? |
Looking at the code would explain it easily, but i didnt put it public for now. The algorithm is really simple:
Thats it. The idea is that you are iterating roots to leaves, and this means that when you do a "get parent transform" it doesnt need to recalculate anything, as it was calculated on the step before. The total number of iterations is 1 full iteration (to calculate local matrix + add to "tree"), and then a second full iteration (only childs) to calculate the world transform with their parent. The biggest hit of performance is that on the "get parent" transform, thats probably going to be essentially random access, wich can fuck with cache a bit. Doing it sorted could be faster but would need sorting overhead. My implementation calculated 140.000 transforms in 4 ms, of wich 1.5ms were spent on the initial iteration and local matrix building (plus insertion into tree), and then 2.5 ms for the parent transformations. scaled to 8 cores on a ryzen. The benchmark was a ton of little spaceships, each of them had the spaceship "core" at root depth, then the left wing as child of the core, and then the right wing as child of the left wing. |
Yes, I see how that would work, it's certainly O(n) but the problem is you're looping all transforms. You don't need to recalculate what didn't change, and when stuff changes you do need to propagate that information (that it changed) to the children transforms. That's where the dirty flag comes handy but then again it won't be too easy to implement that solution in the link especially since Entt loops the array backwards. Maybe a simple solution would be a 'dirty' tag on objects, but then I'd have to store the children in the parent in order to mark them recursively. |
Just have a distinction beetween dynamic objects and static objects. Every engine does that (i dont do a distinction becouse in my tech demo, everything is moving). Usually the amount of dynamic objects ends up being very low. |
The commercial engines I know only have that distinction for static batching. They all have dirty flags so if you don't move an object you don't pay for it. Some even have multiple caching like for example rotation AND mat4x4 transformation (Urho for example). Simply by making a distinction between dynamic and static I'd still have to update all the children of all dynamic transforms each render (or each tick because world position might be used for other systems like AI and sound). I see how that solution works for a simple tech demo but for a real game I don't think it's the most appropriate solution. COPYPASTE OF THE PERTINENT PART:
|
@Alan-FGR Is it a viable approach for you? To be honest, while I was writing the few lines above, another solution that has probably higher performance came to my mind. |
I wouldn't break the discussion in two issues. I'll add a new label anyway for issues like this one. Good point. |
@skypjack thank you.
Isn't removing and reassigning a component slow compared to just swapping two existing components? Or would it effectively swap them internally if you do that?
If there are a few redundant operations due to components being added while I was marking the dirty ones that's no problem because it shouldn't happen too often, so I think the sorting could even be skipped, because otherwise I'd need to keep track of how much the list grew and subtract the value for the
It sure is a viable approach. I think there are other alternatives that could be explored too, for example maybe a dirty "tag" and not a flag in the transform component. If tags are basically dataless components (correct me if I'm wrong) they should be quick to sort in a compound view, and maybe we could then have a "Children" component, so we update them while looping. The problem here is that it's going to be redundant if a child is dirty too, and also you might miss cache when accessing the transform data.
Sure, I'm especially generous today so I offer 0.00001% after the first 4 bazillion euros, deal? |
Definitely slower, even though not that slow. The fact is that we cannot make the
What would you expect from this function? Should it swap the components between the two entities, the two entities and therefore their components within the given pool or whatever? You want the latter, I know, but the former is much more meaningful semantically, right? Thus, ambiguous.
Naa, unless you are dealing with 1M+ entities, insertion sort on an almost sorted array is blazing fast. Look at the benchmark in the README file. It takes only 0.0007s on my laptop for 150k entities. My two cents.
🤔
I suspect it won't be that easy to sort empty components in a compound view, you know... 😄
Well, come on!!! 😂 |
🤣 |
@Alan-FGR |
@skypjack you're 100% right ofc 😉... btw, what do you think about exclusion filter/negative selection for views? For example a view that matches all entities with component A but without component B? |
@Alan-FGR Do you mean to create a dedicated filter built-in in the view? Because doing it is straightforward already, you know:
I don't think we can do more than this honestly, even with a built-in solution. However, if you have an idea of how to improve views along this path, feel free to contact me! 😉 |
@skypjack yes I mean a dedicated filter. Maybe there's some trick to optimize that we're not aware of, but if there isn't then that would only be more stuff to maintain for no practical benefit. |
On my testing doing the "has" thing slowed down everything, wich was an issue on my high performance overkill simulation. |
@vblanco20-1 @Alan-FGR |
I did it with the registry, i did not know that you could do it with the view. That would need some testing to see how it goes. |
@vblanco20-1 No, my fault. The view is constructed only for |
For finding entities that don’t have a component, I usually create a pair of components. |
@Kerndog73 makes sense but sometimes components aren't exclusive, for example you might want to loop the entities with 'Transform' but with no 'Parent' component. Making a 'UnparentedTransform' sounds meh but maybe even for perf reasons that's the way to go. |
Just another viable solution. If you don't mind to make allocations here, remember that views are ranges. |
Hello! I try to write simple engine with entt and faced with some problems. Imagine, that we have components:
and We have System1, that changes Position component of entity e2:
And System2, that makes entity e1 parent of entity e2 and changes Position component of e1. Then System2 performs raycast to make a decision about its next behaviour:
Last problem makes me think about using an event system to store changed components within a list, something like
looks ugly, and very error prone. First problem might be solved by introducing dependencies between systems:
Maybe someone has a better ideas? @skypjack, what do you think? |
@zettdaymond To do any |
@zettdaymond |
@zettdaymond I think you should rather join the gitter channel for this kind of questions. There are programmers much skilled there. Btw, you can mark changed components with a dirty flag (either a real flag somewhere or a dedicated component, it depends on your design). No need to trigger events for that, just split things in more than one system whether required. |
@ArnCarveris Looks interesting, thank you for sharing this. |
@skypjack Thanks for the answer!
Imagine that we have 3 systems which update in main loop:
System1: may use and change position of e1, and set dirty flag But who responsable to unset dirty flag? The answer may be: "The system, who has set it previously in last iteration." Let's see:
If System1 unsets flag, then System2 will not know about System3 changes.
It seems that raycasting depends on behaviour of other systems and we get nested loops over components:
It might be a problem if we want to execute EnemySystem's view() in parallel. And i am not sure that keep such dependencies is a good idea , because we want to keep Systems as independent, as posible. Maybe i am overcomplicating? Sorry for bad english. |
@zettdaymond Is there any chance you join us on gitter (see badge on the README file)? Let me know. Otherwise I'll reply here as soon as I find some spare time to do that. :-) |
Only problem with gitter is now a year or two later I am not sure where the conversation ended ;) |
@dakom You could look through the archives |
Or start a new conversation. 😄 |
@vblanco20-1 I am attempting something similar to what you did in the ECS Huge Battle - that is have a contiguous array that contains all the transforms sorted by depth. I also have read your post where you mention "To do that, I perform a parallel for that iterates over the data of every entity, and stores the calculated matrix into the correct scene tree position". What is unclear to me is how do you know the right position given you don't know how many different levels of depth you are dealing with or how many entities are on each level? If you use any dynamically sized container, its not possible to do that update in parallel since any change in size would be a race on the container internals that deal with memory. So this would have to be done singe threaded. |
I have some questions about the best way to implement some things:
Component Dependency:
for example if i have a "Position" Component and a "Velocity" Componenet and i want to create a new Component called "Physics" to have more complex behaiviour how woud i make Position and Velocity a requirement for having a physics component. I could pass the Registry and the Entity into the Physics component constructor to add the Position and Velocity components if they dont exist but that doesnt seem to be a clean solution.
Best way of implementing child entities:
im kinda thinking about this too i would think that you create a "Parent" component that has a Entity handle to a child and thats it ? but what about passing information down the chain like if i change the position of the parent entity i want to inform the children that the parent moved and update their position accordingly. I would have to check in the "Position" component if it has a "Parent" component and then pass it down or is there a better way?.
Getting the registry or the attached entity in the component:
can you do that without having to pass it into the components that need it? im not sure about that but would it be possible to create a Component base class for those type of things and then have a specialization in the attach function but i dont know if that is possible in C++.
What about baseclass Components:
eg. if i have a Renderable Component and i want to subclass it to implement the draw function or something and add that to the entity and then get all of them with a view by searching all Renderables. is that possible, if not what would be a alternative?
The text was updated successfully, but these errors were encountered: