Handling a large number of actors

[Serefan]

I've been working on a (turn-based) roguelike engine for a while now and yesterday I did some tests stuffing a level with a large number of enemies. Naturally, the game started hanging.

First off, how I've implemented the logic part of my game loop. It makes use of two lists: one containing the currently active physics (objects and actors being thrown around, explosions, etc.) and one containing the actors inside the level. This list of actors is sorted by their action value. The first actor in the list is always the next one to make a move, and each time an actor executes his move, his action value is increased by a certain amount, depending on the cost of the move, and he is re-entered in the list. Here's how I implemented the entire thing:

Code: [Select]

do
{

if(physics.size > 0)
// Check all active physics events, remove those that are finished
else
// Check active actor event, if finished, update actor position in list, and start next actor event

if(physics.size > 0)
// Execute all active physics events
else
// Execute active actor event

}
while((renderer is empty) AND (current actor event is not the player))

To sum it up: as long as it's not the player's turn, I keep iterating over the active events, but the loop takes a break if something changed the player's field of vision. (I realize I could optimize this a bit more, only breaking if a physics event changed player's field of vision, not actor events, but this is not the issue)

In most cases this works well. And having lots of actors in one level is not something that should happen often, if at all. The results of the tests were more or less as follows: the loop takes slightly more or slightly less than a millisecond to execute each event. With 50 actors in play, this amounts to 50 milliseconds. Not ideal, but manageable for a turn-based game. Naturally, this scales linearly. 500 actors equals half a second, which is obviously too much for the game loop.

Now I'm not saying I want levels around with hundreds of actors. But I am however planning on having scenes in my game like a bustling town, with shops, taverns, etc. where the characters inside have a somewhat realistic routine, tending to their needs, going to work, going to sleep... And I feel like my current approach will ultimately be terribly unfit for stuff like this.

So, I'm curious if there are any better practices out there for handling stuff like this. Is there a way to reduce the time my current system takes? Are there any better systems out there I'm unaware of? Should I instead look out for a system that provides a better way of handling levels as a whole (I'm thinking, for example, dividing it in chunks, but I'm not sure how to go about doing this effectively)? Would I be better off implementing a real-time system akin to that of Dwarf Fortress, so the actor's events will naturally be spread out over different frames?

[Krice]

and he is re-entered in the list.

What actually this means? And why there are two lists?
One way to speed up is simply limit the distance where action happens. And/or limit the amount of actions each actor has outside that distance which means those outside the range will perform only simple tasks, like moving etc.

[george]

Your update loop sounds rather slow regardless of how many actors are on the level. From your description (correct me if I'm wrong) with 50 actors your update loop is 20 times a second. This is without rendering. As a rule of thumb I think you should be able to do twice that without much trouble.

What language are you using? What platform? What functions are taking the most time according to your profiler?

[Trystan]

I only know of three ways to improve performance:

• Do less work.
• Use a more appropriate algorithm.
• Use a more appropriate data structure.

You may want to try a list that automatically sorts itself or try resorting the list in place rather than removing the actor then adding it again. Collections often have built in methods that have low level optimizations - especially in higher level languages. Try to stick to using those.

The best option by far is to do less work. One thing I did for one of my games is to make creatures stay idle until the player sees them or they take damage (from traps, etc). That way most creatures aren't really involved in the update loop. Another thing is that you may be able to cut down on the amount of animations or use less granular time slices. It's hard to say without knowing how your physics events work but I'd guess that reducing the number of times you loop through before returning to the player will have the largest benefit by far.

And of course, profile everything and focus on what takes the most time.

[Rickton]

Chances are it's not the loop itself that's the problem, but what's going on inside the loop. Maybe the actors or physics events are too involved, ie the AI is too complex or inefficient?

[guest509]

I'm not a fantastic coder so keep that in mind.

There are 2 questions that maybe will help:

1. Do you need to be updating guys that are off screen? How far off screen?
2. Is a bustling town going to have more than 50 moving actors on screen at once?

Others can surely help you speed this up with more efficient coding, but after that then one big work around I've used is to not compute things too far away from your character.

If you do need them to move around a bit to give the illusion of a living world then simplify their behavior off screen. Something like a drunken walk instead of a complex decision tree.

[Serefan]

Your update loop sounds rather slow regardless of how many actors are on the level. From your description (correct me if I'm wrong) with 50 actors your update loop is 20 times a second. This is without rendering. As a rule of thumb I think you should be able to do twice that without much trouble.

What language are you using? What platform? What functions are taking the most time according to your profiler?

About the 50 actors -> 20 times a second, you are partially correct; it is the worst-case scenario. That is assuming every actor always takes a turn, after the player takes its turn. In practice, this varies a lot due to energy differences, since different actions consume different amounts of energy. Also, since this is a turn-based game, the game spends most of its time doing nothing, and checking the player's input. Are you saying 50 actors should be updating faster than 20 times a second?

This project is written in Java, and I'm using Eclipse. I have worked on the renderer for a long time, it pretty much works at optimal speed (this is a graphical roguelike). In those worst-case scenarios where every actor takes its turn after the player, this logic part definitely takes the most time.

Chances are it's not the loop itself that's the problem, but what's going on inside the loop. Maybe the actors or physics events are too involved, ie the AI is too complex or inefficient?

I forgot to mention, this test was made without using any actual physics events and with a stupid 'walk-to-a-random-next-square' AI, so this is definitely not the issue. Everything executed by this piece of code were empty placeholder events.

You may want to try a list that automatically sorts itself or try resorting the list in place rather than removing the actor then adding it again. Collections often have built in methods that have low level optimizations - especially in higher level languages. Try to stick to using those.

That's already in there. My actor list is a type of queue (Java's PriorityQueue), which is optimized to take only the head of the list, and is automatically sorted based on the actor's action energy.

and he is re-entered in the list.

What actually this means? And why there are two lists?

One list keeps the currently active physics events. The other (the PriorityQueue) keeps the actors that are currently in play. The idea is that there is always only one active event, since it's a turn based game; but the execution of this event can result in a few physics events, of which there can be more than one at the same time and should execute simultaneously.
Example: a wizards zaps a fireball in the direction of a group of other actors. The flying fireball is a single physics event (a projectile event). Once that event is complete (impact of the fireball), the explosion triggers knockback on the entire group of actors, thus a projectile event is thrown for every actor caught in the blast, throwing them all back at the same time.

I only know of three ways to improve performance:

• Do less work.
• Use a more appropriate algorithm.
• Use a more appropriate data structure.

The best option by far is to do less work. One thing I did for one of my games is to make creatures stay idle until the player sees them or they take damage (from traps, etc). That way most creatures aren't really involved in the update loop. Another thing is that you may be able to cut down on the amount of animations or use less granular time slices. It's hard to say without knowing how your physics events work but I'd guess that reducing the number of times you loop through before returning to the player will have the largest benefit by far.

And of course, profile everything and focus on what takes the most time.

Like I said, this was purely a test of the logic loop. Animations, physics, and AI calculations were taken out for this test. As far as I know, I have to agree with you, what I need is a better turn-based algorithm for my list, and/or a better data structure for my level. I'm just not sure what I need, that's what I'm here for.

1. Do you need to be updating guys that are off screen? How far off screen?
2. Is a bustling town going to have more than 50 moving actors on screen at once?

Others can surely help you speed this up with more efficient coding, but after that then one big work around I've used is to not compute things too far away from your character.

If you do need them to move around a bit to give the illusion of a living world then simplify their behavior off screen. Something like a drunken walk instead of a complex decision tree.

1. I'm not sure, actually. I definitely want guys that are kinda near the screen to be somewhat useful. One of my questions/ideas was using a chunk-like structure for very large levels, and like some of you said, limit the region that's being updated. I'm just not sure how this data structure is best implemented, that's what I'd like to know. One thing of note I forgot to mention is the fact that my level grid is contained in a much simplified version of a quad tree.

2. Well, if I had to take a guess, there would be very few, if no occasions where there actually are 50 actors on screen. 50 actors or more in an entire level however (which could possibly be divided into pieces given an appropriate data structure) would definitely be more frequent.

[Vanguard]

Are you saying 50 actors should be updating faster than 20 times a second?

A roguelike should be able to handle that without performance problems.

[Serefan]

Are you saying 50 actors should be updating faster than 20 times a second?

A roguelike should be able to handle that without performance problems.

That is neither a yes nor a no; I can't really deduce anything from that statement. Let me be clear about this: Unless that number on its own is a problem, I don't really seem to have any performance problems. I simply did an (as of now) unrealistic stress test, and I was wondering if there were any commonly used data structures or algorithms out there that could help when actually trying to deal with hundreds of entities.

[Kyzrati]

For your actor energy system, use this (or reference the other Basin articles on the same topic). It's a really fast method that doesn't require repeated sorting. This may be more or less what you're already doing? In any case, if a program is slow and you want to know why, profile it. Once you fix whatever the bottleneck is it'll definitely be faster than what you've got now. Try not to optimize before profiling--you'll probably end up wasting a lot of time.

[george]

@Thales, right, you haven't mentioned your profiler results. You have a lot of robust profiling options with Java so that should be your first step.

Regarding 50 actors at 20 updates a second, yes, that is too slow. You should get at least 40 updates a second (with rendering, animation, etc.) with no problem, especially with Java, which is relatively fast.

[Vanguard]

That is neither a yes nor a no; I can't really deduce anything from that statement.

What I mean is that regardless of whether or not your 50 actors need to be updating more than 20 times per second (they may, but it depends on the game) your program should easily be capable of performing twice that.  The fact that it struggles to do so suggests a problem exists somewhere.  I can't offer a good suggestion because I don't know enough about your code to say where the problem lies.

[Cfyz]

Also, since this is a turn-based game, the game spends most of its time doing nothing, and checking the player's input.

I think you might utilize this. Most of the actors who do not actually interact with the player (for a simple example, all those outside of player's FOV) may be calculated in advance while waiting for the player's input, from closest to player to farthest. The main idea is to calculate as much as possible during the time game has nothing else to do.

This will increase game engine/logic complexity. There must be some way to check if precalculated move conflicts with actual state. Game data must support some level of parallelism. However, this approach can make an impression of all the actors being handled.

[Krice]

This list of actors is sorted by their action value. The first actor in the list is always the next one to make a move, and each time an actor executes his move, his action value is increased by a certain amount, depending on the cost of the move, and he is re-entered in the list.

Does it have to be this complex? I'm using a power value for each creature, increasing it each turn and when it's full the creature can make the move. If it's not, the creature is skipped. I don't know what is the idea in sorting the list. Why would you need to do that?

[NON]

For your actor energy system, use this (or reference the other Basin articles on the same topic). It's a really fast method that doesn't require repeated sorting. This may be more or less what you're already doing? In any case, if a program is slow and you want to know why, profile it. Once you fix whatever the bottleneck is it'll definitely be faster than what you've got now. Try not to optimize before profiling--you'll probably end up wasting a lot of time.

I just want to say I agree wholeheartedly with this. Always profile and optimize the bottlenecks. The problem could be very far from what you think.