Friday Facts #317 - New pathfinding algorithm

Regular reports on Factorio development.
Pi-C
Filter Inserter
Filter Inserter
Posts: 445
Joined: Sun Oct 14, 2018 8:13 am
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by Pi-C » Sun Oct 20, 2019 1:45 pm

PaqpuK wrote:
Sun Oct 20, 2019 9:24 am
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.
That may come bundled with other issues, though. :-)
A good mod deserves a good changelog. Here's a tutorial (WIP) about Factorio's way too strict changelog syntax!

User avatar
BattleFluffy
Fast Inserter
Fast Inserter
Posts: 121
Joined: Sun Mar 31, 2019 4:58 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by BattleFluffy » Sun Oct 20, 2019 9:01 pm

This pathfinder improvements is awesome! This looks like the exact explanation for all the "frozen bitters" I always see after an intense shelling. And the new heuristic should take care of it. :>

Thankyou for preparing such a detailed explanation of the way the new algorithm works as well.

Time will tell, whether the foolish bitters can penetrate my defences... hmmm.. :>

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

Re: Friday Facts #317 - New pathfinding algorithm

Post by PaqpuK » Sun Oct 20, 2019 10:02 pm

Pi-C wrote:
Sun Oct 20, 2019 1:45 pm
PaqpuK wrote:
Sun Oct 20, 2019 9:24 am


Can it be solved by just reducing the collision hitbox of trees? I know a lot of people use mods for that already.
That may come bundled with other issues, though. :-)
Hmmm, would it be too hard to separate those hitboxes? Is it hardcoded in? I don't like squeak through (because imo you need to think through the layout of your pipes and other stuff), but trees are annoying, especially before you have robots.

User avatar
MasterBuilder
Filter Inserter
Filter Inserter
Posts: 317
Joined: Sun Nov 23, 2014 1:22 am
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by MasterBuilder » Sun Oct 20, 2019 11:41 pm

PaqpuK wrote:
Sun Oct 20, 2019 10:02 pm
Hmmm, would it be too hard to separate those hitboxes? Is it hardcoded in? I don't like squeak through (because imo you need to think through the layout of your pipes and other stuff), but trees are annoying, especially before you have robots.
Make the tree hitbox too small, and they fit between walls or rails and aren't marked for deconstruction when they should be. Then trains collide into them, or bots just hover waiting for a tree that's in the way but isn't marked.
Make tree hitboxes too large and they bottleneck biters.

Problem is there's no real in-between.
A possible solution would be a second, tiny hitbox, just for biters.

Or maybe some logic to cause biters to try to clear a path through trees instead of going single-file through them. This option may have a greater affect on UPS though.
Give a man fire and he'll be warm for a day. Set a man on fire and he'll be warm for the rest of his life.

raidho36
Long Handed Inserter
Long Handed Inserter
Posts: 57
Joined: Wed Jun 01, 2016 2:08 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by raidho36 » Mon Oct 21, 2019 4:16 am

0) ArrayLists have the best performance of the bunch by far, i.e. plain arrays work A LOT faster (just add handler functions on top of them to meet your API needs. In A* it's useful to check highest value nodes first, and inserting nodes w/ sorting will keep the list always sorted by default with minimum sorting overhead)
1) A* can be made to jump across nodes if it finds it's a straight path with no obstacles, making it A LOT faster (at expense of being unable to use non-uniform node traversal costs, so it only applies when there's no penalty for choosing any particular passable path) (you should make it so that collision check is a simple boolean fetch if this doesn't happen to be the case)
2) A* heuristic function can be made lazy by amplifying the distance coefficient, making it A LOT faster (at expense of finding sub-optimal paths under particularly bad obstacle layouts, usually within 5% difference from absolute best path)

The golden rule of optimizing for performance is:
"Measure!"

User avatar
darkfrei
Smart Inserter
Smart Inserter
Posts: 2307
Joined: Thu Nov 20, 2014 11:11 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by darkfrei » Mon Oct 21, 2019 7:14 am

How about to remove collisions between biters and trees? The are looking as insects and can go through any terrain: cliffs are also not a problem.

Maybe also remove collision between player and trees, but he also cannot build there or drive the car through the forest.

tldr: tree.collision_mask = transport_belt.collision_mask

Koub
Global Moderator
Global Moderator
Posts: 5203
Joined: Fri May 30, 2014 8:54 am
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by Koub » Mon Oct 21, 2019 7:31 am

darkfrei wrote:
Mon Oct 21, 2019 7:14 am
How about to remove collisions between biters and trees?
That's exactly what I was thinking : We could argue that biters are the native living form on the planet, and therefore very used to run between the native vegetation.

Also if the trees hitbox can't be shrunk, maybe the biters'/player's can ?
Koub - Please consider English is not my native language.

mrvn
Smart Inserter
Smart Inserter
Posts: 3892
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by mrvn » Mon Oct 21, 2019 10:53 am

In the simplified map how does the heuristic calculate the distance? You could be just crossing one tile at the edge of the chunk or go all the way across the chunk. Worst case there could be a spiral pattern so it takes 100+ tiles to cross a chunk.

So what's your trick there?

mrvn
Smart Inserter
Smart Inserter
Posts: 3892
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by mrvn » Mon Oct 21, 2019 10:54 am

Any plans to use A* for train path finding soon too?

User avatar
darkfrei
Smart Inserter
Smart Inserter
Posts: 2307
Joined: Thu Nov 20, 2014 11:11 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by darkfrei » Mon Oct 21, 2019 11:01 am

Koub wrote:
Mon Oct 21, 2019 7:31 am
Also if the trees hitbox can't be shrunk, maybe the biters'/player's can ?
Collision mask defines colliders between entities, you don't need to change the size of any collision boxes.

ratchetfreak
Filter Inserter
Filter Inserter
Posts: 943
Joined: Sat May 23, 2015 12:10 pm
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by ratchetfreak » Mon Oct 21, 2019 11:05 am

mrvn wrote:
Mon Oct 21, 2019 10:53 am
In the simplified map how does the heuristic calculate the distance? You could be just crossing one tile at the edge of the chunk or go all the way across the chunk. Worst case there could be a spiral pattern so it takes 100+ tiles to cross a chunk.

So what's your trick there?
The trick is fewer nodes to search, each big chunk is 32x32 = 1024 so path finding with the big nodes is 3 orders of magnitude faster than doing it on tiles

mrvn
Smart Inserter
Smart Inserter
Posts: 3892
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by mrvn » Mon Oct 21, 2019 11:45 am

ratchetfreak wrote:
Mon Oct 21, 2019 11:05 am
mrvn wrote:
Mon Oct 21, 2019 10:53 am
In the simplified map how does the heuristic calculate the distance? You could be just crossing one tile at the edge of the chunk or go all the way across the chunk. Worst case there could be a spiral pattern so it takes 100+ tiles to cross a chunk.

So what's your trick there?
The trick is fewer nodes to search, each big chunk is 32x32 = 1024 so path finding with the big nodes is 3 orders of magnitude faster than doing it on tiles
That wasn't the question.

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 » Mon Oct 21, 2019 11:54 am

darkfrei wrote:
Sat Oct 19, 2019 5:09 pm
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.
It is two-sided (and has always been). I only showed the forward search in the FFF to simplify things a bit.
mrvn wrote:
Mon Oct 21, 2019 10:53 am
In the simplified map how does the heuristic calculate the distance? You could be just crossing one tile at the edge of the chunk or go all the way across the chunk. Worst case there could be a spiral pattern so it takes 100+ tiles to cross a chunk.

So what's your trick there?
The heuristic is only supposed to give you a lower bound on the length of the optimal path, not the exact actual length. The heuristic uses the number of chunks that have to be traversed to reach the goal, and knowledge about which chunk to go to next (the came-from pointer in the abstract search). So, the heuristic is (number of chunks to goal) * (chunk size) + (shortest possible distance to the next chunk).

mrvn
Smart Inserter
Smart Inserter
Posts: 3892
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by mrvn » Mon Oct 21, 2019 12:40 pm

mrvn wrote:
Mon Oct 21, 2019 10:53 am
In the simplified map how does the heuristic calculate the distance? You could be just crossing one tile at the edge of the chunk or go all the way across the chunk. Worst case there could be a spiral pattern so it takes 100+ tiles to cross a chunk.

So what's your trick there?
The heuristic is only supposed to give you a lower bound on the length of the optimal path, not the exact actual length. The heuristic uses the number of chunks that have to be traversed to reach the goal, and knowledge about which chunk to go to next (the came-from pointer in the abstract search). So, the heuristic is (number of chunks to goal) * (chunk size) + (shortest possible distance to the next chunk).
[/quote]

Lets say I have this 2x2 chunk with water that I have to go around:
path.png
path.png (4.62 KiB) Viewed 758 times
Going from red to green that is 3 chunks to green and one tile to the next chunk: H(red->green) = 3 * 32 + 1 = 49. But the shortest path is actually 7.

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 » Mon Oct 21, 2019 12:51 pm

mrvn wrote:
Mon Oct 21, 2019 12:40 pm
Going from red to green that is 3 chunks to green and one tile to the next chunk: H(red->green) = 3 * 32 + 1 = 49. But the shortest path is actually 7.
Yes, that can indeed happen. We already use an inadmissible heuristic (because we use static weighting), so it shouldn't be too much of a problem.

mrvn
Smart Inserter
Smart Inserter
Posts: 3892
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by mrvn » Mon Oct 21, 2019 1:33 pm

Oxyd wrote:
Mon Oct 21, 2019 12:51 pm
mrvn wrote:
Mon Oct 21, 2019 12:40 pm
Going from red to green that is 3 chunks to green and one tile to the next chunk: H(red->green) = 3 * 32 + 1 = 49. But the shortest path is actually 7.
Yes, that can indeed happen. We already use an inadmissible heuristic (because we use static weighting), so it shouldn't be too much of a problem.
I hoped you had something more clever. But the difference is probably not noticeable unless you compute the path perfectly to compare. I bet most of the time any difference will be where nobody is watching or even invisible on the map.

To get a proper heuristic you could compute the minimal distance crossing each chunk. For every chunk compute the shortest path (just tiles, ignore entities) to get from any of the four sides to any other side for each connected component in the chunk. For each connected component that would be 12 ints (I would use uint8_t min_dist[4][4]; capped at 255) that can be computed when you determine the connected components of a chunk, either by taking the straight line distance of the closest points or bidirectional search from both sides for a more accurate result. This would get you back to giving a true lower bound although sometimes a lot lower for diagonal paths.

Enrahim
Manual Inserter
Manual Inserter
Posts: 1
Joined: Mon Oct 21, 2019 10:27 am
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by Enrahim » Tue Oct 22, 2019 6:04 am

I am surprised to see that you don't seem to be using jump point search, as your situation seem to lend itself well to that? (Big areas with uniform cost steps). Some modifications to the jps might be needed, but I still guess it would be more efficient than plain A*. It would still benefit from the improved heuristics presented in this forum post.

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

Re: Friday Facts #317 - New pathfinding algorithm

Post by BlueTemplar » Tue Oct 22, 2019 7:05 am

Oxyd wrote: [...]
The pathfinder is limited to doing a certain amount of steps per tick to avoid tanking UPS. With JPS, every iteration of the loop that searches for the next tile where you can make a turn would have to count as a step, and because each of these steps involves the same collision check it does for plain A*, the step limit would have to be very close to the current one, if not the same. And since JPS can visit each position on the map multiple times, it would be potentially slower than what we currently have.
[...]

User avatar
_alphaBeta_
Inserter
Inserter
Posts: 41
Joined: Fri Jul 29, 2016 3:27 am
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by _alphaBeta_ » Tue Oct 22, 2019 4:02 pm

I'm hoping this pathfinding upgrade is a precursor to more sophisticated biter attacks. Would be nice if biters offered more of a challenge by avoiding hazards altogether and going through a hole in your defenses.

valneq
Fast Inserter
Fast Inserter
Posts: 139
Joined: Fri Jul 12, 2019 7:43 am
Contact:

Re: Friday Facts #317 - New pathfinding algorithm

Post by valneq » Tue Oct 22, 2019 9:57 pm

_alphaBeta_ wrote:
Tue Oct 22, 2019 4:02 pm
I'm hoping this pathfinding upgrade is a precursor to more sophisticated biter attacks. Would be nice if biters offered more of a challenge by avoiding hazards altogether and going through a hole in your defenses.
It is unlikely that the biter AI with change significantly in the future – apart from the newly introduced pathfinding optimizations.

If you are looking for more challenging biters, you may try playing with the mod "Rampant" by "Veden". It has a more sophisticated biter AI: probing your defenses, attacking the weak spots, etc. Lots of people love it for that.
See its page on the modportal.

It also works in combination with mods that increase the strength of the biters themselves, such as "Bob's Enemies" or "Natural Evolution Enemies". If you like a proper warfare challenge.

Post Reply

Return to “News”

Who is online

Users browsing this forum: No registered users