Friday Facts #317 - New pathfinding algorithm

Regular reports on Factorio development.
azesmbog
Long Handed Inserter
Posts: 69
Joined: Mon Jan 28, 2019 12:05 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Say the new algorithm ?? H-hehh
TWO! hours did nothing and just watched the new algorithm))
Before my eyes, after the shelling of the cannons, several flocks were organized, both large and smaller. And they stood still. I watched them all this time. During this time, after an hour and a half, several small groups arrived, where they hid for two hours?)) The main group, on the left in the screenshot, melted until it started to disappear, like most others. The remaining screenshots are in the archive. Look at them yourself.
Attachments
show-path2.jpg (478.35 KiB) Viewed 1578 times
181019.ZIP
(2.82 MiB) Downloaded 21 times

DaleStan
Filter Inserter
Posts: 277
Joined: Mon Jul 09, 2018 2:40 am
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

azesmbog wrote:
Fri Oct 18, 2019 3:27 pm
Chunks: 1,725,832
I have seen megabases that are less than one percent that size, and that only because of their pollution cloud, not because they actually used that much land.

If you think something other than the map size is the problem, you'll need to post a save, not just screenshots.

danielsundfeld
Manual Inserter
Posts: 1
Joined: Fri Oct 18, 2019 2:52 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Hello. I'm a junior professor on informatics and during my phd I've worked with the parallelization of the A Star algorithm and I found this ff fascinating. I have a question: what's the data structure you're using for the OpenList and ClosedList?
Usually the ClosedList is implemented using a hash table or STL map. But the OpenList is much more complicated. Commonly implemented using two data structures, a hashmap/map and a priority queue. Although, the famous libboost has a great structure called multi-index and I was able to avoid duplicate nodes in memory just by using it.

If you're interested, search for "PA-Star: A disk-assisted parallel A-Star strategy with locality-sensitive hash for the multiple sequence alignment". The code is also available on github

Oxyd
Factorio Staff
Posts: 1298
Joined: Thu May 07, 2015 8:42 am
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

danielsundfeld wrote:
Fri Oct 18, 2019 4:36 pm
Hello. I'm a junior professor on informatics and during my phd I've worked with the parallelization of the A Star algorithm and I found this ff fascinating. I have a question: what's the data structure you're using for the OpenList and ClosedList?
Usually the ClosedList is implemented using a hash table or STL map. But the OpenList is much more complicated. Commonly implemented using two data structures, a hashmap/map and a priority queue. Although, the famous libboost has a great structure called multi-index and I was able to avoid duplicate nodes in memory just by using it.

If you're interested, search for "PA-Star: A disk-assisted parallel A-Star strategy with locality-sensitive hash for the multiple sequence alignment". The code is also available on github
We use just plain old binary heap for the open list. Plus a map for an all-nodes list, and each node has an “is closed” boolean in it, so that there's just one map to look up both closed and open nodes in, and closing a node amounts to setting a bool, and popping it off the open heap.

nafira
Long Handed Inserter
Posts: 75
Joined: Fri Mar 16, 2018 12:20 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

A n-th level A* pathfinding is a good thing to have (I'm surprised it was not even already here).

What you could do to improve again this algorithm, is to go from 2 level of nodes to a 3 or 4 lvl node A* pathfinding. A power 2 scale or 3 should be a good (or a mix)

matjojo
Filter Inserter
Posts: 315
Joined: Wed Jun 17, 2015 6:08 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Thanks for your hard work Togos!

asdff45
Inserter
Posts: 34
Joined: Sun Aug 07, 2016 1:23 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

You are using the A* Algorithm for defining the final path.
Why are you not using a Jump Point Search instead, which should be faster than the A*?

Oxyd
Factorio Staff
Posts: 1298
Joined: Thu May 07, 2015 8:42 am
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

asdff45 wrote:
Fri Oct 18, 2019 8:51 pm
You are using the A* Algorithm for defining the final path.
Why are you not using a Jump Point Search instead, which should be faster than the A*?
JPS basically means you store fewer nodes in memory, at the cost of examining more, since you can examine a node potentially multiple times during a search (because it's not saved). “Examining a node” in Factorio means doing a collision check, which is a rather expensive operation. So, in other words, it's the trade-off of having smaller open set at the cost of doing more collision checks. I don't think that trade-off makes sense for us.

Funnily enough, all the JPS benchmarks I've seen are on simple grids where examining a node amounts to reading a single bit from memory (wall/not wall), and those benchmarks usually only focus on the number of nodes stored in memory, rather than grid cells actually touched by the algorithm.

Jap2.0
Smart Inserter
Posts: 2075
Joined: Tue Jun 20, 2017 12:02 am
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

TheRealBecks wrote:
Fri Oct 18, 2019 2:45 pm
Great! Is there already a timeline for that new pathfinding engine? Maybe... today?
It was released in 17.70 (a few days ago).
There are 10 types of people: those who get this joke and those who don't.

veverak
Manual Inserter
Posts: 1
Joined: Fri Oct 18, 2019 9:33 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Hi! another CS student here...

Are you aware of D* Lite? It's an algorithm for this problem that works simillary to A* (uses same heuristics), but can be much faster in your use case -> it's designed to handle graph that changes while it is traversed.

So, if you find a path and something changes (new building, or whatever), this algorithm should be faster than starting A* again.

"should be" is however proper term used, as it's not outmatching "repeated A*" in worst case scenario.

John

BlueTemplar
Smart Inserter
Posts: 1973
Joined: Fri Jun 08, 2018 2:16 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

ikiris
Inserter
Posts: 26
Joined: Sun Jul 19, 2015 5:57 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

*cough* flow field vector pathing *cough cough*

afettere
Manual Inserter
Posts: 1
Joined: Sat Oct 19, 2019 5:24 am
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

xARCHONx
Burner Inserter
Posts: 6
Joined: Wed Aug 08, 2018 3:54 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Oxyd wrote:
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.
You know, I wouldn't at all be opposed to smaller biters being able to either squeeze through trees easily, or not collide with them at all.

TOGoS
Former Staff
Posts: 80
Joined: Fri Jun 24, 2016 2:29 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

programaths wrote:
Fri Oct 18, 2019 11:44 am
TOGoS, from conveyor belts to treadmills...there is only a step!
<biters-on-belts.gif>

Thanks for the well-wishes everybody!

darkfrei
Smart Inserter
Posts: 2368
Joined: Thu Nov 20, 2014 11:11 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

You are show the pathfinding only from A to B, is two sided search not better? I can simultaneously search paths A to B abd B to A, just wait when they find the same point, connection point.

PaqpuK
Manual Inserter
Posts: 3
Joined: Wed Sep 18, 2019 6:42 am
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

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.
Can it be solved by just reducing the collision hitbox of trees? I know a lot of people use mods for that already.

BlueTemplar
Smart Inserter
Posts: 1973
Joined: Fri Jun 08, 2018 2:16 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Oxyd wrote:
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.
I guess that you already thought of this, but maybe converting cliffs to be, like water, a tile type rather than an entity - would be a better solution ?
(Also in this way, you can use the same algorithm accounting for map changes for landfill and for cliff explosives...)
And it would hopefully solve all those issues with cliff bounding-box-corners sticking out and trapping belts, rails & cars !
PIC
While on the other hand trees and rocks are ultimately easy to destroy, and biters in fact do regularly destroy them to get a better path : make a very polluting base on the other side of a dense forest from a nest and see the biters clear a path in it !

BlueTemplar
Smart Inserter
Posts: 1973
Joined: Fri Jun 08, 2018 2:16 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

TOGoS wrote:
Sat Oct 19, 2019 4:49 pm
programaths wrote:
Fri Oct 18, 2019 11:44 am
TOGoS, from conveyor belts to treadmills...there is only a step!
<biters-on-belts.gif>

Thanks for the well-wishes everybody!
Give'm hell !

mtfreitasf
Burner Inserter
Posts: 5
Joined: Sat Apr 27, 2019 12:38 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Congratulations on the new pathfinding algorithm and good luck Togos.

I have been expanding my base so I have done a lot of fighting. I usually build a turret barrier and attract the enemies. I have observed that they don't attack the barrier but focus on trying to reach the player, as seen in the snapshot below. If I stand far enough behind, I and the turrets don't suffer any damage. Is it intended or not?
Factorio.png (186.58 KiB) Viewed 679 times
Best regards,

Marcos

Who is online

Users browsing this forum: No registered users