Ideal way to code a lot of npcs?

[elosant]

I have scenes in my story game which warrant having hundreds of npcs on screen at a given time. I also want some of my npcs to roam around the map, doing various tasks to liven up the atmosphere. As of now, I’m doing a barebones ecs implementation but I’m finding that each system takes around ~6ms of frame time given a hundred entities. Writing components also becomes more arcane especially when I have systems that need to dispatch an event from one system to another (collision → physics for example). Jonathan Blow (creator of the witness, braid and jai) also shares a similar opinion regarding entity component systems and its apparent complexity.

1. Should I use conventional OOP for something like this? (I think it’d be more expensive)
2. Does keeping all my entities in a contiguous array help with performance, compared to assigning each with a GUID?
3. Is it worth writing a custom implementation of a humanoid?
4. Are there viable alternatives for something like this?

Here’s some of my code:
entityPool
(base) system

[12904]

OOP all the way… Personally I’ve found that using OOP is one of the best possible styles to use for almost any project… I don’t see why this would be any worse…

Another alternative would be taking a bindable event inside of each NPC with a script and calling all of those events at once… But I personally think OOP is by far the way to go…

[CompilerError]

Your question is going to depend heavily on the goal of the NPC. OOP isn’t necessarily going to solve any problems here, it’s really just one of many techniques for writing reusable code. You’ll want to try to optimize for each case here. Basically the NPCs that roam around the map and do various things are probably going to be more complex and specialized than the ones where you’re doing hundreds of NPCs. In those scenarios you’ll probably want to try to dumb them down as much as possible.

Another thing you can do is avoid the use of loops, at least in the conventional sense. There are events built into the Humanoid to detect when it has finished moving for example, while you could run a loop that says to move the Humanoid to a point every frame or once a second even. You would be much better off hooking into that event.

Again it’s going to depend on the use-case for the NPC. I would strongly encourage writing a robust and efficient (likely event driven) behavior tree module. They’re a relatively simple concept and very simple to work with. Of course there are alternatives to this but again, this is simple to understand for almost anyone and they are efficient since they can be entirely event driven and only perform an operation as necessary. If you combine this with some kind of system where you can extend modules then you would seriously benefit from code reuse.

I’ve always preferred OOP but it does come with a memory cost, which generally pays for itself in code reuse… again that depends on your implementation.

As for your second question, keeping all of the entities in an array will only help depending on how you need to handle working with them. If you’re needing to lookup a specific entity in the list then stick with the GUID approach. You’ll not want to loop through each entity to see if it’s a match when you can do an O(1) lookup on an object instead.

You might find it useful to create a custom humanoid implementation for certain use cases. You likely won’t be able to do what a humanoid does better (and by better, I mean in the memory/computational department).

You’re pretty much free to go about this in whatever way you find best. That may require some research.

You can look into how major game engines handle NPC actions. A lot of them use behavior trees like I had mentioned. I’ve found them to be useful and very simple to work with so that would be my recommendation. That would allow you to curate each type of NPC to be exactly what it needs to be and nothing more.

[colbert2677 (ImagineerColbert)]

I think one of the huge problems in this kind of handling is that people overthink the solution and start launching grand explanations about techniques that are going to complicate and extend how long operations take.

The answer really just comes down to the fact that Humanoids by nature are very expensive to keep in your games. You need to disable what you can of the Humanoid (e.g. via SetStateEnabled) and make sure that the humanoid isn’t overly involved in a task. Push some rendering to the client if you have to and have the server just treat NPCs as a single part.

There are avatar updates upcoming in the future that will allow you to unregister or disable parts of the humanoid you don’t need, so hopefully when that drops it’ll also make NPC management at large less intensive.

Anyway, your questions.

1. OOP is a coding style, won’t change anything here.
2. Not necessarily, no. Pick whatever you can handle best.
3. Yes, if you can. Vesteria is a great example of a game with custom Humanoids that can run well.
4. Depends. There’s usually always another way.

[elosant]

Right now I’m using something slightly more simple than a behavior tree (basically just a normal FSM), although using a BT does sound more robust (its just an FSM with uncoupled nodes right?)

[elosant]

The reason I’m refraining from doing OOP is because it usually has a higher space complexity when defining methods and extraneous attributes per object, or if you set the object’s metatable then you have to deal with the overhead of __index.

An entity system seemed ideal since I have all the logic in one place, and all I have to do is iterate through a contiguous array of entities and call update. I don’t see much of an alternative to state machines for handling npc logic, however, so I’d like to know what you had in mind so as to not over complicate the solution?

Also having a part per humanoid on the server and handling replication manually was a really good idea, thank you.

[colbert2677 (ImagineerColbert)]

For this specific question, I don’t find a BT necessary or ant other kind of system that requires more than some simple iteration and whatnot.

BTs and FSMs are nice and all, they’re helpful when addressing NPC behaviour and laying out what they should be doing, but the main point is the optimisation, no? That would then boil down to having efficient code in place and lightening the load where possible.

You can still have operations that run for a considerable amount of time or longer with BTs and FSMs if some rudimentary root issues aren’t first addressed, which is why I find that it’s something to be considered afterward rather than at the beginning.

[CompilerError]

I didn’t really explain anything, certainly nothing on a “grand explanation” scale. I just made a few suggestions. OP didn’t specify what he needed so I gave him the most efficient and scalable solution I could think of.

Humanoids really aren’t that expensive to use at all. They’re mostly handled on the C-side anyway. There is almost never a reason to create a custom implementation unless the humanoid is forcing a behavior that you don’t want. That is assuming this NPC needs to move around. If not there’s not really any reason to use a Humanoid.

OPs question sounds to me like he has quite a diversity of NPCs in his game. If he’s creating a story based game, don’t you think he’ll want flexibility in his NPCs? I sure would. What you are suggesting is not flexible at all. Your suggestion is basically hard code exactly what you need everywhere you need it. That would absolutely suck long term.

@elosant you’re probably fine using FSMs. They’re more powerful than behavior trees anyway. Just a little less intuitive in my opinion since there’s a lot of config involved. I can imagine you’ll probably have quite a bit of integration with global states within your game since it’s story driven.

[notchloeno (chloe)]

@CompilerError

Humanoids really aren’t that expensive to use at all.

They are when you have hundreds of them, and you’re definitely going to want to optimise as much as possible if you want them all doing idle tasking:

@elosant

I have scenes in my story game which warrant having hundreds of npcs on screen at a given time. I also want some of my npcs to roam around the map, doing various tasks to liven up the atmosphere

[colbert2677 (ImagineerColbert)]

Don’t think you understood my post.

BTs are scalable but that doesn’t automatically equate to efficient. BTs are capable of being as inefficient or moreso than a simplistic NPC handler. Code efficiency is dependent on the way you write it. OP’s NPCs are still capable of being as slow with BTs as without.

Humanoids are expensive and hacky, C-side or not. There’s a reason that there are several complaints about Humanoids specifically throughout the DevForum as well as developers moving to custom humanoid solutions. Look around on the DevForum for a brief understanding of this.

In a story based game, yes flexibility and scalability are demands that need to be met to be able to support several hundreds of NPCs, but that doesn’t address the initial issue of trying to find an efficient solution that adequately resolves the performance problem observed. That’s why I’m saying to forget that and resolve rudimentary root issues before getting into other systems. Failing to resolve the root of an issue leads to larger problems and it becomes significantly harder to backtrack once you’ve already made progress.

Nothing in my post is suggesting hard coding AT ALL. What made that apparent in my post? My specific suggestions, if you read my post again, are the following:

• Disable what you don’t need of humanoids via any currently-available API
• Ensure a Humanoid’s involvement in activity isn’t intensive
• Render Humanoids on the client, have the server treat NPCs as single-Instance entities
• When avatar updates drop, unregister components of Humanoids you don’t require

How is this NOT scalable or flexible? How is this hard coding? It’s not. Getting rid of unnecessary expenses and tasks is very future-supportive.

[CompilerError]

Why do you assume OP can’t write an efficient BT? Anything is capable of being inefficient if done wrong, obviously. There’s no reason to assume he doesn’t understand how to write effective code. Your suggestions are valid and they may help to improve his response times but I’m pretty certain that what you’re suggesting isn’t the problem he’s having. His NPCs are are taking 6ms to respond, each. That isn’t a humanoid problem.

And honestly what is the point in coming to a forum and insulting someone who is just trying to be helpful and derailing the conversation? I apologize that I missed the point of what you were trying to say. I guess I was a bit distracted by the arrogance of what you said and how you said it.

I suppose a good question to ask, since none of us have asked any decent questions is this @elosant:
When you say each system takes 6ms to respond, is that an additive number or can they all run in parallel with 6ms response times? If they’re taking 6ms each and stacking on top of each other, you have a very easy optimization right there. Go ahead and implement @colbert2677’s idea too, sounds like a fine way to cut down on the Humanoid overhead. Hopefully I’m understanding you correctly there.

I guess since you’ve already accepted my answer as the solution we can let this post rest and not waste any more of your time with the bantering.

Thanks for the help in clarifying the problem and solution @colbert2677.

[notchloeno (chloe)]

@CompilerError

Why do you assume OP can’t write an efficient BT? Anything is capable of being inefficient if done wrong, obviously. There’s no reason to assume he doesn’t understand how to write effective code.

To be fair he is literally asking how to write more efficient code

[colbert2677 (ImagineerColbert)]

I appreciate the defensive and hostile tone where not necessary.

@CompilerError

Why do you assume OP can’t write an efficient BT?

I’m not assuming that OP can’t, I’m saying that a BT doesn’t automatically equate to efficiency. OP isn’t the only one who reads this thread. Others who see your solution are going to attempt what you put and their BTs could easily be inefficient. It’s important to clarify that a BT isn’t the magic solution to performance and respective efficiency problems can still occur when implementing them.

Think of it from the perspective of multiple people, both as OP and as someone looking for a solution to a problem that others are having as well. I’m one of the people on that boat. Replying doesn’t mean I know for sure what I’m talking about and I could be easily wrong where proven. I’d like a solution for handling lots of NPCs as well, but a BT doesn’t say anything about improving NPC performance…?

@CompilerError

I’m pretty certain that what you’re suggesting isn’t the problem he’s having. His NPCs are are taking 6ms to respond, each. That isn’t a humanoid problem.

Humanoids themselves are expensive. Your expenses add up when you start using those Humanoids to interact with things. The Humanoid pipeline needs to account for SEVERAL things at one given time, including physics, rendering and replication. A 6ms response time is a performance problem and both code and Humanoids are involved in attempting to diagnose the problem. It is a Humanoid problem.

@CompilerError

And honestly what is the point in coming to a forum and insulting someone who is just trying to be helpful and derailing the conversation?

I’m not insulting you at all. None of my posts have been ad hominem. I simply disagree with the points you’ve raised and I’m explaining why I disagree, using personal experiences and common topics from the DevForum to back my replies. The DevForum is a place for construction. Again, I could be wrong, but you’re not explaining why and it doesn’t help to get pointlessly heated over it.

@CompilerError

I guess I was a bit distracted by the arrogance of what you said and how you said it.

I posed a solution. You disagreed. I disagreed with your disagreement. That’s not arrogance. My responses seem fairly calm and again, I’m using other sources to back my stances. You can just as easily do the research before replying. I’d hate to ramble off about things I don’t know about and act as if what I’m saying is fact. I don’t know that for sure, but

1. No one’s disagreed with it or explained why I might be wrong.
2. I’m not working out of thin air. I’ve searched before and done some reading. Simply searching up Humanoids and combining them with a problem keyword (e.g. performance, inefficiency, hacky, etc) can bring up a lot of threads about this very problem.

@CompilerError

Hopefully I’m understanding you correctly there.

Yep. Often one of the first steps of optimising Humanoids, aside from the code, is to address the NPC itself. Common first steps for optimising NPCs include disabling unnecessary states and managing network ownership appropriately.

On the topic of network ownership, automatic network ownership on NPCs can cause latency due to changes in ownership, resulting in jumps. Always good to leave NPC ownership to the server. Or, like I proposed earlier, have the client render the NPCs and the server only manage them as single-Instances. That way, the primary bottleneck is your own computer.

[elosant]

When you say each system takes 6ms to respond, is that an additive number or can they all run in parallel with 6ms response times?

Each system is attributed to a specific component, most of which are called per frame. Given a hundred entities, a physics system will iterate through every entity regardless of whether or not it is moving (to facilitate things like collision and gravity), a movement system delegated to a movement component (which holds things like a target position, speed, etc) that only iterates through entities with a certain “moving” state and a pathfind system that’ll request the target position from the movement component. The pathfind system calls update on every entity per 1/10 of a second rather than per frame.

The movement system, last I checked, took 6ms of frame time for simple positional updates. Each system is given their own thread, but not every system yields (hence updates may not happen in tandem, which is expected behavior given how the task scheduler works), so the frame time taken by each system is, for the most part, compound. Yielding between iterations does not seem to be feasible, otherwise two frames would have passed, from one entity to the next- with a wait call?

His NPCs are are taking 6ms to respond, each.

Sorry I should have made this clearer, each system takes 3-6ms to iterate through every associated entity and finish update() on all of them. Each npc entity can be hooked to around 3-5 systems.

[HaxHelper (ken)]

@elosant

Writing components also becomes more arcane especially when I have systems that need to dispatch an event from one system to another …

Observers generally don’t belong within an entity system. If you need to communicate between systems, do so with components or data on those components. This will turn the event into pure data which is simply handed off to the right system. It’s clean, and we stay within our framework!

@elosant

… each system takes 3-6ms to iterate through every associated entity …

Can’t really say much about this without seeing update(). Tight loops like these require great care; you may be doing something inappropriate.