Friday Facts #374 - Smarter robots

[FuryoftheStars]

...

Wouldn't it overall be easier to define the failure mode earlier like at 25% charge? [...] Rather than only triggering at 0% charge and slowly flying to the nearest.

I don't believe low battery trigger is 0% currently. I think it's 10% or something like that.

[Barret]

The game is already so polished and, frankly, has been for years, yet the devs keep finding things to improve even further. I commend their endurance and dedication! Recently, people were memeing about BG3 raising the bar in terms of quality, but in my book it is Factorio that had set the standard in a variety of aspects years ago, be it gameplay, aesthetics, UX, QOL, you name it. I can think of couple of games that are on par in one way or another, but none come close to delivering such a well-rounded, coherent and polished experience.

Thank you very much for resuming the FFF blog posts! They certainly sweeten the waiting time until the expansion releases.

[Nidan]

The operations to find whether the charge distance is required only need:
The bot's location.
The target's location.
The bot's charge level.
The bot's energy usage per second (/frame).
The bot's energy usage per tile travelled.
The bot's speed (per second/frame?).
(I'm not sure that it doesn't already have energy per second, per meter, and speed combined into the net energy per second while moving, but it must calculate that to move the bot every frame, so we could just assume they're already combined).
It then takes:

Code: Select all

tileRange = charge / ((energyPerFrame)/(tilePerFrame)+energyPerTile)
tileRangeSquared = tileRange * tileRange
distanceToTravelSquared = (botLocation.x - targetLocation.x)^2 + (botLocation.y - targetLocation.y)^2

Then compare "distanceToTravelSquared" with "tileRangeSquared".
That's 2 divisions, 3 multplications, 4 additions/subtraction, no extra conditionals.

If you want to optimise it (depending on system and how well optimised reciprocal is), and were doing this alongside the normal movement code, you could do the following:

Code: Select all

deltaX = botLocation.x - targetLocation.x
deltaY = botLocation.y - targetLocation.y

(both of these would be needed in normal movement code anyway, presuming the robot doesn't then recharge, so this has near-zero cost)

Code: Select all

speedInv = 1/tilePerFrame
energyPerTileTotalInv = 1/(energyPerFrame*speedInv+energyPerTile)
tileRange = charge * energyPerTileTotalInv
tileRangeSquared = tileRange * tileRange
distanceToTravelSquared = deltaX * deltaX + deltaY * deltaY

Which is now 2 non-shared additions, 2 reciprocals (relatively quick, though I can't find any direct sources for cycle counts), and 5 multiplications.
I think my estimate was close enough, particularly since I'm working off the two types of energy usage individually, even though the game may cache a more useful form, which would either save a multiplication and an addition, or just an addition.

You're missing one piece of extra work here: You also need to calculate the position where the bot would enter recharging mode, i.e. botLocation + tileRange towards the target.

Extra calculations needed

Also, we can do the recharge test a bit cheaper: I count 4 multiplications and 4 additions/subtractions/comparisons, all using values also needed for normal bot movement:

Code: Select all

distance(target_current_position, bot_current_position) > bot_current_energy / bot_total_energy_per_tile
<=> sqrt((target_current_x - bot_current_x)^2 + (target_current_y - bot_current_y)^2) > bot_current_energy / bot_total_energy_per_tile
<=> (target_current_x - bot_current_x)^2 + (target_current_y - bot_current_y)^2 > (bot_current_energy / bot_total_energy_per_tile)^2
<=> ((target_current_x - bot_current_x)^2 + (target_current_y - bot_current_y)^2) * bot_total_energy_per_tile^2 > bot_current_energy^2

If we don't treat bot_total_energy_per_tile as given, we need an additional addition and division to calculate it:

Code: Select all

bot_total_energy_per_tile (at max movement)
= (bot_tiles_per_tick * bot_energy_per_tile + bot_energy_per_tick) / bot_tiles_per_tick
= bot_energy_per_tile + bot_energy_per_tick / bot_tiles_per_tick

But that is just the test whether the bot needs to recharge en route. For figuring out from which position the recharge code would normally trigger, i.e. the position we start searching a roboport from, there's a choice between a square root or some trigonometry. Afaik factorio has precalculated tables for the latter due to multiplayer, so the most expensive operations should be two divisions.
Using trigonometry:

Code: Select all

bot_recharge_position
= bot_current_position + norm(target_current_position - bot_current_position) * bot_current_energy / bot_total_energy_per_tile
= bot_current_position + [cos|sin](atan2(target_current_y - bot_current_y, target_current_x - bot_current_x)) * bot_current_energy / bot_total_energy_per_tile

Using square root:

Code: Select all

bot_recharge_position
= bot_current_position + norm(target_current_position - bot_current_position) * bot_current_energy / bot_total_energy_per_tile
= bot_current_position + (target_current_position - bot_current_position) / distance(target_current_position, bot_current_position) * bot_current_energy / bot_total_energy_per_tile
= bot_current_position + (target_current_position - bot_current_position) / sqrt((target_current_x - bot_current_x)^2 + (target_current_y - bot_current_y)^2) * bot_current_energy / bot_total_energy_per_tile

That last line might look long, but most subexpressions are shared with the recharge test above.

For bot expenses I'm using viewtopic.php?f=204&t=108144
and for cycle counts I'm using http://www.phys.ufl.edu/~coldwell/Multi ... ntmult.htm

Those instruction latencies seem rather large to the numbers I'm used to (throughput of ~1 cycle per integer multiply), so I went searching and found https://www.agner.org/optimize/instruction_tables.pdf. Taking the table for Zen2's xmm instructions (since that's my current CPU), pages 111/112 lists 3 cycles latency for addss/subss/mulss, 10 for divss and 16 for sqrtss. (The latter two are certainly lower than what I've been expecting.)

While these extra calculations might be no issue overall, this discussion ignores one issue: The target might move. In vanilla that's only players and spiders, but once mods enter the picture anything could suddenly teleport around. Previously I would've argued that is a significant problem, but with the addition of the bot task queue from this FFF there must now be logic to handle that. (Although that logic may be to ignore the issue and accept suboptimal planning, in which case there's an argument for potentially flying in the wrong direction until the next recharge being acceptable as well.)


@Oxyd/Devs: For the robot work queue, do you have a rescheduling strategy in case the current target moves, but stays within logistics range?

[zbee]

So hyped for the expansion, and especially for this.
I will say, I think it's rather unfortunate we couldn't get this now though.

[BicycleEater]

...

Wouldn't it overall be easier to define the failure mode earlier like at 25% charge? Then robots caught over no coverage would pick a port, still towards the destination and maybe even at the destination, and fly quickly towards it with charge for at least most of the way. Rather than only triggering at 0% charge and slowly flying to the nearest. You could even have an extra check so it only triggers that failure at 25% when the robot is currently out of coverage. But I feel like this doesn't noticeable impact on in coverage bots as they would just path basically as normal anyways because the new charging algorithm puts them at or close to their destination as is.

Define it as a "reserve energy" variable that we can set, in or out of network. This would also help certain mods that provide logistics coverage without charging ports, as they face similar issues to the bots over lakes problem.

Well, that might help, though I'm not sure that having a different reserve value in the two cases would help. The thing I'm proposing is to fly directly towards the charging port, rather than flying towards the target then diverting to charge. Surely that's at least more elegant, avoids cases where the bot is almost at its destination before turning around (which is not fixed by the changes by the devs, unless they've done more things without telling anyone, as in that case there is no charging port closer than the bot), and avoids at least some unnecessary crawl time. I posted this before, but my proposal is guaranteed to improve travel times, by at least a bit.

[BicycleEater]

...

You're missing one piece of extra work here: You also need to calculate the position where the bot would enter recharging mode, i.e. botLocation + tileRange towards the target.

No, that's not a major factor, as that only needs to be done when the bot is calculated to need recharging, which isn't a factor on the kind of short range hops people are talking about. That calculation only needs doing in the minority case of having to recharge, in which case the bot also needs to search for a charging port,

Also, we can do the recharge test a bit cheaper: I count 4 multiplications and 4 additions/subtractions/comparisons, all using values also needed for normal bot movement:

Code: Select all

distance(target_current_position, bot_current_position) > bot_current_energy / bot_total_energy_per_tile
<=> sqrt((target_current_x - bot_current_x)^2 + (target_current_y - bot_current_y)^2) > bot_current_energy / bot_total_energy_per_tile
<=> (target_current_x - bot_current_x)^2 + (target_current_y - bot_current_y)^2 > (bot_current_energy / bot_total_energy_per_tile)^2
<=> ((target_current_x - bot_current_x)^2 + (target_current_y - bot_current_y)^2) * bot_total_energy_per_tile^2 > bot_current_energy^2

If we don't treat bot_total_energy_per_tile as given, we need an additional addition and division to calculate it:

Code: Select all

bot_total_energy_per_tile (at max movement)
= (bot_tiles_per_tick * bot_energy_per_tile + bot_energy_per_tick) / bot_tiles_per_tick
= bot_energy_per_tile + bot_energy_per_tick / bot_tiles_per_tick

Yeah, I wasn't taking bot_total_energy_per_tile as a given, since the movement code can treat bot_energy_per_tile and bot_energy_per_tick separately. Hence I was factoring in the calculation. I have no knowledge of the codebase, and wanted to be conservative.

But that is just the test whether the bot needs to recharge en route. For figuring out from which position the recharge code would normally trigger, i.e. the position we start searching a roboport from, there's a choice between a square root or some trigonometry. Afaik factorio has precalculated tables for the latter due to multiplayer, so the most expensive operations should be two divisions.
Using trigonometry:
...

Yeah, but again, this is only done when the bot needs to recharge en-route, which is a relatively rare case, and I'd expect the other factors to dominate - particularly since a bot can do many many short hops before needing a recharge, so I figured the take off check would dominate.

...

Those instruction latencies seem rather large to the numbers I'm used to (throughput of ~1 cycle per integer multiply), so I went searching and found https://www.agner.org/optimize/instruction_tables.pdf. Taking the table for Zen2's xmm instructions (since that's my current CPU), pages 111/112 lists 3 cycles latency for addss/subss/mulss, 10 for divss and 16 for sqrtss. (The latter two are certainly lower than what I've been expecting.)

Oh, in that case, it's fine anyway, my numbers go waaay down. I just kinda picked at random, but yeah, it did seem like a lot. Anyway, that gives me numbers like 35 cycles, which is like 10ns. In which case performance impact is negligable in all cases.

While these extra calculations might be no issue overall, this discussion ignores one issue: The target might move. In vanilla that's only players and spiders, but once mods enter the picture anything could suddenly teleport around. Previously I would've argued that is a significant problem, but with the addition of the bot task queue from this FFF there must now be logic to handle that. (Although that logic may be to ignore the issue and accept suboptimal planning, in which case there's an argument for potentially flying in the wrong direction until the next recharge being acceptable as well.)

Yeah, this is always a point, though I don't think my proposed changes impact it too much in vanilla. The bot will make progress towards the old location of the target, and there may be some cases where it e.g. flies past it to recharge behind it, I think the current system doesn't handle it that well either, and I don't know that the proposed change is meaningfully worse.
I'd be happy to see some kind of optimised strategy for moving targets, but for me personally, it's the minority case. Also, currently it's dealt with very poorly anyway sometimes, with bots getting kinda lost anyway. If it is really an issue, then the code for the proposed change could be easily be turned off for movable targets by just acting as if they're in range, which should result in the current behaviour anyway.

[Nidan]

You're missing one piece of extra work here: You also need to calculate the position where the bot would enter recharging mode, i.e. botLocation + tileRange towards the target.

No, that's not a major factor, as that only needs to be done when the bot is calculated to need recharging, which isn't a factor on the kind of short range hops people are talking about. That calculation only needs doing in the minority case of having to recharge, in which case the bot also needs to search for a charging port,
[...]

But that is just the test whether the bot needs to recharge en route.
[...]

Yeah, but again, this is only done when the bot needs to recharge en-route, which is a relatively rare case, and I'd expect the other factors to dominate - particularly since a bot can do many many short hops before needing a recharge, so I figured the take off check would dominate.

I'm not debating the frequency - I have no reliable data there. I'm mentioning it because if, and only if, we determine that we need to recharge en route, we need to calculate the target roboport upfront, since we're planning to fly there directly. Which adds a minor bit of extra work (, which should be more than compensated by the shorter flight duration).

[BicycleEater]

...

I'm not debating the frequency - I have no reliable data there. I'm mentioning it because if, and only if, we determine that we need to recharge en route, we need to calculate the target roboport upfront, since we're planning to fly there directly. Which adds a minor bit of extra work (, which should be more than compensated by the shorter flight duration).

That's fine, it's just that I want to make it clear that it's not a performance concern, which is the only good reason I've seen given against the proposal (other than the obvious dev-time issue, which I'd accept, just I feel it is worth it).
I just want to show that the changes have negligible performance impact - or even improve performance for a given throughput.

[KaiserTom]

Well, that might help, though I'm not sure that having a different reserve value in the two cases would help. The thing I'm proposing is to fly directly towards the charging port, rather than flying towards the target then diverting to charge. Surely that's at least more elegant, avoids cases where the bot is almost at its destination before turning around (which is not fixed by the changes by the devs, unless they've done more things without telling anyone, as in that case there is no charging port closer than the bot), and avoids at least some unnecessary crawl time. I posted this before, but my proposal is guaranteed to improve travel times, by at least a bit.

As far as I can tell from reading the post and looking at the video examples they provided, most bots do attempt to go straight to the target. They do not turn around and only choose to charge at ports at least closer to their target, if not at the target. But some don't go direct because the charging logic now gets informed of bots currently in flight to charge, so it diverts them to ports that will be empty upon arrival, diverted away.

With this change, if you created an artificial "lake" using only 2 ports and a large swath of modded, coverage-only logistics towers between them, then none of the bots should return to the first tower. All bots should slow boat to the far end port even if the origin port is closer to charge.The charging logic always wants a closer port to the target.

[ShyLion]

Can we have these smarter robots in current version? Before 2.0? It should not ruin anything, i think.

[BicycleEater]

...

As far as I can tell from reading the post and looking at the video examples they provided, most bots do attempt to go straight to the target. They do not turn around and only choose to charge at ports at least closer to their target, if not at the target. But some don't go direct because the charging logic now gets informed of bots currently in flight to charge, so it diverts them to ports that will be empty upon arrival, diverted away.

With this change, if you created an artificial "lake" using only 2 ports and a large swath of modded, coverage-only logistics towers between them, then none of the bots should return to the first tower. All bots should slow boat to the far end port even if the origin port is closer to charge.The charging logic always wants a closer port to the target.

Yeah, they do always attempt to go straight to target, even if they'll have to recharge to get there. That's what I'm proposing to change - that they'll go to the charger directly, which will reduce the amount of crawling they have to do.
I'm actually very confused about what change you're talking about.
The change in the fff should avoid going back to charge, and my proposal doesn't change that change.
The difference is, if you look at demo at the bottom of the fff, you can see some bots going towards the target, then turning to recharge. Under my change, they'll know they'll have to do that, and will instead go towards the recharge point immediately, shortening their path and reducing time spent 'crawling'.
If you're just talking about the improvements the fff talks about, I agree they're great, and solve a number of serious problem cases.

[Mur]

This looks amazing and will fix a ton of issues with the bots that I have been having.

[ejg]

Will this be available in the base game as well or just the expansion?

[Necronium]

it is update for base game engine that will come with 2.0

[Kronus_Aero]

I'm in the middle of a playthrough where I have one gigantic roboport network, and I've been constantly tackling every single problem discussed in this FFF. For instance, waiting several minutes for logistics bots to fulfill my personal logistics, because many of my logi bots are a thousand tiles away after having delivered ammo to my wall artillery turrets.

Quite frankly I find this stuff more exciting than new features, keep up the good work!

[MrGrim]

The difference is that if you can guarantee the path won't ever need to change then all of the complexity can be hoisted out of the tick function and only performed during task assignment. The lack of collision and dynamic obstacles allows this. There's no need to check every tick if something got in the way. In fact, the new queueing system literally is waypoints!

It's not static, though. Any roboport at any given moment could be destroyed or deconstructed.

There's no reason this needs to be handled. Either the bot makes it to its target or it runs out of power and searches for a recharge point. The altered shape of the network can be dealt with then. The case of the change takes the target out of the range of the network is already done.

[dexteritas]

[...]

[...]

For efficient computation, it should be enough to determine the graph of connected roboports (nodes) for each type of robot. The nodes would have a connection as long as they are within the maximum range of a robot. After that, a simple routing algorithm can be used.

I wrote down my idea for intelligent robot routing in more detail and created a separate thread for it: Efficient Robot Routing in Factorio.

[j_matya]

Just out of curiosity, since now bots tend to diverge towards the target roboport:

If the robot network is a huge "U" shaped one, and the bots start flying from one end of the U towards the other end of the U, and the area between them is not charted (chunks not generated), will the bots' flying behavior generate new chunks and biters?

[tamanous]

I know that you are mainly looking forward to the new content, and that just quality of life improvements aren't the kind of things that make people buy the game and get excited for.

Nope, I'd love to get more QOL, please.

[ModernMythos]

- Also the repair mechanism for bots isn't the best: Walls get attacked, flame throwers put biters and the walls on fire, bots come in to repair / rebuild walls immediately and die in the fire or to the biters themselves. Maybe you could solve that by not assigning any construction bots to tasks in chunks that are on fire or under attack? Maybe even let players be able to turn that mechanism on or off in the roboports themselves since sometimes we want bots to fly in still to put up walls within a fighting zone to prevent a breach.

An obvious solution: make bots immune to the fire AoE DoT

Has anybody ever considered firefighter bots? They could have water barrels to spray fires down, it's just a thought. A mod to allow construction bots to carry water?