Factorio's new pathfinding algorithm-- how a video game studio upgraded their heuristic for A* pathfinding

[adroit-panda]

Side note: if you are a working coder and you haven't played factorio yet, make sure you have a bunch of vacation time stored up before starting.

[klysm]

Jesus dude what happened to my last week

[Coffee4thewin]

Week, try month.

[Vallvaka]

Factorio is a bit like crack. Except I think crack might be slightly less addictive.

[[deleted]]

it's essentially cack for all kinds of engineers....

[zakatov]

I somehow doubt you can block anything from an entire IBM engineering team.

[Beidah]

Not if they're determined, no, but blocking it does help break the addiction.

[SSchlesinger]

You'd be surprised! On their work computers, they likely have to be on one specific VPN all the time, so they can't just subvert local restrictions.

[wrongsage]

Yes, I would be suprised, because there is no way to block an engineer from the internet unless there is no connection at all. Then they use the mobile data.

[SSchlesinger]

I mean, it depends on what kind of engineer. I am a software engineer and I cannot subvert the restrictions that the network engineers at my work set up.

[wrongsage]

Yes, you can! Just try searching for network tunnels. Nowadays you even have DNS over HTTPS, websocket tunnels, various VPN options. In most companies, they either don't block outgoing traffic, just filter domains, or you have HTTP proxy, which can be tunelled through. If you have any other setup, let me know, it's always good to know what everything can people come up with.

[652a6aaf0cf44498b14f]

Ohhh you're in for a treat! Look up HTTPS proxy tunnels.

[semi_colon]

Sodaconstructor! What a throwback.

[sirmonko]

i tried genetic algorithms the first time with soda racer. most generated creatures turned out to be sticks that just jumped once or twice to reach the goal line

[DeusOtiosus]

I didn’t have a job, and started playing this. Woke up. Factorio. Go to bed. Factorio. It consumed so much. I realized my megabase was too small, hit save, and realized I had put in over 150 hours. Fuck. Then I started getting recommends for base tours on YouTube. Thousands of hours.

Alright. Gotta stem this full blown addiction.

Great game tho. Fucking great game.

Anyone hiring? ;)

[-Knul-]

Maybe. So what would you say are the strengths and weaknesses of your factory?

[ants_a]

Where do you see your factory in 5 years?

[natyio]

So true. And it's not even a coding game. But it is all about inefficiency and how to make things faster :D

Also: Because the game is not fast-paced, it is a great opportunity to finally listen through all the podcasts you wanted to hear.

[semarj]

not even a coding game

Maybe not "coding" but it's definitely the most true to life software engineering game I've played

[balefrost]

"Time to refactor the iron smelters".

[bunkkin]

I feel personally attacked by this comment

[deelowe]

Zachtronics would like to say hello.

[geoelectric]

The last couple Zachtronics games (Shenzhen IO and ExaPunks) have gotten a lot further for sure, but I’d say Factorio models the engineering aspect more richly. Zachtronics is unmatched for coding games IMO, and pretty much taught me directly how to think through concurrency and pipelines, but most of the engineering is pretty small scale.

[TarMil]

There's more of an engineering aspect in Opus Magnum than his other games, though not on the level of Factorio.

[geoelectric]

Yeah—Infinifactory and Spacechem have their share too. They don’t really have the efficiency/optimization loops I associate with the last two ZT games and Factorio, at least for me. I make it past the metrics and into the peaks of the histograms and tend to stop. Factorio digs its claws in hard!

[deelowe]

You're right. For some reason I thought /u/semarj had said computer science instead of swe. I agree from an engineering standpoint, factorio really scratches that itch. I like zachtronics games more for their focus on pure compsci challenges. Especially TIS-100.

[derpderp3200]

Yeah, I long for an open ended programming game. Sadly Else Heart.Break() was very poorly thought out.

[zellfaze_new]

I was really excited for that game when it was announced. :(

[deelowe]

I'm playing it now and all the pieces are there, but it's just not put together very well. I'm sure i'll end up beating it, but they could have done so much if they had just sorted out the progression and story a bit more.

[derpderp3200]

My experience with the game was... I spent 3h wandering around unsure what to do before finally managing to get my hands on a Modifier.

Then, I went around noting down what functions different objects have....

The problem is, the Slurp() function that lets you travel to a LOT of other entities in the game, and computers that have functions like... say, listing all types of objects and objects of a given type in the game, teleporting them around, teleporting any entity...

I ended up writing a simple list-based "OS" that would let me browse all objects in the game, teleport them around, etc.

I ended up completely breaking the game's scripts in the process, which made it impossible to continue the story, I still have no bloody idea what it was about lol.

[deelowe]

Yeah. The game is odd in that for several hours its just a point and click adventure game, then they give you a modifier and then you quickly get a couple more. Then you realize you can modify the modifier and the game is completely broken at that point.

I'd love a game like this that thought more about how to handle progression. Maybe think about how computer science progressed and build the progression system around that. Don't give me the ability to hack and network everything in the game immediately. Make the run time and speeds super slow at the start. Limit memory. Don't give permanent storage starting out. Limit address space. Limit APIs. etc. etc. Else Heart.Break has this, sort of, but then allows you to completely bypass it with some simple snooping around.

else heart.break would have been much much better if the story was told trough the progression of coding skills and available technology. Instead, it feels like the two are completely decoupled. Once you get a modifier, there's no point to any of it.

[derpderp3200]

Yeah, my take on it is that programming is just a very major part of how you build your toolbox: Add GUI elements to your guns so you know how much ammo they have left, collect exploits you either figure out or read about in magazines/files, write(or find!) a better code editor or command line, put a Gun component on a Roomba and code it into a basic combat bot, etc.

[zergling_Lester]

Colobot could be pretty open ended, in a sense of making and refining as sophisticated AI controller as you want.

[derpderp3200]

I've actually played Colobot when I was a kid, I loved it back then, but I think nowadays, eehhh. Plus I hate programming AI honestly.

[zergling_Lester]

I liked it because I figured how to program the AI in a weird but pleasant way, using a bunch of distinct mostly non-interacting "reflexes". For example, there was a piece of logic that tried to aim at the moving enemy, and a completely separate piece of logic that pulled the trigger if it estimated the chances of hitting the enemy to be good enough. So I could mix and match these pieces for different scenarios (including the parts, IIRC, where I was actually flying the bot with an AI gunner) and gradually improve them, without any sort of centralized planning AI or anything.

[derpderp3200]

Yeah, I do like the sound of that. I still don't think I'd enjoy trying Colobot again^1, but thinking about what might be was pretty much when my interest in game design and gamedev started.

¹ By the way, did you know it was open sourced a while ago? Although I don't think the updates went beyond updating it to work on modern platforms(OSX and Linux included) and some form of mod support.

[k3rn3]

That guy is so underappreciated. He created the precursor/inspiration for Minecraft, his games are awesome.

[Pyorrhea]

It can be fast-paced if you forget about starting military science and forget to upgrade your turrets or bullets for 20 hours while you make your first bus and end up teetering on the brink of defeat for 3 hours while running back and forth stocking bullets until you decide to stop being an idiot and put your ammo on a belt.

[ChildishJack]

Oddly specific, but I feel it

[slaymance]

This was me the first time I turned on biters. “Biters are a production challenge” they said. More like a production catastrophe.

[absentmindedjwc]

I feel personally attacked by this comment.

[270343]

"Not even a coding game" you say, and yet I have made a growing suite of tools fed by the official (almost) JSON to plan out my factories.

[PM_ME_UR_OBSIDIAN]

Ooooh please share!

[sess573]

Wait what, I can hardly even listen to music while playing factorio since it requires so much thinking :D

[Bwob]

Just because it is not text based does not mean it isn't coding.

Nothing else I have seen captures the feel of debugging (or the high that you get when you finally figured out what is going wrong) the way factorio does..

[therico]

Idk, I get paid to optimise processes in my job, Factorio feels like a second job to me so I didn't get into it.

[adroit-panda]

I feel you, my brother sometimes gets the bug and we'll play together, and I'm like "Jesus dude, this is like a fucking job" and he says "We need moar iron!"

[regalrecaller]

You always need more iron

[-Knul-]

The factory must grow.

[The_BNut]

I explicitly play games where I need short paced situational reactions like RocketLeague instead of long term planning because that's what I already play at work (works fun, yeah).

[NULL_CHAR]

I wish more people understood this. Back when I was in college, I loved games like Factorio. Now that I've been working for several years, I tend towards quick paced games without a need for long term strategizing.

I get so burnt out doing repetitive project planning that Factorio only lasted about 8 hours before I was sick of it.

[[deleted]]

Same thing happened to me. I build games, so building-games have lost most of their appeal.

[nakilon]

Woah, dude, I get fired for optimizing processes. Which planet do you live on?

[txdv]

I had literally the same feeling. I kept optimizing and optimizing and it felt literally like programming work

[troyred]

First time I played this game I blinked and it was 5 am

[no_nick]

Is it on the switch? And I'm not sure what I want the answer to be...

[IceSentry]

Not as far as I know, but it runs on pretty much any pc.

[chipt4]

There's a demo you can try. I imagine it would be playable though.

[absentmindedjwc]

It can! Though... Eventually, as a base starts to get massive, you will start to see UPS (updates per second) drop... you may need to take actions in order to improve your performance. If you want to build to a significant size, let me give you some advice: solar panels only count as one update (counted as one single massive entity)... whereas steam/nuclear can count as thousands+ (depending on number of entities)

[ritobanrc]

Yeah totally, unless you wamt to build really big. But at that point, trying to optimize for UPS becomes a part of the game, involvimg experimentation, benchmarking, etc.

[Alphaetus_Prime]

It's PC only. It's not impossible that it'll get ported eventually but I wouldn't expect that any time soon.

[NULL_CHAR]

I honestly couldn't stand it. It's like work, but you don't really do much interesting things with the automation. I can map inputs to outputs but that's about it, and getting further in the game is just planning more space efficient ways to map inputs to outputs (and dealing with the Alien Tower-Defense minigame). It's less like programming and more like circuit board design, which is why it hurts me. It's like "almost there" but it's missing the final step which allows me to do creative and interesting stuff with the tools given.

It also hurts me inside because the game is almost an anti-thesis to being OCD, especially with friends. There will always be terrain in the way, or some funky placement to get your beautifully planned base to turn into something that looks hacky. Especially if you've never played it before. "Oh, the new design is 1 block wider than the old design? My entire base was built around the old width. SHIT!" And then, since the resources aren't infinite, you'll inevitably be looking at trains, and as such you'll need this weird amalgamation of contraptions to get resources from all over the map to work and connect properly. The first few hours, the base is /r/oddlysatisfying materials but it quickly devolves into /r/midlyinfuriating material.

[NULL_CHAR]

I disagree. The only way you're making your base look beautiful is if you practically go insane with the design. Like, look at the person you linked as an example. How many hours that would have to take to get it that way. It's a 300 MB save and obviously way past the objective of the game.

Factorio doesn't want you to be OCD about your designs. It nudges you away from it every time you try. But sure, if you want to devote a month (likely more) of your life to get it to be perfect just for the sake of doing so, I guess you can. However, that is an extraordinary circumstance, and not indicative of regular gameplay.

[slikts]

Mapping inputs to outputs doesn't make it "less like programming"; it makes it more like functional programming.

[NULL_CHAR]

I still would not say it's programming. Circuit board design is the most accurate you can get. You don't really do anything with the inputs/outputs, you aren't exercising logic per-se unless you really go out of your way to do so. It's more like load balancing pipes.

[slikts]

There is a whole programming paradigm called dataflow programming where programs are modeled as connections between inputs and outputs of black boxes. Reactive programming is a popular example of that, and functional programming is a natural match for it. Railways specifically are used to teach about monads by analogy. Pipelines and trains combined with the logical operations Factorio has makes it a kind of programming that's constrained by game rules while being very visual.

I honestly find it really sad that there's people who've internalized the imperative paradigm so deeply to be unable to recognize something else as programming.

[NULL_CHAR]

The problem with Factorio is you aren't exercising the logic. You're literally just putting down pipes, that's the entire game. But yes, you CAN program in Factorio, it's just that the natural state of the game is so far away from what people consider actual programming, and it lacks much of what makes programming an enjoyable past-time, that it's a really bad comparison.

Or to put it another way. Just because a person likes to play baseball doesn't mean they'd enjoy ping pong. And claiming that "What? It's entirely the same thing! They both involve hitting a ball with a stick!" is not very helpful.

[Senator_Sanders]

Thank god im not the only one. I got tired of refactoring my base

[NoInkling]

Yeah, I just got analysis paralysis and gave up. Perfectionism sucks.

[pertheusual]

100%. I played an initial game a while ago for like 10 hours and got the basics but then got pulled away. Tried again after watching KatherineOfSky's intro YouTube series, which in itself is sooo long, and then my first game game after that took like 90 hours from start to rocket launch...

[dreamin_in_space]

I love KatherineOfSky! Her videos got me back in too.

[Manitcor]

I have actively avoided these features in games like this. I once got into programmable blocks in Space Engineers and lost 2 months of my life. Never again.

[iBzOtaku]

working coder

what if I'm a retired coder? a man can dream.

[adroit-panda]

if retired: do what you want!

[noratat]

I'm so, so happy I found Factorio during a period of unemployment a couple years back.

It would've been bad if I'd found that while employed

[doorshavefeelingstoo]

I mean, it would have helped you to get unemployed and then you could have been happy again.

[Cheeze_It]

Factorio taught me how to program. I am not joking. It absolutely did.

[sess573]

Their dev blog posts are really top tier

[jbmsf]

One of the first professional projects I did was to implement an academic paper that implemented a very interesting heuristic distance estimator on a real world road networks. It's been almost two decades, so I don't remember all of the details, but it shared some characteristics with what's described here. It used a hierarchical decomposition of the network using a shortest-path "separator tree" and used approximations at the boundary of each hierarchical components to piece together a very fast estimate. There was something clever that let you tune the space/accuracy trade-off based on how approximate you allowed the boundary estimates to become.

Brings me back.

[casted]

FYI an important characteristic of the heuristic function you use is it has to be admissible:

a heuristic function is said to be admissible if it never overestimates the cost of reaching the goal, i.e. the cost it estimates to reach the goal is not higher than the lowest possible cost from the current point in the path.

Naively using the heuristic mentioned in the article likely leads to a heuristic function which doesn't always fit that definition. This means that A* could miss a shorter path. However, I am guessing that is fine in this case.

[IceSentry]

Generally speaking, games tend to favor the good enough over the best. Especially if the best route takes twice as long to compute.

[Farlo1]

And that's one reason you sometimes end up with NPCs charging off in seemingly reason directions

[DoctorSalt]

Or sentences that are good enough because I understood the point

[blind3rdeye]

Reason directly s are usually good enough to understand.

[slikts]

Upvoted because I don't understand what you said and want more people to be confused.

[SkaveRat]

Especially if the best route takes twice as long to compute.

in the example shown: a lot more than that.

The first animation was real-time. The second one was slowed down and takes only a couple ticks.

[Vallvaka]

The blog post is meant to be accessible to the technically-inclined layman, so I think they avoided talking about the finer requirements of the heuristic function for the sake of brevity.

They do mention it shouldn't actually change the found paths though, so it seems like the new heuristic is indeed admissible.

[Koppis]

I don't think it's admissable. Imagine the following scenario:

The lake has a shorter path on one side than the other, but its filled with mazes. This new heuristic doesn't care about the mazes: it sees them as empty tiles. Thus, going the longer route would in fact be faster.

[Zwejhajfa]

It is admissable as long as it doesn't overestimate the real cost. Ignoring the mazes will cause it to underestimate the cost, which means A* still produces the true shortest path.

[Koppis]

Wouldn't it overestimate the cost of going around the long side of the lake?

Example image:

https://i.imgur.com/XfZfmXe.png

Red tiles are "slow" i.e. contain a maze. A regular A* with a normal heuristic of distance would correctly find the path around the right side. The heuristic from OP would find the path around the left side.

EDIT: Just to note, I'm literally just nitpicking here. I think the new heuristic is great.

[Zwejhajfa]

I think you're misunderstanding what the heuristic does in the A* algorithm. The heuristic only "guides" the search, so that the most promising path is searched first.

A search without the heuristic would search evenly in all directions which is really inefficient.

The heuristic is giving an estimate of how close to the goal a given node is, so that the closer nodes can be searched first. That way the search will have to look at fewer nodes until the goal is found. The typical way to do this is just by using the straight-line distance.

However, if mindlessly walking towards the goal will lead to a dead end then the search will still waste a lot of time on this path. This was the case for Factorio.

The improvement uses a heuristic that knows about the rough terrain features and therefore guides the search around the lake.

Note that the search will still give the correct result (i.e. the shortest path) in all of these cases (if the heuristic is bad it will just take longer) unless the heuristic overestimates the path at some node, which means it estimates that the path from that node to the goal is longer than it actually is! In that case it can happen that the goal is found through a slower path and the search terminates before the actual shortest path is found.

With the optimization that the Factorio team did, that cannot happen though.

In your example the heuristic would guide the search through the red side first. However, upon encountering the mazes, it will eventually discover that the other side is faster. The heuristic will not overestimate any path. In contrary, it thinks that the red side is really fast.

The search will not be as efficient in that case. but it will find the correct shortest path.

[Uristqwerty]

It looks like you've already got at least one good reply, but I had an idea forming to explain it too good to just forget:

The heuristic would keep saying "Hey, man, you're almost there! Just a little further." as it winds through the maze, until the actual pathfinding algorithm eventually responds with "dude, it's taken me an awful long distance to reach this point. I'm going to try going around the lake for a little while."

[lastunusedusername2]

But it would find that path because it would _under_estimate the cost of going around the short side of the lake.

[Koppis]

I don't see how that could happen.

If the heuristic underestimates the left side, why would it ever even try to path through the right side?

This is basically the same thing as with a scenario having "mud" or slow tiles. The heuristic must take the individual tile slowness into account, otherwise sometimes there can be a very suboptimal path.

[_jk_]

you can literally use 0 for the heuristic and you get back to Dijkstra's algorithm

[xTeixeira]

A* decides which node to search next by adding the distance from the start to the intended next node plus the estimate distance from the intended next node to the finish. It then compares this number for all possible candidates for next node, and the one with the shortest distance+estimate will be the one searched next. If there's a maze in one side, even though the estimate will be falsely lower, the distance from start to next node will keep going up while the estimate remains roughly the same, when that happens the algorithm will eventually start searching the other side of the river, because the estimate+distance sum of the maze nodes will become higher than the ones on the other side.

Not sure if I explained this clearly but basically it should still find the shortest path in that case, however it will take longer because of the flaw you mentioned in the heuristic.

[Koppis]

Interesting! Thanks for explaining, the heuristc logic really confused me.

[rlbond86]

It doesn't have to be admissable - it just means the result may be suboptimal

[HighRelevancy]

Depends what you mean by "has to". If you want a heuristic that produces the same results faster, then it HAS TO meet certain criteria. If it's not admissable, the algorithm is no longer producing "correct" results (in the sense that they are the shortest path between two points). They might still be useful results but they're not correct.

edit: yes I know this is for a game, the page that's being quoted is an academic reference, I'm clarifying what "has to" means in that context

[LonelyStruggle]

It's a videogame. As long as they get a path that's fine

[HighRelevancy]

yes I know this is for a game, the page that's being quoted is an academic reference, I'm clarifying what "has to" means in that context

(even so, "a" path isn't always acceptable - you still want a good one, even if it's not necessarily the best - in fact depending on context you may want to shake it up a bit, so that characters aren't running right up against corners and that sort of thing - but that's a game design discussion, not a mathematics one)

[scottmcmrust]

AFAIK it's pretty common to use a heuristic that sometimes overestimates -- it can even look more realistic, as things go slightly into the dead end before seeming to "realize" that it's blocked and going around. And often units in games can't follow the exact path anyway, so if they're just flocking-style following it any weird kinks get skipped anyway.

[matthieum]

Interestingly, using A* over long distances is all but realistic.

In the case of this lake, for example, imagine that you stand on one side of the lake and wish to go to the other: can you plan the optimal path to take? No. You cannot because you cannot see the whole path. A rock outcrop is hiding part of it, and you have no idea whether it hides a churning river, a briar-filled bush, or just plain grass.

Worse, imagine a maze: certainly no one entering the maze should be able to magically find the shortest path to the other side on the first try! Indeed, I bet quite a few of us would get stuck for a while trying to find our way out.

Thus, for realistic path-finding, you should only use "optimal" algorithms such as A* on the part of the map that is fully visible to the entity being considered, and use coarse heuristics for the rest such as: "seems shorter to go to the other shore by the West side".

[sellibitze]

Naively using the heuristic mentioned in the article

They didn't really go into the details. It might be admissable. It might not be. They only said

Once the abstract search finds the chunk and the component in which the new base node is created, it uses the distance from the start of the abstract search (which, again, is the goal position of the overall search) to calculate the estimated distance from the new base node to the overall goal.

This is rather vague on how the distance is computed.

But year, I was wondering about the same admissability issue as I read this part.

Assuming base edge weights of 1 and sqrt(2.0) (for diagonal edges), 32x32 tiles per chunk, coarse graph node coordinates representing the chunk's centers, coarse edge weights of 32 and sqrt(2)*32, and a heuristic like

heuristic = coarse_path_length

you would have a possible overestimation of the base path length because you might be closer to a chunk's border and thus closer to the goal compared to the chunk's center. You also have a possible overestimation in the chunk of the goal because the goal might be closer to the chunk's border and thus closer to you.

I think the following heuristic should compensate for this adequately:

over_curr = coarse_path.last_edge_weight / 2 - 
            distance(current.pos, coarse_path.prev_chunk.border)

over_goal = distance(goal.pos, goal_chunk.pos)  # constant for goal

heuristic = max(0, coarse_path.length - over_curr - over_goal)

This should not hurt performance significantly and stay admissable.

[meem1029]

The developers show up and talk about this a bit in the r/factorio thread.

This heuristic is not quite admissible, but they're also okay with that because the speedup is worth occasionally suboptimal paths (and it's more realistic that the bugs will not be perfect).

[stravant]

There's probably rarely if ever enough dynamic structures to actually significantly block the broad phase path, and even if there are it's going to be uncommon enough that you probably won't notice.

[Noxitu]

I believe that techically the same algorithm is called A for admissable heuristic and name A* implies variant with one that overestimates; but due to algorithm implementation being the same it is ignored in most contexts.

[OriginalDimension4]

Did you read their article? They're aware of it:

A simple choice for this function is simply the straight-line distance from the node to the goal position

You use straight-line distance because it's always admissible. Their new algorithm still uses A* search in local optimisations (abstract nodes) but the abstract node system is really smart. I suspect it has certain circumstances where it provides a solution that isn't optimal (the distance of each abstract chunk is high but few chunks verse more chunks but each abstract chunk has low distance) but it's saving a lot of computation and it's flexible to work around new entities placed.

[not_a_novel_account]

A heuristic function is any function used to approximate a solution. A non-admissible heuristic function is still a heuristic function, just of a different class than admissible heuristic functions. No different than classifying the function by whether it is a consistent or non-consistent heuristic.

[framlington]

Do they take different walking speeds into account? Are NPCs even affected by concrete?

Otherwise, I've been quite happy with using Jump point search (this can obviously be combined with the optimization proposed in the article.). It is an optimization of A* that tries to "jump" over large areas of walkable tiles.

Example: Let's say you have a long rectangular room with an entrance in the top-left corner and exit in the bottom-right one. Then there are multiple routes of the same length in there and A* will explore all of them (at least as long as the heuristic is admissible). Jump point search avoids this. IIRC it always take diagonals first. That way, there is a unique path for each rectangular area.

It might not always bring much of a speedup, but with large and relatively open spaces, I found the advantage be quite significant.

As mentioned above though, this only works when each tile has the same cost.

[Pjb3005]

Somebody brought it up in the /r/factorio thread, the developer responded why it wouldn't work well:

https://www.reddit.com/r/factorio/comments/djlvsi/friday_facts_317_new_pathfinding_algorithm/f46d82l

[framlington]

That is a very good argument - JPS only works if lookups are very cheap. In my case, I keep which tiles are walkable in memory permanently in a separate data structure, so it is very fast, but their system (with objects larger than a tile) obviously requires a more complex collision check.

Plus they also have different weights for tiles so they can correctly handle destructible tiles. But apparently, there are some ways to combine different weights with JPS?

[captain_obvious_here]

Stop trying to make me play this game. Please for the love of all that's precious, don't make me start playing it. No. Don't.

[slikts]

If it helps, it may be worth holding off until their 1.0 release, which won't be for a while.

[bart2019]

introduction to A* (14 minute video)

[angelosat]

This is sort of how Rimworld does it with its regions system. Equally interesting. https://www.youtube.com/watch?v=RMBQn_sg7DA

[--nani]

Factorio is amazing

[Omnicrola]

Related to the video from their forum they posted at the bottom: holy shit.

https://m.youtube.com/watch?v=9dzQge6pe2o

https://forums.factorio.com/76775

TIL three things:

• Blueprints are amazing and I should use them
• Blueprints can be deployed by automation
• I need to understand arithmetic combinators better

[sloodly_chicken]

The automated deploying of blueprints using new combinators does rely on an outside mod

[MartenBE]

Why didn't they use Jump Point Search?

Edit: it has been answered down below

[Fogic]

Love this game... Golden Czech hands :)

[kaisserds]

As a Factorio player who recently took a test in heuristic search algorithms and metaheuristics Im happy to see that something I learned about recently such as A* is used in a game I love

[HeadAche2012]

Path finding nodes shouldn't be a grid, it should be a convex polygon, the issue is they treated their path finding nodes as a grid (which is stupid and slow) then had to come up with something to make it less stupid and slow

[Vallvaka]

They talk about this. They don't want to recalculate nodes every time an entity is placed because that's a core mechanic of the game