5 ms·

I feel like making this multithreaded is a bit overkill. Or at least it should have presented a situation with many more units. I made an RTS in C++ a while ag

I feel like making this multithreaded is a bit overkill. Or at least it should have presented a situation with many more units. I made an RTS in C++ a while ago and was able to build paths for many units per frame on a fairly large map. And even if I couldn't, there's many optimizations I would have considered before threading, like only building a partial path based on portals. Or building a "bad" path and simplifying it on future frames. Here's a great A* references with a bunch of helpful tricks: http://theory.stanford.edu/~amitp/GameProgramming/ http://theory.stanford.edu/~amitp/GameProgramming/

stefan_ 4y ago
The basic sin here is doing pathfinding around a million square cells just because that happens to be the base of your rendering. You merge it all into convex polygons and suddenly the pathfinding is a pen&paper homework problem because theres about 5 of those left.
- substation13 4y ago
  Most classic RTS games have you place buildings on a grid. The buildings block movement so are important for pathing. You could merge large squares of open space as an optimization though.
- FooBarBizBazz 4y ago
  And if you pathfind on the visibility graph of those polygons' vertices, your path is even optimal in Euclidean space. Granted, that's a slightly larger graph, but still much smaller than all the grid cells. And actually, depending on the connectivity of the fine square grid, pathfinding on it is pretty suboptimal too, because you're only finding paths that are shortest in Manhattan- or 8-connected distance (barring some fast-marching/Eikonal thing). If your units are really restricted to those motions then that's correct, but if they can move continuously then you're losing a lot of diagonals. So that's another argument for polygons.
- qikInNdOutReply 4y ago
  https://en.wikipedia.org/wiki/Quadtree https://en.wikipedia.org/wiki/Quadtree actually
AshleysBrain 4y ago
(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
deleted 4y ago
[deleted]

stefan_ 4y ago

The basic sin here is doing pathfinding around a million square cells just because that happens to be the base of your rendering. You merge it all into convex polygons and suddenly the pathfinding is a pen&paper homework problem because theres about 5 of those left.

substation13 4y ago
Most classic RTS games have you place buildings on a grid. The buildings block movement so are important for pathing. You could merge large squares of open space as an optimization though.
FooBarBizBazz 4y ago
And if you pathfind on the visibility graph of those polygons' vertices, your path is even optimal in Euclidean space. Granted, that's a slightly larger graph, but still much smaller than all the grid cells. And actually, depending on the connectivity of the fine square grid, pathfinding on it is pretty suboptimal too, because you're only finding paths that are shortest in Manhattan- or 8-connected distance (barring some fast-marching/Eikonal thing). If your units are really restricted to those motions then that's correct, but if they can move continuously then you're losing a lot of diagonals. So that's another argument for polygons.
qikInNdOutReply 4y ago
https://en.wikipedia.org/wiki/Quadtree https://en.wikipedia.org/wiki/Quadtree actually

AshleysBrain 4y ago

(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

deleted 4y ago

[deleted]