Bot pathing for big bases

[dewitpj]

Hi,

Not sure if this should be a bug, but let's file it here first

I have quite a big, stretched out base - I started from the spawn position and the build was something like this:

N
^
|
|
W---+---------------------------> E
|
|
|
|
v
S

I have resources all over the place. The build to the east is much longer than any of the other builds. My logistics network is connected to the whole base. Sometimes, a bot needs to move stuff from the south point, to the east point. The bots then try and cross in a straight line from E to S, until they run out of energy. At this point they turn around and this process is repeated endlessly.

Can I proposed that the logic be changed to do pathing "via" the charging points if the direct path is too long ?

Cheers,

Pieter

[ssilk]

This has been discussed deeply in the threads listed in viewtopic.php?f=80&t=18093 Roboport/Logistic Network/Robot enhancements
Where I added this now too.

In short words: this is complex, cause you need to plan a route for each robot. In the meantime I can only recommend not to build such robot networks, belts are much better for that kind of transport. See wiki for the reasons https://wiki.factorio.com/index.php?tit ... ch_case%3F

[MindChanger]

You can use belts, train or...

There is some lastest topic about "Dispenser Chest" (viewtopic.php?f=6&t=28612)
"Dispenser chest" (or system that I proposed) located in W part would do the thing.
This chest would just magazine items from S and as it is shorter way to E than S, robots would go to this "dispenser chest" for items.
Problem solved.

[dewitpj]

This has been discussed deeply in the threads listed in viewtopic.php?f=80&t=18093 Roboport/Logistic Network/Robot enhancements
Where I added this now too.

In short words: this is complex, cause you need to plan a route for each robot. In the meantime I can only recommend not to build such robot networks, belts are much better for that kind of transport. See wiki for the reasons https://wiki.factorio.com/index.php?tit ... ch_case%3F

Sorry - I did miss that thread.

Yes, this will add a few calc's to the game, but I believe that it might not "be that bad" ?

Let's look at the following "logic"

if the distance to the target is greater than the range of the bot
then
find path to the roboport that owns the target, via roboports
else
do direct pathing
fi

Now, this pathing can be cached since the only thing that will change this is a roboport being added to the *current* network. I am thinking that the caching will be something like - if you wanna get from roboport A to roboport Z, you have to go via B,F,H. This pathing can also be calc'ed when the network changes.

As for why I am doing this - this is building out my rail network, but the biters/spitters has been set to max. Which means I end up with this massive dense enemies to get rid of. I use laser turrets and walls to build the rail. For this, I use chests to store the "stuff" in. I then put out a roboport, build the lasers etc around it, then clear out the area and rinse-repeat

The problem is that robots are left behind when I move to build out some other areas and then they are assigned other tasks which means they can't get to them

[ssilk]

find path to the roboport that owns the target, via roboports

You have never played with more than some hundred bots, have you?

Well, it is way more complex than this.

[dewitpj]

find path to the roboport that owns the target, via roboports

You have never played with more than some hundred bots, have you?

Well, it is way more complex than this.

Currently I have 800 bots, 400 logic and 400 construction. Think about this being cached and the impact is way less then one would expect. Targets can only be owned by roboports given that they define the area.

The game already does a bit of this when you build the roboport given that it draws the lines. The only one that is stumping me at the moment is a circular path but I am sure more coffee will fix that

[dewitpj]

Just thought about it some more - how about this is only done if the robot returns to the same charging station for the same job. So:

I am busy with task 0x123 (as example)
My previous charging station was 0x100
I am now returning to station 0x100 to charge as it is closest or what ever the logic is currently.
Clearly this is not working for me, now how would I get to the roboport that owns the target

The above will add a bit to the memory foot print along with two if statements everytime the robot recharges (First to check the current task and if the same then compare the charing station) - this does assume that a robot will do 2 or more tasks without recharging if the charge level is high enough (which I believe they do )

[Ghoulish]

Yes, this will add a few calc's to the game, but I believe that it might not "be that bad" ?

I've often wondered this when it comes to bot pathing. It's either a case that it would exponentially add to the processing needed (though if it's cached..?) OR it's on the to do list for a revisit/rework at some point down the line. Does anyone with good knowledge in this area know?

[dewitpj]

Yes, this will add a few calc's to the game, but I believe that it might not "be that bad" ?

I've often wondered this when it comes to bot pathing. It's either a case that it would exponentially add to the processing needed (though if it's cached..?) OR it's on the to do list for a revisit/rework at some point down the line. Does anyone with good knowledge in this area know?

My post above this one shows a possible solution to this or at least a way to reduce the number of calcs Floating point math (used to calc the bot's pathing atm) is quite heavy on the CPU where as memory look ups and compares are often single clock cycles. I can't think of a way to get around the floating point math thou, since the bot still has to fly to the roboport...

But - limiting this math to the times when it's needed (vs using it as the default pathing), along with some caching might has a small enough impact so that it's not noticed.

But yes, it would be nice to get a dev's PoV on this

[TheSkiGeek]

It feels like it wouldn't be too hard to compute optimal paths between all the roboports, since it only has to be updated once each time a roboport is placed. You could potentially do it lazily in the background for the existing ones when a new roboport is placed.

If you did that then you could have the bots do this:

1) fly directly to the closest roboport
2) follow the precomputed path from that roboport to the roboport closest to the destination
3) fly directly from that roboport to the destination

Which should be really, really cheap. Maybe add a short-circuit check to see if it's faster to fly straight to the destination.

[MindChanger]

Precomputing path can eat a lot of CPU work with high number of roboports and robots (see travelling salesman problem and this problem is even bigger, because you have to calculate it for each robot).

[ssilk]

It feels like it wouldn't be too hard to compute optimal paths between all the roboports, since it only has to be updated once each time a roboport is placed. You could potentially do it lazily in the background for the existing ones when a new roboport is placed.

Theaoretical yes. Practial they don't go to the next roboport, if it is too crowded. The formula is simple: Use next roboport If distance to roboport in tiles is bigger than number of waiting bots.

So the "shortest path" currently changes with the amount of bots waiting for charge and it can be awaited, that such a very useful behavior will be in a reworked pathing algorithm.

Which is quite difficult (as I already stated). So I would not put more brain into this suggestion. It needs to be changed, yes, but we cannot tell the developers how.

Instead we should tell the the WHAT. What would I like to do, what is annoying etc. But I don't see new insights in this thread till now, everything already discussed.

[hoho]

Precomputing path can eat a lot of CPU work with high number of roboports and robots (see travelling salesman problem and this problem is even bigger, because you have to calculate it for each robot).

No, you won't really need to calculate it for each robot.

If I were to design such a system, I'd generate a graph of roboports and precalculate fastest paths from each roboport to every other roboport. If something needs moving from one location to another, find the closest roboports to start and end and use the precalculated route between them.

Generating such a graph even for a few thousand roboports shouldn't be *that* resource intensive.

Of course, dealing with recharging queues require a different approach. For that it might make sense to iterate over closest roboports to find one with shortest queue at the moment bot energy reserves drop low enough to require recharge. Higher distance to port will add weight to the calculation, if a port is too "heavy", don't go there and prefer ones with longer queues but closer.

[MindChanger]

Hmm, I think you're right. If precalculated paths for roboports and this information saved somehow it wouldn't make much CPU loading all the time (only when new roboprot is put).

[Harkonnen604]

It's O(N^3) CPU and O(N^2) RAM to calculate all shortest paths from the scratch using Floyd-Warshall. As I remember it's just O(N^2) CPU to add a new node, but deconstruction still needs full recomputation. Another way to handle that could be decomposing logistic network into convex (rectangular) pieces and perform graph calculations with these big pieces while using current bot routing algos within a rectangular piece.

Another thing I mentioned in another thread - it would be nice if bots predict point on their travel line when they reach critical charge level and decide to head for recharge, and head to that preselected roboport right away - this way there will much less redundant zig-zags and turning around. Though in your situation bots will just stand still in the roboport they are if they keep returning back there

[hoho]

It's O(N^3) CPU and O(N^2) RAM to calculate all shortest paths from the scratch using Floyd-Warshall.

For a network of 1000 ports it means a billion "operations" and million "units" of memory.

Memory requirement is tiny and can be ignored. Billion operations is quite a bit but doable in a couple of seconds in a background thread - nothing bad will happen if bots use the old pre-calculated values for a few seconds. The calculations themselves should also be quite simple considering there is no real "pathfinding", just points on a 2D grid with no obstacles. Not to mention that it can be GREATLY simplified by making it hierarchical by combining bigger concave areas covered by ports into a single unit.


It would be doable for sure. It'll take time and effort and I'm not sure if there is much point in doing that. Robot networks aren't meant to span thousands of chunks via spaghetti-like "roads".

[MindChanger]

viewtopic.php?f=8&t=28268

I created Magazine delivery, if placed correctly it can fix your problem!
Not tested much tho

[dewitpj]

viewtopic.php?f=8&t=28268

I created Magazine delivery, if placed correctly it can fix your problem!
Not tested much tho

Sorry - I don't see how

[MindChanger]

viewtopic.php?f=8&t=28268

Sorry - I don't see how

U don't see how - but what exactly?
Blueprint?
How to place correctly?

[ssilk]

... how it helps to solve the problem mentioned in this suggestion. I would also say it's a bit off-topic.