next »

[BlueSweatshirt]

Soo, I don't know *too much about threads*. Afaik, threads are different sections of a process which can run simultaneously if the hardware allows it.(and also to my understanding, run better on multicore processors.)

Moving on though!

I've been working on AI calculations lately. I've managed to make some awesomely accurate/intelligent calculations for my game... Except they're extremely slow! When I say extremely slow, I mean that it can create a noticeable pause in the game to calculate.

While pondering optimization, something occurred to me-- humans and other beings don't necessarily make these decisions in an instant. So maybe it's fine if they don't, maybe that would actually be more realistic?

I thought about some voo-doo methods to process decisions part-by-part over a number of cycles to avoid lagging my game. The AI just makes decisions in parts. Sadly, this is kind of inefficient as it leads to tons of unnecessary member variables in my classes.

So then I thought about making an entirely new thread for the AI decision making. Holy crap! Maybe that's a good idea? I'm not very experienced in threading or the messy parts of computing, so I'd like to get some feedback on this idea.

[xgalaxy]

Couple of thoughts.

1) If end users machines don't have multi-core processors, and your ai is truly taking a lot of processing power then stuffing it in a thread probably won't help.

2) Using a single thread doesn't scale. You'd be better off creating a general thread task scheduler / pool / queue (whatever you want to call it) and have that consume a bunch of different ai tasks then having a single thread for all your ai. Not only will this scale much better, but you can use it for more then just ai.

3) If you are not careful, you could end up causing more performance problems. Too many context switches, etc. In general, these kinds of problems are tough to deal with, but can really pay off if handled correctly.

[Rob Lach]

If you're using a hard timer to lock your framerate you can just make everything except AI current frame crucial.

You can use a priority queue with priorities based on how short the "thinking time" is for an action. Then you can feed those into a scheduler to delay when the result is pushed forward if everything has been already computed but you still want that action delay. If you do more work than the CPU can handle in a frame though, you'll have slower AI as the amount of work increases.

On a related aside:

Spreading AI over a number of frames is a pretty common practice. For example, path finding is easily paused and continued from frame to frame. You may even notice these types of delays when they extend across quite a bit of time in games like RTS where you select a massive amount of units and give them a common destination; the game essentially doesn't push the move command until all of them have computed their paths and those computations may take dozens of frames.

[Charybdis]

I thought about some voo-doo methods to process decisions part-by-part over a number of cycles to avoid lagging my game. The AI just makes decisions in parts. Sadly, this is kind of inefficient as it leads to tons of unnecessary member variables in my classes.

I am afraid I dont really see this as a valid concern. It just means you need to have a better program design. Personally, I have always spread AI over many frames without using threads and it has always worked well for me. But to each their own. What kind of game are you making? The AI for a single intense opponent like chess, is much different to something like pathfinding for agents in an RTS.

[Average Software]

In my current project, which is a turn-based tactics game, I have a dedicated thread for each AI player.

In my case, this architecture was necessary, because my game runs on a client-server model and the AI players have to behave in parallel, just as if they were over a remote network connection.

It really isn't all that difficult to get your AI working like this, as long as you coded for it from the start.  Trying to wedge it in without it being in the original design is probably a bad idea, and should only be done if you absolutely have to.

[BorisTheBrave]

So there's two different aspects to AI threading:

1) Divide up work into small pieces so a pool can attack it.
2) Arrange AI to be incremental, i.e. it doesn't discard all work every time the game state changes. This is a superset of "spreading AI work over multiple frames".

(1) is relatively well understood, there are many books on the general task of making an algorithm more parallelizable. It's not easy though.

(2) is more specific. I can suggest the following general techniques:
Convergent behaviour:
Anything that is convergent usually works well over multiple frames. Give a few convergence iterations from the previous state to account for any changes, and you are good to go. Note that if too much has changed, that it may take several frames for the AI to react, this is undesirable in some circumstances, and ideal in others.
Examples: flocking behavior, path finding by diffusion

Dynamic data-structures:
You can keep some data structures up to date as you do regular processing. Often this is cheaper recomputing from scratch every frame.
Examples: reusing the broadphase from your physics engine (for area queries and raycasts). Invalidating only locally changed data.

Decision trees:
If you have a decision tree of possible outcomes as part of your AI, you can keep the subtree that corresponds to your opponents actual move. Decision trees in general are quite easy to parallelize, as you can evaluate two different branches indpendently.
Examples: alpha-beta pruning.

[Nix]

Threading should always be a plan B in game programming. You already (usually) have everything built on top of a perfectly good update loop which is quite good at doing lots of different things at once without all the nasties associated with threading. Don't use threading just because you don't want to solve the problem of chopping computation up into chunks. You should do that anyway. Also don't use threading because you don't want "too many member variables." That's just silly. Create #regions (if your environment supports that), separate things into #includes, make new classes to keep things more contained, or just organize your code better and comment things nicely. When spaghetti code gets really bad, I sometimes like to organize regions of my source files with separators like this:

///////////////////////////////////////////////////DRAWING FUNCTIONS////////////////////////////////////////////////////////////

There are certainly good reasons to pursue threading in a game project, but the reasons you suggested aren't good ones.

2) Using a single thread doesn't scale. You'd be better off creating a general thread task scheduler / pool / queue (whatever you want to call it) and have that consume a bunch of different ai tasks then having a single thread for all your ai. Not only will this scale much better, but you can use it for more then just ai.

I don't agree with the idea that a single thread doesn't scale. It absolutely does if you're smart about it. As I said, the update-loop system can be used very well to emulate many of the things that threading can do without many of the complications. A task scheduler via priority queue could certainly be useful, though. I haven't seen your AI code, but a "scheduler" might be helpful in cutting the computation up. I once used a priority queue as the primary data structure to simulate fish population and the effects harvesting through time. It worked well. I can talk to you more about how that might work if you would like. Still, though, I don't think that it should be in a separate thread.

[BlueSweatshirt]

Ahh, that was all very helpful.

In my case it was AI analyzing the environment and creating a kind of dynamic pathfinding system for themselves. They basically do this by analyzing the game grid for themselves and with line-checks between points, etc. One thing I really liked about this was that the AI could figure out where to go by themselves and also find cover/a place to run away to.

Thanks everyone!

Also, Average Software, that's a really cool way of doing it! Since it's a turn-based game though, is it really necessary for the AI to act on separate threads? Or is there a caveat which I'm missing? 

[xgalaxy]

I don't agree with the idea that a single thread doesn't scale. It absolutely does if you're smart about it.

Hypothetically speaking, lets say I design an AI system that uses a pool of worker threads and you design an AI system that is designed to use a single thread.

On a machine with many cores, the AI system using a pool of worker threads will run much faster, all other things being equal. As more cores appear in the machine, the AI system using a pool of worker threads will steadily begin to outpace the AI system using a single thread. The AI system using a pool of worker threads is also much more future proof, as access to better hardware means it will continue to gain performance increases, while the AI system using a single thread is stuck at the performance of a single processing unit.

An AI system that utilizes a single thread does not scale, no matter how cleverly it is written.

[Triplefox]

Of course a single thread doesn't scale if you just arbitrarily define the problem to need only horizontal scaling. Unfortunately most of the interesting performance problems in games require some amount of vertical scaling, and they tend to become the bottleneck faster than the parallel parts.

To put it in other terms - parallelization is "preventive medicine" for a game's performance envelope. Better single-thread performance is "life-saving surgery." You can ward off some performance problems with threading, but sooner or later you will stumble on the fundamental constraint of game worlds being stateful and mutable by design - even if you go out of your way to allow AI to operate apart from the world interactions. And in the meantime you incur sizable maintenance costs, which are the "human factor" of scaling.

[bateleur]

Before trying multithreading, you should at least consider the possibility of using coroutines.

[st33d]

Since it's a turn-based game though, is it really necessary for the AI to act on separate threads?

A "thinking" load bar would be acceptable for this situation. Normally I would advocate scheduling the AI over frames (or threads if you have them), but scheduling it over a load bar is acceptable for turn based.

It would allow you to relax and make the AI as overkill as you need before optimising it.

[Dacke]

Seeing how it's turn based, shouldn't it be fairly easy and even convenient to actually use an special thread for the AI?
(You mileage may vary based on what language you are using.)

Usually the big challenge with threads is to prevent two threads from modifying the same thing at the same time. But as it's turn based, you can just allow write-access from one thread at a time. When it's the player's turn, the AI shouldn't be changing anything. And when it's the AI's turn, the player thread should not be allowed to modify anything (just let it read the game state, scroll around etc.). Let the threads take turns with the game state and you'll be fine.

The big benefit being that the game doesn't freeze while the AI is running, without any need of breaking things up. If you do it right, you also get a good structure for multiplayer. Just treat every player (computer) as a separate thread and hand the gamestate write-access to the player in turn. As far as the game is concerned, it doesn't matter if it's an AI or human who is currently accessing the gamestate.

[_Tommo_]

Couple of thoughts.2) Using a single thread doesn't scale. You'd be better off creating a general thread task scheduler / pool / queue (whatever you want to call it) and have that consume a bunch of different ai tasks then having a single thread for all your ai. Not only will this scale much better, but you can use it for more then just ai.

This would be true *in theory* but utterly fails into the reality of current PCs because

-70% of pcs have 2 cores
-any pc has other software that uses any other core running, so you actually DO NOT want to use 100% of every core; it would make the system unresponsive and the game laggy.
-it is *really* difficult to deal with the sinchronization issues of a pool design
-[if you use C/C++]it is *really* ugly to design a pool, as potentially every task can need a new Task child class, and it destroys any OO design you had in your game.
-and after all there are some problems that can't scale, so if your game has its max efficiency with 2 threads, stick with it. Having more and more threads only pays back until a certain sweet spot, and in games it is usually around "2" or "3" unless you aren't willing to invest heavy money and time on it.
-indie games are lightweight, so threads are often needed for concurrency more than for extracting computing power, as the OP states.

Obviously none of this is true for AAA console titles, so there having a pooled job dispatcher is nearly mandatory... but this is not the case.

In my games I typically use a task-driven helper thread that does whatever needs to be done while the game runs; it is cleaner than keeping track of the state of whatever you are running, and it should be faster even on single core machine (OSes do scheduling much better than you).

[Average Software]

Seeing how it's turn based, shouldn't it be fairly easy and even convenient to actually use an special thread for the AI?
(You mileage may vary based on what language you are using.)

Usually the big challenge with threads is to prevent two threads from modifying the same thing at the same time. But as it's turn based, you can just allow write-access from one thread at a time. When it's the player's turn, the AI shouldn't be changing anything. And when it's the AI's turn, the player thread should not be allowed to modify anything (just let it read the game state, scroll around etc.). Let the threads take turns with the game state and you'll be fine.

The big benefit being that the game doesn't freeze while the AI is running, without any need of breaking things up. If you do it right, you also get a good structure for multiplayer. Just treat every player (computer) as a separate thread and hand the gamestate write-access to the player in turn. As far as the game is concerned, it doesn't matter if it's an AI or human who is currently accessing the gamestate.

In my case, I use a client-server model and the server has exclusive write access to the game state.  The players send their moves to the server, the server evaluates them and alters the game state, and then reports the results to the players.  The players are never able to alter the game state.  This neatly solves access issues, and translated perfectly to network based multiplayer.