Moving multiple objects on a map

Question

I have multiple objects on my isometric game, for example, NPC's doing path finding automatically to walk around the map. Now there could be any number of them from 0 to infinity (hypthetical as no PC could handle that).

My question is: is simply looping each one individually the smartest way to animate them all? Surely as the number of units increases you will notice a lag occuring on units near the end of loop still "waiting" for their next animation movement.

The alternative is a swarm algorithm to move all objects together. Is that a smarter idea or do both situations apply depending on the circumstances of the game?

Answer 1

Whichever algorithm you choose to update your NPCs, they will still have their animations updated one at a time. Yes, there are multiple cores, and you could write a multi-threaded update loop that can update 2, 4, 8 or however many NPCs at a time. However, this would only be necessary in extreme cases, and there are many easier methods to employ first.

A major one, only animate the units that are visible. This applies to your assumption that there could theoretically be infinity units to update. The number of units that need an animation update is finite. The maximum is the number that can reasonably fit into the view of your camera and still be large enough to notice animation changes.

But what you really need to do is write a simple update loop that updates each npc's animation one at a time. Then you test the performance to see if you really need to improve it. If you spend too much time wondering which way to do it best, you'll never finish.

Answer 2

Swarm algorithm is probably not the word you're looking for, as it conjures associations with flocking.

What I think you're trying to say is some sort of level of detail (LoD) for behaviour, which isn't a bad idea at all. After all, behaviour can be simulated at different granularities (e.g. we don't need to simulate every sub-atomic particle's movement to animate a walking dog).

Example: In a 3D medieval battle game you wouldn't animate every individual bone on a single soldier which shows up as 4 pixels on the player's screen, instead you would treat the soldier's battalion as a single entity (the military catch-all phrase "unit" is most appropriate here) and consider only its movements in reaction to the world state. This would result in a simple translation vector, which you of course still need to apply to each individual soldier, so you will never get rid of the loop(*), but you will be able to minimize the number of calculations needed within it.

Once the battalion gets closer to the camera you add a check to make sure each soldier is touching the terrain, and closer still you'll actually start animating them individually.

Rewinding from this example to your current endeavor, depending on the distance of the entity from the player's view (and the speed with which the player would be able to move the view) you would:

1. translate and animate them normally (when the units are on screen)
2. translate but not animate (when they are just off screen)
3. update them less than once per frame (when they are further away)
4. not even update them (if this wouldn't lead to strange situations)

For 2 and 3 you would be able to use the method of grouping the behaviour of multiple entities, especially if they were supposed to move in (relative) unison anyway.

In closing: whether this is applicable to your game depends on its mechanics, and (as was already mentioned) if you actually need these optimizations: avoid "premature optimization". :-)

---

(*) Though one could make use of a scene graph to defer the propagation of the translation to the drawing phase of the game loop.

Answer 3

"The alternative is a swarm algorithm to move all objects together"

What does together mean? In programming, together will be updating at the same time which in turn means updating them in separate threads, otherwise there is no together, it will always be linear, one after the other. Needless to say, separate threads does not guarantee updating at the same time if there are not enough available cores.

Bytes56's suggestion to animate only the units that are visible is sound but to avoid the weird effect of the NPC suddenly stopping to animate as soon as it goes off-screen, you may want to update NPCs that are in a certain radius around the player.