My plan is to have the AI figure out what it wants to do during the time the player is completing their turn, which should take at least several minutes every turn because of the format of the game. No mashing End Turn repeatedly while doing nothing.

The NPCs will not be interacting and changing the gamestate but only figuring out what their “Goals" are and sometimes evaluating potential actions that could move them forward. I was hoping that I could use multithreading to do this very efficiently maybe using 5-7 cores while the player is using the 8th core. Of course worst case maybe you only have 4 total cores but better than nothing.

I expect to not run into a ton of problems because nothing the player does should rely on what the NPCs are doing since they don't change game state but only their decision making stuff.

I am just trying to figure out if there are any obvious problems I am missing and what the best way to handle this in C++ would be.

First, if this is turn based, why do you think the AI needs five cores for several minutes to figure out what to do?

Is this Dwarf Fortress world creation level details? (And even that doesn't take all that many minutes.)

Second, yes, multiple cores can be used to calculate for multiple different entities. In general, you will want to structure your simulation such that all entities read from a “current” version of the world, and write to a “new” version of the world, such that you each entity only writes to its own “output” slot, and everyone else reads your previous state from your “input” slot, and no locking is needed. This means you double-buffer your world state, rather than update in place. If you need to send messages between entities, you can make a “mailbox” where each entity enqueues their outgoing messages, and the recipients see the incoming messages during the next step.

If you do physical simulation, this may not be immediate enough, though – physical simulation generally requires you to run everything in sync, and then solve all the constraints (at least per constraint connected subgraph) in one big matrix solver.

hplus0603 said:

First, if this is turn based, why do you think the AI needs five cores for several minutes to figure out what to do?

Is this Dwarf Fortress world creation level details? (And even that doesn't take all that many minutes.)

Second, yes, multiple cores can be used to calculate for multiple different entities. In general, you will want to structure your simulation such that all entities read from a “current” version of the world, and write to a “new” version of the world, such that you each entity only writes to its own “output” slot, and everyone else reads your previous state from your “input” slot, and no locking is needed. This means you double-buffer your world state, rather than update in place. If you need to send messages between entities, you can make a “mailbox” where each entity enqueues their outgoing messages, and the recipients see the incoming messages during the next step.

If you do physical simulation, this may not be immediate enough, though – physical simulation generally requires you to run everything in sync, and then solve all the constraints (at least per constraint connected subgraph) in one big matrix solver.

The detail may or may not be as much as DF but yeah generally pretty high with lots of data being processed per character. So I intend to have a two phase NPC Character decision process. First they each firgure out what they want to do, ideally with as many cores as possible being used, then they sequentially perform the actions they want to perform. So the second part doesn't need, and probably can't use, very much multithreading because they will be changing stuff “outside their own head” at that point.

This is a [Map & Menu] game, characters are just their data plus an icon, no sprites or models, so I believe I am not doing what you mean by physical simulation.

I don't think I can “double buffer” my world state, because of RAM concerns, but I don't think I need to go that far. Characters will just be generating some strings and maybe ints that won't be read by anything else until we get to the execution stage which should be sequential single threaded.

hplus0603 said:

Second, yes, multiple cores can be used to calculate for multiple different entities. In general, you will want to structure your simulation such that all entities read from a “current” version of the world, and write to a “new” version of the world, such that you each entity only writes to its own “output” slot, and everyone else reads your previous state from your “input” slot, and no locking is needed.

This is probably simpler than it sounds: in a game with simultaneous turns where AI agents and human players are similar (e.g. each controls a single character) everyone thinks about the turn's move or moves simultaneously, using the read-only game state at the end of the previous turn as input, and when everyone has decided all moves are executed producing an updated game state. In practical terms, the player is going to be the slowest thinker, and a large number of AI agents can be processed in multiple threads with work queues (with very little locking overhead).

Carefully designed game rules could allow some parallelism in move execution: for example, if going to some location is a common move type and these locations are sufficiently isolated, the game could process each location independently (and therefore simultaneously): collect the set of characters who intend to go there, decide in which order they arrive if it is important, and process subsequent events in that location.