Friday Facts #317 - New pathfinding algorithm

[azesmbog]

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.

[DaleStan]

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]

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]

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]

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]

Thanks for your hard work Togos!

[asdff45]

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]

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]

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

It was released in 17.70 (a few days ago).

[veverak]

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]

You've been featured on Hacker News !

[ikiris]

*cough* flow field vector pathing *cough cough*

[afettere]

Cool stuff, but similar to https://www.computer.org/csdl/proceedin ... 2OmNAolH2Q

[xARCHONx]

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]

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

<biters-on-belts.gif>

Thanks for the well-wishes everybody!

[darkfrei]

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]

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]

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]

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]

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

Best regards,

Marcos