Optimize Drone Movement

Ideas that are too old (too many things have changed since) and ones which won't be implemented for certain reasons or if there are obviously better suggestions.

Moderator: ickputzdirwech

TI-89
Long Handed Inserter
Long Handed Inserter
Posts: 50
Joined: Thu Feb 09, 2017 2:00 am
Contact:

Re: Optimize Drone Movement

Post by TI-89 »

So to look at performance 'in aggregate,' let's look at what happens if someone suddenly requests... say ~40k iron plates (I did 9 chests with request of 20k -- again window maxes at capacity so the network will send only 4.8k at a time *for each chest*). Going from the time of my screenshots, this flow took ~23 minutes, giving an average throughput of about 1800u/min -- not too shabby. Especially when you consider I did not optimize for this experiment, simply requested the most plentiful resource in the network I was in. Obviously I was building for 'large scale logistics,' but it's entirely possible to optimize for a particular resource flow. However, I wasn't even sure where the plates would come from. Screenshots hardly do it justice, but you can see the flow develop as the various links are saturated. Across the entire transmission, the pathing is very good. But if you look at individual bots, the distance travelled could vary greatly.
http://imgur.com/a/k1Ynm

I really don't think processing power really even needs to be discussed for consideration for this proposed change. But for the sake of discussion, realize that caching paths is difficult because the best path is probabilistic based on current conditions. This includes the level of charge of each bot at the time of pick up, as well as the queue size at each port the bot will consider pathing to. And this would hurt performance overall unless you also consider bots that might decide to path to that port while the bot in question is in the air. Then of course you still need a congestion avoidance algorithm unless you want latency to vary hugely whenever your network is under any kind of load.
If the pathing algorithm were to be changed, I think it would require a forwarding based solution (roboports maintain state). But then you need to simulate this distributed solution for ports to have up to date info about network conditions, and really there's not much feedback built into the network, so there's no way at all to justify this behavior in terms of how it happens 'in the world.' For a simple, naiive solution, the current pathing is much better than I would have guessed when I started this game.
ross
Burner Inserter
Burner Inserter
Posts: 15
Joined: Thu Dec 08, 2016 11:55 pm
Contact:

Re: Optimize Drone Movement

Post by ross »

What is the correct way to use construction bots in a base which expands infinitely in one direction? As the base expands, the provider chests containing construction materials get farther and farther from where they're needed. If requester chests for the materials are set up at the frontier, they have to have inserters to provider chests for the construction bots to use the materials, which results in an infinite logistic bot loop; and the requester chests still have to be manually removed and moved to the new frontier periodically anyway. If trains are used (assuming a train stop can be fit in the construction material production area, which pretty much is never the case), new train stops have to be created every few minutes, and the old ones become obsolete and un-used. Is there a better solution?
JohnyDL
Filter Inserter
Filter Inserter
Posts: 535
Joined: Fri May 16, 2014 3:44 pm
Contact:

Re: Optimize Drone Movement

Post by JohnyDL »

Ross this should be solved by Buffer chests in 0.16 and using Logistics to move such loads out of the prerogative of construction bots.
Nasabot
Fast Inserter
Fast Inserter
Posts: 102
Joined: Fri Oct 30, 2015 11:16 am
Contact:

Re: Optimize Drone Movement

Post by Nasabot »

I prefer better UPS over better pathfinding (pathfinding can be solved by the player)

An optimizsation Id like to see is inserter and bots always wait to deliver their maximum number of items. This might drastically reduce actions.
JohnyDL
Filter Inserter
Filter Inserter
Posts: 535
Joined: Fri May 16, 2014 3:44 pm
Contact:

Re: Optimize Drone Movement

Post by JohnyDL »

if delivering to chests then bots will deliver full stacks if possible the pain is when the supply chest doesn't fill in time just involves better planning I think.
Borg
Manual Inserter
Manual Inserter
Posts: 1
Joined: Mon Nov 12, 2018 10:49 pm
Contact:

Re: Optimize Drone Movement

Post by Borg »

Fundamentally, I have one request: when I lay out a blueprint for a rail connection out to an ore patch, I do not want to come back later and find that all my rails are in construction robots that have failed to find a functional path and are stuck flying out from my main base, running out of energy, and returning to the same roboport to recharge and try the same path again. I don't care if it is accomplished by using a pathfinding algorithm with some global awareness, or by having robots remember where they've charged along this delivery and do something different if they start repeating, or some other solution. I just don't want to have to perform detective work to figure out where they've gotten stuck this time.
Nidan
Filter Inserter
Filter Inserter
Posts: 270
Joined: Sat Nov 21, 2015 1:40 am
Contact:

Re: Optimize Drone Movement

Post by Nidan »

There's a simple fix to prevent the bots being stuck in a loop:
Remember the last roboport the bot left/charged at, and whenever the bot needs to charge only allow roboports that are closer to the target than the last one.
Once the bot has reached it's target allow all roboports again.

Keeps the bots pathfinding (or lack thereof) as efficient as it's now, U-shape layouts and alike will still be terrible, but at least guarantees that the bots will make progress and not get stuck, at the cost of 4 or 8 bytes per bot.
Zavian
Smart Inserter
Smart Inserter
Posts: 1649
Joined: Thu Mar 02, 2017 2:57 am
Contact:

Re: Optimize Drone Movement

Post by Zavian »

Nidan wrote: Tue Nov 13, 2018 12:32 am There's a simple fix to prevent the bots being stuck in a loop:
Remember the last roboport the bot left/charged at, and whenever the bot needs to charge only allow roboports that are closer to the target than the last one.
Once the bot has reached it's target allow all roboports again.

Keeps the bots pathfinding (or lack thereof) as efficient as it's now, U-shape layouts and alike will still be terrible, but at least guarantees that the bots will make progress and not get stuck, at the cost of 4 or 8 bytes per bot.
Even simpler. Don't build bot networks with large holes.
User avatar
Oktokolo
Filter Inserter
Filter Inserter
Posts: 884
Joined: Wed Jul 12, 2017 5:45 pm
Contact:

Re: Optimize Drone Movement

Post by Oktokolo »

Zavian wrote: Tue Nov 13, 2018 6:42 am Don't build bot networks with large holes.
Exactly. Had to learn that the hard way.
Bot networks have to be (roughly) convex shapes without (non-tiny) holes. They also should not be too big (upper limit depends on purpose of the network) because of the maximum travel time getting too high.

Bot pathfinding is intentionally dull for UPS reasons. That will not change because of the megabase fetishists wich need them to avoid the UPS impact of belts (it got lower due to multiple optimizations, but is still way higher than that of bots).
User avatar
Ghoulish
Filter Inserter
Filter Inserter
Posts: 468
Joined: Fri Oct 16, 2015 8:40 am

Re: Optimize Drone Movement

Post by Ghoulish »

Let's say there is a second type of roboport, same model but 75 or 50% sized, maybe a fresh lick of paint too. Each roboport only has 2 connections for other roboports. Connecting roboport mk. 2's creates a chain, a direct point from each roboport which the bots would always follow. Would such a system be less impactful than the way bots behave now? Because the bot will know where to go automatically (or is it a case of automatic or not, the bots still use the same amount of cpu?).

One question for me though is what I think bots should be. To me they should be nothing but a dumb tool. Adding extra AI as above is all well and good, but I ask if we should anyway. Already you can do more with bots compared to belts (ugh, that debate again) I say there is no need to make bots smarter, even if you look at what bots currently do in isolation away from that debate, I still say there's no need. If you wanted to run the system above the solution is simple, 3 zones, 2 go west to east and the other north south. A few requesters and providers with inserters linking across each zone and you're done. Pain in the ass though right! It should be! Trains would be the better solution. Even if you were to scale down by 50% that map above and consider this more normal sort of a range setting, they still should not have AI. I say bots should be considered dumb tools which need micro managing, a consideration for pathways must be given, they're not autonomous.
See the daily™ struggles with my Factory! :D https://www.twitch.tv/repetitivebeats
stm
Long Handed Inserter
Long Handed Inserter
Posts: 58
Joined: Sun Feb 12, 2017 3:33 pm
Contact:

Re: Optimize Drone Movement

Post by stm »

While I agree with the assessment, the pathfinding of buts should be improved a bit before 1.0, I disagree with the proposed algorithms which are in fact neither optimal nor computaionally cheap. Taking the beeline is a very cheap O(1) calculation, independent of anything.
Even just trying to move between connected ports requires you to go through a substantial part of your network depend on your layout (at least O(D) (D beeing the distance), propably more like O(D²)). It also would create some strange routing, since at that point even for a convex shape, routing would give some strange step like, or zig-zag routes depending on port placement, even though a beeline would essetially work fine.
What in my Opinion propably should be implemented is a prediction if a bot has enough charge for its trip, and if not which port it is going to head for in that case and then directly head for that port.
At least this would get rid of one problem:
I have not tried it, but I assume one can stall a delivery in the air by having a bot start moving from port A to Target and having A still beeing the closest port for recharging after the charge runs out. If at pathfinding you path to your curent location, you already know something is wrong.
Stm
Darinth
Filter Inserter
Filter Inserter
Posts: 323
Joined: Wed Oct 17, 2018 12:17 pm
Contact:

Re: Optimize Drone Movement

Post by Darinth »

Optimizing drones to use pathfinding without substantial UPS impact is non-trivial, but absolutely possible. Cached pathfinding options should eliminate the cost-per-drone allowing drones to be active in the same vast numbers as they are today. They only need to look up the next node in their path when they leave their current node, after that it's just moving between nodes just like it is today. These pathfinding algorithms can even perform load balancing and other functions to guarantee that drones don't oversaturate particular ports. It's all very possible, and I don't even think it'd be insanely complicated, though everything always ends up having more complication than it appears at first and it'd certainly be non-trivial.

I still think this really boils more down to questions of gameplay. Is having a single logistic network that spans along your entire map and runs along railways a valid method of play? If it is, than pathfinding is important. Without it, this can't function. If this is simply determined as invalid, than you've got some smaller use cases to look at. It looks like Wube has made a final call on this. Logistics bots are designed to operate in small, roughly concave areas where their simple brains aren't going to do anything too incredibly dumb. You have to accept that drones are dumb. They try to go from point A to point B and return to a port if they run out of energy. You unfortunately have to ship materials out to other areas with trains.

I'm hoping we'll see equipment grids on trains in vanilla some day in the future. At that point, it might be possible to setup train schedules that specifically tell them to go to construction areas (even allowing them to construct their own tracks along the way). But I'll be honest, I don't think that you're gonna make any headway convincing Wube that drones should be able to path their way across the map. It's just not in the use-case for drones.
stm
Long Handed Inserter
Long Handed Inserter
Posts: 58
Joined: Sun Feb 12, 2017 3:33 pm
Contact:

Re: Optimize Drone Movement

Post by stm »

Darinth wrote: Tue Nov 13, 2018 4:25 pm Optimizing drones to use pathfinding without substantial UPS impact is non-trivial, but absolutely possible. Cached pathfinding options should eliminate the cost-per-drone allowing drones to be active in the same vast numbers as they are today. They only need to look up the next node in their path when they leave their current node, after that it's just moving between nodes just like it is today. These pathfinding algorithms can even perform load balancing and other functions to guarantee that drones don't oversaturate particular ports. It's all very possible, and I don't even think it'd be insanely complicated, though everything always ends up having more complication than it appears at first and it'd certainly be non-trivial.
That is far from computationally cheap. Even if caching you have to do a lot more operations per bot than currently seems to be done. And that is even neglecting the fact, that you have to load more data from RAM the whole time.
What currently seems to be done is just a charge check and an easy 2D line calculation which is about 15? Instructions in total, of which only about 5 have to be done every tick, since only the player is a moving target entity.
What you are proposing costs orders of magnitude more in computational power.
I still think this really boils more down to questions of gameplay. Is having a single logistic network that spans along your entire map and runs along railways a valid method of play? If it is, than pathfinding is important. Without it, this can't function. If this is simply determined as invalid, than you've got some smaller use cases to look at. It looks like Wube has made a final call on this. Logistics bots are designed to operate in small, roughly concave areas where their simple brains aren't going to do anything too incredibly dumb. You have to accept that drones are dumb. They try to go from point A to point B and return to a port if they run out of energy. You unfortunately have to ship materials out to other areas with trains.
Well in my opinion bots are not really optimal atm (and I am not talking about pathfinding here!)
You can not controll what gets priority and what should go where first, and they are prone to move more items than always neccessary etc..
They are wonderfully flexible, and my current intermediate factory is relying hevily on them, but I am planing to change back to belts for local transport again soon, and only using bots for distribution of intermediate/rarely used products.
Sorting etc. is made trivial since they introduced filters in spliters and you have a lot more controll over everything.
Due to the screen size I have also problems to see what materials are missing in the logistics network, since the lower part often gets overwritten by the GUI. Using belts you easily can see which are running empty and you can easily shift your focus, while for bots I do not know any way to prioritize one chest over 20 other which request the same items.
At the end they trivialize the one thing that makes factorio interesting: designing the flow of your materials.
But YMMV oc
I'm hoping we'll see equipment grids on trains in vanilla some day in the future. At that point, it might be possible to setup train schedules that specifically tell them to go to construction areas (even allowing them to construct their own tracks along the way). But I'll be honest, I don't think that you're gonna make any headway convincing Wube that drones should be able to path their way across the map. It's just not in the use-case for drones.
The equipment grid i a totally different thing.
I too would advocate for such equipment grids. Especially since it is stupid, that e.g. you can carry laser defenses and shields and your tank can not.
Concerning the long range bots I don'T see why one should forbid the player to make stupid choices, and with regards to speed efficiany and so on using logitic bots over long distances is not really a good idea anyway. I still would like the proposed change from my previous post, but stupid bots are a valid design choice. They should decide though, whether they delibaratly want stupid bots, or it is a question of computational efficiency.
Stm
Darinth
Filter Inserter
Filter Inserter
Posts: 323
Joined: Wed Oct 17, 2018 12:17 pm
Contact:

Re: Optimize Drone Movement

Post by Darinth »

stm wrote: Wed Nov 14, 2018 2:36 pm
Darinth wrote: Tue Nov 13, 2018 4:25 pm Optimizing drones to use pathfinding without substantial UPS impact is non-trivial, but absolutely possible. Cached pathfinding options should eliminate the cost-per-drone allowing drones to be active in the same vast numbers as they are today. They only need to look up the next node in their path when they leave their current node, after that it's just moving between nodes just like it is today. These pathfinding algorithms can even perform load balancing and other functions to guarantee that drones don't oversaturate particular ports. It's all very possible, and I don't even think it'd be insanely complicated, though everything always ends up having more complication than it appears at first and it'd certainly be non-trivial.
That is far from computationally cheap. Even if caching you have to do a lot more operations per bot than currently seems to be done. And that is even neglecting the fact, that you have to load more data from RAM the whole time.
What currently seems to be done is just a charge check and an easy 2D line calculation which is about 15? Instructions in total, of which only about 5 have to be done every tick, since only the player is a moving target entity.
What you are proposing costs orders of magnitude more in computational power.
I still think this really boils more down to questions of gameplay. Is having a single logistic network that spans along your entire map and runs along railways a valid method of play? If it is, than pathfinding is important. Without it, this can't function. If this is simply determined as invalid, than you've got some smaller use cases to look at. It looks like Wube has made a final call on this. Logistics bots are designed to operate in small, roughly concave areas where their simple brains aren't going to do anything too incredibly dumb. You have to accept that drones are dumb. They try to go from point A to point B and return to a port if they run out of energy. You unfortunately have to ship materials out to other areas with trains.
Well in my opinion bots are not really optimal atm (and I am not talking about pathfinding here!)
You can not controll what gets priority and what should go where first, and they are prone to move more items than always neccessary etc..
They are wonderfully flexible, and my current intermediate factory is relying hevily on them, but I am planing to change back to belts for local transport again soon, and only using bots for distribution of intermediate/rarely used products.
Sorting etc. is made trivial since they introduced filters in spliters and you have a lot more controll over everything.
Due to the screen size I have also problems to see what materials are missing in the logistics network, since the lower part often gets overwritten by the GUI. Using belts you easily can see which are running empty and you can easily shift your focus, while for bots I do not know any way to prioritize one chest over 20 other which request the same items.
At the end they trivialize the one thing that makes factorio interesting: designing the flow of your materials.
But YMMV oc
I'm hoping we'll see equipment grids on trains in vanilla some day in the future. At that point, it might be possible to setup train schedules that specifically tell them to go to construction areas (even allowing them to construct their own tracks along the way). But I'll be honest, I don't think that you're gonna make any headway convincing Wube that drones should be able to path their way across the map. It's just not in the use-case for drones.
The equipment grid i a totally different thing.
I too would advocate for such equipment grids. Especially since it is stupid, that e.g. you can carry laser defenses and shields and your tank can not.
Concerning the long range bots I don'T see why one should forbid the player to make stupid choices, and with regards to speed efficiany and so on using logitic bots over long distances is not really a good idea anyway. I still would like the proposed change from my previous post, but stupid bots are a valid design choice. They should decide though, whether they delibaratly want stupid bots, or it is a question of computational efficiency.
Stm
Most of your post I'm not going to disagree with. A lot of it boils down to personal preference and in the end what Wube want's for the game. I can't say I don't care, but I'm good with their choices either way on this. It's certainly not going to break the game one way or the other. Even if full pathfinding were to be implemented, bots are still a sub-optimal choice IMO. Isolated loginets with trains delivering required supplies will continue to be the optimal... but sometimes there's something to be said for simplicity.

The only place I'm going to disagree is with regards to feasibility from a computational standpoint. Properly implemented (which is non-trivial, but should be reasonable) it'd absolutely be computationally cheap. Setting up the initially pathfinding algorithms is cheap to do. It'd be wholey unrealistic to do every tick, but setting up the initial infrastructure and then caching paths as they're computed should absolutely be doable. Look less at traditional game pathing algorithms (which are designed more for pathing around obstacles than pathing between sparse nodes) and more at network pathfinding algorithms (which are designed to path cheaply between sparse nodes which is what drones need and often are good at adjusting themselves to deal with network congestion, such as overloaded intermediate roboports). They won't get you optimal solutions, but will get you solutions (and generally good ones). Once the paths are cached, pulling them back is a O(1) operation which is how routers already handle this. Yes, this is still substantially more overhead than a straight movement from point A to point B without pathfinding, but keep in mind that this process only needs to generally be gone through when a drone launches. After the drone launches, it knows it's target and the same cheap-as-dirt algorithm that is currently used continues to be all that processes on a per-tick basis.
stm
Long Handed Inserter
Long Handed Inserter
Posts: 58
Joined: Sun Feb 12, 2017 3:33 pm
Contact:

Re: Optimize Drone Movement

Post by stm »

Darinth wrote: Wed Nov 14, 2018 4:17 pm The only place I'm going to disagree is with regards to feasibility from a computational standpoint. Properly implemented (which is non-trivial, but should be reasonable) it'd absolutely be computationally cheap. Setting up the initially pathfinding algorithms is cheap to do. It'd be wholey unrealistic to do every tick, but setting up the initial infrastructure and then caching paths as they're computed should absolutely be doable. Look less at traditional game pathing algorithms (which are designed more for pathing around obstacles than pathing between sparse nodes) and more at network pathfinding algorithms (which are designed to path cheaply between sparse nodes which is what drones need and often are good at adjusting themselves to deal with network congestion, such as overloaded intermediate roboports). They won't get you optimal solutions, but will get you solutions (and generally good ones). Once the paths are cached, pulling them back is a O(1) operation which is how routers already handle this. Yes, this is still substantially more overhead than a straight movement from point A to point B without pathfinding, but keep in mind that this process only needs to generally be gone through when a drone launches. After the drone launches, it knows it's target and the same cheap-as-dirt algorithm that is currently used continues to be all that processes on a per-tick basis.
The obstacal avoidens actually is the same, the obstacles being holes in coverage and the ports beeing possible positions in your case.
And although the lookup operation might be O(1) due to hashing, the hashing itself will probably cost you more instructions than the trivial movement for the whole route. Otherwise you will need something like O(log(chestcount)), which actually sounds a lot worse than it is, since log(1.000)*10 << 1*100.
What I think you fail to take into account though is the fact that a lot of routes are very short and only require perhaps 10 to 300 tics. So overhead costs of 100 instructions are something which is not neglectable.
Or if you prefere another view, in a rather small setup of 100 transports per seconds (you need at least twice that in routing since the bot has to move to your material first) this gives more than 20.000 additional instructions, instead of about 3.000 for the easy movement.
Now try to scale that up for a megabase which has more than 1k in bots.
And 100 Instructions is not realy a lot. Jumping around in the memory costs at least as much time.
Stm
Darinth
Filter Inserter
Filter Inserter
Posts: 323
Joined: Wed Oct 17, 2018 12:17 pm
Contact:

Re: Optimize Drone Movement

Post by Darinth »

stm wrote: Fri Nov 16, 2018 1:49 pm The obstacal avoidens actually is the same, the obstacles being holes in coverage and the ports beeing possible positions in your case.
And although the lookup operation might be O(1) due to hashing, the hashing itself will probably cost you more instructions than the trivial movement for the whole route. Otherwise you will need something like O(log(chestcount)), which actually sounds a lot worse than it is, since log(1.000)*10 << 1*100.
What I think you fail to take into account though is the fact that a lot of routes are very short and only require perhaps 10 to 300 tics. So overhead costs of 100 instructions are something which is not neglectable.
Or if you prefere another view, in a rather small setup of 100 transports per seconds (you need at least twice that in routing since the bot has to move to your material first) this gives more than 20.000 additional instructions, instead of about 3.000 for the easy movement.
Now try to scale that up for a megabase which has more than 1k in bots.
And 100 Instructions is not realy a lot. Jumping around in the memory costs at least as much time.
Stm
But what's far more important here is frequency of expensive operations. On very short trips (the ones that take 10 ticks) there's no reason to invoke any kind of path finding. If the drone is within flight of it's current location, this is all a moot point. There will never been a reason to invoke any of the more expensive operations. Those 10-300 tick movements that are the bread and butter operations of factory drone work will be mostly unaffected. The most common situations that drone operate under will be unchanged, outside of one quick check at the start of a route to determine if the end-point is inside of flight range. In the grand scheme of things, that's a trivial check and it may well lead to performance increases as drones take more optimized routes under certain circumstance which means less drones in the air. There are additional costs to the route lookups, but they're trivial in the scale of factorio and so rarely used that if time and care were taken when designing the system, I doubt that this system would even be considered.

Also, holes in coverage aren't obstacles to path around Drones can leave their coverage area. It's just a networking question of "Can drones make it from point A to point B?" which is the network equivalent of determining which routers they're connected to and how good those connections are.

From a technical standpoint, drone pathing could be implemented with little-to-no impact on UPS. In fact, due to the drone optimizations resulting in less drones in the air at any given time due to less back-tracking, it might actually be a UPS boost. Especially on mega-base maps where there are 1000s of drones using unoptimized routes that result in drones taking bizarre zig-zag paths.
Rseding91
Factorio Staff
Factorio Staff
Posts: 14345
Joined: Wed Jun 11, 2014 5:23 am
Contact:

Re: Optimize Drone Movement

Post by Rseding91 »

Darinth wrote: Fri Nov 16, 2018 3:10 pm From a technical standpoint, drone pathing could be implemented with little-to-no impact on UPS. In fact, due to the drone optimizations resulting in less drones in the air at any given time due to less back-tracking, it might actually be a UPS boost. Especially on mega-base maps where there are 1000s of drones using unoptimized routes that result in drones taking bizarre zig-zag paths.
That's simply not true. A "mega-base map" will never have drones spanning massive networks as that's super inefficient for item travel times due to how many times the robot has to recharge.

The core question here is: should the game attempt to solve the "you built a ineffective robot network" or should the player solve it. Our stance is: the player should solve it.

We're not adding expensive path-finding logic to robots - I can say that with confidence.

Don't build L or U shaped logistic networks and expect the robots to "be smart" - that's up to you to mange and part of the logistics puzzle that is Factorio.
If you want to get ahold of me I'm almost always on Discord.
Darinth
Filter Inserter
Filter Inserter
Posts: 323
Joined: Wed Oct 17, 2018 12:17 pm
Contact:

Re: Optimize Drone Movement

Post by Darinth »

Rseding91 wrote: Fri Nov 16, 2018 3:52 pm
Darinth wrote: Fri Nov 16, 2018 3:10 pm From a technical standpoint, drone pathing could be implemented with little-to-no impact on UPS. In fact, due to the drone optimizations resulting in less drones in the air at any given time due to less back-tracking, it might actually be a UPS boost. Especially on mega-base maps where there are 1000s of drones using unoptimized routes that result in drones taking bizarre zig-zag paths.
That's simply not true. A "mega-base map" will never have drones spanning massive networks as that's super inefficient for item travel times due to how many times the robot has to recharge.

The core question here is: should the game attempt to solve the "you built a ineffective robot network" or should the player solve it. Our stance is: the player should solve it.

We're not adding expensive path-finding logic to robots - I can say that with confidence.

Don't build L or U shaped logistic networks and expect the robots to "be smart" - that's up to you to mange and part of the logistics puzzle that is Factorio.
I'm pretty sure we're actually in agreement for the most part. :)

From a technical/engine standpoint, I suspect pathing *could* be implemented with little-to-no UPS effects (in fact, I suspect UPS gains are plausible on larger factories that use drones spanning extensive distances) but I still don't believe that it should be a factorio feature. It's simply not within the use-case for drones. There are faster, more effective methods to support long-distance item transport. That's what trains are there for. There are ways to design your bases that it's not needed. And in the end, pathfinding would encourage a use-case for drones that simply isn't within what I think you guys planned for their intended use.
Jap2.0
Smart Inserter
Smart Inserter
Posts: 2379
Joined: Tue Jun 20, 2017 12:02 am
Contact:

Re: Optimize Drone Movement

Post by Jap2.0 »

Darinth wrote: Wed Nov 14, 2018 4:17 pmThe only place I'm going to disagree is with regards to feasibility from a computational standpoint. Properly implemented (which is non-trivial, but should be reasonable) it'd absolutely be computationally cheap. Setting up the initially pathfinding algorithms is cheap to do. It'd be wholey unrealistic to do every tick, but setting up the initial infrastructure and then caching paths as they're computed should absolutely be doable. Look less at traditional game pathing algorithms (which are designed more for pathing around obstacles than pathing between sparse nodes) and more at network pathfinding algorithms (which are designed to path cheaply between sparse nodes which is what drones need and often are good at adjusting themselves to deal with network congestion, such as overloaded intermediate roboports). They won't get you optimal solutions, but will get you solutions (and generally good ones). Once the paths are cached, pulling them back is a O(1) operation which is how routers already handle this. Yes, this is still substantially more overhead than a straight movement from point A to point B without pathfinding, but keep in mind that this process only needs to generally be gone through when a drone launches. After the drone launches, it knows it's target and the same cheap-as-dirt algorithm that is currently used continues to be all that processes on a per-tick basis.
One thing to keep in mind here is that Factorio is at least as, if not more, bound by memory than single-threaded performance, which is something you might want to consider with large amounts of caching.

Darinth wrote: Fri Nov 16, 2018 3:10 pmFrom a technical standpoint, drone pathing could be implemented with little-to-no impact on UPS. In fact, due to the drone optimizations resulting in less drones in the air at any given time due to less back-tracking, it might actually be a UPS boost. Especially on mega-base maps where there are 1000s of drones using unoptimized routes that result in drones taking bizarre zig-zag paths.
I doubt better pathfinding would have a significant affect on how many bots are in the air at a time. No properly designed megabase will have bots stuck in loops or going a significant distance out of their way more to charge than if it was pre-calculated - in a worst case scenerio where an area has full coverage, a bot is 71 tiles away from a roboport (and hence could theoretically go up to 142 tiles out of its way). That case will never happen in a megabase because it requires the bot to be perfectly between 4 roboports and that roboports are in a perfect 50x50 grid, which is not enough to sustain high bot usages. Meanwhile, a bot with the tier 5 speed upgrade (which is not much for a megabase) will travel more than 280 tiles on a single charge. Overall, it may slightly reduce the amount of bots in the air, but it will not have a significant impact. Calculating where to charge when the bot beings its path also removes the benefit of on-the-fly load balancing that is present for bots charging at roboports right now.
There are 10 types of people: those who get this joke and those who don't.
mrvn
Smart Inserter
Smart Inserter
Posts: 5884
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: Optimize Drone Movement

Post by mrvn »

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.
Post Reply

Return to “Outdated/Not implemented”