Friday Facts #200 - Plans for 0.16

Regular reports on Factorio development.
User avatar
Tallinu
Fast Inserter
Fast Inserter
Posts: 143
Joined: Sun Jun 14, 2015 8:14 am
Contact:

Re: Friday Facts #200 - Plans for 0.16

Post by Tallinu »

ske wrote:Are we getting something to make the bots stay in the green zone?
"Optimisation of logistic robot movement" should include making them a little smarter about where they try to move and when. While "staying in the green zone" would be a nice to have feature, there are tons of other simple things that could be improved upon... Like how they often almost reach their destination and then suddenly turn around and travel a long distance away from it because they passed their power threshold, after having wasted a huge amount of that power (and time) flying toward a destination that they could easily have determined was "unreachable" with their current charge level. When one bot occasionally does it that's just a slight nuisance, but when several hundred bots all do that at the same time (for example, when you re-enter your logistics network after using up a lot of your requested items), it can be Extremely Aggravating, having to sit there waiting for the massive swarm of bots to slowly get recharged by the handful of roboports they scattered to after not quite reaching you. :evil: :cry:

It should be a fairly straightforward matter to check the distance to a location when determining a new path (say, they've just launched and are heading toward a provider chest, or they've reached the chest and picked up the cargo and are now ready to head toward the requester or the player). If the distance exceeds the distance they are willing to travel with their current amount of power, then do the following: figure out where they will be when they run out of power, find the closest roboport to that location as if they were already there, and set a direct course for that roboport instead. Once they've recharged they can repath, following the same logic, until they reach their destination. Of course, if the target is a moving player, it's possible they'll run low on power and have to divert toward a roboport anyway... But if a player is running away from their poor logi bots, they deserve what they get. :twisted:

Dealing with issues like wide gaps in a logistics network (U or C shaped networks or situations where someone has unwisely placed roboports along all of their rail lines, for example) would undoubtedly require some additional logic to avoid having robots get "trapped" in one area. But all of that would only need to occur at the moment when the bot determines its new path, and all of the ticks between then and when it reaches that destination are just going to be "move toward destination" along with whatever checks they currently run as they move (for things like the player moving out of the logistics coverage area, the destination no longer existing, and such). A well designed base with a dense roboport network running thousands of bots instead of belts would likely avoid the aforementioned pitfalls -- and any time that the distance to be traveled is less than how far they can go on their current charge, no additional logic would be required anyway. So the performance cost shouldn't be too significant even before it gets thoroughly optimized. ;)

Another thing that would optimize the gameplay experience (rather than the speed of the code behind it) would be that when bots are waiting to recharge, particularly if they are out of power, the next bot in line for a certain charging pad should begin moving toward that pad without waiting for that pad to free up, so that the entire process of handling a swarm of bots which all want to recharge from the same roboport is not drastically slowed down by pads sitting empty but reserved for bots that have to cross the distance from where they're waiting. Since bots don't collide with each other, allowing the next bots in line to move into position so they can instantly begin charging as soon as the bot currently being charged finishes would speed up matters even when bots aren't out of power, and the difference when they are would be quite dramatic.

And speaking of waiting to charge, a bot which just wants to fly to a roboport and dock for a nap should never cut in line ahead of bots that currently have jobs to do -- they should always get bumped to the end of the queue. (For that matter, why can't they just recharge on their docking cradle inside the roboport???) And bots which are already carrying cargo should always have higher recharge priority than bots which are on their way to pick up cargo, except maybe for construction bots that have been assigned to deconstruct objects which conflict with blueprint ghosts (like trees and rocks)... Non-conflicting trees can wait, but having a bot holding an item and hovering over the correct location but unable to place it is terrible. Maybe you can optimize the job assignment code to avoid creating that situation in the first place, though! :)



... Another feature that would be lovely to have is a non-mod structure with a small footprint (perhaps 2x2) that serves solely as a robot charging station. No docking space, no need for it to extend the logistic network, and it should only function at all if placed inside the orange-brown logistics coverage area of a full roboport... or at least the green zone. That way, when you're building those factories with no belts and thousands of bots, you don't have to spam hundreds of large, blocky, not-exactly-cheap, and perhaps even more annoyingly, stacking only to 5 at most roboports everywhere, taking up lots of floor space, making it difficult to walk through an area, and filling the map with crazy quilt patterns of dotted yellow lines and weird coverage zone shapes. If a small area needs to operate around 500 bots, just throw down a couple of roboports to give the bots enough docking space and sufficient logistics coverage, and distribute a couple dozen Auxiliary Robot Charging Stations (or towers, or platforms, or whatever you think they should be called) throughout the areas those bots are likely to be frequenting, and you'd have a much more elegant and much friendlier solution. :D
Jap2.0
Smart Inserter
Smart Inserter
Posts: 2424
Joined: Tue Jun 20, 2017 12:02 am
Contact:

Re: Friday Facts #200 - Plans for 0.16

Post by Jap2.0 »

Tallinu wrote:
ske wrote:Are we getting something to make the bots stay in the green zone?
"Optimisation of logistic robot movement" should include making them a little smarter about where they try to move and when. While "staying in the green zone" would be a nice to have feature, there are tons of other simple things that could be improved upon... Like how they often almost reach their destination and then suddenly turn around and travel a long distance away from it because they passed their power threshold, after having wasted a huge amount of that power (and time) flying toward a destination that they could easily have determined was "unreachable" with their current charge level. When one bot occasionally does it that's just a slight nuisance, but when several hundred bots all do that at the same time (for example, when you re-enter your logistics network after using up a lot of your requested items), it can be Extremely Aggravating, having to sit there waiting for the massive swarm of bots to slowly get recharged by the handful of roboports they scattered to after not quite reaching you. :evil: :cry:

It should be a fairly straightforward matter to check the distance to a location when determining a new path (say, they've just launched and are heading toward a provider chest, or they've reached the chest and picked up the cargo and are now ready to head toward the requester or the player). If the distance exceeds the distance they are willing to travel with their current amount of power, then do the following: figure out where they will be when they run out of power, find the closest roboport to that location as if they were already there, and set a direct course for that roboport instead. Once they've recharged they can repath, following the same logic, until they reach their destination. Of course, if the target is a moving player, it's possible they'll run low on power and have to divert toward a roboport anyway... But if a player is running away from their poor logi bots, they deserve what they get. :twisted:

Dealing with issues like wide gaps in a logistics network (U or C shaped networks or situations where someone has unwisely placed roboports along all of their rail lines, for example) would undoubtedly require some additional logic to avoid having robots get "trapped" in one area. But all of that would only need to occur at the moment when the bot determines its new path, and all of the ticks between then and when it reaches that destination are just going to be "move toward destination" along with whatever checks they currently run as they move (for things like the player moving out of the logistics coverage area, the destination no longer existing, and such). A well designed base with a dense roboport network running thousands of bots instead of belts would likely avoid the aforementioned pitfalls -- and any time that the distance to be traveled is less than how far they can go on their current charge, no additional logic would be required anyway. So the performance cost shouldn't be too significant even before it gets thoroughly optimized. ;)

Another thing that would optimize the gameplay experience (rather than the speed of the code behind it) would be that when bots are waiting to recharge, particularly if they are out of power, the next bot in line for a certain charging pad should begin moving toward that pad without waiting for that pad to free up, so that the entire process of handling a swarm of bots which all want to recharge from the same roboport is not drastically slowed down by pads sitting empty but reserved for bots that have to cross the distance from where they're waiting. Since bots don't collide with each other, allowing the next bots in line to move into position so they can instantly begin charging as soon as the bot currently being charged finishes would speed up matters even when bots aren't out of power, and the difference when they are would be quite dramatic.

And speaking of waiting to charge, a bot which just wants to fly to a roboport and dock for a nap should never cut in line ahead of bots that currently have jobs to do -- they should always get bumped to the end of the queue. (For that matter, why can't they just recharge on their docking cradle inside the roboport???) And bots which are already carrying cargo should always have higher recharge priority than bots which are on their way to pick up cargo, except maybe for construction bots that have been assigned to deconstruct objects which conflict with blueprint ghosts (like trees and rocks)... Non-conflicting trees can wait, but having a bot holding an item and hovering over the correct location but unable to place it is terrible. Maybe you can optimize the job assignment code to avoid creating that situation in the first place, though! :)



... Another feature that would be lovely to have is a non-mod structure with a small footprint (perhaps 2x2) that serves solely as a robot charging station. No docking space, no need for it to extend the logistic network, and it should only function at all if placed inside the orange-brown logistics coverage area of a full roboport... or at least the green zone. That way, when you're building those factories with no belts and thousands of bots, you don't have to spam hundreds of large, blocky, not-exactly-cheap, and perhaps even more annoyingly, stacking only to 5 at most roboports everywhere, taking up lots of floor space, making it difficult to walk through an area, and filling the map with crazy quilt patterns of dotted yellow lines and weird coverage zone shapes. If a small area needs to operate around 500 bots, just throw down a couple of roboports to give the bots enough docking space and sufficient logistics coverage, and distribute a couple dozen Auxiliary Robot Charging Stations (or towers, or platforms, or whatever you think they should be called) throughout the areas those bots are likely to be frequenting, and you'd have a much more elegant and much friendlier solution. :D
You say these things would have little impact on performance, but when you have hundreds of thousands of bots pathing, or even tens or hundreds of thousands, it would make a big impact, as the current system literally sends bots in a straight line toward their target and sends them to a roboport when they fall below a certain charge level. I'll deal with these point by point:
  • Pre-determine charge spots to be more efficient: This would be much more complex than you'd think. The amount of energy used would vary depending on speed researches (not super significantly, but enough to make an impact), and then you'd have to repeat this for longer journeys and either use a system similar to avoiding not-covered zones (see below) or repath multiple times, increasing the CPU load. Furthermore, this could result in inefficient distribution of bots at roboports, because bots seem to take how many robots are at or heading to a roboport into their calculations of where to charge. Calculating this at pathing time would result in large inefficiencies here, unless you created extremely convoluted and inefficient calculations.
  • Avoiding non-covered areas: This would be CPU- intensive to check for, and would probably not allow bots to pass through very small areas of green that they otherwise could have. Furthermore, this would require a system to make bots go via "waypoints" (similar to one option for efficient charging), which in itself would make movement more complicated.
  • (You noted this could be bad for performance, and it might be) Have bots move so that they arrive at charger when the other bot leaves: This shouldn't be super hard (it should just be multiplication) but if you're doing it hundreds of times per seconds, it could be noticeable, and all you really want is faster bot charging. Furthermore, you have to account for if the bot has power or not, and speed research, and which charger is open.
  • Bots entering the roboport charge inside: You again just want bots done charging faster.
  • Smart recharge priority: I think I get how you want this to work, but it would probably result in a very complex priority system that would eat up CPU time.
  • Charging station: I see no problems here. I want this.
There are 10 types of people: those who get this joke and those who don't.
ske
Filter Inserter
Filter Inserter
Posts: 412
Joined: Sat Oct 17, 2015 8:00 am
Contact:

Re: Friday Facts #200 - Plans for 0.16

Post by ske »

Jap2.0 wrote:You say these things would have little impact on performance, but when you have hundreds of thousands of bots pathing, or even tens or hundreds of thousands, it would make a big impact, as the current system literally sends bots in a straight line toward their target and sends them to a roboport when they fall below a certain charge level. I'll deal with these point by point:
  • Pre-determine charge spots to be more efficient: This would be much more complex than you'd think. The amount of energy used would vary depending on speed researches (not super significantly, but enough to make an impact), and then you'd have to repeat this for longer journeys and either use a system similar to avoiding not-covered zones (see below) or repath multiple times, increasing the CPU load. Furthermore, this could result in inefficient distribution of bots at roboports, because bots seem to take how many robots are at or heading to a roboport into their calculations of where to charge. Calculating this at pathing time would result in large inefficiencies here, unless you created extremely convoluted and inefficient calculations.
  • Avoiding non-covered areas: This would be CPU- intensive to check for, and would probably not allow bots to pass through very small areas of green that they otherwise could have. Furthermore, this would require a system to make bots go via "waypoints" (similar to one option for efficient charging), which in itself would make movement more complicated.
  • (You noted this could be bad for performance, and it might be) Have bots move so that they arrive at charger when the other bot leaves: This shouldn't be super hard (it should just be multiplication) but if you're doing it hundreds of times per seconds, it could be noticeable, and all you really want is faster bot charging. Furthermore, you have to account for if the bot has power or not, and speed research, and which charger is open.
  • Bots entering the roboport charge inside: You again just want bots done charging faster.
  • Smart recharge priority: I think I get how you want this to work, but it would probably result in a very complex priority system that would eat up CPU time.
  • Charging station: I see no problems here. I want this.
Those points sound somewhat reasonable but I have a strong feeling that there is a good way to circumvent each one that wouldn't cost a lot of CPU time. Simple algorithms would be inefficient, though. It's mostly a question of developer resources because an inefficient interim solution is not an option.
User avatar
featherwinglove
Filter Inserter
Filter Inserter
Posts: 579
Joined: Sat Jun 25, 2016 6:14 am
Contact:

Re: Friday Facts #200 - Plans for 0.16

Post by featherwinglove »

As CPU intensive as such programming would be, it is quite likely that the logistics network can be analyzed and set up for paths on a lookup table that would be much easier on CPU and memory resources in real time. This would result in either a massive lag spike when a new roboport is placed, or a couple of minutes of strange behavior and possibly a lag plateau on weaker systems while the logistics network is analyzed in a thread parallel to the main game. A real world analogy would be how airliner pilots react to an unusual condition: they tend to grab checklists and the QRH (quick reference handbook), which exist because test pilots and engineers working with the first few examples of the aircraft took the weeks and months to figure out the best procedures for these unusual conditions knowing that when the time comes, Sully and Skiles have only minutes to figure it out.
Zavian
Smart Inserter
Smart Inserter
Posts: 1650
Joined: Thu Mar 02, 2017 2:57 am
Contact:

Re: Friday Facts #200 - Plans for 0.16

Post by Zavian »

Actually I don't think they should make bots "smarter".

Factorio is a game where you assemble a factorio out of a set of simple pieces. The core gameplay is using the provided pieces to build a factory. None of the pieces are smart. It is up to the player to design and build an efficient factory. (If that is what the player want to build). If you want that factory to be efficient, then you need to make good choices when you plan and build it.

(There is one area where I wish bots were smarter though. If I'm in a train, on a multiplayer map, whizzing past some some (de)construction work, I don't want my bots to fly out to work on that and get left behind).
ratchetfreak
Filter Inserter
Filter Inserter
Posts: 952
Joined: Sat May 23, 2015 12:10 pm
Contact:

Re: Friday Facts #200 - Plans for 0.16

Post by ratchetfreak »

featherwinglove wrote:As CPU intensive as such programming would be, it is quite likely that the logistics network can be analyzed and set up for paths on a lookup table that would be much easier on CPU and memory resources in real time. This would result in either a massive lag spike when a new roboport is placed, or a couple of minutes of strange behavior and possibly a lag plateau on weaker systems while the logistics network is analyzed in a thread parallel to the main game. A real world analogy would be how airliner pilots react to an unusual condition: they tend to grab checklists and the QRH (quick reference handbook), which exist because test pilots and engineers working with the first few examples of the aircraft took the weeks and months to figure out the best procedures for these unusual conditions knowing that when the time comes, Sully and Skiles have only minutes to figure it out.
You can't make the robo network optimize in parallel and then use the result whenever it's done because that is not deterministic.
d3x0r
Filter Inserter
Filter Inserter
Posts: 316
Joined: Sun Jun 04, 2017 8:56 am
Contact:

Re: Friday Facts #200 - Plans for 0.16

Post by d3x0r »

Was playing with generating maps earlier; 1) I'd love more granular sliders, the jump between two levels is a huge change in output.
2) I know that resource richness increases with distance, but what about size of patches? Was really working hard to generate a semi challenging rail map; and either the patches were too large and so far apart at the start, or there were too many tiny patches to make a train stop seem very useful... if I could make lots of small spots in the starting area and then increase the size and decrease the frequency with distance was really what I was looking for. (in addition to increased richness).

I know the map options don't really mean what they imply and they interact a lot; like really frequency seems a lot more determined by the size setting, and size more by the frequency. I got to a good patch size, but then increased the frequency and everything shrank, so I increased the patch size, and the frequency went down too much. So back to (1) sliders would give me much more flexibility than small->normal which is a huge step.
Finally settled on this
mrvn
Smart Inserter
Smart Inserter
Posts: 5969
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: Friday Facts #200 - Plans for 0.16

Post by mrvn »

ratchetfreak wrote:
featherwinglove wrote:As CPU intensive as such programming would be, it is quite likely that the logistics network can be analyzed and set up for paths on a lookup table that would be much easier on CPU and memory resources in real time. This would result in either a massive lag spike when a new roboport is placed, or a couple of minutes of strange behavior and possibly a lag plateau on weaker systems while the logistics network is analyzed in a thread parallel to the main game. A real world analogy would be how airliner pilots react to an unusual condition: they tend to grab checklists and the QRH (quick reference handbook), which exist because test pilots and engineers working with the first few examples of the aircraft took the weeks and months to figure out the best procedures for these unusual conditions knowing that when the time comes, Sully and Skiles have only minutes to figure it out.
You can't make the robo network optimize in parallel and then use the result whenever it's done because that is not deterministic.
Maybe you can, maybe you can't. It has nothing to do with being determinsitic. That is a completely different issue.

You don't even need to analyze the network much. Just build a table of waypoints how to reach any roboport from any other roboport. The number of roboports is relatively small and the tables can be updated when a new roboport is added. Then do the following:

- Keep track of which roboport is in range of bot.
- If goal is not in range (of the same roboport) then set a waypoint to roboport nearer to it (table lookup), otherwise set the goal as waypoint.
- If the next waypoint can be reached with the current charge then recharge at the current/nearest roboport.

This will also solve the problem of not leaving the green area since the bot will follow the roboports as waypoints instead of cuting across an U.
Jap2.0
Smart Inserter
Smart Inserter
Posts: 2424
Joined: Tue Jun 20, 2017 12:02 am
Contact:

Re: Friday Facts #200 - Plans for 0.16

Post by Jap2.0 »

mrvn wrote:You don't even need to analyze the network much. Just build a table of waypoints how to reach any roboport from any other roboport. The number of roboports is relatively small and the tables can be updated when a new roboport is added. Then do the following:
Some large bases have thousands or more roboports. That means with a path from each roboport to each other roboport is a table of millions of paths to solve a problem no one can agree on while having a questionable impact on performance.

You probably want that table stored in ram, so even if each path is only a few bytes, that could be several dozen megabytes. Then, having to find a point in that table with an unknown location which could be constantly changing, and having to generate that table in the first place...

I don't think this will ever happen.
There are 10 types of people: those who get this joke and those who don't.
User avatar
featherwinglove
Filter Inserter
Filter Inserter
Posts: 579
Joined: Sat Jun 25, 2016 6:14 am
Contact:

Re: Friday Facts #200 - Plans for 0.16

Post by featherwinglove »

The lookup table could be kept fairly small because it would only need to contain the path results for routes that aren't very obvious, such as when the best route is nowhere near the shortest, as is often the case in oddly shaped bases. When pathing time comes, the bot checks to see if its destination is non-adjacent (adjacent cases are super simple). If it isn't, then it checks the table to see if there is are path notes there for its destination. If there are, it follows them. If there aren't, it's because the network analysis that made the table figured the simple pathing rules were good enough and either didn't make an entry, or dumped it after comparing its similarity to standard pathing. Only the routes that are a pain in the CPU to figure out need to be in the table. I do agree with you that mrvn's table of waypoints idea sounds a lot like a n^2 problem. With this limitation on the table, you only have a scaling problem if you expand your base in a highly non-contiguous manner, with many large areas that lack roboport coverage in its interior. I've never seen anyone do this out to even dozens of roboports, let alone thousands.

(Just in case there are any confused bystanders thinking that a central base fed by resource outposts sounds "non-contiguous", I'm talking about just the base which has the logistics network. Players rarely incorporate outposts and bases into the same robotic logistics system, although with an implementation like this to keep the robots from wandering through biter-infested wilderness, they might do so more often.)
pleegwat
Filter Inserter
Filter Inserter
Posts: 278
Joined: Fri May 19, 2017 7:31 pm
Contact:

Re: Friday Facts #200 - Plans for 0.16

Post by pleegwat »

featherwinglove wrote:I do agree with you that mrvn's table of waypoints idea sounds a lot like a n^2 problem.
That's just space. Computationally, it's travelling salesman, which is NP.

I'd hazard it's probably cheaper computationally and more effective to route within the coverage area instead of between explicit roboports. Then only if the bot determines it does not have enough charge for its intended path, it can schedule to detour via a convenient roboport near its path.

Really though, though NP problems are not solved as such, there is certainly plenty of reading material.
mrvn
Smart Inserter
Smart Inserter
Posts: 5969
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: Friday Facts #200 - Plans for 0.16

Post by mrvn »

pleegwat wrote:
featherwinglove wrote:I do agree with you that mrvn's table of waypoints idea sounds a lot like a n^2 problem.
That's just space. Computationally, it's travelling salesman, which is NP.

I'd hazard it's probably cheaper computationally and more effective to route within the coverage area instead of between explicit roboports. Then only if the bot determines it does not have enough charge for its intended path, it can schedule to detour via a convenient roboport near its path.

Really though, though NP problems are not solved as such, there is certainly plenty of reading material.
First of this is not traveling salesman. You are not trying to find a path that visits all roboports in the shortest total distance. It's a simple graph problem. Given a network where each roboport has a shortest route to every other adding a roboport is simple. You take the table from each roboport in reach (usually no more than 4), add the distance to that roboport and then build your own table taking the shortest entry from the tables. Now I reaslize that removing a roboport is expensive though and needs a full table rebuild. The network may even split in two.

As for having 1000 roboports and therefor the table needing a million entries. So what? That would be 4Mib of memory where each cell holds a 32bit ID of the next roboport. Compared to the GiB of memory already used that is negible. But I totally agree that a lot of the time just picking the roboport thats in the general direction of the destination will be the right thing. So the table could be made sparse to save space.

Or just do an A* search every time you plan a path. It's 1000 roboports for a big base and most of that will cover the whole area on the inside. Unless you have a very long U shaped base A* will include nearly no wrong roboports.
Jap2.0
Smart Inserter
Smart Inserter
Posts: 2424
Joined: Tue Jun 20, 2017 12:02 am
Contact:

Re: Friday Facts #200 - Plans for 0.16

Post by Jap2.0 »

mrvn wrote:
pleegwat wrote:
featherwinglove wrote:I do agree with you that mrvn's table of waypoints idea sounds a lot like a n^2 problem.
That's just space. Computationally, it's travelling salesman, which is NP.

I'd hazard it's probably cheaper computationally and more effective to route within the coverage area instead of between explicit roboports. Then only if the bot determines it does not have enough charge for its intended path, it can schedule to detour via a convenient roboport near its path.

Really though, though NP problems are not solved as such, there is certainly plenty of reading material.
First of this is not traveling salesman. You are not trying to find a path that visits all roboports in the shortest total distance. It's a simple graph problem. Given a network where each roboport has a shortest route to every other adding a roboport is simple. You take the table from each roboport in reach (usually no more than 4), add the distance to that roboport and then build your own table taking the shortest entry from the tables. Now I reaslize that removing a roboport is expensive though and needs a full table rebuild. The network may even split in two.

As for having 1000 roboports and therefor the table needing a million entries. So what? That would be 4Mib of memory where each cell holds a 32bit ID of the next roboport. Compared to the GiB of memory already used that is negible. But I totally agree that a lot of the time just picking the roboport thats in the general direction of the destination will be the right thing. So the table could be made sparse to save space.

Or just do an A* search every time you plan a path. It's 1000 roboports for a big base and most of that will cover the whole area on the inside. Unless you have a very long U shaped base A* will include nearly no wrong roboports.
The point is that no matter how hard you try, you (probably) won't be able to find a solution less computationally intensive than creating a straight line and occasionally checking "if charge < x then charging logic". Changing it would also require a lot of work and could create a lot of bugs. There is also the problem of regenerating tables if you use that method, with lag spikes or wacky behavior, and possibly bugs. Bot pathing during that time could also be an issue.
There are 10 types of people: those who get this joke and those who don't.
mrvn
Smart Inserter
Smart Inserter
Posts: 5969
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: Friday Facts #200 - Plans for 0.16

Post by mrvn »

Jap2.0 wrote:
mrvn wrote:
pleegwat wrote:
featherwinglove wrote:I do agree with you that mrvn's table of waypoints idea sounds a lot like a n^2 problem.
That's just space. Computationally, it's travelling salesman, which is NP.

I'd hazard it's probably cheaper computationally and more effective to route within the coverage area instead of between explicit roboports. Then only if the bot determines it does not have enough charge for its intended path, it can schedule to detour via a convenient roboport near its path.

Really though, though NP problems are not solved as such, there is certainly plenty of reading material.
First of this is not traveling salesman. You are not trying to find a path that visits all roboports in the shortest total distance. It's a simple graph problem. Given a network where each roboport has a shortest route to every other adding a roboport is simple. You take the table from each roboport in reach (usually no more than 4), add the distance to that roboport and then build your own table taking the shortest entry from the tables. Now I reaslize that removing a roboport is expensive though and needs a full table rebuild. The network may even split in two.

As for having 1000 roboports and therefor the table needing a million entries. So what? That would be 4Mib of memory where each cell holds a 32bit ID of the next roboport. Compared to the GiB of memory already used that is negible. But I totally agree that a lot of the time just picking the roboport thats in the general direction of the destination will be the right thing. So the table could be made sparse to save space.

Or just do an A* search every time you plan a path. It's 1000 roboports for a big base and most of that will cover the whole area on the inside. Unless you have a very long U shaped base A* will include nearly no wrong roboports.
The point is that no matter how hard you try, you (probably) won't be able to find a solution less computationally intensive than creating a straight line and occasionally checking "if charge < x then charging logic". Changing it would also require a lot of work and could create a lot of bugs. There is also the problem of regenerating tables if you use that method, with lag spikes or wacky behavior, and possibly bugs. Bot pathing during that time could also be an issue.
The simplest and least intrusive change would also be totally fix the problem and would not cost any more time in the long run, just move some calculations to earlier:

- Plan your straight line just like now.
- Compute point where you run out of charge (cheaper than checking every tick for sure)
- If destination is too far away find recharging station from where you would run out of juice. (this part is just done earlier)
- Fly there directly. (this will actually save time since the distance will generally shorter)
- If already there send a signal that the bot is stuck. (better than constantly flying back and forth)
Zavian
Smart Inserter
Smart Inserter
Posts: 1650
Joined: Thu Mar 02, 2017 2:57 am
Contact:

Re: Friday Facts #200 - Plans for 0.16

Post by Zavian »

@mrvn Is your "solution" going to actually make the challenge of laying out your factory more or less interesting/engaging for the player. Note I'm deliberately not asking if it will make it easier for a player to build an efficient factory. Instead I'm asking if this change would make laying out a factory more or less interesting/engaging/challenging for players? Because if it makes the gameplay less interesting, (and in my opinion I think it probably would), then the devs shouldn't implement it, because it detracts rather than enhances the gameplay.

As an alternative that also shouldn't be implemented, the devs could make it so that roboports continuously broadcast power to all bots in their range, and bots never leave a roboport's range. Hence bots never need to stop to recharge, and never run out of charge. I think that would also solve your issue, and is probably even easier to implement.

As I have said before Factorio's core gameplay comes from laying out and designing your factory. Managing the interactions between the game's entities is a large part of that. If you want an efficient factory, then it is up to you as the factory's designer to properly design your factory. And managing bot recharge is one of those challenges. As such making bots smarter can simply the game's challenges and detract from the gameplay.
mrvn
Smart Inserter
Smart Inserter
Posts: 5969
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: Friday Facts #200 - Plans for 0.16

Post by mrvn »

It changes nothing really on the design of your factory. It just makes the gameplay way less annoying. I don't know how often I stood somewhere waiting for some logistic robots. Then you see them comming and comming and 2m before you they turn around and head back to recharge. Hours later, it fells like, they finally come back and deliver.

In game character must be like: Seriously, we can build a rocket to go to another star but robots don't check their battery before flying somewhere? Is that why we crashed? Didn't take enough fuel?
Jap2.0
Smart Inserter
Smart Inserter
Posts: 2424
Joined: Tue Jun 20, 2017 12:02 am
Contact:

Re: Friday Facts #200 - Plans for 0.16

Post by Jap2.0 »

mrvn wrote:It changes nothing really on the design of your factory. It just makes the gameplay way less annoying. I don't know how often I stood somewhere waiting for some logistic robots. Then you see them comming and comming and 2m before you they turn around and head back to recharge. Hours later, it fells like, they finally come back and deliver.

In game character must be like: Seriously, we can build a rocket to go to another star but robots don't check their battery before flying somewhere? Is that why we crashed? Didn't take enough fuel?
Two things you might be missing:

Computing where they will run out of charge is more complicated than you'd think, as you have to factor in speed bonuses and either change all the paths when a new speed bonus comes along or keep the paths and make bots charge earlier than is perhaps necessary. Furthermore, robots appear to do some logic about which roboport to use based on distance and wait times, and using your idea either bots would not do this logic, and therefore sometimes no spread out between roboports (which would be worse than the "problem" you are trying to solve) or would do the logic when they created their path, which would lead to wierd charging cycles where one roboport is overused and another is underused, and then they flip, and so on. Either way, players would complain, and perhaps label it as a bug. So you see, it wouldn't really help the problem and it would probably be a waste of the developers' time.
There are 10 types of people: those who get this joke and those who don't.
vanatteveldt
Filter Inserter
Filter Inserter
Posts: 947
Joined: Wed Nov 25, 2015 11:44 am
Contact:

Re: Friday Facts #200 - Plans for 0.16

Post by vanatteveldt »

Maybe an easier "solution" would be to special case logistic deliveries to the player to let bots go deeper into the red when near the player. Then after delivery they can take the slow boat to the charging station, but why would we care after we got the stuff?
mrvn
Smart Inserter
Smart Inserter
Posts: 5969
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: Friday Facts #200 - Plans for 0.16

Post by mrvn »

Jap2.0 wrote:
mrvn wrote:It changes nothing really on the design of your factory. It just makes the gameplay way less annoying. I don't know how often I stood somewhere waiting for some logistic robots. Then you see them comming and comming and 2m before you they turn around and head back to recharge. Hours later, it fells like, they finally come back and deliver.

In game character must be like: Seriously, we can build a rocket to go to another star but robots don't check their battery before flying somewhere? Is that why we crashed? Didn't take enough fuel?
Two things you might be missing:

Computing where they will run out of charge is more complicated than you'd think, as you have to factor in speed bonuses and either change all the paths when a new speed bonus comes along or keep the paths and make bots charge earlier than is perhaps necessary. Furthermore, robots appear to do some logic about which roboport to use based on distance and wait times, and using your idea either bots would not do this logic, and therefore sometimes no spread out between roboports (which would be worse than the "problem" you are trying to solve) or would do the logic when they created their path, which would lead to wierd charging cycles where one roboport is overused and another is underused, and then they flip, and so on. Either way, players would complain, and perhaps label it as a bug. So you see, it wouldn't really help the problem and it would probably be a waste of the developers' time.
I grant you that updating for new speed bonuses would be tricky. But I doubt simply ignoring that would have any noticeable effect. So what if bots recharge a bit too early because with the new bonus they could have gotten 5m further. It probably wouldn't have changed the fact that they need to recharge and probably at the same recharging station. And even if not then after the bot recharged at maybe the wrong charging point all will be well again. You could think of it like the bot only gets the upgrade when it next hits a charging point. I think we can safely ignore this.

As for the logic about which roboport to use. Keep that logic. It is possible that you get an oscilating use pattern out of it like you describe but then it already is possible as is. I'm assuming bots "reserve" a charging port when they route to a charging station. So the station not only knows how many bots are at the station but also how many are on the way. Because otherwise all bots would go to the same station till the first arrives and changes the metric. My idea might change when the bots reserve the charging port. Might be earlier now or later. When the flight path is near a charging station it will be earlier but when the direct flight is far from a charging station the current code will fly into wilderness and then very slowly fly back to a charging station. In that case flying direct will be quicker and the reservation will be for a shorter time and thus better.

So I'm unsure if my idea would make the balancing better, worse or have no noticeable effect. Personally my roboports tend to be near maximum distance in a nice grid pattern. I don't think there is much balancing going on at all since usually one roboport has a clear distance advantage over all the others.
Muche
Filter Inserter
Filter Inserter
Posts: 643
Joined: Fri Jun 02, 2017 6:20 pm
Contact:

Re: Friday Facts #200 - Plans for 0.16

Post by Muche »

@mrvn, since bots would compute their path beforehand, similar to how trains do, does this proposal have the potential to trade current efficiency bottlenecks (with best-practice ways how to solve them) for currently unknown ones (but in a way similar to train ones)?
Post Reply

Return to “News”