Botea, Adi, Martin Müller, and Jonathan Schaeffer. 2004. “Near Optimal Hierarchical Path-Finding.” In Journal of Game Development. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.....
Rahmani, Vahid, and Nuria Pelechano. 2017. “Improvements to Hierarchical Pathfinding for Navigation Meshes.” In Proceedings of the Tenth International Conference on Motion in Games, 8:1–8:6. MIG ’17. New York, NY, USA: ACM.
Toll, Wouter van, Roy Triesscheijn, Marcelo Kallmann, Ramon Oliva, Nuria Pelechano, Julien Pettré, and Roland Geraerts. 2016. “A Comparative Study of Navigation Meshes.” In Proceedings of the 9th International Conference on Motion in Games, 91–100. ACM.
And route planning in graphs (with static edge weights) has been studied to death.
> Pathfinding is an old problem, and so there are many techniques for improving pathfinding. Some of these techniques fall into the category of hierarchical pathfinding
You don't need a graduate degree to understand it, but conveying that you understand it on your resume is hard to do in any universally meaningful way without that degree. The words that would grab the attention of the tech lead, the PM, and the HR are all different.
In this case you just linked a bunch of irrelevant papers that didn't solve the problem (pathfinding on an infinite and mutable map) and calling the developers ignorant for not looking at them. It is you who are ignorant thinking that you being a grad student means that you must know better than professionals, and also you lack reading comprehension since they didn't even claim their approach is new. This blog was not meant to contribute as a research paper, it was meant to show the community what improvements for the game they were working on.
The answer is always yes! Partly because no matter how niche a topic is there are people interested in it, and partly because creating such things will help your own understanding.
Go for it!
Say we are given a bidirectional graph G and a radius r. Now take a vertex v, and find the set of all shortest paths from v of length > r and <= 4r. Let us call this set P(v, r). Iterate for all vertices in the graph and real radii, and obtain similar sets. Then, highway dimension is the size of the smallest set (H) of vertices such that all sets collected in the previous step have at least one vertex in H.
Why is this useful-
Empirically, we know that road networks have small highway dimensions. This is interesting because it implies that there are only a handful of vertices from which you can take the shortest paths to all the vertices in the network. Intuitively, it makes sense too. If you want to travel long distances, it's best to take the highway as early as possible, and travel along it for as long as you can, then descend to the local roads as you reach closer to the destination.
Highway dimension basically gives us a theoretical way of capturing the inherent 'hierarchy' of the road network edges and explains why Contraction Hierarchies works so well on road networks (as opposed to random graphs, where CH can be easily beaten). HTH!
Yes this is helpful, thank you so much! :)
If you find this communication hard to digest, then chances are you are not part of the intended audience. It is then mostly pointless to try to change their wording.
There is enough other material (books, Web articles) from other people who deliberately target developers.
There's also a bias in here because if you're using "old" games like AoE II as examples, they were released back in the day before patches were really an accepted thing, so there was a lot more effort that went into solidifying a game before it went gold than there is today.
Get a playable version of the core game into Early Access for a low price, start releasing updates. Your player base provides feedback on the game as it evolves, free beta testing, and growing word-of-mouth promotion. Maybe even ideas for entire systems, especially if you have mod support. Eventually you expand it to have all the stuff that was in your original vision, and you bump the price up for the 1.0 release. Port it to consoles, decide if you want to keep on adding new content to make it the game you barely dared to dream it could be, or move on to the next project.
There's still people who keep a game quiet until they can release 1.0, but there's a lot of small games out there that get their stuff out in public as soon as possible.
if the product is wildly successful and has a future, but is a bit of maintenance nightmare: congratulations, that's the problem you want to have
This might make sense if a bunch of assumptions hold: the chunk-graph does not change during gameplay, map sizes aren't much bigger than the one shared in the post so the number of vertices in the chunk graph is pretty small, land units share the same costs for traversing terrain (i.e. same chunk graph with same edge cost shared by all units).
Rough back of the envelope: number of vertices, V = 20 chunks high * 20 chunks wide = 400. Chunk graph is sparse, each chunk connected to 8 neighbours by undirected edges, so number edges, E = (1/2) * 8 * V .
Memory required to store chunk-graph distance matrix: V^2 * sizeof(distance) = 400^2 * sizeof(float) = 640,000 bytes. Could use +inf for disconnected chunks due to islands.
Time to precompute full chunk-graph distance matrix by repeatedly dijkstra-ing from each chunk to all chunks in the chunk graph: V * T(dijkstra(E, V)) = V * O(E + V log V) = O(V E + V^2 log(V)) = O(V^2 + V^2 log(V)) = O(V^2 log(V)) , which won't scale due to the quadratic-ish V^2 log(V) term, but probably fine if V <= 400 .
The first assumption is mildly violated; the second one is tremendously violated--100,000+-chunk graphs are going to be quite routine, and million-chunk ones definitely plausible.
It’s faster to use an all-pairs shortest paths algorithm, of which there are several with better performance than what you’re suggesting.
We mean the chunk component graph, right?
That does technically change, because you can use https://wiki.factorio.com/Landfill to fill up water and modify which positions a chunk component takes up (and also potentially merge two chunk components), but I think that happens rarely compared to pathfinding.
yes. thanks for helping to clarify.
> > the chunk-graph does not change during gameplay
> that does technically change, because you can use landfill to fill up water and modify which positions a chunk component takes up
Yep, that might be a dealbreaker.
If the terrain only changes from impassable -> passable, not the other way around (e.g. flooding disconnecting bits), then the distances computed for the old map should be valid lower bounds for the distances on the new modified (by landfill) map, so it might be possible to use the old distances as an admissible a* heuristic to guide search to recompute new distances on the new modified map, but that's getting a bit fiddly.
This caching is likely the kind of thing that is probably not worth adding to the codebase unless you get a significant performance boost, as it adds a number of constraints from the required assumptions that impede you from changing the game rules in future
And there are some mods that let you go in the opposite direction, creating cliffs and water.
Doesn't this just move the intensive search work to the precompute that calculates distances?
there'd still be search cost at runtime doing the fine-detail searches since the distance heuristic defined by the chunk-graph is an approximation and misleads the fine-detail search some of the time.
need to profile & run experiments to see if this was anything like a win.
in practice it might be better to increase the accuracy of the chunk-graph heuristic by making it consider more factors, which would make it harder to precompute and cache everything, but might further reduce the number of nodes the fine-detail search needs to expand
edit: another variation of this would be to just start with an empty cache for chunk-graph distance matrix and fill it incrementally at runtime the time whenever you run a chunk-graph distance query as part of the heuristic. Then there isn't any up front time to precompute anything. Might be better if (source_chunk, dest_chunk) pathfinding queries at runtime aren't uniformly distributed but somewhat correlated, which is plausible, since some chunks are likely to be far more interesting locations to travel from/to than others.
And Factorio worlds are not static. So even if you could precompute, you'd have to recalculate the whole thing every time a player places a wall, destroys cliffs, fills water, puts a new building, destroys a biter nest or a biter builds a new nest.
Unrelated: Here are some cool visualizations and simulations for pathfinding we have used in the past for trade shows and mall wayfinding.
Using something like this will on average get pathfinding for something like O(LogN) time. May sound strange or impossible at first - this is less than the number of squares the path goes through, but works and does not need huge space overhead. This is because the CH algorithm selectively adds shortcuts to the graph essentially making it completely skip many squares. Also this is not a heuristic, but a provably correct algorithm (no provable time complexity for arbitrary graph, but I think logN or maybe log^2(N) can be established for the simple graph in this pathfinding).
Here is the pathfinder code:
(The devs themselves didn't comment, but they probably think in a similar way...)
Nuclear reactors are fun because fuel cells are also neutron sources, so their heat output increases if you place them adjacent to each other. The allure of these games, to
me, is a geometry playground where you can make your number bigger if you do a little mental math. The 2D grid nature limits complexity if you have simple rules and components, so the solution is to have more rules and components. ;)
I know a fair bit about the tool set of these games just by spending many hours playing and thinking about them, but I’m not going to turn this post into a design document. I should write/publish one at some point so maybe fewer clumsy balance mistakes are made in future games.
There are instances of games like this popping up. Some of them are low effort money grabs, but some are okay.
I have thoughts for solving the idle nature of the game by having diminishing returns on a design as time goes on (perhaps changing what metric a player wants to maximize) or by giving them complete control of the tick rate (this seems like a bad solution since some players may feel the urge to just idle anyway). I want to add in more fun designs, equivalent to multiblock structures in minecraft. Perhaps a fusion reactor that requires spending energy on confinement coils and heat injection.
Do you know any similar games that don't focus on tower defense and military (like factorio does)? I love the resource flows, transport problems and factory building.
Another way is to have enemies but set them to be peaceful until you attack them first. Downside is that it's finicky. The enemies love to roam randomly, so if you accidentally hit one with a car or build a rail track too close to one of their bases such that one of them wanders on to it and gets run over, all the enemies on the map will instantly become hostile.
Also some of the total conversion mods (IR, Youki, etc) allow an insane investment into the macro, you can just turn off bugs.
Gregtech new horizons is the only bastion of the industrial vision, but unfortunately the eccentric devs focus a bit too much on manual gatey things.
edit: woops i remembered wrong. i wonder how sales are going for this game?
Also, the OP was talking about Mindustry, which, at 89% is in good position too !
I'm just awestruck every time I stop and think about the fact they've written over three hundred of these in-depth articles, complete with annotated screenshots/video in most cases. The quality, depth and sheer consistency of the write-ups given their team size is simply incredible.
Can't really say I know of anything that comes close, but I'd love to hear about anything that does.
I had to develop a new pathfinding algorithm recently. For fun, I've been working on adding NPCs to Second Life. These have to be coded under these constraints:
- Each program is limited to 64KB, for stack, heap, and code. But you can have lots of programs that intercommunicate via messages.
- Finding out about the world is done by ray casting. You get about 100 ray casts per second.
It was interesting to code a maze solver under those constraints. What I wrote is basically "head for goal; if obstructed, wall follow." I do wall following in both directions simultaneously, so the shortest path wins. This finds paths around simple obstacles with minimal time wasted examining cells not of interest. Then, after finding a path, I tighten it up, removing inside corners where possible. This is not absolutely optimal, like A* is, but it's usually pretty good, and requires far fewer ray casts.
That's how secondlife does things? That sounds computationally expensive
I wonder if it would be sufficient to generate the chunk-level path, get the entities moving, and then do local A* to navigate through the individual chunks as-needed. Right now it looks like the algorithm generates the complete A* all at once (just after the chunk-level pathing where most of the bad paths are thrown out).
few ticks basically means instantly.
> This video shows how fast the algorithm works in reality; it hasn’t been slowed down.
>The first video is captioned that it hasn't been slowed down, but the 2nd video, I'm not sure.
I assume they meant https://cdn.factorio.com/assets/img/blog/fff-317-long-pf-bef...
so the one they were asking about is https://cdn.factorio.com/assets/img/blog/fff-317-long-pf-aft...
I just hope he doesn't decide to turn his hand to self-aware general AI. :)
My StarCraft-playing bot uses a similar approach for fast pathfinding. The similarity is that we're both trying to use a better heuristic than straight-line distance. In the case of my bot, it's done by breaking the map into roughly-convex regions, then precalculating the distance from the center of those regions to every other tile by flood-filling. That lets units outside the region use (distance to boundary of goal region + straight-line distance from boundary to goal tile) as a pretty good heuristic.
If you guys want to explore this further you could look into integrating ompl. It has a variety of planners that could be used. I believe you could get an order of magnitude improvement using something like that.
The 3rd+ pictures on are hierarchical pathfinding, which seem to be much, much faster than textbook A* .