Bots that are aware of their charge level and plan accordingly.

[Moosfet]

Presently, though they're certainly aware of their charge level for optimization purposes, the bots act like they have no idea when their charge will hit 20%, and instead always fly straight towards their destination until they reach 20% charge, then divert to the nearest roboport, leading to paths taken that look like this:

naive-algorithm.png (22.51 KiB) Viewed 4933 times

It's sometimes even worse, with bots heading to place an item, stopping a mere tile or two before reaching the destination, turning around, running out of charge before even reaching the roboport to charge, slowly slinking towards it, charging, then going back to place the item. Every time I see it, it strikes me as insane, because being a programmer myself, I imagine the way these things are implemented is that at the start of the journey, the game calculates where the bot will be at 20% charge, then just makes a note that it's on the way there until the game tick when it's going to arrive, rather than check the charge level every game tick, turning the bot's journey into one where it's location each frame can just be calculated with a simple equation rather than having to re-do the math to figure out how to move it one step closer to it's destination each game tick. So, as long as it's doing that, why on earth doesn't it just pick a different destination for the bot given that it knows it won't reach its actual destination?

Imagine if, instead of setting the bot's destination in the middle of nowhere, the game instead says "well, we can't reach that destination, so which of the roboports that we can reach is closest to that destination?

Well, step one looks like this: The roboports in the circle are close enough to reach (going all the way to 0% instead of only 20% charge, since, being smarter, the bots no longer need that 20% reserve). So it picks the one that is closest to the destination, and flies there.

step1.png (39.76 KiB) Viewed 4933 times

No need to path-find (the reason suggestions about improving this behavior have been rejected in the past) but instead what's going on is similar to what already happens. Just, rather than waiting until reaching the 20% point to find the nearest roboport, we find it right from the start. So this doesn't require any more computation than the game already does.

Then, after recharging at that roboport, the bot does the same thing: It realizes that the destination isn't inside the circle, and so of the roboports in the circle, it picks the one which is closest to the destination.

step2.png (42.94 KiB) Viewed 4933 times

Then, step three:

step3.png (43.61 KiB) Viewed 4933 times

Then step four:

step4.png (35.8 KiB) Viewed 4933 times

I actually stole the base image for this from another thread where Rseding91 said "As I've said before: this is not likely to ever happen. It would increase the CPU cost of robots by massive amounts for incredibly miniscule gains." However, again, I'm not suggesting path-finding the shortest path. What I'm suggesting is actually fewer calculations than the game already does.

Presently the game:

1. Checks if bot can reach destination. Upon realizing that it can't:
2. Calculate the point at which it would reach 20% charge, and set that point as the destination.
3. Once there, create a list of all nearby roboports, determine the closest one, plus some other considerations like how many other bots are already charging there.
4. Set that roboport as the new destination.

What I'm suggesting:

1. Checks if bot can reach destination. Upon realizing that it can't:
2. Create a list of all nearby roboports, determine the closest one, plus some other considerations like how many other bots are already charging there.
3. Set that roboport as the new destination.

It's one less step. Thus, this won't hurt game performance, it'll actually improve it.

These bots are able to pick up and drop off items on their own, and they're able to fix broken equipment, but they have no idea when they're going to hit 20% charge and no ability to plan recharges? It's silly. Especially since it wouldn't require any more calculation than the game already does, if a bot isn't going to reach it's destination, it should head for a recharge station instead.

[FuryoftheStars]

Get a +1 from me.

[Nidan]

Presently the game:

1. Checks if bot can reach destination. Upon realizing that it can't:
2. Calculate the point at which it would reach 20% charge, and set that point as the destination.

Do you have a source for this? I'd say they simply home in on the destination, calculated each tick, and once reaching low charge divert to a roboport (~ step 3 & 4).


I feel there are still some open questions with your proposal:
How are the bots going to track moving targets? When only updating after each charge I can easily construct a pathological case where the bot would never reach a target, even if the bot is faster than the target.
How are enemies going to find bots to shoot at? If all we have is the bots starting point and max range, we'd need an area search with a radius of the enemies aggression range plus the bots range to find all bots we need to calculate the exact position for.
How are the bots going to handle better roboports appearing or their current recharge port disappearing? Or a tech increasing bot speed? (Is decreasing possible?)

[Moosfet]

Do you have a source for this? I'd say they simply home in on the destination, calculated each tick, and once reaching low charge divert to a roboport (~ step 3 & 4).

I think you may be right actually. Otherwise they wouldn't be able to deal with moving targets nor, as you mention, would enemies know where they are. In any case, it doesn't really affect what I'm saying about how this isn't a more difficult algorithm. Figuring out how far the bot can go is a simple multiplication, (charge level) * (distance per charge unit), done once when the bot leaves a roboport, so it won't hurt performance. The game only seems to release one robot per game tick so I think it can handle calculating the robot's max distance and comparing it to the distance of the destination. The saved calculations just in the bots not being in the air as long will surely make up for whatever is lost by that calculation.

How are the bots going to track moving targets? When only updating after each charge I can easily construct a pathological case where the bot would never reach a target, even if the bot is faster than the target.

In the other thread I was reading about such cases. I'm not looking to fix everything that could go wrong, just this problem as it seems like very low-hanging fruit. If you're talking about a problem that doesn't exist now, but would with my proposal, then I'll need you to elaborate.

How are enemies going to find bots to shoot at?

That's another reason I'm probably wrong about the game calculating the out-of-energy location. So they'd have to travel as they do now. ...which is fine, I wasn't suggesting to change how their position is updated each game tick, just how the game chooses their destinations.

How are the bots going to handle better roboports appearing or their current recharge port disappearing? Or a tech increasing bot speed? (Is decreasing possible?)

Do they handle this now? If so then I guess the game recalculates when they get an upgrade, and so it would do the same thing with my proposal. If not then IDK why my idea needs to do it either. Again, I'm not looking to fix every problem, but this particular one seems like really low-hanging fruit with the solution I propose.

[FuryoftheStars]

How are enemies going to find bots to shoot at?
[…]
How are the bots going to handle better roboports appearing or their current recharge port disappearing? Or a tech increasing bot speed? (Is decreasing possible?)

I feel like both of these questions have no bearing on the proposal because the answer is simply “the same way they do now”. There’s nothing really about this proposal that would change these.

[Nidan]

Do you have a source for this? I'd say they simply home in on the destination, calculated each tick, and once reaching low charge divert to a roboport (~ step 3 & 4).

I think you may be right actually. Otherwise they wouldn't be able to deal with moving targets nor, as you mention, would enemies know where they are. In any case, it doesn't really affect what I'm saying about how this isn't a more difficult algorithm. Figuring out how far the bot can go is a simple multiplication, (charge level) * (distance per charge unit), done once when the bot leaves a roboport, so it won't hurt performance. The game only seems to release one robot per game tick so I think it can handle calculating the robot's max distance and comparing it to the distance of the destination. The saved calculations just in the bots not being in the air as long will surely make up for whatever is lost by that calculation.

I'm not concerned about a single multiplication, those are cheap. Rather the area search to find a suitable roboport and the need to keep track of it. Doing the search only once per recharge is fine, since the time of that search will, as you wrote, simply be moved forward. But there are cases where it'd need to be done multiple times per recharge (see my third question). This is a performance cost and without a sufficient performance gain elsewhere may make it unlikely for the idea to be implemented. Eliminating the need to touch each bot's position every tick would have been great. (I doubt less flying time in a hole containing network will be seen worthwhile.)

How are the bots going to track moving targets? When only updating after each charge I can easily construct a pathological case where the bot would never reach a target, even if the bot is faster than the target.

In the other thread I was reading about such cases. I'm not looking to fix everything that could go wrong, just this problem as it seems like very low-hanging fruit. If you're talking about a problem that doesn't exist now, but would with my proposal, then I'll need you to elaborate.

The way I understood your proposal was that each bot, when leaving the roboport, would calculate it's next recharge point (or final destination) and wouldn't be touched until it arrives there. Thus there's no chance to immediately react to a moving target.

How are enemies going to find bots to shoot at?

That's another reason I'm probably wrong about the game calculating the out-of-energy location. So they'd have to travel as they do now. ...which is fine, I wasn't suggesting to change how their position is updated each game tick, just how the game chooses their destinations.

Ok, when still updating the bots position each turn, this concern disappears.

How are the bots going to handle better roboports appearing or their current recharge port disappearing? Or a tech increasing bot speed? (Is decreasing possible?)

Do they handle this now? If so then I guess the game recalculates when they get an upgrade, and so it would do the same thing with my proposal. If not then IDK why my idea needs to do it either. Again, I'm not looking to fix every problem, but this particular one seems like really low-hanging fruit with the solution I propose.

Assuming movement decisions are made each tick, there's no need to handle it now, movement calculations will just read the current values. Except for the current target disappearing (which may also be a roboport for recharging), at which point the game will probably search for a new one.

How are enemies going to find bots to shoot at?
[…]
How are the bots going to handle better roboports appearing or their current recharge port disappearing? Or a tech increasing bot speed? (Is decreasing possible?)

I feel like both of these questions have no bearing on the proposal because the answer is simply “the same way they do now”. There’s nothing really about this proposal that would change these.

The way I understood the suggestion was that the bots current position should no longer be explicitly stored, but rather calculated on demand when needed. For the second question one could argue to just bite the bullet of having to (re)do extra work since these happen only once in a while (, but see my reply after the first quoted bit). But for biter targeting, area searches are one of the more expensive problems, so multiplying the area needed to search will kill performance.

[Koub]

Presently the game:

1. Checks if bot can reach destination. Upon realizing that it can't:
2. Calculate the point at which it would reach 20% charge, and set that point as the destination.
3. Once there, create a list of all nearby roboports, determine the closest one, plus some other considerations like how many other bots are already charging there.
4. Set that roboport as the new destination.

What I'm suggesting:

1. Checks if bot can reach destination. Upon realizing that it can't:
2. Create a list of all nearby roboports, determine the closest one, plus some other considerations like how many other bots are already charging there.
3. Set that roboport as the new destination.

It's one less step. Thus, this won't hurt game performance, it'll actually improve it.

These bots are able to pick up and drop off items on their own, and they're able to fix broken equipment, but they have no idea when they're going to hit 20% charge and no ability to plan recharges? It's silly. Especially since it wouldn't require any more calculation than the game already does, if a bot isn't going to reach it's destination, it should head for a recharge station instead.

I'll link the original post you're refering to here, for completeness : viewtopic.php?f=80&t=18093.
Specifically, you might want to give a look at this post and maybe also this one.

I think that no matter how much we think our solutions are "simpler" than what's currently implemented, and how we think it should be lighter computationally wise, in reality, what we suggest always add overhead when compared to what's ingame now.

Don't get me wrong : I'm as infuriated as you are when I see a bot stop its path mere tiles before it completes its task just to get back to the last roboport it flew over to get a refill before coming back to finish its task.

[ssilk]

What came into my mind is this: the position of each robot seems to be updated each tick. Which is great (because Factorio seems to do this for 10000 robots per tick without much hassle), but indeed: most times we can absolutely predict where a robot should be at a given time. This is only interrupted by:

- robot upgrade (moving faster)
- new orders when they have no order
- target is moving
- death
- and some more obscure things I don’t know yet.

For all other cases, the robots position needs not to be calculated each tick, because it’s a straight line from source to destination (or to the point when fuel gets low). I would say 99% of all time the robots do nothing else.

That doesn’t mean we can do robot-routing. That’s a completely different task. Why? Like the interruptions-list from above there are interruptions for a robot-route. Like
- a new roboport goes online
- a roboport has no power anymore or is removed/destroyed
- one robotic network is split into two
- and vice versa two networks are joined together to one
- and more things I forgot.

Calculating a route is much, much more costly, than calculating a direction. And as seen above we need from that route only the first part, because when recharging, the plan changes completely, because we cannot predict where the robot will recharge (the chance, that the plan works as predicted is very low).

To sum that up:
- spares calculating position each tick (position depends on starting point, speed vector and time)
- needs calculating of route before starting
- needs to be calculated for every bot extra
- but route can be cached (but cache needs to be invalidated when network changes)
- in any case you need the old algorithm, e.g. for following a vehicle.

In my eyes: a very big and deep change, because it would mean to rewrite the whole robotic code, so that it can handle these two cases (moving each tick vs. pre-calculated routing).

A better idea?

Yeah, perhaps. What if the player can provide “btn-routes”? (Better than nothing routes).

Let’s say we have the roboport A from above. What if we could say: if the target is not within the reach of this roboport, the only way - the next target - you can go is to that roboport? We can have several destination roboports and the robot will choose that, which is nearest into his direction.

Simple calculations: is the robot within an area of a roboport which has routes? Yes? Take this roboport as temporary target and move to that roboport. Temporary target is resolved, when the robot needs to refuel within the area of target roboport or reached the roboport for refuel.

I think that would solve a lot of problems (and introduce nice new ones ).

[Moosfet]

I think that no matter how much we think our solutions are "simpler" than what's currently implemented, and how we think it should be lighter computationally wise, in reality, what we suggest always add overhead when compared to what's ingame now.

IDK about that, because how I'm imagining the bots work now is pretty simple, and what I'm suggesting isn't really adding any new functionality, it's just the same functionality performed in a different order. To say that it's going to require more computation is like telling me that you can't do your dishes now instead of tomorrow because doing them now is more work. It doesn't matter what schedule you use, you're washing the same number of dishes: Exactly the number that you dirty. In the same way, it doesn't matter if Factorio figures out which roboport to divert a bot to at the start of its journey or when it reaches 20% charge. Either way it's performing the same amount of calculations to divert the same number of bots.

Calculating a route is much, much more costly, than calculating a direction.

The game already calculates a route in the form of "take the route that is straight towards the destination." It takes almost no time for the game to calculate this route. What you're thinking of, that is much more costly, is path-finding. I'm not proposing path-finding.

And as seen above we need from that route only the first part

...which is why I'm suggesting only calculating the first part.

because we cannot predict where the robot will recharge (the chance, that the plan works as predicted is very low).

Why would you say it's low? Whatever roboports exist when the bot departs a roboport are the roboports that are most likely to exist 30 seconds later when the bot needs to recharge. ...and if they're not? What does the game do now and why can't it continue to do what it does now with my proposal?

But there are cases where it'd need to be done multiple times per recharge (see my third question).

The one I said you'd have to elaborate on if you're talking about something that doesn't occur in the game now but would with my proposal? That wasn't your third question but everything I can find that looks like a third to me seems irrelevant, so IDK what else you could be referring to.

Eliminating the need to touch each bot's position every tick would have been great.

Well, that was just me imagining that Factorio's bot calculations were even less than they actually are. It's not an enormous calculation to update the position though.

Code: Select all

dx = target.x - bot.x;
dy = target.y - bot.y;
d = sqrtf(dx * dx + dy * dy);
mx = how_far_a_bot_can_go_per_game_tick * dx / d;
my = how_far_a_bot_can_go_per_game_tick * dy / d;

For static targets you can just add the same (mx, my) to the bots position each game tick, and so you can avoid that costly sqrtf() by caching the previous (mx, my) and re-using it if the target hasn't moved. So updating the position is just two additions. Even that sqrtf() isn't the biggest deal though, evidence of that being that the game goes ahead and does it for each bot flying towards a player each game tick.

(I doubt less flying time in a hole containing network will be seen worthwhile.)

Well, I doubt it would be a noticible improvement, as it's just a tiny piece of what Factorio does, but since everyone is concerned about UPS, I think it's worth pointing out that this idea would probably be a break-even change at worst.

Compare the above code, which has to be executed every tick as the bot targets a moving player, to the following code, which has to be executed only once when the bot leaves a roboport:

Code: Select all

dx = target.x - bot.x;
dy = target.y - bot.y;
d = sqrtf(dx * dx + dy * dy);
max_d = how_far_a_bot_can_go_per_charge_unit * bot.current_charge_level;
if (d > max_d) {
	// Employ the same nearest-roboport algorithm that the game already will 
	// use when the bot inevitably runs out of charge, to find a roboport for it to 
	// divert to now, instead of waiting and finding the roboport to divert to later.
} else {
	// proceed as the game currently does
};

The only difference between that and what the game currently does is one line that performs one multiplication, to determine how far the bot can go on its current charge level, and this only needs to happen when the bot leaves the roboport. Aside from that one addition, it just re-arranges what the game already does, which is like taking out your trash today instead of doing it tomorrow. Either way, you're still taking the same amount of trash to the curb every year, and so the only effect of doing it sooner is that you don't have to smell your stinky garbage, or in the case of Factorio, you don't have to watch the bots do stupid things.

So then compare the complexity of that one multiplication to the complexity of adding (mx, my) to the bot's position each game tick that it's in the air. How many additions do you have to do before you're up to the time it takes to perform a multiplication? At some point you're there. Doing this will get the bots to take better paths, which will mean they're in the air less, and so fewer of those additions have to be done before they're back in a roboport and nothing more than a variable that is now set to 37 instead of 36. That's a savings in computation and quite possibly can result in less overall computation than not performing that multiplication and having the bot spend more time flying around instead.

Indeed, another way this could save UPS is in the case of moving targets. Say you walk into your robot area and so now there's a thousand bots heading straight towards you, but you're at the extreme edge, so it's going to take them minutes to get to you. In the meantime, they're constantly tracking your position and changing their direction each tick, which involves that sqrtf() calculation. If instead they had all realized that they can't reach you and need to recharge somewhere along the way, they'd all be heading towards a non-moving recharge point instead, and so your movements wouldn't matter and they could continue to re-use the same (mx, my) to move closer to their recharge point each game tick, thus avoiding that sqrtf() for most of their journey. (...and before someone says "but what if you move closer, they'll ignore you rather than change their mind about recharging and come to you instead" let me point out that the bots already ignore you when they've decided to recharge and won't come to you even if you move in front of their path, so how about we take the win of them no longer taking zig-zag paths around lakes and just accept that the solution to that problem doesn't solve every problem?)

I'm not saying this would be noticeably better UPS, I'm just saying that it won't be worse, because I know people like to shoot down ideas for performance reasons. ...which again is why I'm not suggesting a complete overhaul of how bots work, I'm just suggesting one very minor tweak to what they already do. I'm talking about the low-hanging fruit here. The fact that there's fruit higher on the tree that we can't reach is irrelevant.

[Nidan]

because we cannot predict where the robot will recharge (the chance, that the plan works as predicted is very low).

Why would you say it's low? Whatever roboports exist when the bot departs a roboport are the roboports that are most likely to exist 30 seconds later when the bot needs to recharge. ...and if they're not? What does the game do now and why can't it continue to do what it does now with my proposal?

(Inner quote is from ssilk, but it ties into what I'm trying to say.) It can change. While the expectation is for the situation to be mostly static, the earlier the recharge roboport is picked, the more bots are going to be affected if the situation changes.

(An indication that you now quote a different post would have been nice.)

But there are cases where it'd need to be done multiple times per recharge (see my third question).

The one I said you'd have to elaborate on if you're talking about something that doesn't occur in the game now but would with my proposal? That wasn't your third question but everything I can find that looks like a third to me seems irrelevant, so IDK what else you could be referring to.

With "third question" I meant this one:

How are the bots going to handle better roboports appearing or their current recharge port disappearing? Or a tech increasing bot speed? (Is decreasing possible?)

In essence the same already mentioned above, there are events for which a bot's target needs to be recalculated. whereas factorio's current bot update loop would handle them implicitly, or, in case of recharge roboport destruction, has a smaller window in which it is affected.

I'm trying to factor in the devs past reactions to suggestions that could impact performance negatively, even if only slightly. That's why I said

Eliminating the need to touch each bot's position every tick would have been great.

As that'd mean no CPU and, more importantly, no memory bandwidth used to update bots. These gains would easily pay for any potential recalculation due to the reasons mentioned above.
On the contrary,

(I doubt less flying time in a hole containing network will be seen worthwhile.)

Well, I doubt it would be a noticible improvement, as it's just a tiny piece of what Factorio does, but since everyone is concerned about UPS, I think it's worth pointing out that this idea would probably be a break-even change at worst.

[...]

I'm not saying this would be noticeably better UPS, I'm just saying that it won't be worse, because I know people like to shoot down ideas for performance reasons. ...which again is why I'm not suggesting a complete overhaul of how bots work, I'm just suggesting one very minor tweak to what they already do. I'm talking about the low-hanging fruit here. The fact that there's fruit higher on the tree that we can't reach is irrelevant.

Even you say that the UPS gain, if any, would be negligible. So the benefit that remains is mostly visual. As I said above, the devs have been mostly averse to potential performance losses in the past.
If they had infinite time, sure, try it and see how it actually affects performance. But as things stand, my guess is they decide to spend their time elsewhere. (I mean, if I had infinite time, there are many things I'd improve in my company's code, but sadly I don't.)

(This topic isn't exactly new, see e.g. this thread from 2016 in "Not a bug": /viewtopic.php?t=37124, where the situation is even worse. The bots fail to cross the hole and get stuck in an infinite loop instead.)

[ssilk]

(This topic isn't exactly new, see e.g. this thread from 2016 in "Not a bug": /viewtopic.php?t=37124, where the situation is even worse. The bots fail to cross the hole and get stuck in an infinite loop instead.)

This one is in my opinion more or less a bug. Because in my last game I had this, but not only with lakes, I just had a bigger area, which had no roboport.
IMHO: If a bot on his travel loads the second time on the same roboport, then this robot should aim to a random roboport in reach instead to the target. Something like this....

The game already calculates a route in the form of "take the route that is straight towards the destination." It takes almost no time for the game to calculate this route. What you're thinking of, that is much more costly, is path-finding. I'm not proposing path-finding.

I thought: Yes, indeed, it should not matter, if I calculate the path to make the bots more efficient. Because the amount of extra calculation is later spared with the number of bots doing the same transport. Or in other words: There might be not so much difference between calculating the best path from A to B, because the bots will spare time to transport the item. They can go earlier to sleep and you spare eventually much more CPU-power, if you make their pathfining more efficient.

BUT!

The problem with making bots too efficient is, that then belts might not be used so much. And that depends the core of the game! That's goes highly to game-play-value and basic gameplay. Yes, one could argue, more efficent bots = more fun. But at that point me as developer would also handle quite conservative because this can easily break the basic gameplay.

[FuryoftheStars]

How are enemies going to find bots to shoot at?
[…]
How are the bots going to handle better roboports appearing or their current recharge port disappearing? Or a tech increasing bot speed? (Is decreasing possible?)

I feel like both of these questions have no bearing on the proposal because the answer is simply “the same way they do now”. There’s nothing really about this proposal that would change these.

The way I understood the suggestion was that the bots current position should no longer be explicitly stored, but rather calculated on demand when needed. For the second question one could argue to just bite the bullet of having to (re)do extra work since these happen only once in a while (, but see my reply after the first quoted bit). But for biter targeting, area searches are one of the more expensive problems, so multiplying the area needed to search will kill performance.

The way I understood the suggestion was that the OP believed that was already how the bots operated, but at no point did it seem like they were advocating that it should be changed/made this way, and isn't the core of the OP's suggestion, anyway.

(This topic isn't exactly new, see e.g. this thread from 2016 in "Not a bug": /viewtopic.php?t=37124, where the situation is even worse. The bots fail to cross the hole and get stuck in an infinite loop instead.)

This issue would actually be solved by the OP's suggestion. Edit: Actually, this may be wrong in some specific cases.

The problem with making bots too efficient is, that then belts might not be used so much. And that depends the core of the game! That's goes highly to game-play-value and basic gameplay. Yes, one could argue, more efficent bots = more fun. But at that point me as developer would also handle quite conservative because this can easily break the basic gameplay.

Err, forgive me, but why should we leave things in (what can be considered by some) a broken state just because fixing it would potentially make it better than something else? I mean, if that's the case (that it makes bots better than belts), then aren't there other ways of balancing them, such as adjusting bot speed or battery capacity, charge rate, etc?

[mrvn]

What came into my mind is this: the position of each robot seems to be updated each tick. Which is great (because Factorio seems to do this for 10000 robots per tick without much hassle), but indeed: most times we can absolutely predict where a robot should be at a given time. This is only interrupted by:

- robot upgrade (moving faster)
- new orders when they have no order
- target is moving
- death
- and some more obscure things I don’t know yet.

For all other cases, the robots position needs not to be calculated each tick, because it’s a straight line from source to destination (or to the point when fuel gets low). I would say 99% of all time the robots do nothing else.

That doesn’t mean we can do robot-routing. That’s a completely different task. Why? Like the interruptions-list from above there are interruptions for a robot-route. Like
- a new roboport goes online
- a roboport has no power anymore or is removed/destroyed
- one robotic network is split into two
- and vice versa two networks are joined together to one
- and more things I forgot.

Calculating a route is much, much more costly, than calculating a direction. And as seen above we need from that route only the first part, because when recharging, the plan changes completely, because we cannot predict where the robot will recharge (the chance, that the plan works as predicted is very low).

To sum that up:
- spares calculating position each tick (position depends on starting point, speed vector and time)
- needs calculating of route before starting
- needs to be calculated for every bot extra
- but route can be cached (but cache needs to be invalidated when network changes)
- in any case you need the old algorithm, e.g. for following a vehicle.

In my eyes: a very big and deep change, because it would mean to rewrite the whole robotic code, so that it can handle these two cases (moving each tick vs. pre-calculated routing).

A better idea?

Yeah, perhaps. What if the player can provide “btn-routes”? (Better than nothing routes).

Let’s say we have the roboport A from above. What if we could say: if the target is not within the reach of this roboport, the only way - the next target - you can go is to that roboport? We can have several destination roboports and the robot will choose that, which is nearest into his direction.

Simple calculations: is the robot within an area of a roboport which has routes? Yes? Take this roboport as temporary target and move to that roboport. Temporary target is resolved, when the robot needs to refuel within the area of target roboport or reached the roboport for refuel.

I think that would solve a lot of problems (and introduce nice new ones ).

I think you are still not getting the proposal at all.

Let me try to rephrase (a slightly altered because it uses the original 20% charge point) the algorithm reusing functionality already in the game where possible:

1) When a target it set for the robot calculate distance to the target and distance the bot can travel
2) if "can travel" < "distance to target" then compute point where bot hits low charge (simple multiplication of direction * distance)
3) pretend the robot is at that point and has low charge and trigger the "find recharging port" function
4) set the robot to "going for recharge" mode with the charging port calculated in 3

1+2 are trivial math and done only once per target that is assigned to a bot. It will eat a few CPU cycles, probably less than 100.
3+4 is code that the game already has and WILL execute once the bot reaches 20% charge.

Unless the bot is destroyed or otherwise diverted from the target before it reaches 20% charge this only adds an overhead of <100 CPU cycles. On the other hand it will make the bot travel straight to the next recharge port instead of going zig-zag. The shorter flight time for the bot surely will save more than 100 CPU cycles because it saves on checking if aliens can attack the bot or if the bot flies into fire or other things you have to check every tick for bots. The algorithm also doesn't ask for anything the bot can't already do. It already has the capability to go to recharge and then pick up it's original mission again. All that changes is that the bot gets diverted earlier

Nothing else should change for bots. The current behavior when the target is removed, a roboport added or removed, logistic networks cut or joined. All of that remains AS IS. There is no route planing for the bot that would cost time. All this proposal needs is to move the "where do I go to recharge" calculations to a bit earlier in time, when the bot leaves.

And yes, if a roboport is added while the robot is in flight that port might be better for recharging but the new algorithm will have already choosen to recharged at some old roboport. This might result in a worse flight path. But over the time of the game flight paths like shown in the OP happen thousands to millions of times while a new roboport getting added that would make a better route is a blip in time. I think everybody would except that caveat.

It doesn't even change anything for moving targets. If the target is out of reach initially then the bots goes to recharge somewhere closer. If it is in reach initially then it tries to catch up. This will cause some changes in the bot behavior and when driving towards the bot the new code might send it to recharge while the player could have closed the distance before the bot runs out of charge. This will be balanced by all the time the bot fails to catch up due to going zig-zag. Or the reverse, when driving away the bot tries to catch up and runs out of charge reverting to the old zig-zag while going straight for recharge would be smarter. The new algorithm isn't perfect and isn't route planing. It just makes the really stupid cases less stupid.

The new algorithm can also detect when a robot goes into a loop, returning to the same roboport to recharge over and over (port I'm leaving == port I'm going to recharge next). This could show an alert with the map positions of the robort and destination telling the user the bot is stuck in a loop.

[ssilk]

I think you are still not getting the proposal at all.

I think I understood it, but we speak from different things. I was completely sidetracked from the idea, that robots are calculated each tick and not once at the start of their travel.

In other words: You can calculate the position of the bots either by adding a vector each tick to their X- and Y-Positions (as it seems to be?), OR you can calculate their position if you have the starting point, the vector and time (ticks) since start. Then you only need to wait for the listed interruptions.
Indeed I really don't know how the bots are calculated.

And why I thought this is relevant to this topic is, because if Factorio uses only the first method (step-by-step), then it could spare a lot of CPU to do such calculation as proposed. I know it's a stupid thought and I'm sorry for sidetracking.


BTW: your algorithm misses one point:
0) Calculate how long the bot can travel with the amount of charge

And what you also forget is, if you need to calculate distances there is always higher precision math involved. Takes a lot of cycles, compared to simpler integer math currently needed.

[mrvn]

I think you are still not getting the proposal at all.

I think I understood it, but we speak from different things. I was completely sidetracked from the idea, that robots are calculated each tick and not once at the start of their travel.

In other words: You can calculate the position of the bots either by adding a vector each tick to their X- and Y-Positions (as it seems to be?), OR you can calculate their position if you have the starting point, the vector and time (ticks) since start. Then you only need to wait for the listed interruptions.
Indeed I really don't know how the bots are calculated.

And why I thought this is relevant to this topic is, because if Factorio uses only the first method (step-by-step), then it could spare a lot of CPU to do such calculation as proposed. I know it's a stupid thought and I'm sorry for sidetracking.


BTW: your algorithm misses one point:
0) Calculate how long the bot can travel with the amount of charge

And what you also forget is, if you need to calculate distances there is always higher precision math involved. Takes a lot of cycles, compared to simpler integer math currently needed.

That's part of strep 1: "distance the bot can travel".

As for integer math being simpler: X86 has a blindingly fast floating point performance. Used to be people did integer math via the FPU because it was faster. Nowadays you do SIMD which is even faster but I don't think that applies to bots.

The math we are talking about is: (speed * charge)^2 < (x1 - x2)^2 + (y1 - y2)^2

That takes like 10 CPU cycles on modern hardware assuming the bots data and the target coordinates are in cache or registers. Some extra delay if the branch predictor is wrong on the comparison. That's the extra cost for this feature every bot must pay once per target. If it doesn't have enough charge then some more math is involved to figure out the point where it runs out of charge and then find the nearest recharging port. The later will easily be 1000 - 10000 times slower because it will involve looking up roboports and lots of ram access to get their coordinates. But again, that is all computations you are going to do anyway when the bot runs out of charge.

PS: coordinates are int and speed and charge doubles, right?

[ichVII]

There is one problem I see with this suggestion. Say you have a poorly planned logistic network with a huge hole inside. Then, the bot which want to do a job at the other side of the hole leaves a roboport, calculates its recharging spot, realizes the closest recharge point is the roboport it just departed, plans to go there and repeats this calculation each tick.

Currently, you at least see that the robots are trying to cross the hole and then slowly return home. With the suggestion, they would always be stuck at a roboport and it would be way harder to spot the issue. One could of course fix this by including a check if the path to the recharge port is way to short and give a warning like the "bots missing materials" or "buildings missing bots" messages we currently have.

[FuryoftheStars]

There is one problem I see with this suggestion. Say you have a poorly planned logistic network with a huge hole inside. Then, the bot which want to do a job at the other side of the hole leaves a roboport, calculates its recharging spot, realizes the closest recharge point is the roboport it just departed, plans to go there and repeats this calculation each tick.

Currently, you at least see that the robots are trying to cross the hole and then slowly return home. With the suggestion, they would always be stuck at a roboport and it would be way harder to spot the issue. One could of course fix this by including a check if the path to the recharge port is way to short and give a warning like the "bots missing materials" or "buildings missing bots" messages we currently have.

Hmm, yeah, I suppose this would still be an issue if the roboport it's leaving from is literally the closest one to the job site. So what I said earlier:

(This topic isn't exactly new, see e.g. this thread from 2016 in "Not a bug": /viewtopic.php?t=37124, where the situation is even worse. The bots fail to cross the hole and get stuck in an infinite loop instead.)

This issue would actually be solved by the OP's suggestion.

Is actually wrong.

That said, it would be a lot easier (programmatically) to detect that situation with the OP's suggestion vs current: if the bot leaving immediately establishes the point it left from as the closest, then you know that will always happen (unless a new one is placed), and you can then generate an alert, and/or even flag that bot as unsuitable for the job and find another.

[Moosfet]

Let me try to rephrase (a slightly altered because it uses the original 20% charge point) the algorithm reusing functionality already in the game where possible:

1) When a target it set for the robot calculate distance to the target and distance the bot can travel
2) if "can travel" < "distance to target" then compute point where bot hits low charge (simple multiplication of direction * distance)
3) pretend the robot is at that point and has low charge and trigger the "find recharging port" function
4) set the robot to "going for recharge" mode with the charging port calculated in 3

1+2 are trivial math and done only once per target that is assigned to a bot. It will eat a few CPU cycles, probably less than 100.
3+4 is code that the game already has and WILL execute once the bot reaches 20% charge.

I like this better than my proposal actually. It's more obviously just a re-arrangement of what the game already does.

After thinking about the impact of eliminating the 20% reserve, I think it actually does come at a significant cost. Presently that 20% reserve allows the bot to fly from its destination (after it's completed its task) to the nearest roboport. If the 20% reserve is removed, then that return-to-nearest-roboport distance also has to be calculated, which, the distance isn't a big calculation, it's the second nearest-roboport search that it requires which would have a performance impact. IDK how much since it depends on how it's implemented but it would obviously be a much harder sell to the performance-weary, so I'm not interested in arguing for it. You'd need a ruler and a calculator to know the difference between a bot traveling 80% of how far it could travel, and 100%, so visually there would be essentially no difference anyway.

The other difference between your description and my proposal is that, in step 3, I proposed examining all roboports near the robot's current position (which I assume the game doesn't search all roboports, but instead has lists of roboports in regions of the map, so it only has to search ones in the area) and finding one that is both in range of the robot but also closest to the destination. This is one additional distance calculation per roboport, which I doubt is significant enough to matter, but the performance-weary may not agree. So this too would be a difficult sell, and again, I don't think there would visually be much difference between the more-optimal behavior of my proposal and the more obviously-no-additional-performance-cost behavior of yours.

So, like I said, I'm interested in the low-hanging fruit, and your fruit is lower-hanging and visually indistinguishable.

[mrvn]

There are 3 more factors to consider (why I think the 20% is better):

1) The roboport might be busy and then the bot hovers in place waiting for its turn. If it runs out of charge before it's its turn then flying those last few meters to the charging port take longer and slows down charging for everyone. Just a little bit safety margin in case the bot network is nearly at it's limit.
2) In your case you examine all roboports in a radius of 100% fuel from the start. Half of that region will be further from the target than the source.
3) In my case the bot searches in a radius of 80% fuel from the point where it is down to 20%. Note that this might find a roboport that is 160% fuel from the source. So this will sometimes pick a roboport to recharge that is out of reach and get there very slowly. Just like it does now. Hopefully the roboport it finds is nearer or at an angle so the bot cuts the corner and has a shorter distance to travel. But this will preserve cases where bots can currently reach the target very slowly by crossing a void.

As for how bots find the closes roboport I have no idea. I don't think the devs have revealed that. But I would have a list of near roboports cached in each chunk (or a table of lists indexed by the logistic network ID) so the bot can quickly check which of those are in its own logistic network and which of those has the least number of bots waiting to charge.

[FuryoftheStars]

3) In my case the bot searches in a radius of 80% fuel from the point where it is down to 20%. Note that this might find a roboport that is 160% fuel from the source. So this will sometimes pick a roboport to recharge that is out of reach and get there very slowly. Just like it does now. Hopefully the roboport it finds is nearer or at an angle so the bot cuts the corner and has a shorter distance to travel. But this will preserve cases where bots can currently reach the target very slowly by crossing a void.

Question: would it not be better to search in a radius of 20% fuel from the 20% point?