Jump to content
  • Advertisement
Sign in to follow this  
00arch00

Handling large amounts of enemies

This topic is 3833 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm using C++ / SDL / OpenGL to make a 2d top-down scrolling mmorpg. My design goal is to recreate another mmorpg I used to play. The other game was poorly coded, had terrible collision detection and numerous bugs, and was slow and inefficient. So far my client uses 0% cpu with 3 layers of scrolling background, a tile engine running on top of that, and a player moving around and shooting with working collision detection. My problem is that if I create an extreme amount of enemies, say 1million, and put them all on a board that scrolls around - then the game goes very slow of course. That is with a primitive for loop to cycle through each enemy. I had somewhat of a solution worked out where I was testing to see what enemies are onscreen and giving them a flag and then counting those flagged enemies and using a smaller for loop for the render code. That helped a little ,but I'm looking for something better. I need to get rid of the for loop altogether. Right now the enemy handling is hardcoded into the client, and there is no networking yet. There is currently 1 large room, but my goal is to have hundreds of rooms - this is why I'm looking for a way to handle so many enemies. I was trying to use the 9 square technique to seperate enemies and something went wrong with it. What is the most efficient method for handling large amounts of enemies? Any advice is appreciated.

Share this post


Link to post
Share on other sites
Advertisement
Lazy evaluation.

Of all those million enemies, only a handful (say, two dozen) ever needs to interact with the user at any given point in time. Therefore, just don't process (or even load into memory) the others until the user reaches an area where these enemies would be visible.

Share this post


Link to post
Share on other sites
Thanks for your answer.

I think that would work well for a single player game, or a simpler mmorpg.

What if I need the enemies to move around and interact with each other even if they are offscreen from any players? There are some special events I have in mind that would require some enemies to be updated even if there are no players in the room. How can I handle something like this? I was planning to deactivate unused enemies in regions where there aren't any players, but how can I do this and still modify attributes of the enemy's class if I need to?

Share this post


Link to post
Share on other sites
If that doesn't make any sense what I'm going for is a "persistent" game, where if you cast a spell on an enemy and leave the room, the next player who comes in sees the enemy affected by the spell. I would also like enemies to regain life while players are away, and for enemies to be able to cast spells on each other.

Share this post


Link to post
Share on other sites
Quote:
Original post by 00arch00
What if I need the enemies to move around and interact with each other even if they are offscreen from any players? There are some special events I have in mind that would require some enemies to be updated even if there are no players in the room. How can I handle something like this? I was planning to deactivate unused enemies in regions where there aren't any players, but how can I do this and still modify attributes of the enemy's class if I need to?


Time-dependent attributes are a solution which reduces computations if certain objects are observed infrequently (to get the value at time 't', you don't need to compute it at time 't-1', and so you don't have to update invisible objects). Similarly, don't use time-step updates (that would require to iterate through all objects) but use schedule-based updates instead (you know the next update for an object will be required at time 't+n', which means you can just skip the next 'n' updates).

By combining both time-dependent attributes (for values which evolve often by following a simple rule) and scheduling (for values which evolve rarely by following a complex rule) you can greatly reduce your work overhead.

To follow your life gain idea: store the amount of damage sustained as a function of time, of the form 'A exp (B - C t)'. When you need to know how much damage was sustained by an enemy, evaluate this function for 't = now'. When you deal damage to an enemy, set A = oldDamage + newDamage, B = C * now, and leave C (the regeneration speed) the same. This implements regenerating monsters that you never update.

Share this post


Link to post
Share on other sites
Quote:
What is the most efficient method for handling large amounts of enemies?


The only way is to have less enemies. Either process them in turns (only a fraction of them on each turn), or use more hardware, having each machine handling only a small part of them.

For online game you cannot send 1 million entities to clients anyway.

Quote:
I had somewhat of a solution worked out where I was testing to see what enemies are onscreen and giving them a flag and then counting those flagged enemies and using a smaller for loop for the render code. That helped a little ,but I'm looking for something better. I need to get rid of the for loop altogether.


This is rendering and unrelated to the actual number of objects. You'd usually use some kind of spatial partitioning, a quad tree or something similar. Rendering tens of thousands for complex scenes shouldn't really be a problem, usually the number should be in hundreds or thousands.

Quote:
Right now the enemy handling is hardcoded into the client, and there is no networking yet. There is currently 1 large room, but my goal is to have hundreds of rooms - this is why I'm looking for a way to handle so many enemies. I was trying to use the 9 square technique to seperate enemies and something went wrong with it.


1 million per room? I doubt it. If this is instanced game, you can always have each room run on separate server.

Share this post


Link to post
Share on other sites
For a persistent world where objects actually need to exist and be processed, you cannot escape processing them. However, updating them less frequently, using a similar system to what ToohrVyk suggests, can save you doing a lot of unnecessary processing.

Certain things (targeting, detailed movement, attacks), which operate every frame when a player is nearby and which are heavy, can be completely turned off when no player is near. Movement can be done on a random deviation from its previous known location, or if accurate movement is still needed (i.e. not going through walls) you can run your movement algorithm (A*?) every 1000 frames and move the character up to 1000 times as far.

Things such as casting a timed spell on an entity would set a 'next must process' time. For example if I cast a 1 minute spell on an enemy, it would collect a 'next must process' of 1 minute. You would build up a collection of these 'must process' times, and you would only need to process the entity at those times.

Some things, like regeneration or weapon recharge, don't need special processing at all. You can simply work out how much regen/recharge has happened since the last processing time when the entity is processed for another reason (such as a spell wearing off, or a player coming within activation range).

Share this post


Link to post
Share on other sites
I was thinking about it. (still a noob developer) Why don't you make some enemies static? meaning once they have been affected by something they stay being updated etc, but if a enemy is not/has not been affected by anythign then the only ones who need to stay on the server are the static ones. Then all you would do is load the non-static enemies when the player can see them.

Share this post


Link to post
Share on other sites
If I understand you correctly, Kentu, thats pretty much just lazy evaluation, as suggested above by ToohrVyk.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!