Optimize Drone Movement

Ideas, that are too old (too much things changed) or won't be implemented cause of some reasons or if there are obvious better suggestions.
Rseding91
Factorio Staff
Factorio Staff
Posts: 7976
Joined: Wed Jun 11, 2014 5:23 am

Re: Optimize Drone Movement

Post by Rseding91 » Fri Nov 23, 2018 4:29 pm

mrvn wrote:
Fri Nov 23, 2018 10:16 am
keyboardhack wrote:
Fri Feb 17, 2017 11:04 pm
Assume a base has 20.000 robots in a network, they always have something to do and don't need to recharge. If we assume an average travel time for each robot to be 4sec then 20.000 / 4 = 5000 robots need to pathfind per second.

Factorio runs at 60UPS which means that factorio would have to process 5000 / 60 = 83,3 paths for each update(1 update = 16ms). With a graph consisting of >1000 nodes it would literally be impossible to do it in < 16ms.

Everyone agrees that it would be a good idea to add pathing to robots but no one knows how to do it in a way that is just as fast as how it works right now. Simulation speed is the main reason that robots are stupid.
The game already does this. Because every time a drone flies of it "path finds" where to go. Then when it runs out of fuel it "path finds" the nearest charging station.

There is no need to path find the whole way from A to Z. The simplest improvement for drones would be to still do exactly the same thing they do now expect with foresight. When a drone leaves it calculates the distance to the target and checks available fuel. It then knows at which point of the path it runs out of fuel. But instead of waiting to reach that point calculate the nearest charging port from that point at the start and then switch the destination to that charging port directly. The amount of "path finding" work per drone remains the same just the timing changes a bit.
Robots don't path-find at all when they set out to do something. They go directly to the target. If in going directly to the target they run out of energy they then search for a roboport nearby to recharge at.

Nobody is going to be able to find a solution which is as cheap as the current implementation because you can't get cheaper than "go directly towards the target" which means adding *any* additional work is more expensive.
If you want to get ahold of me I'm almost always on IRC and Discord.

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

Re: Optimize Drone Movement

Post by mrvn » Mon Nov 26, 2018 9:46 am

Rseding91 wrote:
Fri Nov 23, 2018 4:29 pm
mrvn wrote:
Fri Nov 23, 2018 10:16 am
keyboardhack wrote:
Fri Feb 17, 2017 11:04 pm
Assume a base has 20.000 robots in a network, they always have something to do and don't need to recharge. If we assume an average travel time for each robot to be 4sec then 20.000 / 4 = 5000 robots need to pathfind per second.

Factorio runs at 60UPS which means that factorio would have to process 5000 / 60 = 83,3 paths for each update(1 update = 16ms). With a graph consisting of >1000 nodes it would literally be impossible to do it in < 16ms.

Everyone agrees that it would be a good idea to add pathing to robots but no one knows how to do it in a way that is just as fast as how it works right now. Simulation speed is the main reason that robots are stupid.
The game already does this. Because every time a drone flies of it "path finds" where to go. Then when it runs out of fuel it "path finds" the nearest charging station.

There is no need to path find the whole way from A to Z. The simplest improvement for drones would be to still do exactly the same thing they do now expect with foresight. When a drone leaves it calculates the distance to the target and checks available fuel. It then knows at which point of the path it runs out of fuel. But instead of waiting to reach that point calculate the nearest charging port from that point at the start and then switch the destination to that charging port directly. The amount of "path finding" work per drone remains the same just the timing changes a bit.
Robots don't path-find at all when they set out to do something. They go directly to the target. If in going directly to the target they run out of energy they then search for a roboport nearby to recharge at.

Nobody is going to be able to find a solution which is as cheap as the current implementation because you can't get cheaper than "go directly towards the target" which means adding *any* additional work is more expensive.
They path find, even if the path is simply "as the crow flies". And I just described an algorithm that has exactly the same cost and doesn't do any additional work. It just changes the time when it does the work a bit.

User avatar
Oktokolo
Filter Inserter
Filter Inserter
Posts: 399
Joined: Wed Jul 12, 2017 5:45 pm

Re: Optimize Drone Movement

Post by Oktokolo » Mon Nov 26, 2018 2:35 pm

mrvn wrote:
Mon Nov 26, 2018 9:46 am
Rseding91 wrote:
Fri Nov 23, 2018 4:29 pm
Robots don't path-find at all when they set out to do something. They go directly to the target. If in going directly to the target they run out of energy they then search for a roboport nearby to recharge at.

Nobody is going to be able to find a solution which is as cheap as the current implementation because you can't get cheaper than "go directly towards the target" which means adding *any* additional work is more expensive.
They path find, even if the path is simply "as the crow flies". And I just described an algorithm that has exactly the same cost and doesn't do any additional work. It just changes the time when it does the work a bit.
The vanilla algorithm has a slightly lower cost in the case where the bot can reach its target without having to refuel. This might be relevant for those megabase fetishists wich tend to run thousands of bots on relatively short routes.
Factorio currently uses the most cheap and UPS-friendly way possible.
I would be happy to trade some CPU cycles for less cheap bot pathfinding and work-assigment though...

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

Re: Optimize Drone Movement

Post by mrvn » Mon Nov 26, 2018 3:13 pm

Oktokolo wrote:
Mon Nov 26, 2018 2:35 pm
mrvn wrote:
Mon Nov 26, 2018 9:46 am
Rseding91 wrote:
Fri Nov 23, 2018 4:29 pm
Robots don't path-find at all when they set out to do something. They go directly to the target. If in going directly to the target they run out of energy they then search for a roboport nearby to recharge at.

Nobody is going to be able to find a solution which is as cheap as the current implementation because you can't get cheaper than "go directly towards the target" which means adding *any* additional work is more expensive.
They path find, even if the path is simply "as the crow flies". And I just described an algorithm that has exactly the same cost and doesn't do any additional work. It just changes the time when it does the work a bit.
The vanilla algorithm has a slightly lower cost in the case where the bot can reach its target without having to refuel. This might be relevant for those megabase fetishists wich tend to run thousands of bots on relatively short routes.
Factorio currently uses the most cheap and UPS-friendly way possible.
I would be happy to trade some CPU cycles for less cheap bot pathfinding and work-assigment though...
Does it actually?

How do bots determine that they are out of fuel and need to find a recharge point? Do they decrease the fuel level every tick and check if it's low enough to need a charging point? Or do they check before flying off and set them self a timer "I will need to recharge in 134 ticks"?

I assume they do the former, costing time every tick. While my algorithm would actually never need to check the fuel mid-flight. So it could even be cheaper.

Darinth
Long Handed Inserter
Long Handed Inserter
Posts: 75
Joined: Wed Oct 17, 2018 12:17 pm

Re: Optimize Drone Movement

Post by Darinth » Mon Nov 26, 2018 3:58 pm

mrvn wrote:
Mon Nov 26, 2018 3:13 pm
Oktokolo wrote:
Mon Nov 26, 2018 2:35 pm
mrvn wrote:
Mon Nov 26, 2018 9:46 am
Rseding91 wrote:
Fri Nov 23, 2018 4:29 pm
Robots don't path-find at all when they set out to do something. They go directly to the target. If in going directly to the target they run out of energy they then search for a roboport nearby to recharge at.

Nobody is going to be able to find a solution which is as cheap as the current implementation because you can't get cheaper than "go directly towards the target" which means adding *any* additional work is more expensive.
They path find, even if the path is simply "as the crow flies". And I just described an algorithm that has exactly the same cost and doesn't do any additional work. It just changes the time when it does the work a bit.
The vanilla algorithm has a slightly lower cost in the case where the bot can reach its target without having to refuel. This might be relevant for those megabase fetishists wich tend to run thousands of bots on relatively short routes.
Factorio currently uses the most cheap and UPS-friendly way possible.
I would be happy to trade some CPU cycles for less cheap bot pathfinding and work-assigment though...
Does it actually?

How do bots determine that they are out of fuel and need to find a recharge point? Do they decrease the fuel level every tick and check if it's low enough to need a charging point? Or do they check before flying off and set them self a timer "I will need to recharge in 134 ticks"?

I assume they do the former, costing time every tick. While my algorithm would actually never need to check the fuel mid-flight. So it could even be cheaper.
Unfortunately, we're at an academic disagreement. And, Rseding is the expert on the subject of Factorio's engine. I still suspect that with proper sets of checks the engine could incorporate pathfinding and in doing actually become more UPS efficient, but it's all mostly irrelevant anyways.

Even if I *can* be done, it probably *shouldn't* be done as doing so opens up and encourages an invalid use-case for drones. Drones are designed to operate in a relatively small, concaveish area. Adding pathfinding would encourage people to have drones that actually and functionality bypass even things like train networks for a lot of things. With enough drones & roboports I could absolutely transport ore from distant sets of outposts if there was pathfinding, and that's just not what drones should be doing. That's the job of trains. I just don't think it would benefit the gameplay that Wube is going for.

What I might like to see is just shifting the check for whether a target is within the drone's fuel range to the drone launch and if its not, rather than trying to go directly to it's target go to the roboport that is as far along it's path as it can go. If there isn't one... display a notification. This gives a player an alert that a drone has what is effectively an impossible assignment, and I think would give the vast majority of the UPS benefits that any kind of path finding algorithim could plausibly provide (by reducing drone flight times) without implementing an actual pathing algorithm that would fundamentally change drone capabilities.

User avatar
Oktokolo
Filter Inserter
Filter Inserter
Posts: 399
Joined: Wed Jul 12, 2017 5:45 pm

Re: Optimize Drone Movement

Post by Oktokolo » Tue Nov 27, 2018 1:07 am

mrvn wrote:
Mon Nov 26, 2018 3:13 pm
While my algorithm would actually never need to check the fuel mid-flight. So it could even be cheaper.
So with your algorithm, drones wont slow down when out of fuel?

Darinth
Long Handed Inserter
Long Handed Inserter
Posts: 75
Joined: Wed Oct 17, 2018 12:17 pm

Re: Optimize Drone Movement

Post by Darinth » Tue Nov 27, 2018 2:48 pm

Oktokolo wrote:
Tue Nov 27, 2018 1:07 am
mrvn wrote:
Mon Nov 26, 2018 3:13 pm
While my algorithm would actually never need to check the fuel mid-flight. So it could even be cheaper.
So with your algorithm, drones wont slow down when out of fuel?
No, using his algorithm drones will know before taking flight if they can make it to their destination and either A: would refuse to make a trip that they can't make due to fuel constraints or B: utilize the event system (I assume factorio utilizes a reasonable event system) to change the drone speed when they'd run out of fuel.

The only problems that I can immediately see come as a result of drones flying after moving targets. If a drone is chasing after a moving target and reaches it, stands still for a few ticks while it does repair to say a vehicle, but then has to chase the vehicle and potential repeat this process several times it would have to recalculate fuel timing at each interval. Alternatively, the game could simply ignore the small discrepancy of standing still while repairing (lets assume repair or transfering cargo takes just as much energy as moving) and every drone will know the exact moment it would run out of energy and be able to add that event to the queue at take-off. It'd add some extra ram usage, but lets give a generous 60 bytes of memory needed per queued event (I'd expect it's less than that, but I'd prefer to err on the side of caution when making assumptions about someone else's engine) 10,000 drones each queueing 1 event adds up to another 600k ram usage. That's less than a meg.

Technical obstacles and edge-cases, but I don't think the technical obstacles are insurmountable. This really boils down to gameplay that I don't think I'd want to see encouraged. The most I'd probably like to see is them smart enough to move directly to the closest drone port to their destination that they can reach when they can't reach their destination, rather than the zig-zagging they currently do.

Darinth
Long Handed Inserter
Long Handed Inserter
Posts: 75
Joined: Wed Oct 17, 2018 12:17 pm

Re: Optimize Drone Movement

Post by Darinth » Tue Nov 27, 2018 4:54 pm

Actually... as long as they're going to an immobile location and are able to reach their destination... there's not even actually a reason to add those events to the queue... you know factually that they'll never fire and would need to be removed later. If you know the drone will reach it's destination, there's no need to even do fuel checks...

Trebor
Long Handed Inserter
Long Handed Inserter
Posts: 95
Joined: Sun Apr 30, 2017 1:39 pm

Re: Optimize Drone Movement

Post by Trebor » Tue Nov 27, 2018 5:09 pm

Nerf bots!! Make them less UPS friendly by giving them brains.

pleegwat
Fast Inserter
Fast Inserter
Posts: 105
Joined: Fri May 19, 2017 7:31 pm

Re: Optimize Drone Movement

Post by pleegwat » Tue Nov 27, 2018 5:44 pm

Bots in flight would have to be updated every tick anyway to update their current location. Assuming the bot location and energy reserve are all in the same cache line, the only actual performance cost is in fetching the bot's speed, and that's the same value for all bots so effectively free.

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

Re: Optimize Drone Movement

Post by ratchetfreak » Wed Nov 28, 2018 10:02 am

Bot's are not entirely inactive during flight. They need to update which chunk they are in. Which means removing themselves of the old chunk's entity list and adding themselves to the new one.

This is to improve collision detection with them so biters can detect and attack them and players can interact with them.

User avatar
Oktokolo
Filter Inserter
Filter Inserter
Posts: 399
Joined: Wed Jul 12, 2017 5:45 pm

Re: Optimize Drone Movement

Post by Oktokolo » Wed Nov 28, 2018 2:09 pm

Darinth wrote:
Tue Nov 27, 2018 4:54 pm
Actually... as long as they're going to an immobile location and are able to reach their destination... there's not even actually a reason to add those events to the queue... you know factually that they'll never fire and would need to be removed later. If you know the drone will reach it's destination, there's no need to even do fuel checks...
There is at least one non-deterministic entity in every Factorio game wich can change the existance of targets. You do not know what the player will do after the bot started its travel. Also, there are (deterministic) biters wich you would have to consider.
You have to check for target existance or bots will keep traveling to non-existing targets (wich might be okay though).

Darinth
Long Handed Inserter
Long Handed Inserter
Posts: 75
Joined: Wed Oct 17, 2018 12:17 pm

Re: Optimize Drone Movement

Post by Darinth » Wed Nov 28, 2018 3:19 pm

Oktokolo wrote:
Wed Nov 28, 2018 2:09 pm
Darinth wrote:
Tue Nov 27, 2018 4:54 pm
Actually... as long as they're going to an immobile location and are able to reach their destination... there's not even actually a reason to add those events to the queue... you know factually that they'll never fire and would need to be removed later. If you know the drone will reach it's destination, there's no need to even do fuel checks...
There is at least one non-deterministic entity in every Factorio game wich can change the existance of targets. You do not know what the player will do after the bot started its travel. Also, there are (deterministic) biters wich you would have to consider.
You have to check for target existance or bots will keep traveling to non-existing targets (wich might be okay though).
Drones don't have to check for target existence. Entity destruction should trigger a check to see if there are drones moving to it to cancel their movement. One of these requires a check for every drone every tick, the other only requires a check on the (relatively speaking) rare event of entity destruction.

Generally speaking, you want to minimize the amount of processing entities have to do every tick. Event driven models can frequently do the same thing that a 'check every tick' model can do, at a fraction of the processing power. Commonly with a bit more RAM usage... but relatively speaking to the CPU power RAM is usually cheap.

Edit: Also, where's the relevancy in that anyways? This still doesn't change fuel checks and even that is only tangentially related to drone movement optimizations. The game obviously does some form of checking for if their target entity still exists (don't know if it's done by drone-code on a per-tick basis or done during entity destruction...) but this doesn't actually change the fact that drones don't technically need to track their fuel usage in-flight.

Edit2: I apologize. At this point, I think that I'm functionally off-topic. I'm not actually interested in seeing drones given pathing, but enjoy the academic discussion of whether or not it's feasible from a UPS point-of-view.

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

Re: Optimize Drone Movement

Post by mrvn » Thu Nov 29, 2018 11:04 am

pleegwat wrote:
Tue Nov 27, 2018 5:44 pm
Bots in flight would have to be updated every tick anyway to update their current location. Assuming the bot location and energy reserve are all in the same cache line, the only actual performance cost is in fetching the bot's speed, and that's the same value for all bots so effectively free.
Not every tick. Bots move in straight lines so their position is perfectly determined by knowing when they left from where to where. You only need to compute the actual position for bots that are visible or near enemies. Which brings in ratchetfreks comment about updating which chunk bots are in during their fleight.

But as they fly in a straight line for every chunk it is trivial to compute when they will leave the chunk and set a timer. Then update the actual bots position only when:

1) the bot is in a visible chunk
2) the bot is in a chunk visible to an enemy
3) the bot crosses a chunk border
4) the bot runs out of fuel so speed changes

For 4 I would probably reset the "from" and "start time" fields of the bot. That way all computations will be for constant speed.

Post Reply

Return to “Outdated/Not implemented”