Optimize Drone Movement

[Rseding91]

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.

[mrvn]

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.

[Oktokolo]

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]

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]

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.

[Oktokolo]

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]

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]

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]

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

[pleegwat]

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]

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.

[Oktokolo]

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]

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]

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.

[Twisted6]

Reviving an old post a bit but I support this. There's got to be a way to implement rudimentary path finding efficiently. Too many times have I seen bots flying back and worth from ports because the gap they're trying to cross is too far or flying into biters when they cut corners. I like to cover my walls in ports which means I often have areas in the centre of my base with no ports. They either need smarter path finding or infinite charge and invulnerability (invulnerability would stop them from suiciding when repairing the walls too). You used balance as a reason to not make them smarter but they're overpowered as it is anyway. Just make them slower, carry less, use more power or just straight up remove logistic bots from the game and only have construction bots. Keeping them stupid/suicidal isn't a good way to balance them and just makes them frustrating to babysit.

[Jap2.0]

There's got to be a way to implement rudimentary path finding efficiently.

How?

[mrvn]

There's got to be a way to implement rudimentary path finding efficiently.

How?

With my simple algorithm that doesn't increase computations and might even reduce them:

1) When a drone starts compute the fuel cost to reach the goal.
2) If enough fuel is present send the drone on it's way.
3) If it lacks enough fuel find the next roboport to recharge (currently this happens when the drone runs out of fuel, now it happens when you send it. No change overall).
4) Compute fuel cost to reach roboport.
5) if the drone has enough fuel to reach it send it on its way.
6) if it lacks fuel compute the position/tick where it runs out of fuel. Send the drone on its way and set a timer to reduce the drones speed at that point.

Note: In step 3 the next roboport should be nearer to the goal. There might not be any and then the drone has to fly directly to the goal and slow down when it runs out of fuel. Generally take the direct flight when the next refueling + direct path takes longer than direct path now.

The extra path finding for refuel will only be done when needed. Which means the current algorithm would do them too. Just a bit later. On the other hand the drone will fly straight to the roboport instead of flying zig-zag. If possible it will never run out of fuel and slow down. So overall the flight time will be (sometimes greatly) reduced meaning less bots are needed thus saving cpu time.

[nuhll]

Haha, i think the bot logic is more a game challange then anything else (like rocket destroy resources)

But still, what about only fly inside the yellow border, would that also take more CPU then fly direct?

[mrvn]

Haha, i think the bot logic is more a game challange then anything else (like rocket destroy resources)

But still, what about only fly inside the yellow border, would that also take more CPU then fly direct?

Same thing but harder.