Handling a large number of actors

[Serefan]

@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.

Yes well to be honest Eclipse seems to have its own profiling system. I've tried getting the profiler to work but I didn't manage to do so as of yet (I've never done this before), what little information I found on the internet didn't work for me. I must have been doing something wrong but I don't know what, the profiler kept ending up without any data.

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.

This data wasn't calculated from my entire game loop. I implemented my own little debugger system, and I calculated the time taken for each piece of the game loop independently. Input checking and rendering were next to none. These numbers you're talking about were calculated from the logic update independently, so I don't understand how the problem could lie elsewhere.

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.

That's a great idea, thank you. The decision on what move to make for each character is a little object of its own making it perfectly manageable to check those conflicts even after I expand my action possibilities.

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?

No I don't have to do it this way at all. It's simply the first thing I thought of. I don't see why you would consider it complex though, it kinda reminds me of the FFX battle system: next guy to make a move does his thing, then he moves up the list, repeat.

The priority queue, according to oracle, should be optimized to poll for the next element in the list, as well as sorting an already nearly sorted list, so I took that and went with it. Correct me if I'm wrong, but what you're suggesting here is that the sorting procedure specifically is taking the most time? I was planning to check up on that, so I'll get back to you on that.

I suppose I could use that power value idea, or more specifically, I'd do the opposite, decrease it each turn and make a move when zero, that way I can easily account for actions taking in different amounts of time. I'd have to change the way the game waits for the player to make a move though. As it is now, since there's only one actor event active at any given time, the player's event is simply an extension of the normal actor event that suspends its execution until the player has decided on his move.

[Serefan]

Huh, creepy. I decided to keep it as it is until I worked out a good idea from what I've gathered here, and moreover until I actually came around to implementing the big city level. The only thing I did yesterday was install a new version of Eclipse. I decided to run another test with 500 little minions running around... And execution time is around one third of what it was yesterday. Someone either explain this to me or send me a bible and a crucifix to protect me against this witchcraft.

Also, I tested the speed of re-inserting the actor in the list while I was at it, and that actually happened extremely fast. The list re-ordering is definitely not an issue.

...I did also have my laptop tumble to the floor though. Maybe it learned it's lesson and decided to be good.

[Quendus]

Find a profiler that works. It doesn't have to be perfect and it doesn't have to be integrated in your IDE. It just has to tell you which function is so inefficient that processing a single actor takes a whole millisecond on a modern CPU.

[Rickton]

Worst case scenario you could compare the CPU time before and after running certain sections of code.

[Serefan]

Worst case scenario you could compare the CPU time before and after running certain sections of code.

Like I said, that is exactly what I did.

[Serefan]

Honestly I feel most responses here are really besides the point of what I actually asked. Everyone's focusing on this profiling and optimizing this tiny piece of code which is really not my priority. All I wanted to know was if there are any established structures that can be used when playing around with levels that are too large to update using simple strategies like this one, for example some kind of level partitioning system.

[Z]

Some rough calculations:

Inserting an event to a priority queue takes roughly log(N) operations, where N is the size of the queue. (Assuming the priority queue in Java is implemented with a heap, or another data structure suited for this purpose.)

Moving a creature in a random direction takes roughly 100 operations. Probably less. Depends on how exactly it is done.

A computer performs roughly 100 000 operations per millisecond (actually more).

With 500 actors, we get 500*(100+9) = 50000 = 0.5 ms. You would need to have 100000 actors (120 ms) to have problems with this.

Even if the list of actors was dumb (N operations to insert), with 500 actors you would still get 500*(100+500) = 300000 = 3 ms.

If you have problems with 50 actors, then the problem must be elsewhere. That's why people are suggesting you to use a profiler.

[Paul Jeffries]

Honestly I feel most responses here are really besides the point of what I actually asked. Everyone's focusing on this profiling and optimizing this tiny piece of code which is really not my priority. All I wanted to know was if there are any established structures that can be used when playing around with levels that are too large to update using simple strategies like this one, for example some kind of level partitioning system.

The reason nobody has been able to give you what you want so far is that you haven't provided anything like enough information to let us figure out what the problem is.  The optimum way to arrange your game-loop will depend entirely on which operations are taking the longest time to run, which we don't know and you probably won't know either until you get a profiler working.  There is no one-size-fits-all answer here besides 'find out what is taking all the time and try to do it less'.

[Serefan]

The reason nobody has been able to give you what you want so far is that you haven't provided anything like enough information to let us figure out what the problem is.

That's the whole thing - I don't have a problem that needs to be fixed. I was asking a hypothetical question. The question being whether there are any established methods out there for handling environments that are simply too large to simply handle in their entirety. From what I'm gathering here the answer would be no - which would be a perfectly fine answer by the way; I just wanted to make sure I didn't miss anything while looking for one.

[Z]

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.

Actually the scheduling method used by the OP is much better IMO. I think the article you linked contains an error (AFAIK Crawl has no monsters of speed 100 and 101, it made a decision to have no monsters with such small differences in speed, and I believe it is a conscious and sensible decision). Also it likes ADOM's time management system, which has its weird effects: when running from an enemy of the same speed, I sometimes get two moves while the enemy does not move, then the enemy has two moves while I am skipping. This seems to be an artifact of the speed system used (if I move in segment X, then my next move is sometimes in segment X+9, sometimes in segment X+10, this is not synchronized with the enemy, and that's why we get the weird effect). I suppose the same would happen with the system described in the article.

Also checking energy > 0 on each tick is not that efficient, especially if you want to be accurate and have many ticks per move. A good priority queue does not do repeated sorting on each insertion, it is much more efficient (if you are checking an actor 10 times per move like ADOM does, the efficiency is comparable, but accuracy is very low).

[Kyzrati]

I wasn't too focused on what the OP was actually using, or if that was even the problem (because it's most likely not), just thought I'd throw those articles out there for him to look at since he was talking about sorting and action systems. I should've left that off because the real problem was lack of profiling.

Not to derail the discussion, but highly granular action point systems that can result in extra moves here and there are not necessarily a bad thing for non-puzzle oriented games. It can depend on the style of the game, enabling very complex movement systems in games where speeds are highly dynamic, anyway. Even if not dynamic, how many players actually notice the difference between X+9 and X+10? (I would still agree that static relative movement speed is the way to go in most games, though. And as a side note, it seems the problem with DCSS movement is it does away with variable relative speeds by making certain values meaningless.)

[Z]

I think that a monster with speed equal to PC's should move each turn (where "turn" is defined as the interval between two player moves), slower monsters should sometimes skip turns, and faster monsters should sometimes get an extra turn. In ADOM, sometimes a monster alternately skips a turn and makes two moves. This is bad in more tactical games (harder to plan), and even in less tactical ones it makes no sense IMO and is annoying. (I do not see X+9 vs X+10 either, but I infer this as a reason for this behaviour.)

In my smaller games (Hydra Slayer and HyperRogue) speeds are always powers of two (normal, 2x slower or 2x faster), this approach allows the player to plan their movements easily, which is good for tactics.

Could you elaborate on the problems with DCSS movement?

[Kyzrati]

Ah, wasn't thinking about actors actually skipping a turn only to later make two consecutive moves. That does seem somewhat odd. I was only thinking about getting (or losing) the occasional odd move, which seems reasonable. (I never played ADOM for very long since the early game repetition started grating on me, so I didn't have a chance to notice that.) Strange that occurs in ADOM though, since an simple energy based system doesn't seem to result in that effect. Maybe I'm thinking about it wrong.

Imagine an energy system whereby all actors get 100 points per turn. Assume the player requires 100 energy to move, and therefore moves every turn. A monster that requires 110 energy to move will skip its first turn (not enough energy to move yet), then move every turn after that for 10 turns before skipping one turn, then the cycle repeats. I think the true cause is that it gets a lot more complicated once there are actions other than movement thrown in.

I'm not too familiar with the intricacies of DCSS movement mechanics, but know it uses different time systems for the player and monsters, which isn't practical for other games where the player has access to specific movement values, which ideally should be consistent and comparable. About certain values, see this.

[Paul Jeffries]

That's the whole thing - I don't have a problem that needs to be fixed. I was asking a hypothetical question. The question being whether there are any established methods out there for handling environments that are simply too large to simply handle in their entirety. From what I'm gathering here the answer would be no - which would be a perfectly fine answer by the way; I just wanted to make sure I didn't miss anything while looking for one.

Fair enough - I apologise for misreading your intent.  One thing you could do if you want to have large environments and don't want to simply freeze parts of it is to have a separate, simpler, system for actors which are beyond a certain range from the player.  If they are out of sight range exact movement speed is unlikely to be all that important - you could simply assume that far-away actors all move at the same speed and move them into a separate queue that processes each actor in turn and so doesn't need sorting or energy counting (until they move closer to the player again).

In my smaller games (Hydra Slayer and HyperRogue) speeds are always powers of two (normal, 2x slower or 2x faster), this approach allows the player to plan their movements easily, which is good for tactics.

Generally speaking, I greatly prefer this kind of approach over more free-form timing systems, which make it hard to keep track of creature movements and feel slightly fiddly.  It also seems a bit silly to me to rigidly partition space into a grid but then not be prepared to do the same thing to time.

That said, I am thinking of having a variable-movement-speed mechanic in my next game, but it will be one where movement between tiles is animated and actors can freeze 'in between' tiles during the player's turn, so that the turn order should still be fairly obvious.

[Quendus]

In an efficient language like Java it's quite easy to have thousands of actors each moving several times per second (by the wall clock), on a map with hundreds of thousands of tiles. I didn't find the OP very clear, but it didn't sound like there was anything in the system described which would prevent simulation of that scale being carried out efficiently. The alternative time systems are well-used and reliable, but shouldn't have  Certainly a desktop or laptop made in the last 10 years shouldn't have any performance-related reason to use any kind of special treatment for "out-of-range" monsters on a scale smaller than that, though there may be good gameplay reasons to do so.

The reason nobody has been able to give you what you want so far is that you haven't provided anything like enough information to let us figure out what the problem is.

That's the whole thing - I don't have a problem that needs to be fixed. I was asking a hypothetical question. The question being whether there are any established methods out there for handling environments that are simply too large to simply handle in their entirety. From what I'm gathering here the answer would be no - which would be a perfectly fine answer by the way; I just wanted to make sure I didn't miss anything while looking for one.

I'm not sure you meant by "an environment too large to handle in its entirety" - if you mean the number of tiles on the map exceeds the memory of the JVM, that can be compensated for by saving out-of-range areas to disk. Except for AI pathfinding (which should be used sparingly on large maps), map size shouldn't have any effect on the time it takes to process a turn. I assume that the actors and map tiles are double-referenced, so that the occupant of a tile and the position of an actor can both be found in constant time.

Either way, the answer to your hypothetical question is there are, but theoretically they shouldn't be much better than the method you described. However, all of those systems should be able to give better performance than what you described.

What time periods were you measuring in your timing system? Did you actually create a scene with hundreds of actors and measure the time it took to process a turn, or did you measure the time it took to process a single event? What was the precision of the clock system you used? If the smallest unit of time it can measure is a millisecond, then you may have a very fast system that's being diagnosed with a nonexistent problem.