There's a _lot_ of work on hierarchical route planning in games. I don't mean to put down the developers or anything, and I'm so glad all of this works, but there are plenty of ideas in the academic-world that I think developers should know more about.
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.
Note that they meant that they have a new algorithm for their game and not a new algorithm for the world, so don't shit on them for no reason. For all we know they could have already read the papers you mentioned. They even mentioned that this was an old technique in the blog:
> 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
It took me till my late 30's to realize this is the power of a graduate degree. There are lots of people out there who understand programming, and there's a tier of programmers who understand research as a fundamental part of it.
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.
The problem with many phd's is that they don't understand how useless research papers are in most cases. You have very tight constraints and the algorithms written by researchers are almost never optimal, you have to do significant tweaks or reinvent it entirely to fit it into your constraints.
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.
There are often comments of the form " I've been thinking of doing x, is there any interest?"
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.
Long shot, but if by any chance you could explain Highway Dimension [1] like I'm 5, and how it leads to faster routing algorithms, I would definitely be interested! I've watched some of Goldberg's videos (e.g. [2]), so I have some vague intuition, but not nearly as much as I feel I could/should. (Though it's entirely possible it's just something that can't be meaningfully ELI5'd in a usable manner... I don't know.)
Sure! That is a classic paper, I didn't know there was a video too. Let me try:
Highway Dimension-
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!
Oh wow! To confirm I understand this, is the following correct? "The radius-r highway dimension of a graph G is the(/a?) minimal set of vertices that must be visited when traveling a distance ∈ (r, 4r]." I'm actually a little unclear on r—I assumed HD is a function of r, but you said you iterate over all real radii to obtain HD, which would mean HD is independent of r?
HD is independent of r.
And it's not the minimal set of vertices that must be visited.. it is the smallest set of which at least one must be visited. Another good explanation of HD is in section 1.3 of the skeleton dimension paper (https://arxiv.org/pdf/1609.00512.pdf).
Oh, sorry, I was vague about the visiting—I meant the set must be visited, i.e. something in it must be visited. I'll take a look at that one too, thanks!
Wow, the abstract on skeleton dimension looks quite amazing. I only happened to come across HD after working on a tangentially related algorithm, but I didn't keep up with the progress on that front... it didn't even hit me they might've already progressed beyond that to a stronger measure. That's pretty awesome, thanks for sharing!
Oh wow, you're actually compiling a list! I'm not sure this is relevant (it's for a different stochastic routing problem), but here's something I have, if you feel it's relevant enough to be added: https://git.io/SOTA-Py
I actually learned something today about pathfinding by (re) reading that post for 15 mins. The papers linked make no sense to me. Maybe the paper authors need make abstracts and summaries more approachable.
The authors are optimising for communicating with their peers: scientists and academic researchers.
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.
I've always loved the Factorio devs for seeming to make their game not only fun but also a well-designed piece of software. The gamedev industry, particularly by indie devs, is notorious for doing whatever it takes to make it work, code health be damned.
It's because in most cases investing in "code health" beyond what they already do is a mistake in the game industry. Games are mostly disposable products. Only when you're going to be maintaining it a long time does the investment pay off.
One of the key considerations nowadays, though, is that games are far less disposable than they were in, say, the 90's/00's; there's an expectation that players will be getting bugfixes and features and even expansions/DLC for a long while after the original release date. That confounds even further with the recent trend of "Early Access" and similar schemes for player-driven alpha/beta testing.
I'm not sure that actually holds, or at least we would need to split up the games industry to see how it applies. If we're talking about games specifically designed for long-term play and ongoing updates (Dota 2, CS:Go, Fortnite, etc.) then yes I agree. If we're talking about your standard AAA releases likes CoD: whatever or most indie games, it's generally a "get it out the damn door" situation because the sales graph is extremely downward sloping over time.
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.
There's lots of indie games that get tons of updates, too. Minecraft is the big one in this space that kinda defined the model, Factorio is one of them too. Dwarf Fortress has had regular updates since 2006.
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.
Similarly, a lot of games built with Valve's Source engine get continual updates even today - a decade or more after release - specifically because Source gets updates and therefore so do the games built on it. It's interesting to see updates come in for Half Life 2: Deathmatch even though absolutely nothing player-facing has changed (to my knowledge) since the 00's.
The game engine is reused between most games in a series, e.g. CoD, so there is still an incentive to invest there. They skimp on story/art/content though.
I think a big part of that is that historically most games are updated relatively little after they are released, so maintainability of the code base is secondary to not letting the release date slip. But Factorio is a game that has been getting updates for a while now post-release, so the devs have to be happy revisiting the code, which increases the incentives for keeping the code maintainable and the code health high. It seems like more games are moving towards this model (lots of updates post-release), so I'd expect to see the game industry start to adopt some of the practices used by the software industry in general to keep code maintainable.
I think rather it's a revenue issue, until relatively recently there was no way to profit from updated games, so you're better off moving on to the sequel, or next year's edition of the game. Also a lot of the video game development culture likely stems from console releases, which again until "recently" could not be updated (only new versions of disks/carts for future customers) so it was not feasible to plan for future maintenance, beyond what was necessary for derived codebases.
it's a hit driven industry, so maybe the dynamics are pretty startup-ish: you don't know if the product is going to take off, so cut corners to reduce costs in the short run at the expense of future maintainability, since you don't know if the product will be profitable and have a future until after it ships.
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
A small tweak to this approach would be to precompute and cache the entire chunk-graph distance matrix, so the chunk-distance between any two chunks can be computed by a lookup, instead of searching. Use a bit of memory and make the time to generate the world a bit slower, but could be viable if the chunk-graph pathfinding calls are still slowing things down a bit at runtime.
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 .
> 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).
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.
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.
> > 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
You can add walls which biters try to move around. I think they add an extra cost since they don't move around them perfectly, and often they try to attack the thinner parts of the walls.
>A small tweak to this approach would be to precompute and cache the entire chunk-graph distance matrix, so the chunk-distance between any two chunks can be computed by a lookup, instead of searching.
Doesn't this just move the intensive search work to the precompute that calculates distances?
you got it. not feasible to precompute the fine detail full graph, since it has far too many vertices, arguably feasible for the chunk-graph, since it is small.
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.
Your calculations are for a tiny piece of the map. Factorio worlds are infinite. So "the chunk-distance between any two chunks" cannot be precomputed.
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.
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).
Yeah, there was a recent PowerPC request (following IBM open sourcing their chips and them getting into the enthusiast price range), but the forum moderators answered that a supported version didn't make economic sense, and an unsupported version would be a bad idea :
This looks like the same framework as a recent reactor idler I player recently. I think it is the same dev. It was horribly time gated and had a scummy practice of offering the player to “buy fast ticks” and then balanced the game around it. I like reactor games (and am working on one, praised be to ic2 and gregtech) so I played it, but I cheated in infinite fast ticks. Even then the game took me weeks of open browser time and CPU load to get to the end. Reactor games have inherent metagame difficulties to overcome and this dev exploited them to make money. I am not a fan of them.
They’re a small class of game where you have a 2D cartesian grid where you can place heat sources, heat spreaders, and heat dissipators. The goal is to maximize heat production without melting down. The first instance I know of such a game is industrialCraft2’s nuclear reactor. You can play with it here.
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.
You can play Factorio with the enemies turned off. I do that too, because I find getting distracted by enemies annoying. The downside is that the whole military part of the research tree becomes pointless.
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.
Have you played the Seablock mod?
It's basically that.
https://mods.factorio.com/mod/SeaBlock
Also some of the total conversion mods (IR, Youki, etc) allow an insane investment into the macro, you can just turn off bugs.
I'd really hesitate to say that factorio focuses on tower defense/military. There is defense, but unless you are ramping up the difficulty the bugs aren't really that much of a problem - more of a low level pressure unless you expand deep into their areas - and, you have the option to turn them off completely when starting a new game, and you wouldn't be losing a major part of the appeal (like minecraft with creepers off).
I have played factorio a lot, and at this point I'm looking for a different game, or something where the design does not include bugs in the pointless way factorio does. It's an otherwise fantastic game. Maybe it's not even wrong to have adversaries, but the way it's done in factorio is so simplified (infinite bugs from outer space) it seems like satire.
Note that this post is #317. The Factorio team has the best development blog on the planet in my opinion.
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.
Pathfinding isn't hard if you have full information and enough memory to store it. Most full info grid pathfinding algorithms, like A-star, are basically variations on flood fill.
I had to develop a new pathfinding algorithm recently.[1] 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.
The way this comment was initially italicized through so many breaks was truly surprising and took me a few seconds to figure out. By the time I clicked reply you'd already updated it though. For those reading this, it connected everything between the initial A* and the second A* and was jut weird.
The visualizations in this article are really well done. I've read a bit about hierarchical pathfinding before, but this is the first time I feel like I actually "get" it.
Great optimization. I wonder if the second video is also real-time? The first video is captioned that it hasn't been slowed down, but the 2nd video, I'm not sure. If it is real time, it still seems like it takes a few seconds to generate the path.
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).
The best part is the minifactory at the bottom of the page. Completely nuts to launch a rocket in that small of a space in that little time. Everyone should scroll down and check it out if you haven't.
Most of my enjoyment of factorio has been watching the factories of other people. I have been playing industrial games for ten years and I still stumble through the game that’s primarily based around discovery. Seeing what thousands of hours can accomplish is inspirational.
DaveMcW regularly does amazing and unbelievable things in Factorio, like the in-game video screen[1]. Whereas I am happy to muddle half a dozen combinators together with my lazy head on - to control a level display, delivery buffer, or turn off specific features etc.
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.
Huh. I've been playing Factorio this week on a rail-world and cheesing the biter bases with artillery, the way they're describing. Some of the bugs manage to make it around the lakes from pollution spread, but cleaning them out with artillery makes them wander and disappear off screen.
Since I don't think a true optimal route is necessary here I would have checked out RRT instead of a*. There are variants of it that are much much faster that can find almost optimal routes.
If you guys want to explore this further you could look into integrating ompl[1]. It has a variety of planners that could be used. I believe you could get an order of magnitude improvement using something like that.
It’s A*. I wrote one encapsulated as an ES6 JavaScript Class a while back. Just dropping it here if anyone finds it useful.
https://github.com/ronilan/a-mazing-thing Use as you wish.
I think it's still A*, but with a better heuristic than straight line distance (the simplified-map path). From the summary near the end: "we are still essentially using the same old pathfinder we've been using for years now, only with an upgraded heuristic function."
As far as I understand they go back, goal to start with A* and use heuristic scoring that is smarter than the simple Taxicab geometry. That is at least what I understood from what the text explains. I might be wrong though.
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.
https://arxiv.org/pdf/1504.05140.pdf