Hacker News Reader

Comment by MintPaw | Hacker News Reader

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/

View on HN

(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!

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

I've not heard of flow fields before! Do you know a good reference to read up on them?

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

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

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.

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...

> 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.

I'd imagine that's not the only thing that will be multithreaded.

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

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.

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.

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.

https://en.wikipedia.org/wiki/Quadtree actually

Reply on news.ycombinator.com