I'm working on a Java game/simulation and there are several NPC's that will be active at once. I want to implement different types of AI for each NPC, but one problem I came across right away was that I want each NPC to have at most X amount of time to "think" when it is that NPC's turn to think. In other words, I don't want the game to bottle-neck while one NPC is thinking because I implemented a more resource-intensive algorithm. What I would like to achieve is the following: - There are 5 NPC's, each with a different AI algorithm - Each NPC will get X amount of time to run through it's algorithm, or Y amount of cpu instructions I've considered assigning each NPC to a thread, but I have no guarantee that the operating system will allow each thread to be executed for the same amount of time.

At a guess, store the AI's current state and then break off calculation at/after X milliseconds.

Should work for a brute-force method, anyway.

Theoretically that sounds like a solution that would work. But I'm thinking to implement that I would need to save the state of the AI after each line of code in the algorithm for whatever action that AI is trying to perform or compute. This would double the amount of code, and likely more than double the amount of cpu time needed to execute a given algorithm.

Could you throw out some pseudo-code to clarify if I'm missing the mark here?

Though I do like the idea, and that's basically what I'm trying to accomplish, I feel that it is probably not the job of each individual AI to count how long it has been executing an algorithm. I need something like a thread monitor.

Thanks for the response.

AI is my weak point, so not really. However, I don't think you'd need to save the state after each line - Each AI class and function naturally has its own state data; you'd just have to make sure it's stored before breaking off.

This question is one of the reasons why I bought Millington's "AI for Games". Unfortunately, while the book provides good info on various task execution schemes, it was not very forthcoming on the part about getting AI routines to play nice with the time slice, apart from vaguely suggesting that AI routines be implemented in a friendly manner, ie do a bit of computation but return after a while if doing something intensive, storing the intermediate results. This is probably the only way to do it in a single-threaded environment, but it does require you to use timer code in your AI routines. On the other hand, it allows for a kind of "best guess" to be made available that can be immediately acted upon, for instance the direction to move while the pathfinding is working on the full path.

For Java specifically I think you should investigate the possibility of implementing AI routines as Runnable and throwing them into a thread pool (see the Executors factory class). This means that you have to open yourself to the wonderful world of multi-threading, but the Java concurrency facilities provide a lot of cool functionality for you. Whether the Executors pools will spread the love equally among the threads is a question that would need further looking into, however.

To Narf:
This question actually doesn't require extensive knowledge of Artificial Intelligence. It is more of a question relating to concurrent/parallel programming. In the context of AI it is a little bit easier to visualize, though.

Each class does have its own state data, I agree. With Java, we're talking about members of a Java class. But I also need to take into consideration any variables that are in scope when the execution is "broken off".

A quick and dirty example:
for (double i = 0.0; i < 1000000; i += .01) {
this.computeFactorial(i);
}

Ignoring the fact that this example is stupid, I think we can agree that this for-loop will take a while to run... relatively speaking. Let's say the X amount of time originally referred to is reached when the variable, i, is 1000.00. "i" is just a local variable so I'm not quite sure how to store the state of this class, which includes storing the value of "i", without actually putting a method called saveState() in the for-loop too.


To lightbringer:
I will look into the Executors factory class. I am decently familiar with multithreading in C from taking an Operating Systems class. Unfortunately, I also learned in that class that different operating systems don't necessarily implement the fair but equal round-robin scheduling scheme like what would be desirable for this solution. I'll see what I can find after a bit more research.

What you're looking for is known as an "anytime algorithm". Googling that should turn up some useful information.

What is your performance criterion? If your willing to trade off some performance you can run the AIs within an embedded scripting engine (like Lua or Python or Ruby) which gives u fine control of execution. Old games use to do this for NPCs using a cycles budget for each NPC (Grim Fandango for example) and even modern games do this (Eve Online uses stack less Python threads) allowing them to run hundreds of concurrent AIs and tasks within a limited CPU budget.

Good Luck!

-ddn

Sneftel:
That anytime algorithm idea is pretty interesting. That does solve another unmentioned problem which was whether or not any action could be performed at all when the NPC ran out of "thinking" time. If I implement my algorithms in an 'anytime' way then that issue is solved.

I do not believe that solves the main problem though. An anytime algorithm will give me a partial result more or less at any point in time. But anytime algorithms don't help me govern all the NPC's so that each NPC must give me a partial result after a specified maximum amount of time (ie. each turn).

ddn3:
My goal for performance is for a small number of NPC's to run in parallel in near real time. Because I'm limited to a two-core processor, I don't want two NPC's hogging the cpu for complex planning, for example.


I'm curious that this problem doesn't have an obvious answer. There are tons of console games on the market that must have faced this problem before. If you think of a first-person shooter when playing in campaign mode. Most games will have a one hero vs. lots of bad guys plot going on. Or a racing game. One car driving against a dozen opponent cars. All of these agents seem to be thinking all in parallel. How do these commercial games solve that problem?

Thanks again for the responses.

Your criterion are quite different than what normal game developers have. The requirement that each AI don't share state (ie each AI has it's own algorithm and correspondingly state) and you want to give each AI equal amount of CPU time (implying some sort of preemptive threading model where each AI's running process can be halted).

Most AI's in games share state, that is they share some cached path information, spatial checks, shared visibility, etc.. to reduce redundant computation. Also most AI's have the exact same fundamental algorithms with a few tweaks to add some variety and are optimized for this. So you can run 100's of them per frame within the alloted CPU time.

2nd requirement of exact CPU usage per AI, that's almost never done in games since it's never needed. The entire AI system usually get a fixed time slice per frame of the CPU and must work within that bounds. It's unimportant how much each AI gets as long as it performs adequately within that criterion and they usually all run on the same thread so there isn't any need for multithread coding (ie rsrc locks, etc..) techniques.

A language like Java or C++ or C# doesn't offer fine grain execution control (unless there is some API for preempting threads on the microsecond which I'm unaware of). So many games implement a scripting language for their AIs which they can control the execution context of the AI's down to the number of instructions executed per frame (instruction of the scripting language not assembly) with some loss of performance (generally scripts will run about 10x slower than C) but you do gain alot of flexibility.

These scripts are usually some high level language like Python, Lua, Scheme or some custom language invented just for that project, and thats pretty much how commercial developers do it.

Good Luck!

-ddn