Back to General and Gameplay Programming

How to manage multiple enemies/mobs in open world RPG

General and Gameplay Programming Programming Unity

Started by Jaime Gonzalez Bonorino September 28, 2015 11:54 PM

7 comments, last by Norman Barrows 8 years, 6 months ago

Jaime Gonzalez Bonorino

421

Author

September 28, 2015 11:54 PM

Hi there gamedev community,

I'll go directly to the question.

How is the best way to handle A LOT of enemies without slowing my game process?.

I am currently testing, i have a vector of an "enemy" class, and its fine for my testing purposes. The problem is, imagine i have +3000 enemies in my map, how can i manage to execute their IA Behavior, and test who the player attacked, etc.

Im currently using a for loop from 0 to MAX_ENEMIES_IN_GAME, but with +3000 enemies my fps will drop to almost zero hahaha.

Sorry for my bad english, i'll re-write the question if needed, just ask!

Thanks


for (int j = 0; j< MOBS_EN_JUEGO; j++)
	{
		_mobs[j].run(_pj.getX(),_pj.getY(),&_pj); //Make the enemy walk to player position
	}

EDIT: I thought something like, only test the enemies who are close to the player, but for selecting those enemies, i would have to do the same for loop, so... haha.

The only way i can think of it, its to make a bunch of 100x100 areas instead of a full map, so i can forget about the enemies that are not in the area

Servant of the Lord

33,739

September 29, 2015 01:34 AM

for() loops aren't slow. The logic they contain can be slow. Iterating over 100,000 objects shouldn't be a problem. If 3000 is slowing you down, it's the code within the for() loop. Could you post your run() function?

Are you re-doing the pathfinding every tick? You should only be doing the pathfinding when the environment changes, and just cache the result.
Are you doing complicated AI decision-making for every entity every tick? Try doing it every N tick. i.e. if you have 3000 entities, do 0-1000 AI logic one tick, 1000-2000 the next tick, and 2000-3000 the third tick. You still have every entity update/move every frame, but they only "rethink" every few frames.
As you mentioned, the farther away an entity is, the less frequently it should think. If an entity is 500 feet away, offscreen, maybe make it only think once every ten ticks. If it's really far away, don't update it at all if your game design permits it.
My guess is your real slowdown is that you're accidentally drawing all the entities even when they are off-screen. I doubt the code you posted is the real slowdown (unless it's actually doing pathfinding in the run() function). Have you actually profiled yet? Profiling tells you where your program is spending the most time.

Jaime Gonzalez Bonorino

421

Author

September 29, 2015 01:56 AM

for() loops aren't slow. The logic they contain can be slow. Iterating over 100,000 objects shouldn't be a problem. If 3000 is slowing you down, it's the code within the for() loop. Could you post your run() function?

Are you re-doing the pathfinding every tick? You should only be doing the pathfinding when the environment changes, and just cache the result.

Are you doing complicated AI decision-making for every entity every tick? Try doing it every N tick. i.e. if you have 3000 entities, do 0-1000 AI logic one tick, 1000-2000 the next tick, and 2000-3000 the third tick. You still have every entity update/move every frame, but they only "rethink" every few frames.

As you mentioned, the farther away an entity is, the less frequently it should think. If an entity is 500 feet away, offscreen, maybe make it only think once every ten ticks. If it's really far away, don't update it at all if your game design permits it.

My guess is your real slowdown is that you're accidentally drawing all the entities even when they are off-screen. I doubt the code you posted is the real slowdown (unless it's actually doing pathfinding in the run() function). Have you actually profiled yet? Profiling tells you where your program is spending the most time.

Thank you for the answer.

Actually, i dont implemented all that enemies yet, i was only trying to get a picture of some programming tricks for the case, so i dont really know if my game will slow down that much.
You gave me some nice ways to do it in case my design needs it, thank you, i would never came with the second one haha.

As for the drawing, i coded a camera system that ensures im only drawing only what i can see.

SeanMiddleditch

17,596

September 29, 2015 03:43 AM

Run a profiler on your game. Find out _for sure_ where the slowdown is.

If you're on Windows, use Very Sleepy as a free profiler. There's also a profiler built into Visual Studio.

If you're on Linux, consider perf, which is a very capable tool (though not the easiest to use because, you know... Linux).

Sean Middleditch – Game Systems Engineer – Join my team!

Ashaman73

13,718

September 29, 2015 04:24 AM

The problem is, imagine i have +3000 enemies in my map, how can i manage to execute their IA Behavior, and test who the player attacked, etc.

Here are some tips with pseudo code:

1. Have a next update/next ai time like this:


obj::updateAi() 
{
   // do something with obj

   
   if(is_player_around==true) {
     // hi-frequent update time
     obj.next_ai_updattime = current_time + 100;
   } else {
     // low-frequent update time
     obj.next_ai_updattime = current_time + 3000;
   }
}


main_loop:
for each obj in my_game_objects do
{
   if(obj.next_ai_updatetime<current_time) {
     obj.updateAI();
   }
}

2. use timed events, e.g. like this


addEvent(event) 
{
   obj.event_list.add(event);
   obj.next_event_time = min(event.execute_at,obj.next_event_time);
}
process_all_events_up_to_time(obj,time)
{
  min_event_time = MAX;
  for each event in obj.event_list do
  {
     if(event.execute_at<current_time) {
       event.execute(obj);
       obj.event_list.remove(event);
     } else {
        min_event_time = min(min_event_time,event.execute_at);
     }
  }
  obj.next_event_time = min_event_time;

}

main loop:
for each obj in my_game_objs do
{
   if(obj.next_event_time<current_time) {

      process_all_events_up_to_time(obj,current_time);
   }
}

3. for objects, which needs to be updated really seldomly, e.g. a pusling shrine which is active for only a few seconds after being triggered, use the event system instead of the update system like this:


pulsing_shrine_triggered_update(obj) = 
{

   // do something, e.g. heal nearby creatures

   // done ?
   if(!done) {
     // trigger again in 1 second
      obj.addEvent(pulsing_shrine_triggered_update,current_time+1000);
   }
}

4. if you use the tips from above, replicate the times in an array for faster memory access,because you really need to test only the timestamps most of the time. No need to access large objects all the time. Thought the performance benefit might be small to tiny ;-)

Ashaman

Gnoblins: Website - Facebook - Twitter - Youtube - Steam Greenlit - IndieDB - Gamedev Log

SeanMiddleditch

17,596

September 29, 2015 06:04 AM

(again, profile first, but...)

You can also use "AI Level of Detail." Enemies that are far away from the camera don't need to update as often because the player can't see them well or at all. They also don't need to have high-fidelity AI.

Reduce the frequency of AI ticks for an enemy based on distance and direction from the view frustrum. Far-away enemies don't need to be all that smart to look believable. Enemies that aren't even near the frustrum can't be seen at all and aren't likely to be seen soon, so they can be really dumb.

Also consider just simplify expensive calculations for those enemies. If the player can't actually see an enemy, there's no point to do high-fidelity path-finding. If the enemy is far enough away they can even just teleport around with nobody being the wiser. The same goes for any other expensive calculations. Friendly inter-NPC interactions can be disabled and inter-NPC combat can be simplified to basic rolls instead of the full combat system.

And of course, if the enemies are really far away, they can just be put on ice and stop updating entirely, or update very very infrequently.

Sean Middleditch – Game Systems Engineer – Join my team!

Norman Barrows

7,180

September 29, 2015 01:12 PM

Actually, i dont implemented all that enemies yet, i was only trying to get a picture of some programming tricks for the case, so i dont really know if my game will slow down that much.

sounds like the thing to do is a rapid prototype of 3000 enemies, and un-optimized AI. IE step one should be to see if brute force is good enough, or whether you have to "get jiggy with it".

if it turns out that a vector of 3000 badguys just updating them all isn't fast enough, reach for the profiler. it may indicate a need for the optimizations as described by Servant, Sean, and Ashaman.

then you can build the game knowing your already tested system will perform well.

always test brute force first. often it can be good enough. this is an approach i learned from Carmack and Abrams.

if brute force won't cut it, then its time for fancy algorithms.

Norm Barrows

Rockland Software Productions

"Building PC games since 1989"

rocklandsoftware.net

PLAY CAVEMAN NOW!

http://rocklandsoftware.net/beta.php

baseball435

286

September 29, 2015 01:44 PM

Depending on how large your map is you can split the map into separate sections or chunks. Each chunk would contain the entities that lay within it's bounds and it would only update/render those entities if the player is in or near the chunk.