• Advertisement
Sign in to follow this  

Handling large amounts of enemies

This topic is 3567 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
Just do what they have been saying...
Do not load the npcs into client until the player is in range.
If lets say someones nukes that npc...

Player1 Enters Room and asks server for room data (NPCs etc...)
Server sends NPC data (1 Enemy for now)
Player1 Nukes Enemy
Server Subtract Enemy HP with damage
Player1 Runs Away (No longer in loading range, player deletes NPC from memory)
Player2 Comes in same room (Enemy same HP)
Player2 Loads same NPC, it has the same HP as the other player saw

why?

Because you dont need a visual image for the server, let the server take care of updating the npcs, not the client...Client just asks for the enemy info when he gets close enough. Hope that helped some.

Share this post


Link to post
Share on other sites
Quote:
Original post by Leaedas
Player1 Enters Room and asks server for room data (NPCs etc...)
heh, it's always fun when you see someone speculating. Why would the client ask? The server knows where the player is and is authoritative.

Everything else is fine, except for one gameplay mechanism. The NPC might as well just be deleted as it's health doesn't matter. If someone runs away to heal, there's no reason the server should store the NPC unless the game is meant to be extremely persistent. It might as well just generate a new one when player 2 walks into the room. Less resources to keep track of. But this gets into gameplay too much which can be solved by setting reset timers on rooms or enemies such that no activity for a time and an NPC is automatically stored/destroyed.

Share this post


Link to post
Share on other sites
Thanks for the reply.
I basically know that stuff already.

I'm not having a problem with 1 enemy. I'm having a problem with 1,000,000 enemies. At the moment I have successfully created a smooth scrolling room with 250,000 enemies complete with rendering and working collision detection.

The only limitation on the number of enemies I can create is virtual memory.
I am working on an engine that will use a room-based system and remove enemies from memory in inactive rooms. I expect most rooms to be active anyway so that will only help part of the time. I gained a huge performance increase by eliminating a variable assignment in the active enemy counter for loop.

Specifically I changed:

count++;
enemyindex[count]=count_index;

to

enemyindex[count++]=count_index;


I was already using a timer with SDL_Delay for the main game loop.
If I add a timer to the render code seperately it either makes the screen blink if it is set higher than the tick rate, or it doesn't have much of an affect at all if I set it lower. It does increase performance a lot but it's no good if the enemies disappear. Apparently the render loop can't read from my array except for when the timer is going off. Maybe I could assign values to pointers and then reference the pointers from the render loop instead. As far as I know the timer doesn't create a seperate thread.

I know the performance will increase drastically when I move the collision code off the client to the server, and eliminate the unneccessary rendering, but I'm doing this because I can optimize the collision detection by checking FPS on the client while it is running. What I plan to do is send each client a TCP packet containing all of the active enemies and their locations as they enter a room.
Then the client will handle rendering the onscreen enemies. I will only collision check enemies that are actually visible to a players client.
There's just no way of getting around checking all the active enemies with a for loop to see if they are onscreen and need further processing.
The actual loop will probably have a lot less than 1,000,000 enemies I'm just trying to optimize it as much as possible since the server will have to handle so many other things. Also when I add multiplayer functionality that will tax the loop more as it will have to check each enemy against all the players bullets instead of just 1. I'm shooting for at least 500 player capacity.

I am going to have say 100+ rooms of various sizes. Around 50+ enemies per room. I can unload enemies from inactive rooms, but if they are all active the server will have to check them all.
I can't delete objects from server memory in active rooms because they will be persistent.

I am thinking about doing it like pixel perfect collision checking.
ie. you check first for a collision between 2 circles or squares to save cpu power, then if you have a collision proceed to check pixels for collisions.

My idea is to check each room to see if a player is in it, if so mark the room active. Then break the rooms into a grid and only process grid blocks within view of a player. Then I'll add the enemies in each active grid block to a new array to be tested against bullets. I'll assign each player a room as they enter and only check for collisions in the active grid blocks in the room the player is in. To put a suggestion from here to use I was thinking about having a control object for each area that will do AI for enemies in the background and
wait until the enemies are updated by a client coming near to apply changes to the objects serverside.

I just need advanced optimization tips from some pros.
I mainly want to avoid server lag caused by slow collision checking.
I also want to minimize the TCP data sent to conserve bandwidth.

Would a vector array be the fastest way to add active enemies to the servers collision checking loop? Why can't my render code draw enemies when I put the code that updates their x,y coordinates inside a timer?

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?

They don't actually have to move around and interact with each other even when they are offscreen... they only have to appear to the player as if they were moving and interacting when offscreen...

Since it's hard to explain this in terms of enemies, I'll explain the concept in terms of a burning building. You should be able to extrapolate from here and figure out how it may tie into your specific needs.

Imagine a 2D tile map of a building. One tile is on fire, and every 10 seconds any tile that is adjacent to a flaming tile catches fire. So 30 seconds in, the fire has spread three times.

If the player is not anywhere near the flaming building, processing the spreading fire is a waste of cycles. Instead, all it needs to keep track of is how much time has elapsed since the fire was started. When the player gets near enough to the house that it loads into memory, it uses this elapsed time to calculate which tiles should be on fire. So if 30 seconds have passed, the "spread fire" function is called three times upon loading the building (giving the illusion that the fire has been spreading while the player has been gone).

This means that there is no actual processing going on unless a player is nearby, but the player will never be able to tell the difference. Another example: Imagine an army of 5000 soldiers marching from one city to another. If the player isn't there to see it, it can be internally tracked simply by a position and a radius on the world map. If the player nears the army the soldiers are spawned wherever there is open ground, making it appear to the player as if each soldier had been walking the whole distance, when in reality the army just came into existence.

Now imagine that a war breaks out and this army loses 1500 units. Store this as a damage modifier against the army itself, and the next time the player "finds" this army it will dynamically spawn with 1500 less units. In this way you're not tracking who died, just how many.

Of course, you can extrapolate this into all sorts of different uses, both in large and small scale. The key part is to make as much of the information dynamically-generable as possible so that you don't have to do a bunch of per-frame processing for each monster/unit.

Good luck!

Share this post


Link to post
Share on other sites
I was simplifying, and it really depends on the network design, Sirisian.
I wasn't sure if "heh, it's always fun when you see someone speculating" was an insult or not, but I am a network programmer. Was in a hurry when writing the explanation. Good luck 00arch00.

Share this post


Link to post
Share on other sites
Quote:
I am going to have say 100+ rooms of various sizes. Around 50+ enemies per room. I can unload enemies from inactive rooms, but if they are all active the server will have to check them all.

That's of the order of 5000 entities, not a million. There's a big difference there. For 5000 entities, don't even bother trying to be clever on the server side, any reasonable machine will be able to deal with that trivially (as long as the AI for each one doesn't need to know about all the others, I suppose). If you restrict your network notifications to the 50+ per room, then that shouldn't saturate client-side bandwidth either; server-side bandwidth could be a problem and you will need to look at professional hosting if this is a rapid-update game, but I don't think you can avoid updating everything in your current room fairly often.

Don't prematurely optimise.

Share this post


Link to post
Share on other sites
Taking what Bob Janova say and adding one further step if the server knows where each client is and knows how far offscreen each enemy is it can further reduce updates concentrating bandwidth on those that really matter to the player.

Share this post


Link to post
Share on other sites
Quote:

Quote:
I am going to have say 100+ rooms of various sizes. Around 50+ enemies per room. I can unload enemies from inactive rooms, but if they are all active the server will have to check them all.


That's of the order of 5000 entities, not a million. There's a big difference there. For 5000 entities, don't even bother trying to be clever on the server side, any reasonable machine will be able to deal with that trivially (as long as the AI for each one doesn't need to know about all the others, I suppose). If you restrict your network notifications to the 50+ per room, then that shouldn't saturate client-side bandwidth either; server-side bandwidth could be a problem and you will need to look at professional hosting if this is a rapid-update game, but I don't think you can avoid updating everything in your current room fairly often.

Don't prematurely optimise.


Thanks for your reply.

If you multiply 5000 entities x 200 players you have 1,000,000. I'm looking to have 500 players or so if I can make it happen.
Assuming there were 500 players on at one time, that's already 2,500,000 possible iterations. Also every player and enemy will have 4 weapons each, except low levels.
There will be a significant amount more processing to do on all the active enemies, players, bullets, lots of maneuvers, etc. Enemies will interact heavily with each other. It will have quite complicated AI. I want chat too, but I'm just going to put that on another server. The work adds up fast.

It is possible for all the rooms to be active at the same time, and most of the enemies in each room. Some rooms also might have over 200 enemies.
If there are 500+ players online there's a good chance there will be at least 1 player in each room, which will throw a lot of optimizations out the window. So I'm not so much prematurely optimizing as just trying to be cautious and plan ahead so I don't run into as much trouble later.

I will definately be using professional hosting. It will be as rapid-update as possible. The 4 weapons will have a locking target system, but there will also be another moving projectile weapon. That's where I really need the speed. I want the collision to be as fast as possible so players don't get too frustrated by not being able to hit their targets. I'm not concerned at all about the client bandwidth. I'm concerned with the server bandwidth, and more importantly the server cpu usage. If the loop isn't fast enough it will eat the cpu and drop packets and be one big lagspike.

I do appreciate your input though Bob. I hope the server won't have any problem with it, but it never hurts to be prepared for the worst. I was being a little conservative with my estimates, I would like to make the world as large as possible. Just thought I'd start with something a little more reasonable.

I don't know exactly what kind of performance to expect from a pro game host. About the best I've seen was a quad core with 4gb ram and fiber optic connection. That should be a bit peppier than ole Bessy here. That's an expensive rig though. If I can make the code faster and use less cpu I could save money as well =D
From what I've seen better cpu and more ram cost a lot more money on a game host. The bandwidth is mostly the same.



//////////////////////////////////////////////////////////////////////////////
// Special thank you to Jbourie, excellent advice - I will use some variation of
// that idea wherever possible to reduce cpu usage. I'll wait until I try it out
// before I ask you any more questions about it.
///////////////////////////////////////////////////////////////////////////////











Share this post


Link to post
Share on other sites
Quote:
If you multiply 5000 entities x 200 players you have 1,000,000

You're surely not spawning a whole new world for each player that signs on, though? (Otherwise it's not a multiplayer experience at all.) A million possible interactions is fine, although you shouldn't actually have every entity interacting with every player every frame, in most cases. But it's still only 5200 (5000 NPCs plus 200 players) entities that need to be updated and stored.

Share this post


Link to post
Share on other sites
Quote:
If you multiply 5000 entities x 200 players you have 1,000,000. I'm looking to have 500 players or so if I can make it happen.
Assuming there were 500 players on at one time, that's already 2,500,000 possible iterations. Also every player and enemy will have 4 weapons each, except low levels.
There will be a significant amount more processing to do on all the active enemies, players, bullets, lots of maneuvers, etc. Enemies will interact heavily with each other. It will have quite complicated AI. I want chat too, but I'm just going to put that on another server. The work adds up fast.


Is this a shared world, or single-player game that for some reason runs on a remote server?

In a shared world, you have one instance of each, the enemy, room and player. So it's a sum. 5000 enemies are 5000 enemies, regardless of whether there's 1 player or 1000.

If you want to keep a copy of client state on server, that's no problem either - just pass pointers to server-side client-state. You still only update 5000 enemies.


As a comparison, in the server I worked on, there were over 1000 possible persistent entities (=anything, quest entries, inventory items, ...) per player, with thousands of possible concurrent players, out of a total of tens of thousands of accounts in addition to static world.

At any given step, the number of entities that needed attention was between dozens and hundreds. This is further improved by locality of actions. A player that's fighting will be updating itself 10 times a second, and the mob it's fighting. So ~50 events will affect 2 entities total per time-step (250ms in my case - for "real-time" actions, 4 times a second was enough). Even in large population areas, the number of events that occurred was in hundreds, or thousands under heaviest stress, but only affecting hundreds of entities.

Are you sure you got your math right?

Persistent world items were either updated differentially on as-needed basis (a tree that grows will check its size once someone wants to cut it down, or comes in range, or some similar criteria). The simulation remains global, but is updated only as needed). So no need for global pass, especially since database can contain hundreds of millions of entities.

Share this post


Link to post
Share on other sites
Demo:
http://stupidfresh.info/demo.rar

Help wanted page:
http://www.gamedev.net/community/forums/topic.asp?topic_id=490331

That's what I'm working with.
I'm glad everyone seems to agree that the server should have no problems keeping up. This will be my first attempt at making a large-scale server. So far it sounds like it will be easier than I thought. I have some winsock experience, I was just worried about cpu usage on the server. Hopefully it's not going to be too much of a problem.

It's a shared universe.

Share this post


Link to post
Share on other sites
Quote:
everyone seems to agree that the server should have no problems keeping up


Don't assume that that will be the case -- if you implement something wrong, it's very easy to make the server choke. However, it should be possible and straightforward to implement the design you've described so far, without choking a modern server computer. What we're saying is that you "just" need competent implementation -- not rocket science or secret super-inventions.

Share this post


Link to post
Share on other sites
I wanted to point out that:


count++;
enemyindex[count]=count_index;


and:


enemyindex[count++]=count_index;


is not the same thing. You're looking for:

enemyindex[++count]=count_index;

Share this post


Link to post
Share on other sites
Quote:

Bagheera

I wanted to point out that:

count++;
enemyindex[count]=count_index;

and:

enemyindex[count++]=count_index;

is not the same thing. You're looking for:

enemyindex[++count]=count_index;


You're right. Good call. I had it wrong the first time.
The first code would start counting at 1.
I needed to start at 0 instead.
Thanks for pointing this out.

Quote:

hplus0603

Quote:
everyone seems to agree that the server should have no problems keeping up

Don't assume that that will be the case -- if you implement something wrong, it's very easy to make the server choke. However, it should be possible and straightforward to implement the design you've described so far, without choking a modern server computer. What we're saying is that you "just" need competent implementation -- not rocket science or secret super-inventions.


Ok we shall see if I have what it takes. I'm pretty comfortable with winsock, so I feel good about it.

I did some work on it yesterday:
enemies move on timers
enemies change direction on timers
enemies collide with walls
enemies show thrust when moving
tweaked the render code
added background music

Maybe you could tell me what would be the normal way to
split the world into a grid? I need to do this because a 32bit int
can't hold the x,y coords. Is this what a quad tree would be good for?












Share this post


Link to post
Share on other sites
Quadtrees are alright, but if you can sacrifice the RAM then I'd say go with a uniform grid. As in make a Cell class. Then make a multidimensional array of them. The cell class has a linked list of entities. So you insert objects into the cells. It's extremely easy to cull objects and serialize what you need and don't need since you know every player's view rectangle then you just expand it a bit and it normally works out well. There's more advanced methods, but that should get you started.

Share this post


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

  • Advertisement