Friday Facts #317 - New pathfinding algorithm

Regular reports on Factorio development.
User avatar
FactorioBot
Factorio Staff
Factorio Staff
Posts: 249
Joined: Tue May 12, 2015 1:48 pm

Friday Facts #317 - New pathfinding algorithm

Post by FactorioBot » Fri Oct 18, 2019 11:03 am


User avatar
Gergely
Filter Inserter
Filter Inserter
Posts: 531
Joined: Sun Apr 10, 2016 8:31 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by Gergely » Fri Oct 18, 2019 11:05 am

A topic this good this early?

I must be dreaming!

User avatar
LotA
Fast Inserter
Fast Inserter
Posts: 115
Joined: Fri Oct 10, 2014 11:41 am
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by LotA » Fri Oct 18, 2019 11:22 am

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.
Last edited by LotA on Fri Oct 18, 2019 11:34 am, edited 2 times in total.

DanGio
Fast Inserter
Fast Inserter
Posts: 223
Joined: Sat May 10, 2014 6:22 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by DanGio » Fri Oct 18, 2019 11:30 am

👋 Bye TOGoS & thank you !

T-A-R
Long Handed Inserter
Long Handed Inserter
Posts: 91
Joined: Tue May 22, 2018 4:20 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by T-A-R » Fri Oct 18, 2019 11:38 am

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
Burner Inserter
Burner Inserter
Posts: 5
Joined: Fri Feb 22, 2019 6:44 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by programaths » Fri Oct 18, 2019 11:44 am

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

Zaflis
Filter Inserter
Filter Inserter
Posts: 305
Joined: Sun Apr 24, 2016 12:51 am
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by Zaflis » Fri Oct 18, 2019 12:02 pm

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
Factorio Staff
Factorio Staff
Posts: 1297
Joined: Thu May 07, 2015 8:42 am
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by Oxyd » Fri Oct 18, 2019 12:04 pm

LotA wrote:
Fri Oct 18, 2019 11:22 am
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
Inserter
Inserter
Posts: 45
Joined: Fri Oct 28, 2016 2:42 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by xeln4g4 » Fri Oct 18, 2019 12:14 pm

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
Burner Inserter
Burner Inserter
Posts: 5
Joined: Tue Jun 16, 2015 5:13 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by kulib » Fri Oct 18, 2019 12:23 pm

Oxyd wrote:
Fri Oct 18, 2019 12:04 pm

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
Filter Inserter
Filter Inserter
Posts: 355
Joined: Fri Oct 16, 2015 8:40 am

Re: Friday Facts #317 - New pathfinding algorithm

Post by Ghoulish » Fri Oct 18, 2019 12:27 pm

Bye bye TOGoS, hope your new job pans out well, thanks for helping make Factorio the game we love.
See the daily™ struggles with my Factory! :D https://www.twitch.tv/fruityrob

User avatar
Nedreow
Burner Inserter
Burner Inserter
Posts: 12
Joined: Wed May 06, 2015 3:08 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by Nedreow » Fri Oct 18, 2019 12:31 pm

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

User avatar
LotA
Fast Inserter
Fast Inserter
Posts: 115
Joined: Fri Oct 10, 2014 11:41 am
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by LotA » Fri Oct 18, 2019 12:59 pm

Oxyd wrote:
Fri Oct 18, 2019 12:04 pm
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
Manual Inserter
Manual Inserter
Posts: 1
Joined: Fri Oct 18, 2019 1:11 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by Lord Darkness » Fri Oct 18, 2019 1:18 pm

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
Factorio Staff
Factorio Staff
Posts: 1297
Joined: Thu May 07, 2015 8:42 am
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by Oxyd » Fri Oct 18, 2019 1:30 pm

Lord Darkness wrote:
Fri Oct 18, 2019 1:18 pm
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.
Lord Darkness wrote:
Fri Oct 18, 2019 1:18 pm
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.

User avatar
Lubricus
Fast Inserter
Fast Inserter
Posts: 239
Joined: Sun Jun 04, 2017 12:13 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by Lubricus » Fri Oct 18, 2019 1:35 pm

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.

User avatar
BlueTemplar
Smart Inserter
Smart Inserter
Posts: 1812
Joined: Fri Jun 08, 2018 2:16 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by BlueTemplar » Fri Oct 18, 2019 1:57 pm

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
Burner Inserter
Burner Inserter
Posts: 5
Joined: Fri Jan 05, 2018 9:26 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by Cgeta » Fri Oct 18, 2019 2:40 pm

Ooh wow :D
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
Inserter
Inserter
Posts: 32
Joined: Sat Mar 26, 2016 3:47 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by TheRealBecks » Fri Oct 18, 2019 2:45 pm

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

beiju
Inserter
Inserter
Posts: 39
Joined: Thu Feb 02, 2017 3:52 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by beiju » Fri Oct 18, 2019 2:48 pm

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?

Post Reply

Return to “News”

Who is online

Users browsing this forum: No registered users