Friday Facts #317 - New pathfinding algorithm

[FactorioBot]

Here it is! (beep boop)

https://factorio.com/blog/post/fff-317

[Gergely]

A topic this good this early?

I must be dreaming!

[LotA]

Magnificent !

Although, I'm wondering if cliffs should not be taken into account by the "abstract pathfinder", It's not something you can remove early on and even when you can, most of it will remain intact (as you will probably only remove cliffs from inside your base). The only moment the pathfinding "slows down" is precisely when it has to find a way around cliffs using the "base pathfinder". Moreover, you don't need to update the abstract map on any cliff destruction, just once in a while, ideally when a bitter comes close and "finds out" a new way is available.
Anyway this looks very very promising.

[DanGio]

Bye TOGoS & thank you !

[T-A-R]

They are coming, we're all doomed! (excited!:D)

In some way it feels sad ToGoS is leaving the team, but he done a great job ( the mapgen evolved alot) and i like the current maps alot. And i guess we'ra all happy we can consider it done and finished. Thanks you for your effort, and being part of Wube! I wish you all the best in your next challenge. And i hope you will take Wube's no nonsense spirit with you to.

[programaths]

TOGoS, from conveyor belts to treadmills...there is only a step!

[Zaflis]

Awesome pathfinder i must say. One little question about it though, because i heard the AAI vehicles use biter AI too. Can it be told to find a path that ignores trees and rocks, and just drive through them? How about other vehicles in the way, will they somehow semi-smartly still group together?

[Oxyd]

Magnificent !

Although, I'm wondering if cliffs should not be taken into account by the "abstract pathfinder", It's not something you can remove early on and even when you can, most of it will remain intact (as you will probably only remove cliffs from inside your base). The only moment the pathfinding "slows down" is precisely when it has to find a way around cliffs using the "base pathfinder". Moreover, you don't need to update the abstract map on any cliff destruction, just once in a while, ideally when a bitter comes close and "finds out" a new way is available.
Anyway this looks very very promising.

Taking cliffs into account on the abstract level is not a bad idea, but it would mean that splitting a chunk into components would now have to look at the chunk's entities, which is considerably more complicated and slower than simply looking at its tiles – tiles are, basically, just integers.

Also, the biggest hurdle for the base pathfinder now is something very relatable to everyone: Trees.

[xeln4g4]

Good luck TOGoS! Wish you all the best for your future! Looking forward for any mods from you! Thank you for your contribution to this great game!

[kulib]

Also, the biggest hurdle for the base pathfinder now is something very relatable to everyone: Trees.

So it is true... The biggest enemy of the game not only for players but for the game itself. Trees.

[Ghoulish]

Bye bye TOGoS, hope your new job pans out well, thanks for helping make Factorio the game we love.

[Nedreow]

I remember reading a development journal / video for Rimworld where the developer explained a very similar system of simplifying chunks into nodes and edges. I cannot find it anymore though. Does anyone else have a link?

Also good luck at your next job TOGoS

[LotA]

Taking cliffs into account on the abstract level is not a bad idea, but it would mean that splitting a chunk into components would now have to look at the chunk's entities, which is considerably more complicated and slower than simply looking at its tiles – tiles are, basically, just integers.

Also, the biggest hurdle for the base pathfinder now is something very relatable to everyone: Trees.

Yeah, you're right, cliffs are entities... It would be a lot of pain (in term of code rewrite and cpu usage as the abstract map is calculated) to take them into account for a very slight improvement, probably not worth in the end.
And if cliffs were mere tiles (with blending magic) you'd already took them into account, my bad.

[Lord Darkness]

Thanks for the amazing post! I loved tech tidbits about the game, makes me really want to get into gamedev.

I like the approach to optimise pathfinding, but it makes me wonder: is a traced path assigned to a group of biters who move together or individually, and does it get stored to be used again later, or is it used all the time? Also, does the bitter start working as soon as the pathing starts, or does it wait for it to be complete?

The part of memorizing paths made me think it it'd be nice to make it work like ants, like one would open up a path and set it with pheromones, stuff like that, and others would just follow it. The pathing could be generated "on-the-fly" by one "explorer" bitter on the group, and the others would just follow. I mean, it's a little weird that a bitter know exactly the pathing it'd need to go somewhere prior to going there, right? From a gaming standpoint it's fine, but is it really necessary?

I also wondered if it'd start walking immediately, because if not, I'd trace the pathing backwards, haha, although I suppose the results would probably be the same. Or is it possible to trace both ways (from start to end) and make them meet eachother midway? Would in theory double the speed as well, though it could lead to some inconsistencies.

Sorry for speaking my mind, I have no clue about this at all, never messed with pathfnding myself, haha, but it really made me think about ways to otpmise it and make it cooler.

[Oxyd]

Thanks for the amazing post! I loved tech tidbits about the game, makes me really want to get into gamedev.

I like the approach to optimise pathfinding, but it makes me wonder: is a traced path assigned to a group of biters who move together or individually, and does it get stored to be used again later, or is it used all the time? Also, does the bitter start working as soon as the pathing starts, or does it wait for it to be complete?

Biters usually form groups, so only one path needs to be found for the entire group. Also, the paths do get cached so they can be re-used later.

Or is it possible to trace both ways (from start to end) and make them meet eachother midway? Would in theory double the speed as well, though it could lead to some inconsistencies.

Yep, it does currently work both ways. In the FFF, I only showed the forward direction to keep things simple, but there is also a backward search that goes from goal to start and they usually meet somewhere in the middle. It doesn't really make it that much faster usually, but it's important when either the start or goal is on a small island – one of the two directions will explore the entire island first, and once that happens, you can report that a path cannot exist. If the search only worked one way, and you wanted to go from a large continent to a small island, you'd have to explore the entire continent to learn that the island is unreachable.

[Lubricus]

Amazing that you guys is able to improve the old A* algoritm for your case.
Realistically biters don't have a prefect knowledge of the terrain and wouldn't always take the shortest path. I would have get lost and meandering around until i find the right way, and I assume I am smarter than a biter.
So don't be afraid to use more heuristic algoritms where some biters go around and take a more stupid path.

[BlueTemplar]

I wouldn't assume that, I'm willing to bet that ants beat humans where pathfinding is concerned...
Speaking of pheromones, Rampant uses them, along with potential fields (potential fields of pheromones?) :

Pathfinding - Unit groups will use potential fields to perform only single step pathfinding allowing for efficient and dynamic pathing

But also for stuff like :

Probing Behavior Against Defenses - unit groups will attempt to avoid chunks that are soaked in death

Player Hunting - Unit groups will track the player based on there emitted pheromone cloud

But then potential fields have their own issues :

· Poor performance in narrow passages
· Poor performance in a dynamic environment
· Prone to get stuck in local minima situations
· Problems in dealing with the symmetrical obstacles

(Which might be acceptable for a mod, but not for Factorio itself.)

P.S.: Though my gripe with Rampant is how the pheromone field is very hard to visualize... on purpose ?

[Cgeta]

Ooh wow
I always thought factorio already had some kind of "large scale" pathfinding
Since I had occasionally seen biters walk straight into a cliff, and only then walk around it. I thought that the regular pathfinder led them through it, and then some higher resolution pathfinder started up and led them around it

I wonder if the biters will still attack poles, rocks, or trees that are in their way even thought they could just walk around it. But I guess it could partly be that the biters have different sizes, and they don't fit where the path leads them to?

I'm amazed to see how well it works even at big distances like that!

[TheRealBecks]

Great! Is there already a timeline for that new pathfinding engine? Maybe... today?

[beiju]

The pathfinding improvements are super interesting!

Will mods be able to query the heuristic value between two arbitrary points? If not, would that be likely to be added if someone requests it?