Factorio Forums

torne wrote:

mrvn wrote: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).

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

Linosaurus wrote:

Ranakastrasz wrote: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 wrote:

Linosaurus wrote:

Ranakastrasz wrote: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.

mrvn wrote:

Ranakastrasz wrote: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.

Ranakastrasz wrote: [... quote that doesn't matter ...]

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
}

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

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

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 wrote: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 wrote:

d3x0r wrote: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.

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

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.

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

SockPuppet wrote: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.

SockPuppet wrote: - 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.

SockPuppet wrote: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

SockPuppet wrote:- 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.

SockPuppet wrote:- 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.

Rseding91 wrote:

Ranakastrasz wrote: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.

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

SockPuppet wrote:- 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.

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.

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.

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.

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

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.