Pathfinding logic runs in same thread as update logic?

Development
1

First, I’d like to say that I love the concept and am pleased with most of the work so far.

However, the stuttering bug is something I believe may have a simple solution.

Normally, Stonehearth runs like glass on my machine, with frame rates well above 60fps. However, every few seconds, the game will pause for about a quarter of a second. (Please let me know if I’m the only one who experiences this, as I might be crazy…)

As a developer, I was curious what was causing it, so I set to bug hunting.

What I’ve discovered so far is that the stutter occurs when a villager finishes a task and takes up a new one. There are likely a bunch of things going through the villager’s mind at that point, but most should take on the order of micro seconds. Pathfinding, however, takes a long time. When you’ve got a 3-dimensional space of 400,000 pieces, pathfinding takes an eternity.

This, I suspect, is where the problem lies. After deciding on a task, a villager must ask the pathfinding algorithm how to reach its destination. If this is a blocking algorithm, then all other update logic will stop until the algorithm returns - hence, I believe, the stutter.

Unfortunately, asynchronous logic is a tricky business. I can propose 2 solutions, but without seeing the code base it is impossible to suggest which is better.

One option would be to spawn a new thread containing the pathfinding algorithm whenever a villager wishes to travel. This would likely be the simpler of the two approaches, as it only requires the villager to hold onto the thread handle between update frames, until such time as the algorithm returns.

The other option would be to create every villager in their own thread, where they can spin their blocky wheels all day and night without affecting the rest of the simulation. This is more complex as it would require the use of semaphores, and the draw and update functions would need to be able to communicate with villagers between threads. However, this solution may open new possibilities further down the development road, as different entities could potentially communicate without the need for a central commander (for example, combat could take place between a villager thread and an enemy thread, where the only communication to the outside world would be to read the terrain).

If this has already been addressed and/or I’m totally off the mark, please feel free to delete this.

I look forward to seeing how Stonehearth develops!

3 Likes
2

Good instincts. :wink: We are in fact working feverishly on the pathfinder, and it is in fact, related to not just stuttering, but also obsessive-wood-carrying behaviors.

3

welcome aboard @Finnboghi! :smile:

absolutely not… its good to have fresh perspective from an outside developer! i hope you’ll stick around and provide more insight as the client progresses… :smiley:

2 Likes
4

The main issue with your idea could be that lua is not thread safe at all. Spawning new threads is not exactly free and most of the time, the synchronisation/lock costs overshadow whatever performance you gain from having it threaded. Especially putting each villager in a new thread (which is kind of pointless, seeing as the average CPU can only run 2-8 threads at any given time and there’s likely going to be way more settlers) is a bad idea.

Without any knowledge of the PF itself (it’s part of the engine as far as I can tell), I think a lot could be gained by having it asynchronous (i.e. some sort of incremental algorithm - the usual suspects Dijkstra, A* and friends all support that) which would just fire a callback. Edit: It seems like… that is already the case?

In the end, without the fitting numbers (average PF calls per minute, average PF execution time) it’s hard to propose a good system. We could have all sorts of proposals, like having a threaded PF manager from which lua polls et cetera but if that is the most effective one is questionable.

5

What about using time-sliced path planning? I read about it recently and if I understand correctly, it uses a central manager class to start the different searches. In every frame, there is a constant amount of time reserved for path finding. The searches are done iteratively with a few iterations each frame. When the search is completed, a callback is used to notify the object affected.

I never used this technique in any scenario but maybe someone has some knowledge about how it’s done?

6

FWIW, Lua uses coroutines instead of threads. It’s a huge help in conceptually separating different chunks of AI logic, without actually introducing the complexities of true async threading. Though we do have that too, in our C++ layer.

7

@sdee
None of the pathfinding is running in Lua, is it? I assumed all the pathfinding is in C++?

1 Like
8

radiant/modules/pathfinder/pathfinder(_wrapper).lua highly suggests something like this.

I remember that Garry moved some functions completely to lua from C because the transition C <-> lua apparently takes some time. But that might just be because of the way he handles lua.

9

Correct! The AI in LUA creates instances of the C++ pathfinder whenever it needs them. The AI then goes off and does something else until the pathfinder returns. The gist of the OCD wood problem is that the pathfinder is incorrectly returning over and over and over again for wood that’s already been processed.

2 Likes