14 ms·

New pathfinding algorithm

478 points by jsnell 7y ago

social_quotient 7y ago
Neat! Unrelated: Here are some cool visualizations and simulations for pathfinding we have used in the past for trade shows and mall wayfinding. https://qiao.github.io/PathFinding.js/visual/ https://qiao.github.io/PathFinding.js/visual/ https://clementmihailescu.github.io/Pathfinding-Visualizer/ https://clementmihailescu.github.io/Pathfinding-Visualizer/ https://www.growingwiththeweb.com/projects/pathfinding-visualiser/ https://www.growingwiththeweb.com/projects/pathfinding-visua... https://www.reddit.com/r/dataisbeautiful/comments/78of3s/pathfinding_algorithms_visualized_oc/ https://www.reddit.com/r/dataisbeautiful/comments/78of3s/pat...
krisrm 7y ago
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.
- xsmasher 7y ago
  They probably wrote the visualizer to debug the system while they were working on it!
- willis936 7y ago
  The factorio devs have weekly writeups of this caliber. They’re great reads if you like the idea of making games.
nsilvestri 7y ago
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.
- Waterluvian 7y ago
  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.
  - yellowapple 7y ago
    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.
    - mdorazio 7y ago
      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.
      - Mathnerd314 7y ago
        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.
      - TomMarius 7y ago
        Minecraft is already more than 10 years old
dgant 7y ago
Neat! 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.
akersten 7y ago
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).
- sand500 7y ago
  >the pathfinder was slowed down significantly to make this video, to show how it works. At normal speed, the entire search takes only a few ticks. few ticks basically means instantly.
  - dragontamer 7y ago
    The 2nd picture: > This video shows how fast the algorithm works in reality; it hasn’t been slowed down.
    - jsnell 7y ago
      Right, but this is about the fourth picture. Which, like sand500 quoted, is slowed down significantly.
    - sand500 7y ago
      My parent mentions >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-before.mp4 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-after.mp4 https://cdn.factorio.com/assets/img/blog/fff-317-long-pf-aft...
ronilan 7y ago
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 https://github.com/ronilan/a-mazing-thing Use as you wish.
- dragontamer 7y ago
  The first picture and second pictures are A* , which is then demonstrated to be insufficient for the game. The 3rd+ pictures on are hierarchical pathfinding, which seem to be much, much faster than textbook A* .
  - ronilan 7y ago
    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.
    - username90 7y ago
      The entire blog is about how to create said heuristic, you can't just brush it off.
      - ronilan 7y ago
        Who brushed?
  - mkl 7y ago
    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."
  - deleted 7y ago
    [deleted]
donio 7y ago
https://anuke.itch.io/mindustry https://anuke.itch.io/mindustry is an open source game with some similarities to Factorio Here is the pathfinder code: https://github.com/Anuken/Mindustry/blob/master/core/src/io/anuke/mindustry/ai/Pathfinder.java https://github.com/Anuken/Mindustry/blob/master/core/src/io/...
- kzrdude 7y ago
  Thanks for the link. 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.
  - hobs 7y ago
    Have you played the Seablock mod? It's basically that. https://mods.factorio.com/mod/SeaBlock 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.
  - Arnavion 7y ago
    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.
  - misnome 7y ago
    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).
shoo 7y ago
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 .
- bduerst 7y ago
  >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?
  - shoo 7y ago
    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.
bduerst 7y ago
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.
brunoTbear 7y ago
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.
- byron_fast 7y ago
  Surely this is a top gaming achievement of all time.
- willis936 7y ago
  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.
  - NeedMoreTea 7y ago
    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. :) [1] https://www.youtube.com/watch?v=mgfwwqwxdxY https://www.youtube.com/watch?v=mgfwwqwxdxY
    - ShamelessC 7y ago
      How in the... That's amazing. How is the video itself even "stored"? Does this require a mod?
      - BlueTemplar 7y ago
        Just like memory cells are made IRL electronics using latches, you can make memory cells in Factorio using combinators : https://wiki.factorio.com/Tutorial:Combinator_tutorial#Memory_cells https://wiki.factorio.com/Tutorial:Combinator_tutorial#Memor...
strbean 7y ago
Was hoping for flow field pathfinding: https://www.youtube.com/watch?v=bovlsENv1g4 https://www.youtube.com/watch?v=bovlsENv1g4 https://leifnode.com/2013/12/flow-field-pathfinding/ https://leifnode.com/2013/12/flow-field-pathfinding/
BlueTemplar 7y ago
rare pic of biter phalanx (circa 32 BC, colorized) : https://www.reddit.com/r/factorio/comments/8q5q3c/rare_pic_of_biter_phalanx_circa_32_bc_colorized/ https://www.reddit.com/r/factorio/comments/8q5q3c/rare_pic_o...
veselin 7y ago
I am surprised that the text mentions the word contraction and yet doesn't really do https://en.m.wikipedia.org/wiki/Contraction_hierarchies https://en.m.wikipedia.org/wiki/Contraction_hierarchies 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).
Animats 7y ago
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. [1] https://github.com/John-Nagle/lslutils/blob/master/npc/mazesolver.lsl https://github.com/John-Nagle/lslutils/blob/master/npc/mazes...
- OnlineGladiator 7y ago
  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.
- Havoc 7y ago
  >- Finding out about the world is done by ray casting. You get about 100 ray casts per second. That's how secondlife does things? That sounds computationally expensive
  - Animats 7y ago
    It's about like real world robotics from 15 years ago, where you had a LIDAR or two with a modest data rate.
afettere 7y ago
Not exactly new - https://www.computer.org/csdl/proceedings-article/ictai/1997/82030084/12OmNAolH2Q https://www.computer.org/csdl/proceedings-article/ictai/1997...
payasr 7y ago
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. 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.314 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 https://arxiv.org/pdf/1504.05140.pdf
- izacus 7y ago
  Will using those make a measurable difference to the game?
  - username90 7y ago
    No, they either assume immutable maps or graph based maps like road networks.
- cheschire 7y ago
  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.
  - deleted 7y ago
rl3 7y ago
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.
- mschuetz 7y ago
  Closely followed by the Dolphin blog.
Havoc 7y ago
I like the authors writing style. Makes it easy to follow his thought process
rowanG077 7y ago
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. [1] https://github.com/ompl/ompl https://github.com/ompl/ompl

478 points by jsnell 7y ago

Neat! Unrelated: Here are some cool visualizations and simulations for pathfinding we have used in the past for trade shows and mall wayfinding. https://qiao.github.io/PathFinding.js/visual/ https://qiao.github.io/PathFinding.js/visual/ https://clementmihailescu.github.io/Pathfinding-Visualizer/ https://clementmihailescu.github.io/Pathfinding-Visualizer/ https://www.growingwiththeweb.com/projects/pathfinding-visualiser/ https://www.growingwiththeweb.com/projects/pathfinding-visua... https://www.reddit.com/r/dataisbeautiful/comments/78of3s/pathfinding_algorithms_visualized_oc/ https://www.reddit.com/r/dataisbeautiful/comments/78of3s/pat...

krisrm 7y ago

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.

xsmasher 7y ago
They probably wrote the visualizer to debug the system while they were working on it!
willis936 7y ago
The factorio devs have weekly writeups of this caliber. They’re great reads if you like the idea of making games.

nsilvestri 7y ago

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.

Waterluvian 7y ago
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.
- yellowapple 7y ago
  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.
  - mdorazio 7y ago
    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.
    - Mathnerd314 7y ago
      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.
    - TomMarius 7y ago
      Minecraft is already more than 10 years old

dgant 7y ago

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

akersten 7y ago

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

sand500 7y ago
>the pathfinder was slowed down significantly to make this video, to show how it works. At normal speed, the entire search takes only a few ticks. few ticks basically means instantly.
- dragontamer 7y ago
  The 2nd picture: > This video shows how fast the algorithm works in reality; it hasn’t been slowed down.
  - jsnell 7y ago
    Right, but this is about the fourth picture. Which, like sand500 quoted, is slowed down significantly.
  - sand500 7y ago
    My parent mentions >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-before.mp4 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-after.mp4 https://cdn.factorio.com/assets/img/blog/fff-317-long-pf-aft...

ronilan 7y ago

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 https://github.com/ronilan/a-mazing-thing Use as you wish.

dragontamer 7y ago
The first picture and second pictures are A* , which is then demonstrated to be insufficient for the game. The 3rd+ pictures on are hierarchical pathfinding, which seem to be much, much faster than textbook A* .
- ronilan 7y ago
  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.
  - username90 7y ago
    The entire blog is about how to create said heuristic, you can't just brush it off.
    - ronilan 7y ago
      Who brushed?
- mkl 7y ago
  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."
- deleted 7y ago
  [deleted]

donio 7y ago

https://anuke.itch.io/mindustry https://anuke.itch.io/mindustry is an open source game with some similarities to Factorio Here is the pathfinder code: https://github.com/Anuken/Mindustry/blob/master/core/src/io/anuke/mindustry/ai/Pathfinder.java https://github.com/Anuken/Mindustry/blob/master/core/src/io/...

kzrdude 7y ago
Thanks for the link. 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.
- hobs 7y ago
  Have you played the Seablock mod? It's basically that. https://mods.factorio.com/mod/SeaBlock 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.
- Arnavion 7y ago
  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.
- misnome 7y ago
  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).

shoo 7y ago

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 .

bduerst 7y ago
>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?
- shoo 7y ago
  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.

bduerst 7y ago

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.

brunoTbear 7y ago

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.

byron_fast 7y ago
Surely this is a top gaming achievement of all time.
willis936 7y ago
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.
- NeedMoreTea 7y ago
  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. :) [1] https://www.youtube.com/watch?v=mgfwwqwxdxY https://www.youtube.com/watch?v=mgfwwqwxdxY
  - ShamelessC 7y ago
    How in the... That's amazing. How is the video itself even "stored"? Does this require a mod?
    - BlueTemplar 7y ago
      Just like memory cells are made IRL electronics using latches, you can make memory cells in Factorio using combinators : https://wiki.factorio.com/Tutorial:Combinator_tutorial#Memory_cells https://wiki.factorio.com/Tutorial:Combinator_tutorial#Memor...

strbean 7y ago

Was hoping for flow field pathfinding: https://www.youtube.com/watch?v=bovlsENv1g4 https://www.youtube.com/watch?v=bovlsENv1g4 https://leifnode.com/2013/12/flow-field-pathfinding/ https://leifnode.com/2013/12/flow-field-pathfinding/

BlueTemplar 7y ago

rare pic of biter phalanx (circa 32 BC, colorized) : https://www.reddit.com/r/factorio/comments/8q5q3c/rare_pic_of_biter_phalanx_circa_32_bc_colorized/ https://www.reddit.com/r/factorio/comments/8q5q3c/rare_pic_o...

veselin 7y ago

I am surprised that the text mentions the word contraction and yet doesn't really do https://en.m.wikipedia.org/wiki/Contraction_hierarchies https://en.m.wikipedia.org/wiki/Contraction_hierarchies 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).

Animats 7y ago

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. [1] https://github.com/John-Nagle/lslutils/blob/master/npc/mazesolver.lsl https://github.com/John-Nagle/lslutils/blob/master/npc/mazes...

OnlineGladiator 7y ago
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.
Havoc 7y ago
>- Finding out about the world is done by ray casting. You get about 100 ray casts per second. That's how secondlife does things? That sounds computationally expensive
- Animats 7y ago
  It's about like real world robotics from 15 years ago, where you had a LIDAR or two with a modest data rate.

afettere 7y ago

Not exactly new - https://www.computer.org/csdl/proceedings-article/ictai/1997/82030084/12OmNAolH2Q https://www.computer.org/csdl/proceedings-article/ictai/1997...

payasr 7y ago

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. 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.314 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 https://arxiv.org/pdf/1504.05140.pdf

izacus 7y ago
Will using those make a measurable difference to the game?
- username90 7y ago
  No, they either assume immutable maps or graph based maps like road networks.
cheschire 7y ago
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.
- deleted 7y ago

rl3 7y ago

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.

mschuetz 7y ago
Closely followed by the Dolphin blog.

Havoc 7y ago

I like the authors writing style. Makes it easy to follow his thought process

rowanG077 7y ago

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. [1] https://github.com/ompl/ompl https://github.com/ompl/ompl