How does StoneHearth leverage multi-threading for A.I.?

Scripting & Code
1

Hey community!

I’m studying software development and am currently studying up on threads and concurrency. As I read through such materials I get excited and start wondering about game development. Eventually I’d like to endeavor in small personal game projects to help solidify my personal understanding of coding methodology, and I can definitely foresee the most daunting task would be planning out multi-threading for pseudo-A.I.

Perhaps this is the wrong board to post to, or even the wrong forum, but the community here is awesome and I feel like if I can get a solid answer I could understand how StoneHearth works under the hood a little better - and thus multi-threading as well.

I guess my question is to what extent should you multi-thread for A.I.? To elaborate what I’m trying to understand, consider the various needs of the Hearthlings:

:runner: Pathfinding
:briefcase: Tasking (Jobs)
:hamburger: Individual stats and states.
:bulb: Surroundings awareness.

With just those 4 things it seems like you have what is necessary to have a relatively complete A.I. But how do you break those up on a technical level?

The way my nubile mind would attempt to tackle these are:

Pathfinding: 1 thread for pathfinding that receives the location of the Hearthling and the requested destination, maps it out, and passes back vector information to the Hearthling in an array that he/she can work through.

Tasking: 1 thread for job tasking that hands out jobs to the most proximate/available Hearthlings.

Stats&States: 1 thread for Hearthling management that iterates through each Hearthling and updates their stats and animation states based on their tasks.

Environmental Awareness: 1 thread that iterates through an array of special objects that ping nearby Hearthlings for pseudo-awareness. For example, a Hearthling is killed by a goblin and its corpse (the object in question) is on the ground… and every 200 milliseconds the body would attempt to “ping” the nearest Hearthling within a certain radius and either delegate a task or change the state of said Hearthling - maybe sending the Hearthling into a state of alarm or caution, or take the corpse to a graveyard.

How acceptable or not is this line of thinking?
Should each Hearthling have their own thread instead?
How many threads would be too many for a game?

I’ve tried to do some reading online on multi-threading and A.I. but I’m not entirely sure what it is I’m actually looking for as I search :sweat:… and the answers aren’t as specific as I’d like, leaving me ruminating over this :confounded:

Any thoughts or resources the community can chime in with would be helpful!

1 Like
2

I’m a little vague on the current state of things, but I’ll pass on what I understand about how the AI in Stonehearth works. Hopefully this can help you at least understand some things about how the Stonehearth Devs have designed their AI. I’ve included a little reasoning where it would be helpful.

If I’m mistaken about anything, I’m sure someone will set me straight in due time :wink:

Actions

The AI in Stonehearth is built around Actions. Actions are things that an AI can do. These Actions can be grouped into packs, which allows them to be easily assigned to any NPC in the game (from your faction or any other faction).

Many actions are compound actions. If for instance, you want a Carpenter to make a table, he first has to go pick up the needed materials and bring them to the appropriate workbench. You’ll notice that each of these sub-actions I just described includes a movement component. So the AI may need to find multiple paths for a single “action”.

To determine what the AI will do next, it has to figure out what it CAN do. The AI has a set of “thoughts” based on its set of actions. Each thought starts off in a “not ready” state. The AI regularly checks the dependencies of each thought to see if it is possible to do. When all the dependencies are satisfied, the thought becomes “ready”. If something changes the conditions before the associated thought can be started, it will go back to the “not ready” state though.

Actions have varying priorities. Obviously, an NPC can only accomplish one action at a time, so it has to pick the most important thing to do first. So when multiple actions are “ready” at once and no other action is in progress, it acts on the highest priority.

Tasks

One problem with the original design of the AI was that for every actionable item in the world, every AI with a relevant action would get a new “thought”. If you added 20 mining zones to the world, every hearthling would get 20 new “mining action” thoughts! Obviously, as you got more NPCs and added more zones, the processing required would increase exponentially. 2 NPCs with 2 zones = 4 thoughts and 20 npcs with 20 zones = 400 thoughts!

To fix this, they created new AI entities called Tasks. Each AI that can perform the related action now has a single thought that listens in on the Task and waits to be told what to do.

The Task itself manages all the thinking about whether each actionable item can be done. If it can be done, it finds a hearthling that can do it and tells them about it. There is some overhead, so you don’t want a Task for absolutely every action, but it does create large amounts of efficiency where it is useful.

Going back to the mining zone example, 2 NPCs with 2 zones = 4 thoughts (1 for each npc and 1 per zone for the Task), but 20 NPCs with 20 zones = 40 thoughts (1 for each npc and 1 per zone for the task).

Pathfinding

There is a high level entity that maps the useful area of the world (anywhere nearby where your faction has been or has been told to go). This map is a simplified version of the voxel map ingame, where it creates as few rectangles as possible that map to the same shape (you can find an article or two about this if you look back through the archives of the Development Blog on the website). Anytime the world changes, this pathfinding map changes too. Because this high level entity exists, it only has to do it once, not once per thought in each hearthlings AI!

For each thought that exists in an AI (NPC or Task), there will be one or more movement actions involved. For each of these, the AI requests a pathfinder to give it a path. The pathfinder then gets the latest copy of the node-map and attempts to return a path. It either succeeds, proves there is no path, or times out (which the game treats as “no path”).

Threads

It is likely that only the Devs could answer the question of how many threads they actually use for the AI. I believe it’s all written in the C++ portion of the code, which is not exposed for modders.

Having said that, my guess would be that each NPC AI and Task AI entity is treated as an individual thread. Node-map creation and maintenance is another thread. Pathfinding may well be a small pool of threads.

5 Likes
3

Hello Axidion, I don’t want to be rude, but I think you should read up on threads, wait until you learn more about this in your study or try some simple game development first. Depending on the language you want to use, there are lots of tutorials on the internet. Please note that a game doesn’t NEED several threads to run. All game logic can be processed in a single thread (although more threads can make the game more performant.)

No, absolutely not. There is no reason to do so and the performance will be worse if you have dozens of threads.

This depends on the processor/number of cores the game runs on. Each core can process a thread at a time. So if you have a single core, it will have to jump from one thread to the other all the time, decreasing the performance. Also, having many threads in a 3D game can make programming extremely complicated.

1 Like
4

I have noticed that multiple A.I. get assigned the same task. i.e. place a block in the same location. First A.I. there drops the block/blocks and the next few get to the location and see that there is no task to complete. If the A.I. see a task complete it walks away, or just gets confused… What I don’t see, is it looking for a new similar task. It tends to take the resource back to the source or just drop it, then look for a new task.

The tasks are overlapping, making the A.I. at this point inefficient. What would work is to divide an area up and give each A.I. its own piece of the pie. if you got 10 feet of road, and 2 A.I. split the task and have one do the first 5 feet, and the other start on the 2nd 5 feet. I have seen it done in other games, and it might clean up some of the processing load.

5

I was going to make a new thread (yuk, yuk), but the title of this old one is basically exactly what I’m wondering.

I just got a new Ryzen 2700x processor, a huge upgrade over my 5-year old cpu, and I can easily have twice as many hearthlings before the game starts to slow down. However, while the game was using ~70-90% of my old 4-core cpu, it’s now just using 12-15% of my new 8/16-core cpu; expanding the task manager to show individual core performance, I notice that one core is at ~90-100%, with a couple others bouncing around 20-50%, and most of them completely unused.

It seems like one thread of the game is taking on a bit too much work. Are there plans to try to distribute that more? I think it would go a long way to improving performance.

1 Like
6

The answer is still quite simple: Because lua is not threadsafe/does not support multithreading, Stonehearth itself does not support multithreading beyond the thread-system already in place (namely n for the GUI because of CEF, 1 for the server-backend, and 1 for the client-backend).

The multihreading options outside of the AI are restricted to tasks that do not require anything from lua (such as pathfinding). Since the play area is quite limited though - and the pathfinding itself requires lua to some extent too - the possible optimisation gain here is rather smallish.

Put differently, there’s little difference between 1-4 cores, and no benefit at when having more. There have been many threads about this topic already, if you dig a bit you’ll find some more in-depth explanations.

2 Likes
7

Lua on its own may not support multithreading, but there are other libraries, like Lua Lanes, that could help. My coding experience is primarily limited to .NET, so I don’t know how much of a pain it is to implement that, but given that Lua is considered a core technology for the game to allow modding and that the performance of the game is so restricted by the single Lua thread, it seems like something that should be seriously investigated.

1 Like
8

A few years ago we talked to some industry people who had worked on large simulation games specifically about performance and AI. It turns out that none of them multi-threaded their simulations, no matter the language, because resolving the output across threads was nearly impossible to debug. Therefore, we continue to explore other solutions. :slight_smile:

6 Likes
9

Cool, thanks for the response!

1 Like
10

.NET is really awesome when it comes to multi-threading and thread handling in general (especially since the introduction of the TPL and “recently” with await/async). lua is not comparable.

Lua Lanes is a Lua extension library providing the possibility to run multiple Lua states in parallel.
Lanes have separated data, by default. Shared data is possible with Linda objects.

Lua lanes isn’t multi threading - Stonehearth already has two separate lua states, and you could even argue that they’re even connected over some shared state, too. If I am reading this right, Lua lanes are basically AppDomains - and you might have already experienced the joy of marshalling stuff across them. It would be probably a very similar, painful experience.

The overhead of creating such objects and orchestrating the whole synchronisation (which is happening with those Linda objects apparently) would likely eat away any possible performance gain. For example, if you were to parallelise the AI, any callbacks into the game components (“is this edible”, “is this seat free” and so forth) would need to dip back into the main thread, therefore rendering the AI thread rather useless. Unless you plan to have a synchronised state across all components in all threads, but that would likely eat memory (and/or performance) like you wouldn’t believe.

There’s not much they can do about this I believe without either tearing down the whole architecture as-is today,