## Personal robots prioritizing nearest first

Post your ideas and suggestions how to improve the game.
JohnyDL
Filter Inserter
Posts: 512
Joined: Fri May 16, 2014 3:44 pm
Contact:

### Re: Personal robots prioritizing nearest first

mrvn wrote:
JohnyDL wrote:here's a basic reason why prioritising bots based on distance really won't work (without even needing to look at the code)

for every target you'll need to work out the distance to it so every tick you need to do ((playerX-targetX)^2+(playerY-targetY)^2)^0.5 to get the distance for every blue print in the world and that calculation doesn't take one processor cycle it takes at least 3 for the additions alone and the multiplication depending on how it's done dozens of cycles, might not sound like a lot but if you have 1,000 BPs you're adding 10k+ things to how many operations your computer has to do each tick already and thats without having to fetch and load the data extra times to do this calculation
First drop the sqrt(). You can compare d^2 instead of d to get the same order.
I already conceded that
JohnyDL wrote:Manhattan distance would work (actually doing the pythagorus but not square root would still work as a metric as comparing distances it's just a scale thing) but it wouldn't look right as a diamond of action rather than a circle.
mrvn wrote:Next add some brains and memory. You do not compute the distance of every ghost every tick. And once computed the distance doesn't change unless the player moves. Even if the player moves you only have to recompute the distance of ghosts within range, which you can do by iterating over chunks.
The only way to know what's in range is to run the surface check on the area closest to the player. I talked about that here
JohnyDL wrote:
SockPuppet wrote:- Compute ranges in blocks of 6x6 instead of 1x1, so that a bot first travels to the 6x6 area, and inside that area to its destination. You have 25 6x6 blocks (30x30 = 25x6x6) for a mk1 roboport, and then 36 per square. That's 61 computations total, instead of 900, at the cost of a suboptimal route for your bots. Blame the underdeveloped bot AI if you want an excuse. They will still perform better at deconstructing by clearing whole areas faster.
That's not how surface search works you can't even quicken the search by looking chunkwise at 32x32 tiles cause it will ask all 1024 tiles in turn.
SockPuppet wrote:- Worst case max range is a 183x183 range (mk2 armor, 1 portable reactor, rest mk2 personal roboports), which spans more than one screen when zoomed out. The travel time of the bots takes longer than to compute the max distance. Also, the bots tend to run out of power before returning from such a roundtrip.
Yup I'm complaining about 900 tile checks the devs are saying it won't work with a 30x30 so 33600 might be a problem.
SockPuppet wrote:- If you still want to play the computational power card: Once you reach megabases with thousands of bots, a few hundred trains and have explored the map quite a bit you experience drops in UPS. Anything less works fine. And this is still on 0.15! We can currently create a massive factory with dozens of players, and still have it playable for all players.
Because of optimisation and not adding ideas that will at best add 1.6% extra processing power at worst, with this way of only looking at the bit in the personal roboport area more than double the runtime 33600 checks per player which are multiple instructions each is already well into the multiple hundreds of thousands of operations. But the way the devs describe it and the fact the game would have to load from RAM locations 33600 times per would soon add up, RAM is measured in MHz after all not GHz so multiply 33600 by 60, I'd say that's 2 million probably none sequential RAM calls per second per player. And that's assuming none is in page files on disk. Nope not possible. I mean seriously not possible, 4 players with these roboports would kill a high end machine with quad channel memory. And remember that's only checking the locations of the surface and it's properties assuming the check can be done in exactly one RAM cycle each, that doesn't even include the fact you have to load the program out of RAM and process that too.
mrvn wrote:
JohnyDL wrote: Then you have to sort the list based on this metric, even using a quick sort a 1000 item array takes 2000 comparisons minimum, and 1000s of swaps and reorganising of the data structure even being generous and saying this takes only 20k cycles to do is still a lot

Combined with a little overhead this reordering of items to make it near first then far probably adds between 100k and 1m clock cycles for just 1000 BP objects (I have single blueprints with more items than that). A reasonable CPU is 3.6GHz, it has to do 60 ticks per second, so factorio only has 60m clock cycles to play with per tick and even then the operating system doesn't give it all of those, resulting in this suggestion basically asking for relatively small size blueprinting to cut an extra 1.6% off factorio's available time (which would add noticeable UPS effects given they were super happy about saving 2% in an FFF a few weeks ago) to make personal robots only a little more life like/better when life like robots would have orders of magnitude more processing power as each one could have a 3.6GHz processor and work in parallel not sequentially.
You also don't compare the distance of every ghost every tick. The best data structure for this is a heap with the nearest ghost at the top. Removing a ghost takes O(log n) time and leaves the next nearest ghost at the top of the heap.

If recomputing the distance (and rebuilding the heap) is too much work for one tick then don't do it. Store the distance and player position for each ghost. Then when processing the heap each time you compare distances first check if the stored distance is up-to-date. If not then recompute. That way you recompute at most O(log n) distances per tick. So with 65536 ghosts within personal roboport range that would be at most 16 distance computations and compares per tick. 20 for a million ghosts, 30 for a billion ghosts.

So instead of your 20k cycles and 1.6% time for 1000 items I'm asking for 200 cycles and 0.016% time to make personal roboports + walking around 2-10 times faster depending on range.
So your solution adds more RAM requirements on the game and duplicates the data leading to the game having to manage keeping the data synced in memory. If I'm also reading correctly I think you're also saying to keep the heap Locally could be calculated at a different time to Server-Side which would cause Desyncs between what my heap is planning and the server has cause my computer and the server are at different speeds and mine can calculate for me but doesn't think other players are important but the server was delayed in reprocessing because it was dealing with other players.

Personally I don't think there's enough time to build the heap in the first place during ANY tick, And suggesting it's O(log2(n)) based on pre-organised data rather than O(n^2) which is the time requirements for the surface search to build the organised data in the first place is simplistic.

You ignore circumstances like placing blueprints anywhere would require a complete rebuild because the heap doesn't know if this new blueprint is in or out of the area or out without either calculating the distances to all the new items O(n) time, n=number of orders, or rescanning the local area O(n^2) time, n=diameter of search area in tiles. Bots building things or players erasing blueprints should cause you to have to reheap for similar reasons or you might end up with bots being issued rescinded orders or even completed orders, that's even if we assume the player doesn't move. If the player does move then the heap needs to scan and add the edges of the range which are in the order O(4n), n=diameter of search area in tiles, each tick anyway. I and I understand you've basically built a queue and you're taking from the top and dismissing but it doesn't help if the player system competes with the roboport network and causes duplicated jobs sent out rather than working with it. The heap has no way to handle an order it doesn't have the item for, it could be dismissed or sent to the bottom of the heap, but that assumes the item won't be added to the player's inventory and the next tick, or the tick after that so you end up with the item being stuck at the top of the heap being recalculated each time for no reason if the item isn't delivered or breaking the player centric model if it's moved to the bottom and becomes available.

And any solutions you come up with to address the issues would add to the compute time, and at this point that's more RAM access time rather than cycles remember.

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

### Re: Personal robots prioritizing nearest first

Still some confusion here.

A heap takes O(n) time to build where n is the number of ghosts you have (in range).

Finding all ghosts in range from scratch takes O(n^2) time, where n is the width/height of the area reachable if I get you right.
I would think it should be O(m^2 + g) where m is the width/height in chunks and g the number of ghosts. But that assumes there is a quick way to get a list of ghosts for a chunk that doesn't check every single tile.

Don't confuse the two.

Next: Ideally you only scan the whole roboport area once when the roboport is added. Then when the player moves you only scan the new parts, which takes it from O(n^2) to O(n). It has also been suggested to:

a) stop roboports when moving fast (like in a train or car) since bots don't even work at that speed
b) shrink the roboport area as you move and then slowly increase it again every few ticks. So the faster you move the smaller the area gets and the less new tiles need to be scanned. Then when you stop moving the area expands back to full over enough ticks to spread the work.

Option b also means that when a roboport is added you can start it with range 0 and then increase to spread the work over many ticks.

Placing a blueprint is O(n) and it already checks the roboport range for all players. You know where every item is placed so no scanning of any tiles is needed. You do have to update the players heap though so potentially it is O(n * log(n) * num_players), which could be a significant increase. The increase of quality of live by far makes up for that though. Blueprints, especially large ones, aren't placed every tick.

As for keeping all players and roboports in sync: That problem is already solved and all clients do all the computations and come to the same conclusion every tick. If the game decides a ghost will be palced by a roboport then it gets removed from all players heaps. That is O(log(n) * num_players) where n is the max number of ghosts in a heap.

As for ghosts where the player has no item for: The way bluebuild seems to handle that is to put the ghost at the back of it's list. Then later, when it has processed all other ghosts, and you now have the item, it is retried. Moving also resets the build order and retries. You can't leave the item at the top of the heap because there is no good way to get the second (third, fourth) nearest item from the heap. So moving impossible ghosts out of the heap for later retry is a must.

And yes, all this needs more ram, I believe O(n * num_players), where n is the number of ghosts total. But O() notations doesn't really tell you how much ram will be needed. The hidden constant factor matters. I don't think it would be infeasable.. But all per tick actions would be O(log(n) * num_players) where n is reasonably small. And player movement actions would be O(n) where n is max 136 or something like that, again small.

Don't forget that all the actions of placing ghosts, erasing ghosts, deciding what roboport should fulfill a ghost, deciding if a ghost is in a players range and so on are all already in the game. Changing the order from a sequential list to a heap adds nothing new there, it only changes the order in which ghosts are processed and changes the costs for insert and remove from O(1) to O(log(n)). I don't believe n is big enough in the game to outweigh the improvement if QOL. Actually the bigger the roboport area and n is the more QOL improves because you gain more when moving around.

JohnyDL
Filter Inserter
Posts: 512
Joined: Fri May 16, 2014 3:44 pm
Contact:

### Re: Personal robots prioritizing nearest first

Your method of handling impossible ghosts leads back to the original solution, which handles things now, there's a list it doesn't matter what order and you move things to the back when impossible. Impossible being no robot or no item. Ordering the this list based on distance to the player has no long-term benefit as items are skipped because they have no robot available rather than no item.

In order to counter the fact that bots are issued in one tick by the personal roboport and then several dozen items are skipped before the next personal roboport robot becomes available one at a time usually in different ticks and not necessarily in sequential ticks when any robot becomes available (personal or infrastructure) you have to recalculate the heap.

I say that because if you have 2 items to do right next to you at the top of the heap tick one you get a robot the first is requested and issued the second is requested and the item sent to the back of the list due to 'impossible no bot' the next bot becomes available exactly one tick later and if the heap isn't recalculated it goes to do a far off job rather than the second close item.

The heap is O(log2(n)) only so long as whatever metric is used to order the heap is a constant, distance to an erratically moving item is far from constant. Pythagoras would turn it into a O(log2(g)+cpg) where g the number of ghosts on the heap and p is the number of players and c is some constant related to the Pythagoras calculation time.

The problem with increasing the radius is that you'd have it work out the rate based on the individual computer if my delta is 2 tiles and yours is 4 on the same cooperation because different computer speeds then we get get a desync, if the delta on local players is prioritized (which is what is wanted, I want my QOL now is the whole philosophy of this idea) then that leads again to desyncs. Or you have every delta sync up someone has a delta of zero and everyone's range resets at somepoint and no-one has the QOL anyway and people report it as bugs. More trouble than it's worth. If the slow computer leaves how do you manage increasing the delta shrinking it is easy increasing without problems is hard.

There is no chunkwise list of ghosts, mod said it I've repeated it.

You don't intrinsically know where every blueprint is when it's added you have to do the Pythagoras steps, in some cases that would be more work than going the surface scan. My solar blueprint is 7000 ghosts without deconstruction orders, sometimes I place them locally, sometimes from map mode, if there are other players I could place a ghost near them, basically it's a blueprint that when placed needs to recalculate the heap of the order O(c7000p) not O(log2(7000+g), either the process needs to do the tile scans locally or the Pythagoras for the entire blueprint and then do a complete rebuild of the heap. I might not place it every tick but a drop in UPS every time a blueprint like that is placed by any player would not be a QOL improvement to me or many people I'm on servers with it would however be an opportunity to troll, place an astronomically large blueprints and erase it over and over to irritate other people. You may not need to do surface scanning for blueprints with 100 items but that doesn't necessarily improve things, right now placing a blueprint is O(g) to the list to the queue of to do items, adding it to a heap instead is O(cgp+log2(g)) or O(cpd^2+log2(g)) where d is the diameter of the square you're scanning.

If you want to try out adding a 'tiny' bit of code to each ghost item and seeing how it affects UPS I suggest you download the creative mode mod and start a sandbox. Rather than placing a blueprint it will fill in the item, I'm thinking this is actually less complex than doing the Pythagoras but it seems to be comparable. Then go grab Qon's fractal balancers and try placing them in turn until you notice the time lag between placing it and being able to move, I find the 64 is small enough to be noticeable when placing it. The 512 I've placed and went and grabbed a soda. At 2048 and beyond I usually let it run overnight (or do it piece meal rather an in one plop) Cause I didn't want to wait for it. Hell in a regular play through I only place solar arrays one at a time because the huccough in UPS is noticeable as hundreds of bots launch.

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

### Re: Personal robots prioritizing nearest first

JohnyDL wrote:Your method of handling impossible ghosts leads back to the original solution, which handles things now, there's a list it doesn't matter what order and you move things to the back when impossible. Impossible being no robot or no item. Ordering the this list based on distance to the player has no long-term benefit as items are skipped because they have no robot available rather than no item.

In order to counter the fact that bots are issued in one tick by the personal roboport and then several dozen items are skipped before the next personal roboport robot becomes available one at a time usually in different ticks and not necessarily in sequential ticks when any robot becomes available (personal or infrastructure) you have to recalculate the heap.

I say that because if you have 2 items to do right next to you at the top of the heap tick one you get a robot the first is requested and issued the second is requested and the item sent to the back of the list due to 'impossible no bot' the next bot becomes available exactly one tick later and if the heap isn't recalculated it goes to do a far off job rather than the second close item.
Obviously you do not process any ghosts if no bot is available. So in your example you only take one item from the heap and then wait for the next bot to become available and the second clostest ghost will still be at the top.
JohnyDL wrote: The heap is O(log2(n)) only so long as whatever metric is used to order the heap is a constant, distance to an erratically moving item is far from constant. Pythagoras would turn it into a O(log2(g)+cpg) where g the number of ghosts on the heap and p is the number of players and c is some constant related to the Pythagoras calculation time.
As mentioned you don't need to be 100% exact with movement and don't have to reheap on every step the player takes. On a tick by tick basis the distance will not change much so the heap is mostly correct. The items at the top will still be far far closer than items at the bottom. And as ghosts are added to the heap as you move the heap can be corrected. The ghosts that are now nearer due to the movement will rise to the top. Unfortunately ghosts that are now further away will not sink on their own. But new ghosts added due to movement will sink to the bottom past those. You can detect when a ghost has it's distance changed to much and then remove and readd them 10 per tick or so. The error in the ordering will probably be imperceptible to the eye.
JohnyDL wrote: The problem with increasing the radius is that you'd have it work out the rate based on the individual computer if my delta is 2 tiles and yours is 4 on the same cooperation because different computer speeds then we get get a desync, if the delta on local players is prioritized (which is what is wanted, I want my QOL now is the whole philosophy of this idea) then that leads again to desyncs. Or you have every delta sync up someone has a delta of zero and everyone's range resets at somepoint and no-one has the QOL anyway and people report it as bugs. More trouble than it's worth. If the slow computer leaves how do you manage increasing the delta shrinking it is easy increasing without problems is hard.
Obviously you can not increase the range depending on the speed of one players system. All calculations are done on every system, so you would have to agree on a rate based on the slowest system. But that would give different rates at different times and would be needlessly complex. The rate of increase in the radius would simply be something like 1 per tick.
JohnyDL wrote: There is no chunkwise list of ghosts, mod said it I've repeated it.

You don't intrinsically know where every blueprint is when it's added you have to do the Pythagoras steps, in some cases that would be more work than going the surface scan. My solar blueprint is 7000 ghosts without deconstruction orders, sometimes I place them locally, sometimes from map mode, if there are other players I could place a ghost near them, basically it's a blueprint that when placed needs to recalculate the heap of the order O(c7000p) not O(log2(7000+g), either the process needs to do the tile scans locally or the Pythagoras for the entire blueprint and then do a complete rebuild of the heap. I might not place it every tick but a drop in UPS every time a blueprint like that is placed by any player would not be a QOL improvement to me or many people I'm on servers with it would however be an opportunity to troll, place an astronomically large blueprints and erase it over and over to irritate other people. You may not need to do surface scanning for blueprints with 100 items but that doesn't necessarily improve things, right now placing a blueprint is O(g) to the list to the queue of to do items, adding it to a heap instead is O(cgp+log2(g)) or O(cpd^2+log2(g)) where d is the diameter of the square you're scanning.
And that is where most of the problems come from. They didn't use a good data structure. Obviously starting with a horrible inefficient data structure you can not make a good algorithm for this. Start with the algorithm and then add the data structure to implement it, not the other way around.

Adding 7000 ghosts would be O(7000 * log(n) * p) where n is the maximum number of ghosts in a heap and p the number of players if you insert each ghost. Or O((7000 + n) * p) if you just add all the ghosts in one step at the end of the heap and then re-heap it. You can chose one of the other for each player depending on the players heap size. So basically around (min(7000 * log(n), 7000 + n) * p).

Right now placing such a blueprint is O(7000 * p). It must already check for each ghost if it is in the players roboport range or bots would not start leaving emidiately. Worst case (since n is limited to the maximum roboport range) it would be 6 (one destruction and one ghost per tile in range) times more work in O() notation. On the other hand the blueprint would get build 20+ times faster. I think players would call that a win, I certainly would.
JohnyDL wrote: If you want to try out adding a 'tiny' bit of code to each ghost item and seeing how it affects UPS I suggest you download the creative mode mod and start a sandbox. Rather than placing a blueprint it will fill in the item, I'm thinking this is actually less complex than doing the Pythagoras but it seems to be comparable. Then go grab Qon's fractal balancers and try placing them in turn until you notice the time lag between placing it and being able to move, I find the 64 is small enough to be noticeable when placing it. The 512 I've placed and went and grabbed a soda. At 2048 and beyond I usually let it run overnight (or do it piece meal rather an in one plop) Cause I didn't want to wait for it. Hell in a regular play through I only place solar arrays one at a time because the huccough in UPS is noticeable as hundreds of bots launch.
That is not a fair comparison as this involves LUA calls. The number I heard from a discussion about making custom combinators is that the buildin combinator is 50000 times faster than one using LUA. Slowing down placing blueprints by 50000 is obviously noticable at a certain size. But we are talking about a fraction of that.

But if you want to try a more realistic (while still LUA) example try out the bluebuild2 mod with longer reach. I don't recommend infinite reach as that results in scans of the whole map and acompaning freeze way too often. But with moderate reach you will not notice an unplayable slowdown even placing huge blueprints.

The fact that bluebuild2 works so well in LUA already makes me sure a proper C++ implementation with changes in the underlying data structures would run just fine despite the roboport range being larger than normal reach.

JohnyDL
Filter Inserter
Posts: 512
Joined: Fri May 16, 2014 3:44 pm
Contact:

### Re: Personal robots prioritizing nearest first

mrvn wrote: Obviously you do not process any ghosts if no bot is available. So in your example you only take one item from the heap and then wait for the next bot to become available and the second clostest ghost will still be at the top.
Actually the code does and a useful side effect is that you get alerts when things need bots or items for free, not doing this means an O(n) pass to work out those things with each time a bot becomes available or a blueprint is placed I say O(n) because you have to check player inventory for items in the player zone and that moves and so on and so on and so on.
mrvn wrote: As mentioned you don't need to be 100% exact with movement and don't have to reheap on every step the player takes. On a tick by tick basis the distance will not change much so the heap is mostly correct. The items at the top will still be far far closer than items at the bottom. And as ghosts are added to the heap as you move the heap can be corrected. The ghosts that are now nearer due to the movement will rise to the top. Unfortunately ghosts that are now further away will not sink on their own. But new ghosts added due to movement will sink to the bottom past those. You can detect when a ghost has it's distance changed to much and then remove and readd them 10 per tick or so. The error in the ordering will probably be imperceptible to the eye.
When do you draw the line for reheap, if not every tick when? if it's every n ticks how do you handle the potential for desyncs between the player and server? if it's variable on processor speed how does it ever sync? How do you handle the moving to a different layer of the map? Factorissimo for example, but there's a potential for this to be used in the vanilla game too, how do you correct the heap piecemeal in a consistent manner if you only 'correct' the closest items according to the heap you might move towards an area that's several hundred tiles away and the 'top' of the heap is now between the 2 positions? How do you detect when a ghost's distance has changed too much without calculating the distance each and every tick and comparing it to the too much value?
mrvn wrote: Obviously you can not increase the range depending on the speed of one players system. All calculations are done on every system, so you would have to agree on a rate based on the slowest system. But that would give different rates at different times and would be needlessly complex. The rate of increase in the radius would simply be something like 1 per tick.
1 per tick either isn't linear as it's the diameter or it isn't practical only scanning 1 tile per tick if your range is changing by as much as 400 (assuming walking speed) how do you manage smooth performance?
mrvn wrote:And that is where most of the problems come from. They didn't use a good data structure. Obviously starting with a horrible inefficient data structure you can not make a good algorithm for this. Start with the algorithm and then add the data structure to implement it, not the other way around.

Adding 7000 ghosts would be O(7000 * log(n) * p) where n is the maximum number of ghosts in a heap and p the number of players if you insert each ghost. Or O((7000 + n) * p) if you just add all the ghosts in one step at the end of the heap and then re-heap it. You can chose one of the other for each player depending on the players heap size. So basically around (min(7000 * log(n), 7000 + n) * p).

Right now placing such a blueprint is O(7000 * p). It must already check for each ghost if it is in the players roboport range or bots would not start leaving emidiately. Worst case (since n is limited to the maximum roboport range) it would be 6 (one destruction and one ghost per tile in range) times more work in O() notation. On the other hand the blueprint would get build 20+ times faster. I think players would call that a win, I certainly would.
Right now the data structure works excellently for the algorithm that's been chosen, what your suggestion amounts to is that it's bad because it can't do this one idea that takes up hundreds of times the processing power anyway.

The suggestion is either change the algorithm by an order of magnitude in complexity and time to run, then completely redesign the data structure that goes with it, oh and not forgetting how dozens of other systems interact with the data structure as it is now, basically it's a rewrite of the game, or bodge it in which is a duplication and a mess, as we've been discussing. We have been discussing the bodge because replacing the ghost's list wholesale would require every tick (every time a bot becomes available (which is every tick if you have idle bots)) calculate every ghost's distance to every player calculations rather than 'just the ones in range' to keep this heap intact. In fact the wholesale change would be better on UPS than a half assed bodge because then you don't have to have the work it does now for non-personal roboports at the same time, though you would end up with roboports issuing commands across the map to do things close to the player, kind of worse than it is now so not the QOL you're expecting.

And I say we're discussing the bodge because you mentioned a maximum heap sixe, if we have a maximum heap size we have a maximum size for the number of ghosts on the map unless they're stored elsewhere too and the heap is again not scalable to N players on multiplayer.

Right now it doesn't check every item every tick, your assumption here is just plain wrong. It checks the top of the list until it runs into a problem and when you place a ghost it adds to the top of the list. Adding a blueprint to the map where you're in range and the first few dozen items are unique and 'impossible no item' will produce a noticable delay before construction starts.
mrvn wrote:That is not a fair comparison as this involves LUA calls. The number I heard from a discussion about making custom combinators is that the buildin combinator is 50000 times faster than one using LUA. Slowing down placing blueprints by 50000 is obviously noticable at a certain size. But we are talking about a fraction of that.

But if you want to try a more realistic (while still LUA) example try out the bluebuild2 mod with longer reach. I don't recommend infinite reach as that results in scans of the whole map and acompaning freeze way too often. But with moderate reach you will not notice an unplayable slowdown even placing huge blueprints.

The fact that bluebuild2 works so well in LUA already makes me sure a proper C++ implementation with changes in the underlying data structures would run just fine despite the roboport range being larger than normal reach.
I'd be hesitant to say LUA takes 50,000 times as long to compute, 5 times I'd buy but not 50,000 the reason I say that is A it's compiled code after launch and compiled code from one language is just as computable as compiled code from another language. Calls might be handled differently because of the translation between sections of code but B Bob's and Angels is a common mod combination with hundreds of addition entities and things to process and really 100 times slowdown would be hella noticible. Circuit conditions might be a special case I don't know, but generally you're orders of magnitude out (and I think I pointed out I get the lag in vanilla games with 7000 ghosts (a drop to 30UPS for me)) so grab a blueprint that's big enough that you notice the slowdown when placing it in vanilla and then try it with the mod, for science.

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

### Re: Personal robots prioritizing nearest first

JohnyDL wrote:
mrvn wrote: Obviously you do not process any ghosts if no bot is available. So in your example you only take one item from the heap and then wait for the next bot to become available and the second clostest ghost will still be at the top.
Actually the code does and a useful side effect is that you get alerts when things need bots or items for free, not doing this means an O(n) pass to work out those things with each time a bot becomes available or a blueprint is placed I say O(n) because you have to check player inventory for items in the player zone and that moves and so on and so on and so on.
The number of bots needed is the size of the heap so you have that. You can also add up the resources needed as you add ghosts to the heap and subtract them when you remove a ghost. No need to continuously go over the list of ghosts to see what is needed. Note how currently the resources needed message only includes the last 600 ghosts. Keeping a total count would actually be more accurate.
JohnyDL wrote:
mrvn wrote: As mentioned you don't need to be 100% exact with movement and don't have to reheap on every step the player takes. On a tick by tick basis the distance will not change much so the heap is mostly correct. The items at the top will still be far far closer than items at the bottom. And as ghosts are added to the heap as you move the heap can be corrected. The ghosts that are now nearer due to the movement will rise to the top. Unfortunately ghosts that are now further away will not sink on their own. But new ghosts added due to movement will sink to the bottom past those. You can detect when a ghost has it's distance changed to much and then remove and readd them 10 per tick or so. The error in the ordering will probably be imperceptible to the eye.
When do you draw the line for reheap, if not every tick when? if it's every n ticks how do you handle the potential for desyncs between the player and server? if it's variable on processor speed how does it ever sync? How do you handle the moving to a different layer of the map? Factorissimo for example, but there's a potential for this to be used in the vanilla game too, how do you correct the heap piecemeal in a consistent manner if you only 'correct' the closest items according to the heap you might move towards an area that's several hundred tiles away and the 'top' of the heap is now between the 2 positions? How do you detect when a ghost's distance has changed too much without calculating the distance each and every tick and comparing it to the too much value?
In vanilla I would never reheap. Not unless the ghosts added in a tick make a reheap cheaper than inserting them individually. But when moving to a different layer of the map that would be a good trigger for a reheap. All current ghosts would become unreachable and you have to scan tiles to find new ghosts on a massive scale. Definitely a occasion to throw the heap away, set the range to 1 and have it increase by 1 per tick till the maximum. It is consistent because every instance of the game does exactly the same calculations every tick. If one of them decides to reheap all of them will.

As for correcting the heap piecemeal in a consistent manner: For each ghosts in the heap I would keep track of the player position when it's distance was calculated so you know the amount of error it has next time you happen to come across it. You can use manhatten distance if you think pythagoras is too expensive. Note the "next time you happen to come across it". As the player moves new items are added. They will be at the maximum distance and thus at the bottom of the heap. Inserting them into the heap will check log(n) items going from the top to the bottom. So it is not just the items at the top of the heap that get corrected but all items along a path to the bottom of the heap. Similar when you remove the top item you replace it with the last item in the heap and then correct the heap. The item sinks down fixing all items in its path. You might not hit every ghost that needs to be corrected in time but I think the chance of that is small. And worst case a ghost will just be build a bit later than a strict nearest first order would require. It doesn't have to be 100% perfect.
mrvn wrote: Obviously you can not increase the range depending on the speed of one players system. All calculations are done on every system, so you would have to agree on a rate based on the slowest system. But that would give different rates at different times and would be needlessly complex. The rate of increase in the radius would simply be something like 1 per tick.
1 per tick either isn't linear as it's the diameter or it isn't practical only scanning 1 tile per tick if your range is changing by as much as 400 (assuming walking speed) how do you manage smooth performance?
Definitely not 1 tile per tick. That would take minutes to grow to the maximum range. I'm talking about increasing the radius by 1 per tick. And yes, that means towards the maximum radius you have more work than at the start. But it isn't that many tiles even for the maximum radius and most of the time the number of ghosts will be even smaller or 0. And you have to move more than 1 tile per tick for the radius to ever go low. It's basically just a way to not waste time scanning millions of tiles while taking a train ride.
mrvn wrote:And that is where most of the problems come from. They didn't use a good data structure. Obviously starting with a horrible inefficient data structure you can not make a good algorithm for this. Start with the algorithm and then add the data structure to implement it, not the other way around.

Adding 7000 ghosts would be O(7000 * log(n) * p) where n is the maximum number of ghosts in a heap and p the number of players if you insert each ghost. Or O((7000 + n) * p) if you just add all the ghosts in one step at the end of the heap and then re-heap it. You can chose one of the other for each player depending on the players heap size. So basically around (min(7000 * log(n), 7000 + n) * p).

Right now placing such a blueprint is O(7000 * p). It must already check for each ghost if it is in the players roboport range or bots would not start leaving emidiately. Worst case (since n is limited to the maximum roboport range) it would be 6 (one destruction and one ghost per tile in range) times more work in O() notation. On the other hand the blueprint would get build 20+ times faster. I think players would call that a win, I certainly would.
Right now the data structure works excellently for the algorithm that's been chosen, what your suggestion amounts to is that it's bad because it can't do this one idea that takes up hundreds of times the processing power anyway.

The suggestion is either change the algorithm by an order of magnitude in complexity and time to run, then completely redesign the data structure that goes with it, oh and not forgetting how dozens of other systems interact with the data structure as it is now, basically it's a rewrite of the game, or bodge it in which is a duplication and a mess, as we've been discussing. We have been discussing the bodge because replacing the ghost's list wholesale would require every tick (every time a bot becomes available (which is every tick if you have idle bots)) calculate every ghost's distance to every player calculations rather than 'just the ones in range' to keep this heap intact. In fact the wholesale change would be better on UPS than a half assed bodge because then you don't have to have the work it does now for non-personal roboports at the same time, though you would end up with roboports issuing commands across the map to do things close to the player, kind of worse than it is now so not the QOL you're expecting.

And I say we're discussing the bodge because you mentioned a maximum heap sixe, if we have a maximum heap size we have a maximum size for the number of ghosts on the map unless they're stored elsewhere too and the heap is again not scalable to N players on multiplayer.

Right now it doesn't check every item every tick, your assumption here is just plain wrong. It checks the top of the list until it runs into a problem and when you place a ghost it adds to the top of the list. Adding a blueprint to the map where you're in range and the first few dozen items are unique and 'impossible no item' will produce a noticable delay before construction starts.
The heap size is limited by the range of each players personal roboport. You can't have more than one ghost and 4 deconstructions (pickup item from ground) per tile. Ghosts not in range of a player wouldn't be in the players heap.

I didn't say it checks every item every tick. I said it checks every item when you place a blueprint. If it would just add them to the end of the global list then it would take a while for the scan to come around to the new ghosts and see they are in range of a player. Once placed it checks one item in the players range per tick but that would be the same with the heap method. To me it looks like the game already has a per player list of ghosts in range.
mrvn wrote:That is not a fair comparison as this involves LUA calls. The number I heard from a discussion about making custom combinators is that the buildin combinator is 50000 times faster than one using LUA. Slowing down placing blueprints by 50000 is obviously noticable at a certain size. But we are talking about a fraction of that.

But if you want to try a more realistic (while still LUA) example try out the bluebuild2 mod with longer reach. I don't recommend infinite reach as that results in scans of the whole map and acompaning freeze way too often. But with moderate reach you will not notice an unplayable slowdown even placing huge blueprints.

The fact that bluebuild2 works so well in LUA already makes me sure a proper C++ implementation with changes in the underlying data structures would run just fine despite the roboport range being larger than normal reach.
I'd be hesitant to say LUA takes 50,000 times as long to compute, 5 times I'd buy but not 50,000 the reason I say that is A it's compiled code after launch and compiled code from one language is just as computable as compiled code from another language. Calls might be handled differently because of the translation between sections of code but B Bob's and Angels is a common mod combination with hundreds of addition entities and things to process and really 100 times slowdown would be hella noticible. Circuit conditions might be a special case I don't know, but generally you're orders of magnitude out (and I think I pointed out I get the lag in vanilla games with 7000 ghosts (a drop to 30UPS for me)) so grab a blueprint that's big enough that you notice the slowdown when placing it in vanilla and then try it with the mod, for science.
Hehe, I once marked 600k alien artifacts for collection. UPS dropped from maybe 50 to 7 in an instance. All the more reason to do nearest first because then ghosts are removed faster and the UPS climbs back up faster (I would like nearest first for all roboports but that might be strethcing it).

quyxkh
Filter Inserter
Posts: 787
Joined: Sun May 08, 2016 9:01 am
Contact:

### Re: Personal robots prioritizing nearest first

I handle this with two sets of armor, one without ports, one with. Swap to the no-port set to deactivate my bots (like before getting on a train). When working, step to one side before issuing a big command, then just run through the area. It's almost no-brainer great for all but really big jobs, especially great for narrow jobs like rail, the bots are done placing/destroying just about the time I get there. For the really big ones it helps to be a little careful how you move, and sometimes a just-one-port set's limited range is best, by the time I get to those I've generally got enough mk2 batteries that popping out a few ports is less hassle than keeping a spare one-port armor set.

Rseding91
Factorio Staff
Posts: 10038
Joined: Wed Jun 11, 2014 5:23 am
Contact:

### Re: Personal robots prioritizing nearest first

mrvn wrote:Hehe, I once marked 600k alien artifacts for collection. UPS dropped from maybe 50 to 7 in an instance. All the more reason to do nearest first because then ghosts are removed faster and the UPS climbs back up faster (I would like nearest first for all roboports but that might be strethcing it).
That has nothing to do with distance based searching and all to do with item entities not having an associated force causing marking/unmarking of them to be O(N) time based of how many other non-entity-with-force entities are marked for deconstruction. Nothing relevant to what you're talking about here.
If you want to get ahold of me I'm almost always on Discord.

JohnyDL
Filter Inserter
Posts: 512
Joined: Fri May 16, 2014 3:44 pm
Contact:

### Re: Personal robots prioritizing nearest first

mrvn wrote:The number of bots needed is the size of the heap so you have that. You can also add up the resources needed as you add ghosts to the heap and subtract them when you remove a ghost. No need to continuously go over the list of ghosts to see what is needed. Note how currently the resources needed message only includes the last 600 ghosts. Keeping a total count would actually be more accurate.
Okay good point on the heap size (so long as the heap contains all ghosts not just the ones in the personal areas of each player) although you can't tell which are missing items and which bots and which any roboport at all, without checking them. Just that there are N items not being worked on.

And I've been saying the only consistent way to do it and not have it break or desync is to do the same thing every tick I know you disagree but it's the truth, any consistent solution has to be done every tick or you have to make sure it isn't necessary by effectively doing the job anyway to determine "nope I didn't need to do it this time"
mrvn wrote:In vanilla I would never reheap. Not unless the ghosts added in a tick make a reheap cheaper than inserting them individually. But when moving to a different layer of the map that would be a good trigger for a reheap. All current ghosts would become unreachable and you have to scan tiles to find new ghosts on a massive scale. Definitely a occasion to throw the heap away, set the range to 1 and have it increase by 1 per tick till the maximum. It is consistent because every instance of the game does exactly the same calculations every tick. If one of them decides to reheap all of them will.

As for correcting the heap piecemeal in a consistent manner: For each ghosts in the heap I would keep track of the player position when it's distance was calculated so you know the amount of error it has next time you happen to come across it. You can use manhatten distance if you think pythagoras is too expensive. Note the "next time you happen to come across it". As the player moves new items are added. They will be at the maximum distance and thus at the bottom of the heap. Inserting them into the heap will check log(n) items going from the top to the bottom. So it is not just the items at the top of the heap that get corrected but all items along a path to the bottom of the heap. Similar when you remove the top item you replace it with the last item in the heap and then correct the heap. The item sinks down fixing all items in its path. You might not hit every ghost that needs to be corrected in time but I think the chance of that is small. And worst case a ghost will just be build a bit later than a strict nearest first order would require. It doesn't have to be 100% perfect.
So are we talking about all ghosts or just the ones in the player zone cause I'm pretty sure we talk about one most of the time but then you say some things that just don't work with that thought, for example "all current ghosts" in this was at odds with the previous paragraph which only works if we're talking about all ghosts being in the heap not just those in personal roboport range.

I think you miss the point with piecemeal, let's say you're moving just 30 tiles (staying inside your roboport range), every tile for 60 tiles in every direction has a tree marked for deconstruction and at this point you have a perfect heap (some how) you walk east those thirty tiles the top of the heap is now 15 tiles to your west because only the top items in the heap were processed by the routine and when the items where you're standing now were added to the list "the last time you came across it", they were added to the heap further away than the items that're now 15 tiles away. The point being because they're not close to the top of the heap, with so many items and so few being processed and corrected each tick, they'll take a long long time for the piecemeal approach to get there. You never (re)process the whole heap at any point and only focus on the top items makes the system broken because you only 'come across' things at the edge boundary and not near the player.... Hang on no you say 'along the path' so does that mean you have to add vector distances to all the items? so you know if an item is more east or west and you process every item that's even slightly east of you to see if they get closer, well they will get closer but not in a linear manner, so that's O((N/2)^2) oh but the ones that're west also need to be moved down but I suppose that's less critical. So you don't need to reheap or reprocess every item either periodically or every tick, you just need to do half of them and add a directionality component check to movement and each ghost. So how do you do that in a way that's O(log2(n)) and not O((N/2)^2)? wait that's only if there's one player if you have two moving towards each other that's actually greater than O(N^2) in the cases that their personal heaps overlap, or greater than O(N^2) if you're considering all the ghosts in the same heap and you have to apply the check as well as the distance calculations.
mrvn wrote: Definitely not 1 tile per tick. That would take minutes to grow to the maximum range. I'm talking about increasing the radius by 1 per tick. And yes, that means towards the maximum radius you have more work than at the start. But it isn't that many tiles even for the maximum radius and most of the time the number of ghosts will be even smaller or 0. And you have to move more than 1 tile per tick for the radius to ever go low. It's basically just a way to not waste time scanning millions of tiles while taking a train ride.
So how does this scale to multiple players? a lot of "not that many" is still a lot. And again I can't tell if you have all ghosts in the heap or just local ghosts to the player or what. And at what rate do you shrink the radius? Would it ever effect exoskeleton legs? cars? tanks? is it only trains at certain speeds?
mrvn wrote:The heap size is limited by the range of each players personal roboport. You can't have more than one ghost and 4 deconstructions (pickup item from ground) per tile. Ghosts not in range of a player wouldn't be in the players heap.

I didn't say it checks every item every tick. I said it checks every item when you place a blueprint. If it would just add them to the end of the global list then it would take a while for the scan to come around to the new ghosts and see they are in range of a player. Once placed it checks one item in the players range per tick but that would be the same with the heap method. To me it looks like the game already has a per player list of ghosts in range.
So we are talking about limited size heaps right? not all ghosts in one heap that's well managed? all 100% sure about that now?

Deconstruction of chests filled with items are actually much larger than 1 ghost and 4 deconstructions per tile and deconstruction of belts is 6 items and a belt but anyway.

And I said top of the global list not end. The top, head, front of the queue, done first before everything else. If you do something anywhere in the player range or elsewhere for that matter it's first done as soon as possible, so obviously you see it get done instantly by your personal robots as the ghost looks and finds you to be the closest roboport available and you have the robots there waiting and the item to construct. That's how it currently works. It acts like an every player has a list of ghosts within their range but it cleverly doesn't need to be so. and thus resource overhead is reduced
mrvn wrote:Hehe, I once marked 600k alien artifacts for collection. UPS dropped from maybe 50 to 7 in an instance. All the more reason to do nearest first because then ghosts are removed faster and the UPS climbs back up faster (I would like nearest first for all roboports but that might be strethcing it).
Addressed by a Dev but also alien artifacts, a previous version of the game with less optimisation.

Philip017
Filter Inserter
Posts: 301
Joined: Thu Sep 01, 2016 11:21 pm
Contact:

### Re: Personal robots prioritizing nearest first

i have been wanting this function for FOREVER i sure hope that they add/change things to implement this quality of life feature!

this is my list of wanted items to add/change about personal robots after 3k hrs played

option 1 - my personal robots do/do not assist other players
option 2 - logistic network robots do/do not assist building/deconstruction of items ordered by me as long as i am with in range and have the materials. as opposed to now if i have not enough robots the network takes over.
function 1 - my personal robots deconstruct/build items nearest to me first, then further away.
function 2 - order of build, deconstruct items 'in the way' first, then build, this seems to be working better than previously.
function 3 - order of build, place power structures before placing other structures, remove power structures after deconstruction all other structures, deconstruct roboports dead last, nothing works with out power, once the network is broken nothing else gets removed.
function 4 - robots out of power get their job reassigned to a charged robot. robots out of power drop their item back into my backpack after returning to charge.
function 5 - robots do not jump out of my pack while i am zooming away in a car/train - hey there is a mod for that!

Possible change - robots do not leave my backpack with out a full charge and do not hover around me but jump back into my pack when their batteries are dead. requiring power to recharge them instead of being able to pluck them from the air and have them fully recharged.

JohnyDL
Filter Inserter
Posts: 512
Joined: Fri May 16, 2014 3:44 pm
Contact:

### Re: Personal robots prioritizing nearest first

Philip017 wrote:i have been wanting this function for FOREVER i sure hope that they add/change things to implement this quality of life feature!

this is my list of wanted items to add/change about personal robots after 3k hrs played

option 1 - my personal robots do/do not assist other players
option 2 - logistic network robots do/do not assist building/deconstruction of items ordered by me as long as i am with in range and have the materials. as opposed to now if i have not enough robots the network takes over.
function 1 - my personal robots deconstruct/build items nearest to me first, then further away.
function 2 - order of build, deconstruct items 'in the way' first, then build, this seems to be working better than previously.
function 3 - order of build, place power structures before placing other structures, remove power structures after deconstruction all other structures, deconstruct roboports dead last, nothing works with out power, once the network is broken nothing else gets removed.
function 4 - robots out of power get their job reassigned to a charged robot. robots out of power drop their item back into my backpack after returning to charge.
function 5 - robots do not jump out of my pack while i am zooming away in a car/train - hey there is a mod for that!

Possible change - robots do not leave my backpack with out a full charge and do not hover around me but jump back into my pack when their batteries are dead. requiring power to recharge them instead of being able to pluck them from the air and have them fully recharged.
The devs have said it's not happening (we're discussing why not and mrvn is trying to convince me there's a way to make it work that adds no extra lag to the game while I don't believe that's possible in a multiplayer scalable fashion)
option 1 the game distinguishes by forces, the only way to not help other players is to change teams and their research doesn't help you either
option 2 your bots taking over a job that's already issued is again part of the problem we have been discussing and probably won't happen.
function 1 not happening
function 2 kind of wish it would but the build order is linear W->E/N->S (ie like text L->R/T->B) if the item is blocked by an deconstruct not in the NE corner it comes after in the list
function 3 again ordering and actually this contradicts function 1
function 4 all robots act the same doing that would mean that robots in the network that need to charge might have to travel 1000s of tiles with no charge to deposit in a storage box rather than charging at a roboport within 50 tiles and continuing
function 5 frustrating but the devs have had no inclination to add this either despite multiple suggestions.

Philip017
Filter Inserter
Posts: 301
Joined: Thu Sep 01, 2016 11:21 pm
Contact:

### Re: Personal robots prioritizing nearest first

actually for function 3, it's multi tier order, deconstruct obstructions (trees, stones), send out robots in relation to, closest first, power poles in the blueprint next - once all deconstruct orders have had robots dispatched, again closest ones first then further ones, finally everything else, again closest ones first then further away.
for deconstruction, it's clear everything but power poles and roboports, then power poles, finally roboports, thus having less issues with the 'oh it killed all my power before finishing removing all my machines/furnaces/belts, usual work around using filtered deconstruction planner, leave all power poles and roboports, come back later and remove them. the deconstruction planner filter has improved quality of life alot for sure!

distance based calculations only apply to personal robots, and should be based on when the robots leave the backpack. it only has to be done when the robot leaves the pack per robot, you can tier this work out on a limited number of personal robots at a time. i would gladly sacrifice some latency to have the robots do what is close to me first and work their way out. this would only have to work for personal robots not logistic system robots.
personally i think the logistic system robot function works great the way it works, but for personal robots, they should definitely work different imo.

as for option 1, it would require a rewrite of how personal robots work, so although it would be extremely nice thing to have, it would be "work" for the devs to change it.

for function 4 - this would only apply to personal robots, not logistic system robots.

for function 5 at least we have a mod for that now, for unmodded - if you aren't carrying too much you can take off your power armor if you remember to do so before hopping a train or car - there are wagons or trunk for your extra stuff if needed. but considering a modder figured out how to do it, i don't see why it can't be optional in vanilla, but anyways.

at any rate personal robots need to have separate programming to logistic system robots to implement these QOL features.

another thing i have just gotten used to, i have to go stand near a roboport to get my deliveries when i come back to town, too many times the robot will come to me not give me my delivery, go back to the nearest roboport and recharge then come back to me and give me my delivery, it would be so much nicer if i had a full battery on my personal roboport, the logistic robot could just get a charge off me and give me my delivery and be back on it's way.

JohnyDL
Filter Inserter
Posts: 512
Joined: Fri May 16, 2014 3:44 pm
Contact:

### Re: Personal robots prioritizing nearest first

Philip017 wrote:actually for function 3, it's multi tier order, deconstruct obstructions (trees, stones), send out robots in relation to, closest first, power poles in the blueprint next - once all deconstruct orders have had robots dispatched, again closest ones first then further ones, finally everything else, again closest ones first then further away.
for deconstruction, it's clear everything but power poles and roboports, then power poles, finally roboports, thus having less issues with the 'oh it killed all my power before finishing removing all my machines/furnaces/belts, usual work around using filtered deconstruction planner, leave all power poles and roboports, come back later and remove them. the deconstruction planner filter has improved quality of life alot for sure!
so your idea is to do two levels of filtering on the queue not one? Both none trivial sorting operations
Philip017 wrote: distance based calculations only apply to personal robots, and should be based on when the robots leave the backpack. it only has to be done when the robot leaves the pack per robot, you can tier this work out on a limited number of personal robots at a time. i would gladly sacrifice some latency to have the robots do what is close to me first and work their way out. this would only have to work for personal robots not logistic system robots.
to calculate the distance it doesn't intrinsically know which is closer you have to A find (surface scan nearby) every ghost and B do Pythagoras calculation to every ghost then C sort it. A and B take a lot of computational time and would slow your game to a crawl if done badly.

Doing it for each and every personal robot is slower than just keeping a list and by latency we could be talking a drop of 1 frame per second for every robot issued your way, so you have 100 bots so do 10 other people on your server all bots launch at once for some reason that's the game effectively frozen for 15 seconds at which point the server considers it a lock up and restarts.
Philip017 wrote: personally i think the logistic system robot function works great the way it works, but for personal robots, they should definitely work different imo.
no you don't elsewhere in your post you complain about it but whatever you decide should happen should be consistent for both networks or it's a mess of programming to control and track when bugs occur
Philip017 wrote: as for option 1, it would require a rewrite of how personal robots work, so although it would be extremely nice thing to have, it would be "work" for the devs to change it.
it's not work it's impossible how can the game know what's yours and what's someone else's if you're on the same team the number of times someone else has plopped a blueprint I need finishing now and go to build.... there's no way no way at all to make that work without removing the team work QOL
Philip017 wrote: for function 4 - this would only apply to personal robots, not logistic system robots.
consistency both or neither, you choose
Philip017 wrote: for function 5 at least we have a mod for that now, for unmodded - if you aren't carrying too much you can take off your power armor if you remember to do so before hopping a train or car - there are wagons or trunk for your extra stuff if needed. but considering a modder figured out how to do it, i don't see why it can't be optional in vanilla, but anyways.
it's been modded into the game means it can be done and there's code for it that the code hasn't been implemented to vanilla means that it's not compatible, it's not intended behaviour or it's not optimizible sufficiently. I'd go with its not the behaviour the devs intend for the game.
Philip017 wrote: at any rate personal robots need to have separate programming to logistic system robots to implement these QOL features.
so duplicate the work and don't bother optimizing decisions like that lead to games never getting out of beta due to technical limitations
Philip017 wrote: another thing i have just gotten used to, i have to go stand near a roboport to get my deliveries when i come back to town, too many times the robot will come to me not give me my delivery, go back to the nearest roboport and recharge then come back to me and give me my delivery,
see complaints about the logistics network
Philip017 wrote:it would be so much nicer if i had a full battery on my personal roboport, the logistic robot could just get a charge off me and give me my delivery and be back on it's way.
so you want the two networks to be entirely separate you want your personal robots to do all these things take over from the other system be completely independent but you want your system to do more better interactions with the logistics system in the same stroke.

Oh cheesecake, I give up you people are mental. :p I suggest you read the whole thread and come back when you're familiar with the discussion so far.

Philip017
Filter Inserter
Posts: 301
Joined: Thu Sep 01, 2016 11:21 pm
Contact:

### Re: Personal robots prioritizing nearest first

no i dont claim to understand how any of this works in programming, i am not a programmer, just a player.

it seems to be a matter of networks and forces, and robots could be changed to be of the personal variety and the logistic system variety.

for my personal roboport it could supply a logistic robot with power, but nothing else. and it would only supply power if the robot has a package assigned to me, and the robot is too low on power to make the delivery. yes lots of conditions, maybe a headache for programming.

besides all the programming work involved, why can't personal robots have totally different logic than logistic system robots, they can pull from the same list of what needs to be done, but work off a different set of functions.

as for the distance calculations, as someone else posted, why not use the chunk data, if im in the chunk do that work first, then the adjacent chunks?

as for what is mine and someone else's stuff, this data could be pulled from the data of who changed what last, the ghost has your name on it. so if something doesn't have my name on it, my personal robots would not go assist if i optioned that.

we are all mental in some way or another

JohnyDL
Filter Inserter
Posts: 512
Joined: Fri May 16, 2014 3:44 pm
Contact:

### Re: Personal robots prioritizing nearest first

okay if you're not a programmer then I'll go simple

it's not simply a matter of segregating networks and forces, there's a master list of ghosts for each force, and you're either part of it or you're not there's no partial forces, AFAIK you can't share research and not bots or vice versa because it takes a substantial amount of processing power to manage something like that.

Rather than bots looking for work, Ghosts and such in the main list look for bots and items, they do this once per tick and not every ghost looks every tick. The methods that make these suggestions work would multiply the number of ghost checks from 1 to pottentially millions and you'd not be able to play the game. Think of your frame rate, the game plays at 60, at half speed you feel it, at a third you'll actually see the stuttering, at a sixth it's a slideshow at this point it's already not a game you can play in any meaningful manner, but the idea continues to push the boundary even lower, if you've ever watched a minecraft youtube video of stupidly large farms or explosions you'll understand the 'Quality of Life' isn't there because the game apears to break when you use it.

You'd need to be connected to the logistic network to allow that sort of charging in the same way as Roboports, but the player is basically a logistics chest.

If you have 2 different sets of instructions you more than double the work the computer has to do managing the system and resolving conflicts. Let alone the headaches and bugs it causes.

Every condition you set is an extra amount of linear work you have to do.

The reason you can't use chunk data is because there's no such thing as chunk data on ghosts. You have to look at every single tile and ask it, this is a quadratic amount of work to do and would fail on multiplayer.

Again, you adding 1 check to each ghost for player name adds that check a huge number of times in this case you add the check based on the number of ghosts multiplied by the number of players and would fail on multiplayer

yeah I'm insane to keep coming back to this topic

Escadin
Fast Inserter
Posts: 180
Joined: Thu Mar 17, 2016 3:15 pm
Contact:

### Re: Personal robots prioritizing nearest first

Pretty long thread so no idea whether suggested before. Can personal robots please be prioritized even if they cannot finish a job all at once? Hate it when I deconstruct a blue print expecting to move it a bit down the bus and then construction bots come from the other end of my factory trying to steal items before they are added to my inventory and move them to a random storage chest wherever.

Also, can those personal robots be prioritized which belong to the player who ordered (de) construction? Same issue as above except now the items land in another players inventory even if he just happened to pass by.
"--? How are commands compounded in a compounded compound command commanding compound composts." -defines.lua

SuicideJunkie
Long Handed Inserter
Posts: 85
Joined: Wed Aug 23, 2017 10:17 pm
Contact:

### Re: Personal robots prioritizing nearest first

As far as prioritizing types of things (EG deconstruction, then power poles, then other stuff), that seems simple.
Just take the existing ghost list, and split it into multiple shorter lists.

Each tick, the top priority ghost list is checked as it is now.
If no bot can be assigned, then again act as now, but try again with the next lower priority ghost list.

Skipping over empty priority levels is trivial, and you'd only spend a little time rejecting multiple ghost tasks if the top few priority levels all have impossible.ghosts.

As to the idea of preventing base bots from taking jobs away from your hardworking personal bots;
Check if the ghost is in range of the personal roboports first. If yes, and the options toggle is set, then simply stop and don't search for stationary roboport availability.

In multiplayer games a griefer would have to be personally present to bot-block, and you could always toggle the option off if the players are pathological, but for small and solo games, enabling the option would improve UPS since it shortcuts some calculations.
If you want the stationary roboports to do some of the work while the option is on, you can simply step away (or shut off your personal ports).

JohnyDL
Filter Inserter
Posts: 512
Joined: Fri May 16, 2014 3:44 pm
Contact:

### Re: Personal robots prioritizing nearest first

Escaping: Unfortunately the bot system cannot tell the difference between you have deployed all your robots and they're working and you have no robots to deploy either way it's 0 available so you could be waiting forever cause you have only one or two bots total to do the work when the base system has 4000. If you don't want your base constructing why not remove all construction bots from your base or build outside roboport range.

Why would a job that's being done keep looking for more bots to duplicate the task as far as its concerned the job is being done

Sorting by player is non trivial and what if said other player is helping, or trying to help, learn some team work or don't play multiplayer.

Suicide Junkie: so instead of one list you propose several lists and you do several times as much work, I'm not saying this is unfeasible but it's still more work and more bugs to track and there are conflicts, is the way you'd sort your build order the same as mine, I mean if I'm deconstructing the first thing I'd want rid of is power, I'm deconstructing it don't do more things stop them stop them all stop them now :p

So more work, not saying this is as bad as ordering by distance but it's still work.

If you're checking all ghosts it's far from none trivial. But it's fairly trivial if you're only doing 20 checks rather than 1. But it isn't free.

Check if ghost is within range of personal roboports, easy as that. Um No. For the nth time

there is no shortcuts to finding out if a ghost is in range of a personal roboport you have to do a surface scan of every tile in the roboports range this takes a lot of computational power and time, and you have to do it every tick

Information gleaned from Devs in this topic and others. It's not something they want to do for single player because of the overhead cost, on multiplayer it is disastrous. There is no list already that does this job and all the ways of handling such things are messy and probably lag inducing

For multiplayer you're saying you already see the grieving potential and that commands could be used to globally disable it (commands which would disable achievements which might be the point of a MMO factorio event which is the only place this trolling would be meaningful) and enabling the option would not cut anything short you only add to the number of checks and conditions a job must jump through to get activated.

Right now the game does 1 check per tick can the first job in the list be done? Yes great, no try again next time.

Your solution item at the top of list 1 are you in range of a personal roboport? Yes (Can that roboport do your job? There are multiple player ports (oh I have to check each one individually, can roboport i serve you? Wait you want it to be your owner too (is roboport i your owner? Yes (can roboport i do your job? Yes Great, no integrate to next roboport) no try again next time) no integrate to next roboport) No (are you in range of a network? Yes (can it do your job? Yes Great, no try again next time) No try again next time) did I do any work? Yes great I'm done, No I have to go through the same process with the next list, how many of these do I have to do?

Escadin
Fast Inserter
Posts: 180
Joined: Thu Mar 17, 2016 3:15 pm
Contact:

### Re: Personal robots prioritizing nearest first

JohnyDL wrote:Escaping: Unfortunately the bot system cannot tell the difference between you have deployed all your robots and they're working and you have no robots to deploy either way it's 0 available so you could be waiting forever cause you have only one or two bots total to do the work when the base system has 4000. If you don't want your base constructing why not remove all construction bots from your base or build outside roboport range.

Why would a job that's being done keep looking for more bots to duplicate the task as far as its concerned the job is being done

Sorting by player is non trivial and what if said other player is helping, or trying to help, learn some team work or don't play multiplayer.
If that was addresseing me then I'm afraid you've missed the point. There is no teamplay involved in trying to tweak a blueprint and thus having to construct and deconstruct a couple of times, but suddenly some essential parts are to be snatched away because either another player happend to speed by in a train or you've added the 51th part when you only have 50 roborts and then a repair drone from the wall tries to carry it home. It's also an active hinderance for teamplay if a second player cannot stop by your workshop and take a helpful look at things without getting his inventory and bots entangled in the construction.

I understand the game needs to determine when there are no or not enough priority bots available but that is pretty simple in principle. One sultion would be to compare the amount of available personal bots to the task count and adds help should it drop below a certain percentage. The other would be let the personal construction network area overwrite all others and only allow your own bots to take tasks within it. If that's not possible to do for you then you just walk away revealing the tasks to other, lower priority networks.

Differentiating priorities between different player networks is more difficult but not impossible.
"--? How are commands compounded in a compounded compound command commanding compound composts." -defines.lua

JohnyDL
Filter Inserter
Posts: 512
Joined: Fri May 16, 2014 3:44 pm
Contact:

### Re: Personal robots prioritizing nearest first

No I got the point and you missed mine, you have to treat all situations the same if you plop a blueprint that's a few thousand entites (like for example, a mid level mall) and you and your whole team have a few personal bots each and you want to build said ghost as fast as possible and you all have a few of the items cause you've been co-ordinating your hand crafting, one person plops the blueprint 9 of you stand around un-able to help,

If you've got a workshop A it can be looked at from map mode, B you probably want it segregated from main networks anyway, and C why'd you place it next to a main train line you could have gone somewhere deeper into the train network and moved 50 tiles from the rails. There are times that other players might pop over and be nosy or helpful but you eliminate teamwork because you don't need to talk to your team, you just ignore everyone else and do your own thing and they never bother you and you never bother them, that's not teamwork. You might as well make a sandbox world and then copy the blueprint across to the MP one when it's done.

I love that 'simple in principle' never matches up to simple in code.

Let's say the amount of bots you have is 50, and there's a 100 entity blueprint, you know you can do it in 2 dispatches from your personal roboport and that getting help from the other end of your base would be a waste of time. Simple right? so you dispatch 50 bots and now there are 50 ghosts and 0 available, you can work out in an instant that 50 bots will become available in a few seconds because your brain can calculate the future in a remarkable manner, the only way the computer would know is to simulate it and then evaluate based on the simulation. It only knows there are 50 ghosts now and 0 bots available from you, it doesn't even know that you have bots in the air, it has no way to check for that, and even if it could, it still couldn't tell how long those jobs might last, it might be quicker to send 50 bots 10,000 tiles and there's no way it could know it isn't. I say that cause you could (in theory) have robot movement speed level 1000 researched and the base bots would hop across there instantaneously while your bots are hovering trying to place items on top of trees that need deconstructing.

Differentiating priorities have to be hard coded into the game, you can't set priorities like that on a per user basis, I'm stood next to you and the algorithm argues which order the queues should be in back and forth indefinitely to no benefit. Say it has some way to decide, the first person alphanumerically is the person that's in charge, well troll named "0000000000000" walks over he says send out all construction orders before deconstruction orders and all your bots are trying to place things rather than clearing trees. And any other metric you think of can be gamed by humans. So it has to be one order for all and then there's the eternal argument my order makes more sense than yours, just no, it's not worth it.

### Who is online

Users browsing this forum: No registered users