Friday Facts #317 - New pathfinding algorithm

[Pi-C]

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.

[BattleFluffy]

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]

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.

[MasterBuilder]

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.

[raidho36]

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!"

[darkfrei]

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]

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 ?

[mrvn]

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]

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

[darkfrei]

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]

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]

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]

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.

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]

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 (4.62 KiB) Viewed 7148 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]

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]

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]

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.

[BlueTemplar]

[...]
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.
[...]

[_alphaBeta_]

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]

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.