Friday Facts #200 - Plans for 0.16

[featherwinglove]

While artillery train is probably fun it is generally useless because we have no way of detecting biter nests automaticly to call for the train.

It's called "radar", kid. The orbital ion cannon has implemented the automatic destruction of freshly scanned biter nests with event.on_sector_scanned since the '90s a while ago. In fact, it is probably far, far easier to use arty train defensively than offensively. One would need to build siding with a stop on the main line (siding so it doesn't block resource trains while at the stop), then, with a bit of coding from a mod and/or Wube, a radar detecting spawners in a certain range, something the user might designate with a YARM-like gadget or GUI widget, calls a train to that stop via the circuit network. The arty train goes to that stop, sets up, lobs a few rounds over the wall, then packs up and leaves while the laser turrets at the wall mop up the survivors coming to search for the arty train that blew up their newest saloon from over the horizon.

I'd say more, but NotABiter has it all pretty much covered

Although (not sure if I'm adding anything), it wouldn't be all that hard to use an arty train offensively even without blueprints. An early arty train campaign (early as in think SL2 prior to logistics robots, and possibly even prior to solar and nuclear power, laser turrets) might start like this:

1. Lay a length of track and put your freshly built locomotive, cargo wagon with ammunition, and artillery car on it. Maybe you'll drive it manually until train station develops, maybe you already have train stations. Let's assume the latter. The arty wagon sets up.

2. Run out ahead wth some rail, power lines, and place a few turrets to defend the rail head and arty train from survivors. Once ready, drop a radar and start designating targets on the strategic map. This will save a helluva lot of turret ammunition vs. old fashioned turret creep.

3. Once the area is secure enough and your rail head can no longer be covered by the artillery, place a train stop and call the artillery train to it. You don't have to drive it manually if you don't want to.

4. Rinse and repeat.

5. Once the cargo wagon has run out of ammunition, you'll probably want to go back to base to set up a train station and supply train that loads up with ammunition and/or propellant, fuel, turret ammunition, repair kits, fishes, grenades (for the trees), etc.. Every now and then, call the supply train, normally loading up at the loading station back home, to a train stop behind your artillery train, or the same stop, as trains do avoid colliding in such conflicts and will still stop behind the artillery train. Load up and send it back home.

6. Notice how the territory you've conquered is longer and thinner than a Bond martini lemon peel

[Grimshad]

FFF is one of my favorite things to read every week. Don't stop.

Also please add the map preview in the game during game creation so I can stop reloading the game until I get one I like. Lol

[TheSAguy]

A week late here, but I think you guys should release Mountains, Rivers, Terrain and wildlife diversity as a DLC!

[Gergely]

A week late here, but I think you guys should release Mountains, Rivers, Terrain and wildlife diversity as a DLC!

Seriously?

Only publishers like having DownLoadableContents. Everyone else (game developers, programmers and end users) hate them!

[orzelek]

A week late here, but I think you guys should release Mountains, Rivers, Terrain and wildlife diversity as a DLC!

Seriously?

Only publishers like having DownLoadableContents. Everyone else (game developers, programmers and end users) hate them!

Tbh if they would do an expansion that would add height to terrain (thats a lot of work for them most likely) that would allow train tunnels/bridges and add stuff like cliffs, rivers (hydro power?) I'd gladly pay for it. Same with space station as an expansion/DLC.

[TheSAguy]

A week late here, but I think you guys should release Mountains, Rivers, Terrain and wildlife diversity as a DLC!

Seriously?

Only publishers like having DownLoadableContents. Everyone else (game developers, programmers and end users) hate them!

Tbh if they would do an expansion that would add height to terrain (thats a lot of work for them most likely) that would allow train tunnels/bridges and add stuff like cliffs, rivers (hydro power?) I'd gladly pay for it. Same with space station as an expansion/DLC.

That's exactly my thought. They have given us so much, I have no problem paying for these additional features, since I know they will put a lot of effort in them!

[featherwinglove]

Comment score below threshold (show)

A week late here, but I think you guys should release Mountains, Rivers, Terrain and wildlife diversity as a DLC!

Something I miss about Reddit

[Tallinu]

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.

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.

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.

[Jap2.0]

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.

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.

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.

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.

[ske]

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.

[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]

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]

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]

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

>>>AAAPACEAAQACBQcAAAAEAAAAY29hbAMCAgoAAABjb3BwZXItb3Jl
AQQBCQAAAGNydWRlLW9pbAUCAQoAAABlbmVteS1iYXNlAQEECAAAAGl
yb24tb3JlAQQBBQAAAHN0b25lBAMCCwAAAHVyYW5pdW0tb3JlBAMCbc
fj2oCEHgCAhB4ABQABAQF7FK5H4XqUPwEAAAAAAAAuQAEAAAAAAADwP
wEAAAAAAFi7QAEAAAAAAOCFQAEAAAAAAFirQAEAAAAAAIjDQAEAAAAA
AECfQAEAAAAAAEB/QAEAAAAAAECPQAEzMzMzMzPzPwEzMzMzMzPzPwF
7FK5H4Xp0PwEAAQAAAAAAAAhAAQAAAAAAAAhAAXsUrkfheoQ/AQABAQ
GN7bWg98bAPgH8qfHSTWJgPwFpHVVNEHXvPgEBAQcAAAABAgAAAAECA
AAAAZqZmZmZmbk/AQAAAAAAAABAAQAAAAAAAOA/AZqZmZmZmdk/Ac3M
zMzMzOw/AQUAAAABFAAAAAFAOAAAAcBLAwABEA4AAAGgjAAAASAcAAA
BAAAAAAAAPkABAAAAAAAAFEABZmZmZmZm9j8BMzMzMzMz4z8BMzMzMz
Mz0z8BAAAAAAAACEABAAAAAAAAJEABPAAAAAEeAAAAAcgAAAABBQAAA
AEAAAAAAAAAQAEBAQAAAAAAAFlAAQUAAAABGQAAAAEAAAAAAAAkQAEy
AAAAAQAAAAAAAD5AAWQAAAABmpmZmZmZyT8BMzMzMzMzwz8BMzMzMzM
z0z8BMzMzMzMz0z8BAAAAAAAAJEABAAAAAAAANEABAAAAAAAAPkABAA
AAAAAAFEABAAAAAAAAPkABAAAAAAAAJEABAAAAAAAACEABCgAAAAFkA
AAAAWQAAAAB6AMAAAEAAAAAAADgPwHQBwAAAQAAAAAAQH9AAwAAAAAA
AAAAAAAA8D/I8gR3<<<

[mrvn]

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]

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.

[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]

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]

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]

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.