Personal robots prioritizing nearest first

[Slayn25]

In a future update would it be possible to implement both methods and have it selectable in the options? Differed by singleplayer/multiplayer?

[Ranakastrasz]

That sounds like a lot more extra work than my suggestions above because you recalculate stuff all the time and the robot count doesn't really correlate to the radius you should cover.

It sparked an idea though: The roboport range is changed dynamically to be just large enough to have a ghost that lacks a bot. So when new ghosts is added within the range and no bot is available the range is reduced to the distance the new ghost has. When all ghosts in range are dealt with the range grows by one each tick till it can't service a ghost again or the maximum is reached. When you move the roboport range could shrink so no new fields are added. Then each tick the range grows one field up to the maximum again, with the condition that all ghosts can be serviced.

That way, when you stand in the middle of a field of ghosts your roboport range would be really small, only near ghosts would be serviced. And when you move around the work would be actually less because a smaller roboport range means less work.

Well, yea, its a lot of work programming-wise, but I was trying to get around the given restrictions. We can't just take every ghost image in range and sort them, because that would be too expensive according to the devs. I don't believe that it would be expensive, but I was trying to find a faster workaround. Its terrible, and honestly reminds me of the garbage code I wrote for Modular Armor Revamp to get Conduits and Burner Generators to work, but it would work. Its a mess, looks terrible, but is functional.
----
I would prefer doing it in a number of different ways If I were to code it.

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.

Given how horifically inefficent my Modular armor mod was, with two nested loops and otherwise, but still ran fine without any slowdown, I don't really believe this would be a problem.

The issue is, apperently, that ghost images request the job, rather than the roboports finding ghost images. I think that is backwards, but It makes a bit of sense.

[Rseding91]

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.

[mp0011]

It should not be much harder than finding buildings within range of electric poles/substations, or machines in range of beacons. Does the game do it all the time, or just when something is changed?

[Rseding91]

It should not be much harder than finding buildings within range of electric poles/substations, or machines in range of beacons. Does the game do it all the time, or just when something is changed?

Only when an electric pole or entity that connects to electric poles is built does one or the other look for things to connect to.

[whitecold]

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.

"find all ghost images in range" must be recalculated anyway when the player moves as it is now, the only thing that is added is the ranges that they must be sorted by. In any case, the number of players is limited, so performance there is not as critical.

[Engimage]

I think it is possible to add a flag like has_ghosts to a chunk and proceed with search only if a player has that chunk in range. Player can keep the list of chunks he can reach and update it with on_player_moved event.
For stationary roboports it is even easier. When you place a ghost and/or roboport it will be added to a nearest roboport's queue which can be sorted by range at the moment of placement (so this will not consume CPU much).

[Ranakastrasz]

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.

"find all ghost images in range" must be recalculated anyway when the player moves as it is now, the only thing that is added is the ranges that they must be sorted by. In any case, the number of players is limited, so performance there is not as critical.

Precisely why I went out of my way to make up a workaround, by screwing with the range of the roboports.

[Lubricus]

Maybe an R-tree could be used to optimize the process to find the nearest "ghosts" stuff to do for the robots. Not the easiest to code...
https://en.wikipedia.org/wiki/R-tree

[Patashu]

Maybe an R-tree could be used to optimize the process to find the nearest "ghosts" stuff to do for the robots. Not the easiest to code...
https://en.wikipedia.org/wiki/R-tree

I was about to suggest this, then I saw you posted it

Doing queries like 'find the closest X near Y' is a big problem in computer science, with a lot of work put into it. It makes stuff like google maps efficient, for example.

Of course, it would be a lot of programming work, but if this feature was desired to be implemented, this is the kind of thing you would look at for inspiration.

[PetWolverine]

Simplest solution: User controlled construction zone size. With ctrl-scroll.
User reduce zone size, and bots works exactly as in lower example.

This suggestion from page 1 seems perfect to me. It adds no extra processing step such as sorting a lot of things by distance. The personal roboports already have a variable range depending on how many you're using, so changing the radius is already supported. Just make the current radius a maximum - still increasing with more ports - and offer the player a way to reduce the range.

This removes a downside of having extra roboports, allowing the player to pile them on without having robots wander off to do distant tasks, and allows efficient, targeted construction, or disabling the personal roboports entirely without unequipping them, or standing for hours while robots work on a huge project, according to taste.

I went from 7 personal roboports to 5 mainly to reduce the range, but I miss the extra 50 bots, so I would like this a lot. And 5 ports is still too much range.

It would be useful to make this adjustable in regular roboports as well, such as with a pair of sliders in the building's UI. Then you could add roboports around the edge of a network to act as extra charging stations without having them form unwanted links with neighboring networks.

[mrvn]

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.

Except that part you already do. You already find all entities that are ghosts in range of the roboport. So however you do that (and I'm sure that's not per tick) wouldn't change. Only thing that changes is that you now insert the found ghosts into a (semi) sorted structure.

And for multiplayer or moving around there really should be a cache for this in each chunk. So you query the chunk if it has any ghosts and if not skip it. No need to check every tile of a chunk.

[Rseding91]

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.

Except that part you already do. You already find all entities that are ghosts in range of the roboport. So however you do that (and I'm sure that's not per tick) wouldn't change. Only thing that changes is that you now insert the found ghosts into a (semi) sorted structure.

And for multiplayer or moving around there really should be a cache for this in each chunk. So you query the chunk if it has any ghosts and if not skip it. No need to check every tile of a chunk.

No we don't. We take a ghost from the list of all ghosts on the surface and check which logsitic network(s) it's in and try to dispatch a robot to handle it once per tick.

[mrvn]

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.

Except that part you already do. You already find all entities that are ghosts in range of the roboport. So however you do that (and I'm sure that's not per tick) wouldn't change. Only thing that changes is that you now insert the found ghosts into a (semi) sorted structure.

And for multiplayer or moving around there really should be a cache for this in each chunk. So you query the chunk if it has any ghosts and if not skip it. No need to check every tile of a chunk.

No we don't. We take a ghost from the list of all ghosts on the surface and check which logsitic network(s) it's in and try to dispatch a robot to handle it once per tick.

Say you have 100000000000 ghosts, no roboports and a personal roboport. Are you saying that each tick the 100000000000 ghosts would check if they are in range of the personal roboport and if so check if the player has a robot idle and if so assign the job? That really screams for an optimization. Like have a list/array/heap of ghosts in each logistic network and have bots request a ghost when they are idle. (and have bots go to sleep till the network has ghosts)

Also, if it is a list then why are ghosts assigned in order until the player runs out of bots and then have a random pattern? A list to me would mean the order ghosts are assigned is the order in which they were created.

[Rseding91]

Say you have 100000000000 ghosts, no roboports and a personal roboport. Are you saying that each tick the 100000000000 ghosts would check if they are in range of the personal roboport and if so check if the player has a robot idle and if so assign the job? That really screams for an optimization. Like have a list/array/heap of ghosts in each logistic network and have bots request a ghost when they are idle. (and have bots go to sleep till the network has ghosts)

Also, if it is a list then why are ghosts assigned in order until the player runs out of bots and then have a random pattern? A list to me would mean the order ghosts are assigned is the order in which they were created.

We take a ghost from the list of all ghosts on the surface and check which logsitic network(s) it's in and try to dispatch a robot to handle it once per tick.

*a* ghost *one per tick*. Not all ghosts each tick.

[Factory Lobster]

Haha, Rseding91 may as well just post the game code at this point. Let us dissect it and make specific programming recommendations

[Ranakastrasz]

No we don't. We take a ghost from the list of all ghosts on the surface and check which logsitic network(s) it's in and try to dispatch a robot to handle it once per tick.

Well, that IS O(1).

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

[mrvn]

Say you have 100000000000 ghosts, no roboports and a personal roboport. Are you saying that each tick the 100000000000 ghosts would check if they are in range of the personal roboport and if so check if the player has a robot idle and if so assign the job? That really screams for an optimization. Like have a list/array/heap of ghosts in each logistic network and have bots request a ghost when they are idle. (and have bots go to sleep till the network has ghosts)

Also, if it is a list then why are ghosts assigned in order until the player runs out of bots and then have a random pattern? A list to me would mean the order ghosts are assigned is the order in which they were created.

We take a ghost from the list of all ghosts on the surface and check which logsitic network(s) it's in and try to dispatch a robot to handle it once per tick.

*a* ghost *one per tick*. Not all ghosts each tick.

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.

[PetWolverine]

We take a ghost from the list of all ghosts on the surface and check which logsitic network(s) it's in and try to dispatch a robot to handle it once per tick.

*a* ghost *one per tick*. Not all ghosts each tick.

This explains why I often see ~600 items reported as missing construction materials when I have way, way more ghosts than that. It must be alerting me to the last 10 seconds' worth of ghosts that it has been unable to find stuff for.

[torne]

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