Archived

This topic is now archived and is closed to further replies.

Edgware

ai framerate independence

Recommended Posts

Edgware    122
Hi All this could be interpreted as a ''not strictly ai question'' but here goes. Say I have several computer controlled characters with some sort of ai. Now say I wanted to update their ai however I dont want to update the characters every frame as the characters do not neccesarily have to be updated every frame (eg updating a bots state 60 frames per second may not be needed - may only update the computer agents state every 20 frames or so). I know that you could work it out with a simple counter and an if statement but are there other approaches eg spreading the ai over several frames? What are the approaches to ai frame rate independence ? Any ideas or suggestions

Share this post


Link to post
Share on other sites
liquiddark    350
You could (and probably should) consider threading your AI. It''s then easy to rate-lock your AI by simply putting the thread to sleep when your processing is done for the current time step.

HTH,
ld

Share this post


Link to post
Share on other sites
Plasmadog    205
Gamasutra had an article a while back which discussed this (among other things). It's a good article and gave me a lot of ideas.
It was something about implementing an "instant replay" feature. Try combining it with a scheduling system as described in their "egocentric AI" article. I have had some good results from this approach.

Edited by - plasmadog on February 7, 2002 8:45:55 PM

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
First of all, your physics and AI and rendering code should be completely independent of each other. So all of your objects should have a render() and update() call. Your main game loop should guarantee an update rate for the logic/AI (say 60hz) and you should render as often as possible.

This way, you guarantee how often your logic/AI code runs and it isn''t tied to how fast you can draw the frame.

Share this post


Link to post
Share on other sites
EvilCrap    134
multithreading ur ai might not be good - - what was one of those rules? dont multithread if your thread has to wait or sync to other threads? you dont want to start processing ai if your in the middle of rendering...

one thing u can try to do is process ur ai when ur waiting around, to say, sync a frame. this way, you arent necessarily processing ai when you could be drawing. however, this may not guarantee that your ai is ever processed very well, or, it may be over processed (if thats possible), so you will probably want to force process sometime or antoher.

it really depends on what kind of ai u got, is it hardcoded, or a script, or what? its really hard to tell you how/when to process your ai without knowing how ur implementing it.

if your using a script/scriptor, then its always possible to script in very small amounts each iteration. if its hardcoded, then things could get ugly...

Share this post


Link to post
Share on other sites
a person    118
umm, if you are multithreading nearly anything you will always have some sort of semaphore. ther are cases were this aint true, but if the thread is that seperated from your processes, then there is no point in running it in your processes. you could easily sync your ai to rendering without the ai interupting the rendering (well to a noticiable point). first you have the ai do its thing every x ms (sleeping when its not doing anything). render thread goes about its merry way except at the end of its cylce does a Sleep(0) to give up its reamaining time. the only time the ai thread haltst he render thread is when it needs to copy the game state. which would not take very long and would only halt the render thread at its start. look into CriticalSections() to ensure your cpu time gets splitthe way you want it, but becareful, you can seriously hose performence if used incorrectly.

now on to the question at hand. multi threading is not the answer. like framerate independent physics, you do the same thing for your ai. you render ai ever x ticks where x is some value of ticks. you can then render physics at some other value of ticks. these ticks are NOT what you get form getTickCount() and are not related. see the fixed time step rendering article which was here or on flipcode.com, it will show you a better idea of whats needed to be done then i will try to explain. but basically you do:

  
// PSUDEO code

#define TICK_MS_PH 33 // 30 times per second
#define TICK_MS_AI 50 // 20 times per second
#define MAX_LOOP 7


for(;;)
{
curTime = gettime();
maxCnt=0;
while((curTime-timeAI)>=TICK_MS_AI || maxCnt>MAX_LOOP)
{
// this would be 1 "frame" of ai

// and should update all things that need to be updated

Do_FakeSmart_Stuff();
timeAI+=TICK_MS_AI;
maxCnt++;
}
// not sure if it would be better to update this

// again or not, test both ways

// though this way MAY be more accuarte

curTime = gettime();
maxCnt=0;
while((curTime-timePH)>=TICK_MS_PH || maxCnt>MAX_LOOP)
{
Do_Fancy_Moving_Stuff();
timePH+=TICK_MS_PH;
maxCnt++;
}
// physics would dictate the interpolation between frames

float percentInFrame = timePH/TICK_MS_PH;
if(percentInFrame>1.0) // in case you bailed early

percentInFrame=1.0;
Render(percentInFrame);
elapsed=curTime-oldTime;
}


hope that helps explain what ppl have been suggesting (at least thats what i hope ppl were suggesting ). just be forewarned, the above psudeo code has a MAJOR flaw, and that is the ai will NOT see movement if the framerate drops too much. you really should be syncing your ai to your physics since when the world changes the ai should change. otherwise your ai will seem very flaky on slower pcs (any pc that can not handle approx double (this assumes ranges that go from 30-90) the framerate your shooting for in smallest tick length) going after things that are not there and such. you should be able to figure out what goes and what stays.

though for true spreading of ai over frames like you suggest would require multi threading or very good time keepign and a scripting system like in unreal. but in that case you are then doing multi threading any, just not with windows threads.

Share this post


Link to post
Share on other sites
Argus    118
quote:
Original post by Puzzler183
I feel a stupid question coming on...

Here it is: How do you thread somehting? What exactly is thread?
Don''t take this as gospel since it''s just my fairly simplistic understanding, but a thread is like a separate process - a set of instructions that takes up some portion of the cpu''s time.

Most computers only have one cpu, so they can only process one instruction at a time (not strictly true but close enough approximation). So they work on instructions in sequence/serial/one at a time. Creating a thread just means you have a new set of instructions that you want the computer to process. The computer then divides its time between that set of instructions, and any other threads that were already in progress. How the cpu divides up its time between different threads is up to the operating system, although you can usually give it some strong hints as to what you want it to concentrate on.

So for instance if you had 2 threads called a and b, then your cpu "instructions processed" timeline might look like :
ababbababaabaababababbbaabbababababa
The advantage of this is that if there isn''t much being done in a then the processor will do more of b''s instructions. The other (bigger) advantage is that you don''t have to worry about calling the AI to do calculations (much) - most of the time you can be sure that the cpu will be spending some time on the AI if it is in an active thread.

So what is being suggested is that you have the AI in a separate thread so that you have the cpu dividing its time between the main game thread and the AI thread without you having to code specifically for it. However, as has been noted, you don''t want the cpu switching to doing some AI instructions in the middle of an important tasks like updating the graphics. There are solutions to this which include suspending the AI thread until the grphics update is finished or giving it a low priority, but those are just technical details.

Of course there are concerns with threading such as synchronization, but as long as you know what the options are then you know what to look up.


Share this post


Link to post
Share on other sites
a person    118
if you thread ANYTHING using the os level calls, make sure you use Sleep() in your game loop or your threads will not get much time at all (read not enough for the ai to be run at a decent rate). if the ai AND game thread both compete for time, its all downhill. multithreading is a pain, and difficult to get right especially in realtime things such as games.

Share this post


Link to post
Share on other sites
Pyabo    124
Edgware, multithreading really is the optimal solution to your original question. "a person" basically didn''t bother to really understand the question or its implications, as he states himself that his pseudocode has a "major flaw" in that it is tied to the frame rate... hence it doesn''t solve the original problem!

Multithreading *is* an advanced topic, but trying to get around it by time-slicing your program''s execution based on tick-counts is NOT the way to go.

Argus, be careful of using the word "process" to define thread, as that will promote some confusion. These are two different things... a PROCESS has its own data and code space, which is independent of other processes running on a system, and can have multiple THREADs of execution. Each thread within a process shares the same memory space (which is why thread-safety mechanisms like critical sections and mutexes are necessary). Does this make sense?

Share this post


Link to post
Share on other sites
a person    118
umm, maybe you misunderstood what i meant by drop in framerate. if you really dont understand the code, here is a version that does not have that problem (its is synced to the physics like it should be).

  
// PSUDEO code

#define TICK_MS 33 // 30 times per second
for(;;)

{
curTime = gettime();
maxCnt=0;
while((curTime-time0)>=TICK_MS || maxCnt>MAX_LOOP)
{
Do_Physics()
Do_FakeSmart_Stuff();
time0+=TICK_MS;
maxCnt++;
// may want to update curtime as well

// curTime = gettime();

}
float percentInFrame = (curTime-time0)/TICK_MS;
if(percentInFrame>1.0) // in case you bailed early

percentInFrame=1.0;
Render(percentInFrame);
}


this does not have the frameate problem. i think the major thing you missed Pyabo is the fact that the reason low framerates would kill the ai is because its not being synced to the physics (hence the gamestate). you could modfy the code to stagger the time for the ai (ie update in incremnets of physics updates). multithreading has even more issues and in the end will be a poor solution for ai in a game, especially if the ai relies on the game state. if the game state changes are based on framerate then the ai will be based on framerate no matter how you seperate it (via fixed time steps or multithreading).

here is a simple logical proof.

Given
AI is dependent upon gamestate
gamestate is dependent upon physics
physics is NOT dependent upon framerate
---
AI is NOT dependent upon framerate.

Given
AI is dependent upon gamestate
gamestate is dependent upon physics
physics is dependent upon framerate
---
AI is dependent upon framerate.


as you can see the ai is only dependent upon the framerate IF the physics is. which is why you use fixed time steps AND not multithreading with framerate dependent physics. i was hoping to break down the problem in a simply fashion and allow him to make the final connection (ie grouping physics with ai), unfortunatly i assume since YOU did not see the connection, then he probally did not see it.

btw Pyabo, please explain to me if you can, how ai can be framerate independent if the physics hence the gamestate is framerate dependent when you thread the ai.

so in the end, Pyabo, its YOU who dont really bother to comprehend the question and its implications. i probally should not have assumed that Edgware knew how ai worked (ie its linked to the gamestate no matter how you slice it).

Share this post


Link to post
Share on other sites
Edgware    122
Thanks for the replies people. I was not just after one way of seperating out the ai from the frame rate/world state so all the different opinions are great

Share this post


Link to post
Share on other sites
Pyabo    124
Ummm.... OK. In the interest of diplomacy, I will concede that you are correct in all things. LOL

Actually, I apologize that I sounded so snippy in my original post, but I was somewhat aghast at someone suggesting that "multi- threading is not the answer." In fact, multi-threading is really THE ONLY answer. Here I go getting snooty again.

The fact of the matter is, this kind of thing is the perfect task to apply multi-threading methodology to. Yes, multi-threading can be ugly, and yes it''s complicated at times, and yes it can also be a big pain the ass. I once spent an entire week tracking down a SINGLE bug due to a thread race condition. However, that being said... multithreading is absolutely necessary in almost any app that actually does more than one single thing, and this definitely includes games. Don''t run from multithreading because it''s difficult it... embrace it, learn it, love it.

Share this post


Link to post
Share on other sites
Unifex    122
Chaps, I have been reading what you have been saying and I think either way can work, its how you implement it.
If it were me, I would give the AI reaction times (stored in the bots class). The reaction time for each bot is incremented by 1, and when their reacion time is met (say 1.2 seconds to notice and react) (60FPS = 60 updates to the AI reaction counter, when it meets 72 it can change its action). This way you rarely call the AI code for a bot on more than once per bot. Simply set the reaction timer staggered when bots are loaded.

What happens? Ok, a bot decides through its AI to go to point X to get a gun. 1 second later, it gets jumped by a player. Low and behold, its reaction timer is reset and for 1.2 seconds its prone before it can change its action (re-run the AI). When the AI runs, it takes a single frame to process and decide what its gonna do, suddenly it dives for cover and fires at the same time.

Bingo. We have a bot that reacts. So, I would created an array of the bots (say we had 10 bots), BOT BOTARRAY[10] (BOT is my custom class with lots of information and storage for convenience and memory of moves it likes, that kinda stuff). Then, process the bots in a wrapped function
process_bots(void)
{
int i = 0;
//walk through the array for each bot
for (i = 0; i < 10; i++)
{
//is the reaction_time greater than the reaction counter?
if (BOTARRAY->reaction_time > BOTARRY[i]->reaction_count)
//if so, they dont get to update
continue;
//ok, lets process its AI
update_ai(BOTARRAY[i])
{
//We could do a quick check here to see if it needs to
//process here, it may not want to change its action
//e.g run for a weapon, go for health
//Do all the AI stuff here
...
}
}
}

This is pretty basic and no where near indepth enough for realtime AI, but you get the idea.
AI is so important in FPS type games that CPU time should be given to it. I wouldnt set up a thread for it, I would make sure I only processed AI for one bot per frame, and optimise later with this in mind.

Share this post


Link to post
Share on other sites
Ferretman    276
quote:
Original post by Pyabo
Actually, I apologize that I sounded so snippy in my original post, but I was somewhat aghast at someone suggesting that "multi- threading is not the answer." In fact, multi-threading is really THE ONLY answer. Here I go getting snooty again.

The fact of the matter is, this kind of thing is the perfect task to apply multi-threading methodology to. Yes, multi-threading can be ugly, and yes it''s complicated at times, and yes it can also be a big pain the ass. I once spent an entire week tracking down a SINGLE bug due to a thread race condition. However, that being said... multithreading is absolutely necessary in almost any app that actually does more than one single thing, and this definitely includes games. Don''t run from multithreading because it''s difficult it... embrace it, learn it, love it.


Heh...I see I missed some fun whilst book editing!

I agree with Pyabo...multithreading is really the best way to handle this. If you multithread you gain immense control over your AI and your physics and you can still plug in timers to get a finer degree of control (as others have suggested) if you want. And honestly it''s not all that hard to learn; synchronization (making sure one thread isn''t trying to read a variable that another thread is in the middle of writing) is pretty easy with modern programming languages.




Ferretman

ferretman@gameai.com
www.gameai.com

From the High Mountains of Colorado

Share this post


Link to post
Share on other sites
Qatal    127
quote:
Original post by a person
umm, if you are multithreading nearly anything you will always have some sort of semaphore


Dont multithread. its bad and messy and win32y and semaphored and all sorts. i have had hideous problems trying to multithread things even when writing something as undemanding as a midi sequencer. (that''s not realtime a game would be worse)

In the same project, i ended up using a system like the one described earlier, manually counting system ticks or game ticks or anything and doing the timing myself. and it works beautifully.

the only downside is the its very easy for your code to get messy, especially if you have several "timed processes" that run at different frequencies.

just my opinion. im a delphi coder, so im not sure how much you want to listen to me. :D

Share this post


Link to post
Share on other sites