Personal robots prioritizing nearest first

[mrvn]

Not sure that is much better, except for CPU usage. So when I have 100000000000 ghosts, one of them being the roboport that needs to be placed so the others become reachable, it will take about 26.5 years to be placed. Blueprints get slower the more ghosts you have.

Somehow I don't believe that that is all you are doing. When I stand next to a forest and deconstruct 50k trees all my construction bots immediately leave to get some wood. If you handle only one ghost per tick then a lot of the time the ghost would be out of reach and no bot would leave. And when I move around the moment a ghost enters my reach a bot leaves. Again, with many ghosts pending there should be a delay till the right ghost is checked again. So the algorithm you describe doesn't seem to match the behaviour of personal roboports.

I'd guess the ghost also gets checked when it's created - lots of other things in the game work this way (check a condition immediately, and if it's false, join some queue to wait).

Yes, that explains one part. Also explains why at the start all the bots leave for ghosts right next to each other in order. But later they leave for seemingly random ghosts, because that's the one being checked the tick the bot became idle. Must also happen when you move and ghosts become reachable to the player. But that would be O(n).

[Linosaurus]

If we can adjust the range of a personal roboport manually however, it would work great I suspect.

Yes, that seems like the best solution at this point. Perhaps reuse the concrete area size controls.

Also, as was mentioned on the first page, it could let you drop the area to 0 to turn the roboport off without having to add an additional hotkey for that.

[mrvn]

If we can adjust the range of a personal roboport manually however, it would work great I suspect.

Yes, that seems like the best solution at this point. Perhaps reuse the concrete area size controls.

Also, as was mentioned on the first page, it could let you drop the area to 0 to turn the roboport off without having to add an additional hotkey for that.

As soon as you can control the range manually there will be a mod to control it automatically.

[Ranakastrasz]

If we can adjust the range of a personal roboport manually however, it would work great I suspect.

Yes, that seems like the best solution at this point. Perhaps reuse the concrete area size controls.

Also, as was mentioned on the first page, it could let you drop the area to 0 to turn the roboport off without having to add an additional hotkey for that.

As soon as you can control the range manually there will be a mod to control it automatically.

Good point....


Alternatively, I suppose you could separate the personal roboport into range and charge equipment, allowing you to adjust the range "Very Manually." That would probably give you something close at least.

[mrvn]

Just FYI: I started a game with the rewritten Bluebuild mod, which handles construction and destruction ghosts within the players normal reach from the start. No construction bots required. The interesting thing is that it constructs and destructs objects from the player outward. Haven't noticed any drop in UPS yet despite running around with several 1000 trees scheduled for deconstruction.

[deer_buster]

This is a pet peve of mine when it comes to bots, especially when they are my personal bots...

[d3x0r]

Maybe already suggested...
But it would seem to me, that when using a deconstruction planner, there's an implied order because you slowly iterate over the surface and gain more entities in it.
Closest first or left-right or top-down doesn't really matter, in the end it will take the same amount of time.... hmm maybe that would take some work to check 'is this already in the planner' else add... easier to just set the planner to the result of find_entities( area )...

it would be appealing if it was in some sort of order.

I wonder if there's a way to trigger existing GUIs - could make a mod that kind of overlays deconstruction planner, but when applied, does a sort of the entities in it. (maybe the same to blueprints)

[namek]

YES!

[pingger]

Square root isn't important. Aside from you always comparing dx*dx + dy*dy, [...]
-Robots appear to chose random jobs, [...] whereas the seemingly random jobs is O(1).

Random jobs need O(N) overall. You are comparing the work for sorting all the ghosts against picking one random ghost. And no need to quicksort, a heap is better because initialization is O(N) (same as adding all ghosts in random order) and you delay the sorting to when things are removed. It gets spread out over many ticks instead of making one tick take millions times longer than the rest.

[... quote that doesn't matter ...]

The "Random" Jobs aren't random. As far as i can tell, they are just iterating through every known job. So the runtime is O(1). I guess the code looks something like this.
Let n be the Job Count.
Let m be the NetworkCount + MatchingRoboportCount

Code: Select all

index=0;
jobs[]=<allKnownJobs>;
onTick(eventData)
{
    index= (index+1)%jobs.count; // O(1) 
    assignBotTo(jobs[i]); // O(1) for jobs[i]; Method is probably just iterating through every Network and checking if it overlaps AND has a free Bot and just takes the first. 
                          // -> So O(m) while m is most of the time much less than the amount of each robot. (Normally about 1 port for more than 100 bots
}

So it is technically not O(1) for the whole calculation, but O(1) to get the Job and not O(n). And for the whole calculation i guess it is about T(n,m) = 4m, while m can almost be seen as a constant. So we get very near to O(1).

Back to Topic:

I have a few cents to add to that Topic:

• Performance wise:
  • Sorting/Ordering/Prioritizing takes Calculation time that is higher than the current.
  • But the amount of overall calculation would be less, since Bots would move in a optimized way and would finish their jobs faster, which would result in more Bots overall available, which means less Bots that are needed, which then reduces calculation times for Bot "pathfinding", Energy, Movement, ...
  • In case the same job is very near (e.g. same chunk) Construction Bots could make use of the Worker Cargo upgrade and carry multiple e.g. Assemblers to place 2 or 3 directly after each other. This would also reduce the amount of calculations for the Bots, since only the Path for the Bot from port->pickup->drop1->drop2->[...]->dropN->roboport is needed, instead of 3 Bots calculating the (almost) same path for port->pickup->drop->port
  • Bots should also firstly check if they can make their way to the target. If they CAN'T make it, they should find a route over roboports. More than 1 time I had a Network in the Shape of a ] and the Bots at the bottom left Corner tried to reach the Top left corner, but after 1/4 of the way the just flew back to the roboport where they started and have held a few hundered items, consumed masses of energy, needed masses of calculation, had to be saved in each save, caused pathfinding for biters trying to hunt them.
  • Also pick a Bot nearest to the pickup location. further reduces Bot path and by this lifetime and calculation time.
• Quality of Live wise:
  • When using a Personal roboport, the Player expects, that the Jobs that are the nearest to him are finished first. I for example often expand my mainbus using a PersonalRoboport: Stand on a Belt, and let the Bots do their work.
  • Players would get their constructions finished much faster.
  • Performance suggestions would also improve the way Logistic Bots are working.

I would really love to see this implemented, but I fear in this side-case they won't ... =(

Greetings
Pingger

[SockPuppet]

As much as I love the personal roboport to speed up basically anything remote, whether it is removing trees or laying down blueprints, I have noticed something inefficient.

My suggestion is:
"Have bots handle tasks NEAR the player before handling tasks FAR from the player".
Currently the observed behaviour is:
"Have bots handle tasks FAR from the player before handling tasks NEAR the player".

Say you have a five trees in a line you want to demolish and you have one robot in your personal roboport and you are standing next to the first tree

Code: Select all

Player - Tree 1 - Tree 2 - Tree 3 - Tree 4 - Tree 5

You mark all trees for deconstruction. Your bot from your personal roboport heads out.

Now say you have trees at distance 1, 2, 3, 4, 5 squares away.
The robot will start at distance 5, tear it down, bring back the wood.

Code: Select all

Player - Tree 1 - Tree 2 - Tree 3 - Tree 4

Then it will do distance 4, tear it down, bring back the wood. etc.
Player - Tree 1 - Tree 2 - Tree 3
etc.

Code: Select all

Player - Tree 1 - Tree 2 - Tree 3 -        -
Player - Tree 1 - Tree 2 -        -        -
Player - Tree 1 -        -        -        -
Player -        -        -        -        -

So when you don't move, it will travel 5+5, 4+4, 3+3, 2+2, 1+1 blocks = 30 blocks.

My suggestion is to have robots start at distance 1, tear it down, bring back the wood. Distance 2, tear it down, etc. It will travel 1+1, 2+2, 3+3, 4+4, 5+5 blocks = still 30 blocks.

Code: Select all

Player -        - Tree 2 - Tree 3 - Tree 4 - Tree 5
Player -        -        - Tree 3 - Tree 4 - Tree 5
Player -        -        -        - Tree 4 - Tree 5
Player -        -        -        -        - Tree 5
Player -        -        -        -        -       

You might say, it is still the same distance, it does not save time. This is true, in case you are standing still.

Now say you don't want to wait for every tree your faithful bot tears down. Now you move closer to the remaining trees after each tree is removed.

In the old case it does not really matter, as you can't move closer because there is a tree in the way.
In the new case, it does matter. You now have your bot move 1 square away, tear down, bring back the wood.

Code: Select all

Player - Tree 1 - Tree 2 - Tree 3 - Tree 4 - Tree 5
Player -        - Tree 2 - Tree 3 - Tree 4 - Tree 5

Then, you move one square closer.

Code: Select all

       - Player - Tree 2 - Tree 3 - Tree 4 - Tree 5

Your bot moves again 1 square, etc.

Code: Select all

       - Player -        - Tree 3 - Tree 4 - Tree 5
       -        - Player - Tree 3 - Tree 4 - Tree 5
       -        - Player -        - Tree 4 - Tree 5
       -        -        - Player - Tree 4 - Tree 5
       -        -        - Player -        - Tree 5
       -        -        -        - Player - Tree 5
       -        -        -        - Player - 

Your bot will have travelled 1+1, 1+1, 1+1, 1+1, 1+1 = 10 blocks.

That's 3 times as efficient! And this isn't even for max range, or 2D.

WHY: Basically, it's not the efficiency that I prefer, but rather the wait time when constructing/deconstruction a large patch. I have 10 bots, and they travel to get that tree at max distance even though I'm standing next to a tree that should be demolished as well. They can handle a dozen deconstructions at 1-2 range in the same time to remove that tree at max distance. It's the wait that bugs me.

Hence this suggestion. Search didn't return results for this, hence this topic.

[burner]

+1
Anyway I remember that there is topic of that same thing. But I think it mostly proves that this feature is important.

[Koub]

[Koub] Merged new topic into older topic

[JohnyDL]

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

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.

[d3x0r]

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

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.

it's a thought... but it only has to be done once, in one tick, once the selection has been completed. The work queue can then just be kept and dispatched as each bot finishes.

[JohnyDL]

it's a thought... but it only has to be done once, in one tick, once the selection has been completed. The work queue can then just be kept and dispatched as each bot finishes.

yeah, that's the math I did it has to be done only once in each tick and then the player moves and all the bots move and those distances are different in the next tick so you have to do it again, and remember that's if there are only 1000 ghosts on the map and one player. For multiplayer I've seen maps with 25-30,000 ghosts, so for each player the Pythagorus needs doing and comparing to find the minimum distance to the closest player with a personal roboport, taking the pythag step to 250k cycles per player and then it has to be sorted, that's 250k cycles assuming its linear (which I know it's not) and there'd be the overheads, with 10 players we're really looking at 1/6th of the processing power available to ticks being spent finding who's closer to which job, with 100 players and I've done MMO factorio maps with twice that the computer spends more time looking at who's closest to which ghost and what to prioritise than playing the game, it really is an unfeasible amount of number crunching to fit in and it won't scale, it scales badly for slow computers, it scales badly for multiplayer and it scales badly for bigger and bigger factories.

And before you say well don't calculate and sort the things that're too far away, that's not an option, it's a task you can do at the blink of an eye with visual data cause your head computer is very optimised for distance estimation for multiple targets and destinations at a glance the computer only 'sees' the 64 bits it's working on at a time and only 'knows' what is where by going through the pythagorus steps and working it out step by step.

[d3x0r]

it's a thought... but it only has to be done once, in one tick, once the selection has been completed. The work queue can then just be kept and dispatched as each bot finishes.

yeah, that's the math I did it has to be done only once in each tick and then the player moves and all the bots move and those distances are different in the next tick so you have to do it again, and remember that's if there are only 1000 ghosts on the map and one player. For multiplayer I've seen maps with 25-30,000 ghosts, so for each player the Pythagorus needs doing and comparing to find the minimum distance to the closest player with a personal roboport, taking the pythag step to 250k cycles per player and then it has to be sorted, that's 250k cycles assuming its linear (which I know it's not) and there'd be the overheads, with 10 players we're really looking at 1/6th of the processing power available to ticks being spent finding who's closer to which job, with 100 players and I've done MMO factorio maps with twice that the computer spends more time looking at who's closest to which ghost and what to prioritise than playing the game, it really is an unfeasible amount of number crunching to fit in and it won't scale, it scales badly for slow computers, it scales badly for multiplayer and it scales badly for bigger and bigger factories.

And before you say well don't calculate and sort the things that're too far away, that's not an option, it's a task you can do at the blink of an eye with visual data cause your head computer is very optimised for distance estimation for multiple targets and destinations at a glance the computer only 'sees' the 64 bits it's working on at a time and only 'knows' what is where by going through the pythagorus steps and working it out step by step.

the map is already sectioned into sectors; so there's only a few sectors that you'd have to do... unless you drug a selection rectangle to deconstruct the whole map.
There's no real reason to make it ALWAYS player-centric just having it be somewhat ordered would be good enough... being entirely random is kinda crazy; it's not even in order it was built, but someone mentioned it's stored in a hash, which is probably what's introducing the randomness.; at least then I could follow the construction to allow robots to travel closer.
and you don't even NEED sqrt; manhattan distances would be good enough.
Yes, when the selection is completed, all players on a map would need to calculate the same ordered list and check if they come in range of the next pending job to be done... but again it's really only once the selection is completed, take the area and the player that did it and do the computation once.

[JohnyDL]

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.

But the players don't do the calculations themselves except for corroboration in multiplayer (I think) it's all done server side with the players doing their personal rendering from the shared data.

But anyway back to the topic if it's without respect to the player it's a cake walk just order the chunks left to right top to bottom and order then by inside the chunks left to right top to bottom, adding stuff to the order when it's created since that list order is static but that doesn't give prioritising nearest item to the player first. Or sort with respect to item type, again not with respect to the player or with respect to order of job creation not the player and what happens if you place hundreds of orders at the same time?

But if it is with respect to the player you need to do the distance calculations with respect to all players at the same time because personal robots don't look for jobs to do but rather jobs will look for available robots (as one of the devs pointed out near the top of the thread). This may sound strange but it logically makes sense for construction, when there are more robots than jobs each job just finds the nearest roboport with bots and has a bot from there do the job even if there are more jobs than bots when available bots hits 0 then the rest of the queue has to wait. Since the jobs only really need to look at the roboports and players to find distances to available bots you cut down a huge amount of processing each chunk can recalculate the order of roboports for it (although I don't think it does) and it's just search them until a bot is found

On the other hand bots looking for jobs if there are no jobs sure the bots can quit looking just as easily as before but if there are any jobs each bot has to look at each job and work out which is closest to them without the ability to use roboports as a shortcut to working out how far away a bunch of bots things are at the same time. The bots also have to check that there isn't a much closer bot somewhere else later in their order that can do the job which again is job looking for bots anyway. And you don't get the incidental benefit of when jobs can't find bots then tell the player *number* of items are missing bot for construction and *number* of items missing from logistics network

[SockPuppet]

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

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.

I understand that doing a perfect match for a moving target will take extra computational power. However, dismissing it just because it takes 1.6% of factorio's total computational power is too simple reasoning.

There are a few things you should also consider:
- By far the most important argument: the personal roboport is something VERY visible to the player. It is one of the few things that is always on-screen, in use and used for a reason. If it becomes active, the player just made a VERY intentional action and is likely watching the result of that action. A player couldn't care less if on the other side of his factory that inserter is moving just that bit slower because it couldn't place a green circuit. However, that forest not being cleared right in front of the player, that becomes annoying.

- The action of a personal roboport takes place only when a player (or 400 players, whatever you want) makes a deconstruction command. Going from idle and creating the command to clear a forest the size of the personal roboport's range takes somewhere between 500ms and a few seconds. That's billions of cycles.

- The player does not use the personal roboport all the time. The time I'm (de)constructing things is far less than the time I'm running around, waiting for things to resupply or thinking about what I want to do next. It isn't used every second of the game.

- The current deconstruction looks like it takes a random selection, which never clears a whole area, but always leaves a few items pending. You don't get a nice clear area to start your work on. Instead you must wait for most of the deconstruction to complete (say 80%) instead of getting to work after 10%. See the attachment what I mean. Why isn't it doing this per grid block? I still have no area to start construction. (yes, this is a 36k deconstruction of yellow belts, with creative mod to keep my inventory empty and be able to have way more bots than in the normal game. It also didn't like the deconstruction action, stalling the game for a few seconds, but still rendering. With creative beacons you can even cause the game's renderer to stall, showing a black screen!).

- The distance computation does not have to be perfect. You can cut a lot of corners. Here are some tips (maybe a developer will even look at it):

Code: Select all

- Do not analyze the entire world, but only the range of the personal roboport.
- Do personal roboport range + N and you have N steps to compute the edge/range.
- It doesn't even have to be perfect: Don't do the entire personal roboport range, but only compute a radius of 6 around the player. In the worst case, you just saved 30*30 - (6*2)*(6*2) = 756 computations and only have 16% of your total computation left, while the (de)construction performance is better than the current random selection. The computation does not become more expensive with more roboports, as you can keep the radius fixed at 6.
- 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.
- 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.

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

The devs have done amazing work to optimize Factorio even further for 0.16. Why not use part of these advantages to increase the on-screen performance of personal bots? The average player is more likely to use a personal roboport, than to create a megabase that runs into UPS problems.

[JohnyDL]

There are a few things you should also consider:
- By far the most important argument: the personal roboport is something VERY visible to the player. It is one of the few things that is always on-screen, in use and used for a reason. If it becomes active, the player just made a VERY intentional action and is likely watching the result of that action. A player couldn't care less if on the other side of his factory that inserter is moving just that bit slower because it couldn't place a green circuit. However, that forest not being cleared right in front of the player, that becomes annoying.

But it's not the few inserters half way across the map in 0.12, 0.13, and 0.14 I experienced significant amounts of lag on multiple playthroughs and it makes running hard, it makes robots fly perceptably slower it's really not something that can be partitioned to other parts of the map and even if it was in multiplayer there's usually no part of the map that's unobserved.

- The action of a personal roboport takes place only when a player (or 400 players, whatever you want) makes a deconstruction command. Going from idle and creating the command to clear a forest the size of the personal roboport's range takes somewhere between 500ms and a few seconds. That's billions of cycles.

Nope the actions of a roboport happen all the time why do you think people get annoyed when they're on trains and their bots get chosen to do a task and fly off getting left behind unable to do their job or keep up with the player.

The player does not use the personal roboport all the time. The time I'm (de)constructing things is far less than the time I'm running around, waiting for things to resupply or thinking about what I want to do next. It isn't used every seco

Again regardless of whether the player is using the personal roboport the personal roboport is working unless you take it out of your power armour or take your power armour off, you've made a fundamental mistake in how personal robots appear to work because of how they aren't connected to the wider network of roboports vs how they actually work in coding.

- The current deconstruction looks like it takes a random selection, which never clears a whole area, but always leaves a few items pending. You don't get a nice clear area to start your work on. Instead you must wait for most of the deconstruction to complete (say 80%) instead of getting to work after 10%. See the attachment what I mean. Why isn't it doing this per grid block? I still have no area to start construction.

I know it's frustrating and it frustates me too but it's down to the way that items look for bots, it's not random it's sequential and when an item can't find a bot it's cycled to the end of the queue you'll notice when you first enter an area or set a construction or deconstruction plan the inital wave seems somewhat organised and this is because the sequential list is organised but when your bots get back in different ticks the list is in a different point in it's search cycle, a trick I use to clear at least a patch to start working is to deconstruct in sections, or to stand on the edge and work in or carry more bots than I could possibly use and flash off and on my personal roboports when the wood is returning sending hundreds of bots out to pick up trees and letting them return to the logistics network and not filling my inventory with wood. Or actually pitching in and giving a small hand where I want to get started. None of these are as perfect as bots getting priority by distance but since priority by distance is such a resource hog I put up with it.

- The distance computation does not have to be perfect. You can cut a lot of corners. Here are some tips (maybe a developer will even look at it):
- Do not analyze the entire world, but only the range of the personal roboport.

Only looking inside the areas of personal roboports has been discussed, regardless of whether you have any ghosts or plans, construction or tree removal or whether there's nothing there you have to do the same checks of the surface as said by a dev earlier

Ideally, a personal roboport would, each tick, find all ghost images in range, quicksort them by distance, and then launch robots in order of closest to furthest away until it ran out of robots. Well, one robot per tick.

The problem with that is "find all ghost images in range" is an O(N) search of the surface - the time scales with the area to search and the number of entities in that area - even when there are no ghosts. The same cost as calling "surface.find_entities_filtered({type="ghost", area=...})" each tick for each player.

I and other players frequently have 5 personal roboport mark 2s that's 8000 of these surface tile checks every single tick, that's if there's a job there or not the only time that there is less lag using this suggestion is if there are both construction orders and deconstruction orders and it adds up to over 8000 jobs in that area, the only realistic way that happens is if you're covering a location in concrete, clearing some trees and placing a bunch of machines with the same blueprint, not impossible but not likely like you said 90%+ of the time you're not doing any construction and your personal robots can't know that unless they do this check

- Do personal roboport range + N and you have N steps to compute the edge/range.

Actually it's at minimum N^2 steps but again you then have to do the surface search on each and every time.

- It doesn't even have to be perfect: Don't do the entire personal roboport range, but only compute a radius of 6 around the player. In the worst case, you just saved 30*30 - (6*2)*(6*2) = 756 computations and only have 16% of your total computation left, while the (de)construction performance is better than the current random selection. The computation does not become more expensive with more roboports, as you can keep the radius fixed at 6.

This is about the only way that seems marginally sensible the 144 tiles directly around the player except the Devs will argue why 144, why not 100, or 49 that works in fact we'll only search as far as the player can reach and mine by hand. While players will argue that it's too small

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

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

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

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.

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.

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.