Performance problems with lots of AI entities
by Tomas Hron · in Torque Game Builder · 06/30/2007 (12:41 pm) · 14 replies
Hi!
First, sorry for my bad english and for that I'm quite noob in torque, so please be patient with me.
I have serious performance problems with my AI scheduled functions. I want to have lots of fast AI fighting entities, approx. 150 in one level. Each of them need to find nearest enemy, follow him and attack him, all the time.
With my solution (which is written below) I have "choking" performance problems with only about 15 of this AI entities and I wanted 150!
Here's the simplified code:
Here starts the problem. Every entity needs to "think what to do" every 200 ms.
This function is taken from Clint Herron's Air locked (which helped me a lot) and is cousing most of the slow down but not all of it.
Another slow down, caused with creating lots of bullets (I think).
I hope you understand me and finaly my question: Is it possible to have so many "thinking" entities in one level? If is what I'm doing wrong? I will be grateful for any suggestion or for pointing me to any solution of my problem.
First, sorry for my bad english and for that I'm quite noob in torque, so please be patient with me.
I have serious performance problems with my AI scheduled functions. I want to have lots of fast AI fighting entities, approx. 150 in one level. Each of them need to find nearest enemy, follow him and attack him, all the time.
With my solution (which is written below) I have "choking" performance problems with only about 15 of this AI entities and I wanted 150!
Here's the simplified code:
function enemyClass::onLevelLoaded(%this, %scenegraph)
{
%this.think();
%this.setForwardMovementOnly(true);
%this.setForwardSpeed(60);
}Here starts the problem. Every entity needs to "think what to do" every 200 ms.
function enemyClass::think( %this )
{
%this.acquireNearestTarget();
%this.followTarget();
%this.schedule(200, "think");
}This function is taken from Clint Herron's Air locked (which helped me a lot) and is cousing most of the slow down but not all of it.
function enemyClass::acquireNearestTarget( %this )
{
%this.target = "";
%sceneGraph = sceneWindow2D.GetSceneGraph();
if( isObject( %sceneGraph ) )
{
%gameObjs = sceneWindow2D.GetSceneGraph().getSceneObjectList();
// Look through all of the scene objects...
for( %cnt = 0; %cnt < getWordCount( %gameObjs ); %cnt++ )
{
%curObj = getWord( %gameObjs, %cnt );
// If we're dealing with a friednly object
if( %curObj.class $= "friendlyClass" )
{
// If we have a target already (from previous loops through this function)
if( isObject( %this.target ) )
{
// Check to see if we're closer
if( t2dVectorDistance( %curObj.getPosition(), %this.getPosition()) < t2dVectorDistance( %this.target.getPosition(), %this.getPosition()))
{
// If so, then take the closer object as our new target
%this.target = %curObj;
}
}
else
{
// If there is no target already, then any available target is closer than no target. So target it!
%this.target = %curObj;
}
}
}
}
}function enemyClass::followTarget(%this)
{
//code for following enemy
...
..
.
if( is distance and angle good enough)
{
%this.fire(1);
}
else {
%this.fire(0);
}
}Another slow down, caused with creating lots of bullets (I think).
function enemyClass::fire(%this, %val)
{
if (%val == 0)
{
return;
}
%this.projectile = new t2dStaticSprite()
{
scenegraph = %this.scenegraph;
class = "enemyBulletClass";
};
%this.projectile.setImageMap( particles1ImageMap );
%this.projectile.setSize("1 5");
%this.projectile.setCollisionActive(true, true);
%this.projectile.setCollisionResponse("KILL");
%this.projectile.setCollisionPhysics(false, false);
%this.projectile.setCollisionDetection("FULL");
%this.projectile.setCollisionCallback(true);
// kill the bulet after it leaves the screen
%this.projectile.setWorldLimit( "KILL",(%this.getPositionX() - 120) SPC (%this.getPositionY() - 120) SPC (%this.getPositionX() + 120) SPC (%this.getPositionY() + 120));
if (!isObject(%this.projectile))
return;
if (!isObject(%this.target))
return;
%this.projectile.setPosition(%this.position);
%this.projectile.setRotation(%this.rotation);
%this.projectile.setLinearVelocityPolar(%this.rotation, %this.projectileSpeed);
}I hope you understand me and finaly my question: Is it possible to have so many "thinking" entities in one level? If is what I'm doing wrong? I will be grateful for any suggestion or for pointing me to any solution of my problem.
About the author
Recent Threads
#2
Your SimSet solution, teached me something new, which is definetly very useful, however helped me only a bit, because I'm trying this in test level, where are only AI entities (75 enemy, 75 friendly) and player. Simset reduced "objects to acquire" to a half, so my FPS is no longer 0.4 , but now 1.0 :). But in levels with lot of objects is using of SimSet absolutely right way.
I've already tried randomizing values of shchedule from 200-500 (500 is the max, because enemies are chasing each other very fastly, and this schedule is also used for firing, which should be something like machinegun and 500 for machinegun is quite a high value). But this isn't prune away the jerking, it's only do small jerking all the time instead of 5 "big jerks" per second.
So my opinion is that:
1) I'm missing something important which should solve this problem easily, because I'm noob.
2) Or my concept of this AI functions is unsuitable for lots of entities in TGB, and I need to completely redesign it.
07/02/2007 (3:32 am)
Thank you David for your suggestion!Your SimSet solution, teached me something new, which is definetly very useful, however helped me only a bit, because I'm trying this in test level, where are only AI entities (75 enemy, 75 friendly) and player. Simset reduced "objects to acquire" to a half, so my FPS is no longer 0.4 , but now 1.0 :). But in levels with lot of objects is using of SimSet absolutely right way.
I've already tried randomizing values of shchedule from 200-500 (500 is the max, because enemies are chasing each other very fastly, and this schedule is also used for firing, which should be something like machinegun and 500 for machinegun is quite a high value). But this isn't prune away the jerking, it's only do small jerking all the time instead of 5 "big jerks" per second.
So my opinion is that:
1) I'm missing something important which should solve this problem easily, because I'm noob.
2) Or my concept of this AI functions is unsuitable for lots of entities in TGB, and I need to completely redesign it.
#3
I've had similar problems in implementing AI in a very similar fashion to how you've done it. In my top-down space game, I'll have 4 AI-controlled ships, each firing weapons (like homing missiles) that have AI, and I often see a slowdown. Lots of bullets can also cause a slow-down.
I disagree with David that an AI doesn't need to think 5 times a second. Action/reaction between a player and AI can be pretty fast, especially with the bullets flying. If it only takes, say, 2 seconds for an object to move across the screen, too slow of thinking wouldn't cut it. While I agree it is a good idea to randomize a little bit for the sake of diversity, it's fairly obvious to a human to see that the AI is thinking slowly. So I don't think that's a solution.
What I have noticed is that if I end the level then reload it, that the slow-down goes away. Perhaps it's a problem of "schedule" calls not properly being canceled? When a ship dies, do you terminate its thinking loop?
07/02/2007 (12:17 pm)
Tomas:I've had similar problems in implementing AI in a very similar fashion to how you've done it. In my top-down space game, I'll have 4 AI-controlled ships, each firing weapons (like homing missiles) that have AI, and I often see a slowdown. Lots of bullets can also cause a slow-down.
I disagree with David that an AI doesn't need to think 5 times a second. Action/reaction between a player and AI can be pretty fast, especially with the bullets flying. If it only takes, say, 2 seconds for an object to move across the screen, too slow of thinking wouldn't cut it. While I agree it is a good idea to randomize a little bit for the sake of diversity, it's fairly obvious to a human to see that the AI is thinking slowly. So I don't think that's a solution.
What I have noticed is that if I end the level then reload it, that the slow-down goes away. Perhaps it's a problem of "schedule" calls not properly being canceled? When a ship dies, do you terminate its thinking loop?
#4
One time savings would be to decouple the firing, targetting, and target aquiring code. For instance, the AI ships probably only need to aquire a target once a second, but they could still be firing 5x or 10x a second. This could either be two separate schedules, or one schedule at the faster rate where you keep a counter and run the aquisition code every fifth time through.
07/02/2007 (1:37 pm)
Given that they're all using the same list of objects, each AI entity doesn't really need their own list. One set of objects could be generated at the start of the level (and added to if necessary), and accessed through a global variable. Although compared to each object keeping a set, the only thing this saves is startup time and memory.One time savings would be to decouple the firing, targetting, and target aquiring code. For instance, the AI ships probably only need to aquire a target once a second, but they could still be firing 5x or 10x a second. This could either be two separate schedules, or one schedule at the faster rate where you keep a counter and run the aquisition code every fifth time through.
#5
PS: you don't need new sets unless you plan 32 player+ matches :) ... you could use the graph groups for example ... 1 for the player, 2 for the AI, 3 for all projectiles or something similar ...
07/02/2007 (2:02 pm)
Is there a reason you would put the missiles in this set at all? They are not needed by any other AI entity ... so putting them in there just makes the AI much slower with no gain. *at least from what I see with my restricted point of view on the whole need and requirements*PS: you don't need new sets unless you plan 32 player+ matches :) ... you could use the graph groups for example ... 1 for the player, 2 for the AI, 3 for all projectiles or something similar ...
#6
It's also possible for you to have a schedule that just processes all the AI for all your units, rather then having say ... 150 schedules ... you have one schedule, which runs through a SimSet and processes the AI for the units one by one ... this schedule can spawn off additional 'one time' schedules if getting to the point faster is necessary (ie; process the queue quickly but let the individual items take there time, if necessary) ...
As Kalle mentioned ... decoupling the 'acquire target' and the 'fire missle' code is a major performance boost as well ... which is also where my increased time between AI updates came from ...
Sorry if my post was a tad confusing, haha ... but basically ... Chris and Kalle sort of hit the nail on the head with their's ...
1) Rather then grabbing a list of all the objects in the scene graph, put the objects you want to look at in a SimSet -- preferably global so it's a reusable 'list'
2) If your schedule runs every 50ms, count upwards from 0 and check the value of the counter ... if the value is 200 (1s) then enter the 'acquire target' if block and reset the counter ... process your 'fire missile' in another similar conditional block ... keep your conditions simple and fast ...
3) Possibly move all your AI code to it's own scheduled function, which works on two SimSet's ... EnemySet and FriendlySet ... for each EnemySet ... find nearest target, begin firing ... possibly spawn off a new 'one time' schedule that does not repeat itself for each of these so as to 'thread' them (more or less) ...
Oh and ... don't forget the cookies in the oven!
07/02/2007 (2:02 pm)
When I mentioned the increased time between thought, I was referring to AI scripts that manage movement for something similiar to say ... an AI Bot in a doom style FPS ... or the AI in a 2d RTS ... if your gameplay requires your AI to think faster, then thats a different story ... It's also possible for you to have a schedule that just processes all the AI for all your units, rather then having say ... 150 schedules ... you have one schedule, which runs through a SimSet and processes the AI for the units one by one ... this schedule can spawn off additional 'one time' schedules if getting to the point faster is necessary (ie; process the queue quickly but let the individual items take there time, if necessary) ...
As Kalle mentioned ... decoupling the 'acquire target' and the 'fire missle' code is a major performance boost as well ... which is also where my increased time between AI updates came from ...
Sorry if my post was a tad confusing, haha ... but basically ... Chris and Kalle sort of hit the nail on the head with their's ...
1) Rather then grabbing a list of all the objects in the scene graph, put the objects you want to look at in a SimSet -- preferably global so it's a reusable 'list'
2) If your schedule runs every 50ms, count upwards from 0 and check the value of the counter ... if the value is 200 (1s) then enter the 'acquire target' if block and reset the counter ... process your 'fire missile' in another similar conditional block ... keep your conditions simple and fast ...
3) Possibly move all your AI code to it's own scheduled function, which works on two SimSet's ... EnemySet and FriendlySet ... for each EnemySet ... find nearest target, begin firing ... possibly spawn off a new 'one time' schedule that does not repeat itself for each of these so as to 'thread' them (more or less) ...
Oh and ... don't forget the cookies in the oven!
#7
07/02/2007 (2:02 pm)
You also might try a slight redesign of the way the AI is thinking. The basic idea would be to have a single AI-manager like class, which has a think method. This think method would be scheduled to be called e.g. every 200ms. It then iterates through all AI objects registered with it (which would have to be done during startup or when an AI object is added) and updates every single one of them, e.g. by calling their respective think method. The major difference is that you only have one schedule in this scenario, instead of 75 for the enemies and another 75 for the friendly units. The larger number of schedules might have a considerable overhead, although I'm not really sure about this.
#8
You know, I tried a schedule manager a while back and didn't see tons of improvement. In Tomas' case it might help since he has so many objects "thinking," but I ended up not using the method myself. I do know that runaway schedule loops can be a major problem. I recently added a couple lines of code doing a "if this schedule running, cancel it" action before any new schedule was created (instead of just the ones I thought needed it). It helped alleviate a lot of the problem.
Has anyone really done a TGB game where the screen is simply filled with sprites moving at high speeds? My game actually is relatively slow compared to some of those crazy vertical shooters. So I'm curious if someone has proved what realistically can be done with scripted AI.
07/06/2007 (12:49 am)
@Stefan:You know, I tried a schedule manager a while back and didn't see tons of improvement. In Tomas' case it might help since he has so many objects "thinking," but I ended up not using the method myself. I do know that runaway schedule loops can be a major problem. I recently added a couple lines of code doing a "if this schedule running, cancel it" action before any new schedule was created (instead of just the ones I thought needed it). It helped alleviate a lot of the problem.
Has anyone really done a TGB game where the screen is simply filled with sprites moving at high speeds? My game actually is relatively slow compared to some of those crazy vertical shooters. So I'm curious if someone has proved what realistically can be done with scripted AI.
#9
As for good scripted IA, it can be done, but maybe not with that much units on a single screen (at least not without some dirty tricks). You'll have to keep it simple.
07/06/2007 (6:19 pm)
Make a circular triggers, mounted on any potential targets, that tell near enemy ships to attack it using onenter callback. No schedule is needed, it'll simplify a good part of your IA.As for good scripted IA, it can be done, but maybe not with that much units on a single screen (at least not without some dirty tricks). You'll have to keep it simple.
#10
as for the trigger concept ... that works ... but your AI units would still need schedules to perform general 'in the basic direction of' unless you wanted them to be 'dead' until they entered the trigger area ... and which point, you'd probably want a very large trigger area so that the units activate before they actually come on screen --
as for 'on screen', I am assuming that you have 150 AI units in the level ... not all on screen at the same time ...
if they are all on screen at the same time and they'd all be doing something, the trigger wouldn't help ... cause you'd still have 150 AI logic routines running constantly in the OnEnter/OnStay to keep the units 'alive' that are on screen ...
Very puzzling ... ;)
07/06/2007 (7:11 pm)
Best approach to serious AI for lots of units would probably be to implement it on the engine side and not through script ... you'll remove a lot of the overhead from the script interpretation ... as for the trigger concept ... that works ... but your AI units would still need schedules to perform general 'in the basic direction of' unless you wanted them to be 'dead' until they entered the trigger area ... and which point, you'd probably want a very large trigger area so that the units activate before they actually come on screen --
as for 'on screen', I am assuming that you have 150 AI units in the level ... not all on screen at the same time ...
if they are all on screen at the same time and they'd all be doing something, the trigger wouldn't help ... cause you'd still have 150 AI logic routines running constantly in the OnEnter/OnStay to keep the units 'alive' that are on screen ...
Very puzzling ... ;)
#11
I was more thinking about a simplification of the "acquire nearest target" thing, using triggers for "aggro" zones on any potential targets.
But, yeah, trigger that activate enemies just before being visible is also a thing to do if they are not all on screen at the same time.
07/07/2007 (10:01 pm)
@DavidI was more thinking about a simplification of the "acquire nearest target" thing, using triggers for "aggro" zones on any potential targets.
But, yeah, trigger that activate enemies just before being visible is also a thing to do if they are not all on screen at the same time.
#12
07/10/2007 (7:03 am)
Many thanks to you all for your very interesting advices. I tried a lot of things (listed above and some other) during last week and nothing helped at all. I started to believe that it's not possible to have so many scripted AI, or "entites which are doing something" in TGB without some engine adjustements, or some dirty tricks (as mentioned by Benjamin). It's backbreaking trying to do something which shouldn't be possible and you dont know it. So without some proof that this is possible I wouldn't waste time on something what cannot be done, but again many thanks to you all, at least I learned some new things!
#13
I had the same problem as you. I spent about 3 days doing nothing but tracking down the problem. And I found it! It may not even be your AI at all, but just a problem exacerbated by the AI.
What I found out for mine was the following: the "thrust" schedule call didn't check to see if it had already been created. Thus, more and more thrust schedule loops were created. This wasn't a problem when I played as a human because I hit the thruster button so seldom. But the AI calls it 4 times a second, and thus the game would bog down immediately. Once I fixed the thruster code it hasn't slowed down since.
I also merged all the AI schedules into a single task manager. That's made things much cleaner for me. If you haven't done this, I recommend it (even if there's no direct speedup).
07/10/2007 (3:04 pm)
Tomas:I had the same problem as you. I spent about 3 days doing nothing but tracking down the problem. And I found it! It may not even be your AI at all, but just a problem exacerbated by the AI.
What I found out for mine was the following: the "thrust" schedule call didn't check to see if it had already been created. Thus, more and more thrust schedule loops were created. This wasn't a problem when I played as a human because I hit the thruster button so seldom. But the AI calls it 4 times a second, and thus the game would bog down immediately. Once I fixed the thruster code it hasn't slowed down since.
I also merged all the AI schedules into a single task manager. That's made things much cleaner for me. If you haven't done this, I recommend it (even if there's no direct speedup).
#14
iAI shows that quite good ... and it even has to do more work than AI in TGB as it is for TGE.
07/11/2007 (2:19 am)
Its definitely possible to do this.iAI shows that quite good ... and it even has to do more work than AI in TGB as it is for TGE.
Associate David Higgins
DPHCoders.com
function enemyClass::acquireNearestTarget( %this ) { %this.target = ""; %sceneGraph = sceneWindow2D.GetSceneGraph(); if( isObject( %sceneGraph ) ) { %gameObjs = sceneWindow2D.GetSceneGraph().getSceneObjectList();The last line, where you grab a list of every object in the scene graph ... is a MAJOR no-no ... of the 150 AI units you might have, I am assuming your level also has additional items ... such as background art, the player art, and perhaps other various items ... depending on how the level is built, you possibly have hundreds or thousands of items in the SceneGraph Object List ...
I would suggest this, in your 'friendlyClass' onAdd or OnLevelLoaded function, add each of your friendly units (the ones you want to be active at the time the game starts) to a private SimSet and just recurse through this SimSet ... which effectively reduces the performance factor quite a bit depending on what else is in your level ...
$friendlySet = new SimSet() {}; function friendlyClass::onLevelLoaded(...) { $friendlySet.Add(%this); } function friendlyClass::AcquireTarget(...) { %cnt = $friendlySet.getCount(); for(%x = 0; %x < %cnt; %x++) { } }That there should give you some extra 'unf' in your code ....
another thing I would suggest is ... not to schedule your AI 'think' function 5 times a second ... have more of a time gap between thought processes ... perhaps make the 'think' time difference a random value between 200 and 600 ... some of your enemies will appear to be a bit 'dumber' (slower) and some will appear to be 'smarter' (faster) ...
If you think about it ... does the AI really have to update it's movement 5 times per second? I honestly doubt it does ...
Hope this helps ...