3 ms·

(Author here) I can imagine multithreading in C++ is a last resort. But with web workers it's guaranteed safe and relatively easy to do with message passing. So

(Author here) I can imagine multithreading in C++ is a last resort. But with web workers it's guaranteed safe and relatively easy to do with message passing. So why not? Even using one thread lifts the performance overhead of pathfinding off the main game thread, which helps scale it up to 1000s of units, which I'm hoping to do!

qikInNdOutReply 4y ago
Why not mention flow fields? They make for important movement improvements.
- AshleysBrain 4y ago
  I've not heard of flow fields before! Do you know a good reference to read up on them?
  - qikInNdOutReply 4y ago
    https://www.youtube.com/watch?v=lOYXUktahv8 https://www.youtube.com/watch?v=lOYXUktahv8 No reading up, but somewhere there was a blog post by the programers and a reference to the paper
  - softcactus 4y ago
    They are actually pretty simple. Essentially you generate the Dijkstra values for an undirected graph (this can be a grid, navmesh, etc), then you create directed edges pointing from high values to low values. So a grid space of value 8 will point to its neighbors with values less than 8, etc. All an agent has to do is query their current spot in the graph and it will return a vector that leads them to the next lowest cost. This is useful if you have lots of agents going to the same location. https://www.youtube.com/watch?v=BHcQ4JCj27w https://www.youtube.com/watch?v=BHcQ4JCj27w The description of this video has a lot of good resources. I made it when I was a much much worse programmer though so I wouldn't bother actually watching the video lol.
  - throwaway17_17 4y ago
    Emerson's chapter from 2013's Game AI Pro acts as a decent overview from what I have heard. [1] - http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter23_Crowd_Pathfinding_and_Steering_Using_Flow_Field_Tiles.pdf http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter23_Crowd...
MintPaw 4y ago
> So why not Because multithreading introduces a lot of complexity, making it inflexible and hard to scale. Of course you would never do it if the code was fast enough to not have to. I never had to consider it, I could generate about 16 complete flow fields per frame on a 512x512 map with no quadtree optimization. It sounds like a nice way to learn webworkers, but I think you're always better off hitting the perf bottleneck first, rather than trying to design around it early.
- ilyt 4y ago
  I'd imagine that's not the only thing that will be multithreaded.
garaetjjte 4y ago
Having excess processing power available is not an excuse for writing inefficient software.

qikInNdOutReply 4y ago

Why not mention flow fields? They make for important movement improvements.

AshleysBrain 4y ago
I've not heard of flow fields before! Do you know a good reference to read up on them?
- qikInNdOutReply 4y ago
  https://www.youtube.com/watch?v=lOYXUktahv8 https://www.youtube.com/watch?v=lOYXUktahv8 No reading up, but somewhere there was a blog post by the programers and a reference to the paper
- softcactus 4y ago
  They are actually pretty simple. Essentially you generate the Dijkstra values for an undirected graph (this can be a grid, navmesh, etc), then you create directed edges pointing from high values to low values. So a grid space of value 8 will point to its neighbors with values less than 8, etc. All an agent has to do is query their current spot in the graph and it will return a vector that leads them to the next lowest cost. This is useful if you have lots of agents going to the same location. https://www.youtube.com/watch?v=BHcQ4JCj27w https://www.youtube.com/watch?v=BHcQ4JCj27w The description of this video has a lot of good resources. I made it when I was a much much worse programmer though so I wouldn't bother actually watching the video lol.
- throwaway17_17 4y ago
  Emerson's chapter from 2013's Game AI Pro acts as a decent overview from what I have heard. [1] - http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter23_Crowd_Pathfinding_and_Steering_Using_Flow_Field_Tiles.pdf http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter23_Crowd...

MintPaw 4y ago

> So why not Because multithreading introduces a lot of complexity, making it inflexible and hard to scale. Of course you would never do it if the code was fast enough to not have to. I never had to consider it, I could generate about 16 complete flow fields per frame on a 512x512 map with no quadtree optimization. It sounds like a nice way to learn webworkers, but I think you're always better off hitting the perf bottleneck first, rather than trying to design around it early.

ilyt 4y ago
I'd imagine that's not the only thing that will be multithreaded.

garaetjjte 4y ago

Having excess processing power available is not an excuse for writing inefficient software.