New pathfinding algorithm | Hacker News Reader

New pathfinding algorithm

factorio.com

478 pointsjsnell109 comments

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

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

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 freedom to think abstractly and not in terms of everything-is-on-fire-all-the-time is absolutely the best thing about being a graduate student :)

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.

I've been thinking about writing a blog series on route planning algorithms if there is enough interest.. let me know if anyone wants it lol?

Yes, please!

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

[1] https://www.microsoft.com/en-us/research/wp-content/uploads/...

[2] https://www.youtube.com/watch?v=ArO1ZviOMhI

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?

Yes this is helpful, thank you so much! :)

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!

Also, there's some recent work on similar metrics, if you are interested. Do check out (https://arxiv.org/abs/1609.00512) and Sabine Storandt's work on how route planning algorithms behave as graphs scale (https://aaai.org/ocs/index.php/ICAPS/ICAPS18/paper/view/1774...)

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!

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.

Go for it!

Thanks Steve!

I wanted to make a tiny routing program, read a few papers but they're too advanced. I'd like some basics :)

There are some excellent ready-to-use libraries too, if you don't want to code everything yourself. Please see the following gist for a list: https://gist.github.com/PayasR/bc46af938195a827e42006c3f5544...

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 know of SOTA and SPOTAR.. thanks! :)

Cool! Yup :)

thanks to you too

thanks a lot man

Will using those make a measurable difference to the game?

No, they either assume immutable maps or graph based maps like road networks.

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

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.

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.

Minecraft is already more than 10 years old

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.

Factorio is still Early Access, 3.5 years and going strong.

That's for the Steam release, the initial crowdfunding itself is 6.5 years old : https://www.indiegogo.com/projects/factorio#/updates/all

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.

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.

That is a chicken-and-egg problem though. One major reason that most games don't get updates is surely because the code is unmaintainable.

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

FYI factorio is still in early access. It hasn't been released. However it's so stable that everyone forget it.

It's possibly the most playable and stable early release game ever. I've been playing this game without crashes for something like 5 years now.

Not just for their own sake, but the blog posts can be very enlightening indeed. Clearly they take some time to produce, which I very much appreciate.

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 .

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

> the chunk-graph does not change during gameplay

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.

> chunk component graph

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

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.

Not to mention cliff explosives (for removing the other major landscape-induced impediment).

And there are some mods that let you go in the opposite direction, creating cliffs and water.

> Time to precompute full chunk-graph distance matrix by repeatedly dijkstra-ing from each chunk to all chunks

It’s faster to use an all-pairs shortest paths algorithm, of which there are several with better performance than what you’re suggesting.

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

And now i have my next weekend project keyyed up :)

factorio generates terrain on the fly so this isnt possible. also you alter the terrain by placing stuff on it.

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.

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://clementmihailescu.github.io/Pathfinding-Visualizer/

https://www.growingwiththeweb.com/projects/pathfinding-visua...

https://www.reddit.com/r/dataisbeautiful/comments/78of3s/pat...

I am surprised that the text mentions the word contraction and yet doesn't really do 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).

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

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.

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.

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.

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.

You could always check out gregtech :^)

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.

https://factoryidle.com/ is another, similar game, in-browser, for those on platforms where Factorio is not supported.

What platforms does Factorio not support that people play games on? According to steam it support windows, mac, and linux.

Mobile or non-x86 hardware?

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 :

https://forums.factorio.com/viewtopic.php?f=6&t=76453

(The devs themselves didn't comment, but they probably think in a similar way...)

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.

What's a reactor game?

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.

https://github.com/MauveCloud/Ic2ExpReactorPlanner/releases

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.

https://www.reddit.com/r/incremental_games/comments/6jfuxq/l...

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.

how does this game claim to only need 100MB of ram? small maps sizes?

edit: woops i remembered wrong. i wonder how sales are going for this game?

Since it's currently[1] the 8th best-rated game on Steam of all time, I'd say really well.

-[1]: https://store.steampowered.com/search/?sort_by=Reviews_DESC

Steam Store ranking is a bit iffy (and you included DLC and bundles), SteamDB ranks Factorio as n=°2 (behind Portal 2) :

https://steamdb.info/stats/gameratings/

Also, the OP was talking about Mindustry, which, at 89% is in good position too !

https://steamdb.info/app/1127400/graphs/

Mindustry have small maps, Factorio have endless procedurally generated maps, that is a big difference.

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.

Closely followed by the Dolphin blog.

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

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.

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

It's about like real world robotics from 15 years ago, where you had a LIDAR or two with a modest data rate.

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.

They probably wrote the visualizer to debug the system while they were working on it!

The factorio devs have weekly writeups of this caliber. They’re great reads if you like the idea of making games.

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

The 2nd picture:

> This video shows how fast the algorithm works in reality; it hasn’t been slowed down.

Right, but this is about the fourth picture. Which, like sand500 quoted, is slowed down significantly.

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

so the one they were asking about is https://cdn.factorio.com/assets/img/blog/fff-317-long-pf-aft...

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.

Surely this is a top gaming achievement of all time.

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

[1] https://www.youtube.com/watch?v=mgfwwqwxdxY

How in the... That's amazing. How is the video itself even "stored"? Does this require a mod?

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

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.

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.

[1] https://github.com/ompl/ompl

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

https://leifnode.com/2013/12/flow-field-pathfinding/

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

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

rare pic of biter phalanx (circa 32 BC, colorized) :

https://www.reddit.com/r/factorio/comments/8q5q3c/rare_pic_o...

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.

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

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.

The entire blog is about how to create said heuristic, you can't just brush it off.

Who brushed?

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

Reply on news.ycombinator.com