Personal robots prioritizing nearest first

[mrvn]

i guess it is the way it is for performance reasons.

calculating which entity is currently 'nearest' has to be calculated every time a single entity is removed or you move.

i dont think the QOL improvement would justify the performance hit.

But maybe i'm wrong here, who knows but the devs.

Entities could simply be kept in a heap structure instead of a hash table as it seems to be now. The nearest entity would naturally float to the top of the heap. Insertion and removal would take O(log n) time instead of O(1) amortized time as for the hash table. For a 64x64 tiles region insertion and removal would be up to 16 times slower. Would that even be noticable? Or would it totaly disapear under the cost of allocating or freeing and initializing a new ghost entity. I don't think the per entity cost would be that huge, esspecially if it is only used for personal roboports, not all roboports.

When you move the distance of every entity changes. Also a lot of entities can enter or leave the reachable area. If you change the diatance of every entity in the heap separately then that would be O(n * log n) but if you instead just change the distance and then re-heap the whole thing in one go it is O(n). Computing the sqrt(dx*dx + dy*dy) for each entity costs probably more than re-heaping.

Now if the player is running around with 6 exoskeletons, driving a car or riding a train this might be a problem. First off I would love it if roboports would simply stop sending out robots while moving. At least while moving faster than the robots can fly. Secondly you could take advantage of the chunks. For each chunk compute the minimum distance to the player. Then start with the chunk the player is in and find the nearest entity there. If any other chunk has minimum distance less than the nearest entity then add entities from that chunk to the heap. Otherwise handle the nearest entity. Worst case for this algorithm will be when you stand unmoving in a huge (de)construction area near the end. All the chunks lying on a circle around the player will have to be considered. But that's still a lot better than dealing with the whole area under the roboport (linear instead of quadratic).

If that is still too much:

* Does it have to react instantaneous? You could only re-heap every 1-5 seconds instead of on every move.You could devide the chunks into subchunks to get finer groups of entities to sort.

* Does it have to be perfect? Compute the distance of an entity as distance to center of chunk + distance of chunk to player. Handle the chunk (+ neighbours when near a border) the player is in prefectly, the rest by approximation. You can then keep a heap of entities in each chunk and keep a heap of chunks sorted by the approximately nearest entity of each chunk. Moving around only resorts the heap of chunks, not each chunks heap.

That last one would also be useful for using this with roboports. When a construction bot needs work it picks the nearest roboport that needs work done, then the chunk nearest to that roboport that needs work done and last the entity nearest to the center of the chunk..

[Rseding91]

i guess it is the way it is for performance reasons.

calculating which entity is currently 'nearest' has to be calculated every time a single entity is removed or you move.

i dont think the QOL improvement would justify the performance hit.

But maybe i'm wrong here, who knows but the devs.

Entities could simply be kept in a heap structure instead of a hash table as it seems to be now. The nearest entity would naturally float to the top of the heap. Insertion and removal would take O(log n) time instead of O(1) amortized time as for the hash table. For a 64x64 tiles region insertion and removal would be up to 16 times slower. Would that even be noticable? Or would it totaly disapear under the cost of allocating or freeing and initializing a new ghost entity. I don't think the per entity cost would be that huge, esspecially if it is only used for personal roboports, not all roboports.

When you move the distance of every entity changes. Also a lot of entities can enter or leave the reachable area. If you change the diatance of every entity in the heap separately then that would be O(n * log n) but if you instead just change the distance and then re-heap the whole thing in one go it is O(n). Computing the sqrt(dx*dx + dy*dy) for each entity costs probably more than re-heaping.

Now if the player is running around with 6 exoskeletons, driving a car or riding a train this might be a problem. First off I would love it if roboports would simply stop sending out robots while moving. At least while moving faster than the robots can fly. Secondly you could take advantage of the chunks. For each chunk compute the minimum distance to the player. Then start with the chunk the player is in and find the nearest entity there. If any other chunk has minimum distance less than the nearest entity then add entities from that chunk to the heap. Otherwise handle the nearest entity. Worst case for this algorithm will be when you stand unmoving in a huge (de)construction area near the end. All the chunks lying on a circle around the player will have to be considered. But that's still a lot better than dealing with the whole area under the roboport (linear instead of quadratic).

If that is still too much:

* Does it have to react instantaneous? You could only re-heap every 1-5 seconds instead of on every move.You could devide the chunks into subchunks to get finer groups of entities to sort.

* Does it have to be perfect? Compute the distance of an entity as distance to center of chunk + distance of chunk to player. Handle the chunk (+ neighbours when near a border) the player is in prefectly, the rest by approximation. You can then keep a heap of entities in each chunk and keep a heap of chunks sorted by the approximately nearest entity of each chunk. Moving around only resorts the heap of chunks, not each chunks heap.

That last one would also be useful for using this with roboports. When a construction bot needs work it picks the nearest roboport that needs work done, then the chunk nearest to that roboport that needs work done and last the entity nearest to the center of the chunk..

Now startup multiplayer with 10 people and do all of that logic 10 times per game tick when they've built 30,000 ghosts on the map.

It would ruin performance. It already has in the past and changes had to be made.

[vedrit]

I think this very much needs to be implemented. Here are my two cents.
Rather than trying to find the distance of every marked object and determining which is closest, why not modify the current method to do the following.
The game will break the original bounding box drawn by the player down into steps radiating from the center.
Starting at the origin step, the game tells those objects to find bots. Only until that step either every object has a bot, or has reached some other threshold, will the game move on to the next step.

Sound reasonable?

[Hannu]

Now startup multiplayer with 10 people and do all of that logic 10 times per game tick when they've built 30,000 ghosts on the map.

It would ruin performance. It already has in the past and changes had to be made.

Is this very marginal play style with tens of players and 100000 bots preferred over all other styles? In my personal opinion optimizing for normal robot assisted building would serve larger number of players. Every player clear couple of thousands of wood or build things with couple of hundreds of entities with reasonable number of personal bots. They lose hours of playtime, because that kind of tasks are very common, and get annoyed because all things are optimized for insane bot based multiplayer megabases and have very poor performance in normal situations.

If it is "official" decision then it is and everyone have to live with it, but it could be better to tell it explicitly and do not hide behind vague CPU performance every time someone ask or suggest quality of life improvements. Clear decision would probably also decrease futile suggestions and whining.

[Rseding91]

Now startup multiplayer with 10 people and do all of that logic 10 times per game tick when they've built 30,000 ghosts on the map.

It would ruin performance. It already has in the past and changes had to be made.

Is this very marginal play style with tens of players and 100000 bots preferred over all other styles? In my personal opinion optimizing for normal robot assisted building would serve larger number of players. Every player clear couple of thousands of wood or build things with couple of hundreds of entities with reasonable number of personal bots. They lose hours of playtime, because that kind of tasks are very common, and get annoyed because all things are optimized for insane bot based multiplayer megabases and have very poor performance in normal situations.

If it is "official" decision then it is and everyone have to live with it, but it could be better to tell it explicitly and do not hide behind vague CPU performance every time someone ask or suggest quality of life improvements. Clear decision would probably also decrease futile suggestions and whining.

The decision was already made long ago when we decided to program it as it works now. That's not to say it won't ever change but right now it's working exactly as we designed it to.

[Engimage]

I find it really annoying as it is right now. I do understand that it was designed this way to optimize CPU load but still I see it would be beneficial if the behaviour would be changed to the opposite or altered by any other means to make it work.
I do see next benefits that we could possibly get to improve gameplay:
1. Prioritizing different types of buildings. For example it is mostly essential to build power lines before anything else, then Roboports, then turrets with walls being the last.
2. Prioritizing closest entities first
...

While this is some hit on CPU I do not see it being that huge as bots will not need making their decisions every tick if construction/deconstruction queue does not change.
I do understand that currently both logistic and construction bots follow the same logic so it is well streamlined as it is. But I think the game will really benefit from such change and many people would be grateful.

[BrickNukem]

Given the sentiment of some of the posters here, I feel the need to say I fricking love this game and how smooth the experience is. Despite it being a very minor annoyance (out of exceptionally few anyway), I decided to post this topic because I find it interesting. I don't mind that it's low on the priority list, and I fully trust you guys to find better ways to improve the game.

[mrvn]

Now startup multiplayer with 10 people and do all of that logic 10 times per game tick when they've built 30,000 ghosts on the map.

It would ruin performance. It already has in the past and changes had to be made.

The number of ghosts on the map is irelevant. The number of ghosts in range of players is. Also when you do the approximation using chunk midpoints then the number of players is irelevant too, since each chunk maintains its heap independent of any player. What is relevant is the number of robots, which would be greater with 10 players, and work is only done when a robot needs a job, not 10 times a tick.

But lets look at the simplest case, just a global heap. Then yes, you need one heap per player. Adding or removing an entity becomes 10 times as expensive. But with just 30000 ghosts on the map that is 10 sqrt() calls, at most 150 comparisons and at most 150 swaps of a pointer per ghost created or destroyed (not per tick, mind you). Add some overhead for backpointers and to coordinate players. Yeah, this does not scale well. I really opt for using the per chunk heap with approximate distance.

Note: The per chunk heaps could be used by roboports too and then you have easily 100+ roboports and 1000+ bots. Players, even 10 of them, are negible there.

Note2: Adding 30000 ghosts in one go would mean a hickup in the game for sure. But I bet you could just add the ghosts to each chunk unsorted and then re-heap each chunk the first time it gets checked for ghosts. Unless the player has 30000 construction bots most chunks would only be checked for ghosts many seconds later.

Note3: if the game gets a bit slower by this I would still want it. The benefit of nearest first bots would be huge even if the ups drops when you add 30000 ghosts.

[Engimage]

sqrt() calls, at most 150 comparisons and at most 150 swaps of a pointer per ghost created or destroyed (not per tick, mind you). Add some overhead for backpointers and to coordinate players. Yeah, this does not scale well. I really opt for using the per chunk heap with approximate distance.

You do not need sqrt for comparison purposes just leave it as it is. You need sqrt only to know the exact distance which does not matter here.

[malventano]

It would ruin performance. It already has in the past and changes had to be made.

Silly question, but have you considered that if a simple prioritization could cut the time the bots were active in half, that it would more than makeup for the prioritization calculation overhead? If they get done twice as quickly, even if that optimization is only applied to bots launched from the personal roboport, that's a considerable QoL improvement, and would most definitely be a net positive since the bots would go back to inventory in half the time.

[mrvn]

It would ruin performance. It already has in the past and changes had to be made.

Silly question, but have you considered that if a simple prioritization could cut the time the bots were active in half, that it would more than makeup for the prioritization calculation overhead? If they get done twice as quickly, even if that optimization is only applied to bots launched from the personal roboport, that's a considerable QoL improvement, and would most definitely be a net positive since the bots would go back to inventory in half the time.

Couldn't have said it better. Even with a lower UPS it would still be faster overall.

[orzelek]

It would ruin performance. It already has in the past and changes had to be made.

Silly question, but have you considered that if a simple prioritization could cut the time the bots were active in half, that it would more than makeup for the prioritization calculation overhead? If they get done twice as quickly, even if that optimization is only applied to bots launched from the personal roboport, that's a considerable QoL improvement, and would most definitely be a net positive since the bots would go back to inventory in half the time.

Couldn't have said it better. Even with a lower UPS it would still be faster overall.

I'm not sure how difficult it would be... but maybe it could be optional?

From the discussion I gather that for people building stuff with 100's entities top it would work very well without problems. Especially in single player.
And those that plan to do 10k+ entity ghosts would keepit disabled.
(And yes I do realize making it optional might be a cost in itself - I think it would be worth it. Currently way that personal bots realize your orders always gets me puzzled.)

[BlackKnight]

Although I am sure there are many more items we would all like prioritized ahead of this as well as items that the devs find way more important at the moment, yet this 'bot-task priority by proximity' would still be a really great feature to add at some point in the future.

Forgive my ignorance on my limited knowledge of programming, but wouldn't it be sufficiently efficient to base all construction bot request tasks on the proximity within the grid from the players initial position when the request was made? Each bot would look for the lowest number not yet assigned to another bot which would be permanently attached to the grid until its task was completed or canceled.

[Koub]

I trust the devs. If they say they have thought about it, ad discarded it because the result would make things overall worse, they surely have their reasons.
I really wish, though, there was a solution to the fact that the bots build/deconstruct things in such a random-like pattern. I spent literally hours watching bots go back and forth when I built my wall around my base, whereas I could have sped things up so much by "helping" them walking as they would have advanced.

[vedrit]

I think this very much needs to be implemented. Here are my two cents.
Rather than trying to find the distance of every marked object and determining which is closest, why not modify the current method to do the following.
The game will break the original bounding box drawn by the player down into steps radiating from the center.
Starting at the origin step, the game tells those objects to find bots. Only until that step either every object has a bot, or has reached some other threshold, will the game move on to the next step.

Sound reasonable?

Am I chopped liver, or has this possible solution already been discussed and discarded?

[Ranakastrasz]

Square root isn't important. Aside from you always comparing dx*dx + dy*dy, instead of sqrt(dx*dx+dy*dy) if you don't need the actual magnitude, you can always use abs(dx)+abs(dy), and just get the square-like distance.



The issue, as I see it.

-Robots appear to chose random jobs, instead of ones that are most efficient, distance wise. While for the immobile roboport structure, this is OK, for the Personal roboport, it reduces efficiency significantly.
-Obvious solution, of sorting distances of the jobs, requires O(N log(N)) (Quicksort) which is too expensive, whereas the seemingly random jobs is O(1).

As such, we need something cheaper which still makes them feel smarter.

First thought, Blueprints inside and outside the roboport range are filtered. Square-like, so no square-root involved.
Second thought, you already know the distance, at one point, it has to have been calculated. however, a sort in this situation is too expensive, (not sure why)

Idea- Variable radius. Run once, determine how many jobs exist. If more than robotCount, shrink radius to cover exactly robotCount jobs. Issue, unlike a simple, Lowest/highest, you need to get the 10th lowest. Can't think how to do that off the top of my head, as it just goes back to running a quicksort...

Idea radius shrinks to sqrt(robotCount) by default (Precalculated), and every tick, expand/shrink it based on the situation. If more jobs than robots, shrink. If less jobs than robots, expand. Half a tile per tick, or something.
-In effect, it would use existing information, which is already recalculated every tick with player movement, change the range filter slightly, and use a simple comparison. I don't think that is more than O(N)

Assumptions and Evidence.
-- You do check the range, because otherwise robots couldn't know whether ghost images were inside or outside their radius.
-- You do know how many robots are available, because 10xRoboport, and inventory.
-- You probably know how many ghost images are around, I think, because you checked their range, and it choses a random one, I think.
-- It does recalculate, because personal roboports are mobile, and this probably happens every tick. (or every 10 ticks or something, since you don't move THAT fast)
-- Variable radius is possible, because multiple roboports.

Not sure if it would work, but I think it might.

[torne]

It works entirely backwards from how you are proposing - the ghosts are the thing the game is looking at, not the roboports.

For each ghost in turn:
1) Look for roboport networks whose build radius covers this ghost. If there's no network at all, it does nothing.
2) If there's at least one network network but none of those networks has the correct item, it triggers the "missing item" alert.
3) If there's a network with the item but no free robots, it triggers the "no robot" alert.
4) If there's a network with the item and a free robot, then the robot gets assigned to build this ghost.

The roboports aren't actively doing anything in this process, so having them change their radius dynamically can't really work.

[Ranakastrasz]

It works entirely backwards from how you are proposing - the ghosts are the thing the game is looking at, not the roboports.

For each ghost in turn:
1) Look for roboport networks whose build radius covers this ghost. If there's no network at all, it does nothing.
2) If there's at least one network network but none of those networks has the correct item, it triggers the "missing item" alert.
3) If there's a network with the item but no free robots, it triggers the "no robot" alert.
4) If there's a network with the item and a free robot, then the robot gets assigned to build this ghost.

The roboports aren't actively doing anything in this process, so having them change their radius dynamically can't really work.

1) Look for roboport networks whose build radius covers this ghost. If there's no network at all, it does nothing.

Adjust the roboport's build radius for that steop.

That said, I need to redo my idea due to assumptions being shown wrong.

[mrvn]

Although I am sure there are many more items we would all like prioritized ahead of this as well as items that the devs find way more important at the moment, yet this 'bot-task priority by proximity' would still be a really great feature to add at some point in the future.

Forgive my ignorance on my limited knowledge of programming, but wouldn't it be sufficiently efficient to base all construction bot request tasks on the proximity within the grid from the players initial position when the request was made? Each bot would look for the lowest number not yet assigned to another bot which would be permanently attached to the grid until its task was completed or canceled.

That would be just as hard because you have to find the lowest number that is within the range of the roboport. Sorting the reachable ghosts by a number is the same a sorting them by distance.

[mrvn]

Square root isn't important. Aside from you always comparing dx*dx + dy*dy, instead of sqrt(dx*dx+dy*dy) if you don't need the actual magnitude, you can always use abs(dx)+abs(dy), and just get the square-like distance.



The issue, as I see it.

-Robots appear to chose random jobs, instead of ones that are most efficient, distance wise. While for the immobile roboport structure, this is OK, for the Personal roboport, it reduces efficiency significantly.
-Obvious solution, of sorting distances of the jobs, requires O(N log(N)) (Quicksort) which is too expensive, 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.

As such, we need something cheaper which still makes them feel smarter.

First thought, Blueprints inside and outside the roboport range are filtered. Square-like, so no square-root involved.
Second thought, you already know the distance, at one point, it has to have been calculated. however, a sort in this situation is too expensive, (not sure why)

Idea- Variable radius. Run once, determine how many jobs exist. If more than robotCount, shrink radius to cover exactly robotCount jobs. Issue, unlike a simple, Lowest/highest, you need to get the 10th lowest. Can't think how to do that off the top of my head, as it just goes back to running a quicksort...

Idea radius shrinks to sqrt(robotCount) by default (Precalculated), and every tick, expand/shrink it based on the situation. If more jobs than robots, shrink. If less jobs than robots, expand. Half a tile per tick, or something.
-In effect, it would use existing information, which is already recalculated every tick with player movement, change the range filter slightly, and use a simple comparison. I don't think that is more than O(N)

Assumptions and Evidence.
-- You do check the range, because otherwise robots couldn't know whether ghost images were inside or outside their radius.
-- You do know how many robots are available, because 10xRoboport, and inventory.
-- You probably know how many ghost images are around, I think, because you checked their range, and it choses a random one, I think.
-- It does recalculate, because personal roboports are mobile, and this probably happens every tick. (or every 10 ticks or something, since you don't move THAT fast)
-- Variable radius is possible, because multiple roboports.

Not sure if it would work, but I think it might.

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.