Personal robots prioritizing nearest first

[mrvn]

Hehe, I once marked 600k alien artifacts for collection. UPS dropped from maybe 50 to 7 in an instance. All the more reason to do nearest first because then ghosts are removed faster and the UPS climbs back up faster (I would like nearest first for all roboports but that might be strethcing it).

That has nothing to do with distance based searching and all to do with item entities not having an associated force causing marking/unmarking of them to be O(N) time based of how many other non-entity-with-force entities are marked for deconstruction. Nothing relevant to what you're talking about here.

One more reason why there should be a way to add/remove ghosts through the chunk instead of a global list. O(n) isn't too bad if n is limited to 1024 tiles in a chunk.

[mrvn]

The number of bots needed is the size of the heap so you have that. You can also add up the resources needed as you add ghosts to the heap and subtract them when you remove a ghost. No need to continuously go over the list of ghosts to see what is needed. Note how currently the resources needed message only includes the last 600 ghosts. Keeping a total count would actually be more accurate.

Okay good point on the heap size (so long as the heap contains all ghosts not just the ones in the personal areas of each player) although you can't tell which are missing items and which bots and which any roboport at all, without checking them. Just that there are N items not being worked on.

And I've been saying the only consistent way to do it and not have it break or desync is to do the same thing every tick I know you disagree but it's the truth, any consistent solution has to be done every tick or you have to make sure it isn't necessary by effectively doing the job anyway to determine "nope I didn't need to do it this time"

And I still disagree. The number of resources needed is fixed when you add a ghost. A ghost never changes what it needs. So you can sum up everything you need at the start. Every time a ghost is processed you remove the resource need. You also know what resources are available and when an item is added or removed from an inventory. The resources missing doesn't change per tick, only when something happens.

Actually if I had to write the code I would have a table of lists of ghosts with resources missing sorted by resource. Every time a resource is added to a logistics network the top of the respective list is added back as active ghost that needs a bot.

In vanilla I would never reheap. Not unless the ghosts added in a tick make a reheap cheaper than inserting them individually. But when moving to a different layer of the map that would be a good trigger for a reheap. All current ghosts would become unreachable and you have to scan tiles to find new ghosts on a massive scale. Definitely a occasion to throw the heap away, set the range to 1 and have it increase by 1 per tick till the maximum. It is consistent because every instance of the game does exactly the same calculations every tick. If one of them decides to reheap all of them will.

As for correcting the heap piecemeal in a consistent manner: For each ghosts in the heap I would keep track of the player position when it's distance was calculated so you know the amount of error it has next time you happen to come across it. You can use manhatten distance if you think pythagoras is too expensive. Note the "next time you happen to come across it". As the player moves new items are added. They will be at the maximum distance and thus at the bottom of the heap. Inserting them into the heap will check log(n) items going from the top to the bottom. So it is not just the items at the top of the heap that get corrected but all items along a path to the bottom of the heap. Similar when you remove the top item you replace it with the last item in the heap and then correct the heap. The item sinks down fixing all items in its path. You might not hit every ghost that needs to be corrected in time but I think the chance of that is small. And worst case a ghost will just be build a bit later than a strict nearest first order would require. It doesn't have to be 100% perfect.

So are we talking about all ghosts or just the ones in the player zone cause I'm pretty sure we talk about one most of the time but then you say some things that just don't work with that thought, for example "all current ghosts" in this was at odds with the previous paragraph which only works if we're talking about all ghosts being in the heap not just those in personal roboport range.

I think you miss the point with piecemeal, let's say you're moving just 30 tiles (staying inside your roboport range), every tile for 60 tiles in every direction has a tree marked for deconstruction and at this point you have a perfect heap (some how) you walk east those thirty tiles the top of the heap is now 15 tiles to your west because only the top items in the heap were processed by the routine and when the items where you're standing now were added to the list "the last time you came across it", they were added to the heap further away than the items that're now 15 tiles away. The point being because they're not close to the top of the heap, with so many items and so few being processed and corrected each tick, they'll take a long long time for the piecemeal approach to get there. You never (re)process the whole heap at any point and only focus on the top items makes the system broken because you only 'come across' things at the edge boundary and not near the player.... Hang on no you say 'along the path' so does that mean you have to add vector distances to all the items? so you know if an item is more east or west and you process every item that's even slightly east of you to see if they get closer, well they will get closer but not in a linear manner, so that's O((N/2)^2) oh but the ones that're west also need to be moved down but I suppose that's less critical. So you don't need to reheap or reprocess every item either periodically or every tick, you just need to do half of them and add a directionality component check to movement and each ghost. So how do you do that in a way that's O(log2(n)) and not O((N/2)^2)? wait that's only if there's one player if you have two moving towards each other that's actually greater than O(N^2) in the cases that their personal heaps overlap, or greater than O(N^2) if you're considering all the ghosts in the same heap and you have to apply the check as well as the distance calculations.

Every entry in the heap would store the distance from when it was last calculated. Then the next time the entry is visited the distance is recalculated and the compared. Nothing in that is O(n^2). It is just a little bigger hidden constant factor in the O(log(n)).

So lets say you are moving 30 tiles. Then you aren't moving 30 tiles, you are moving 1 tile 30 times. Each time a bunch of new trees enter your range and are added to the heap. And a bunch of trees fall out of range and are removed. For each tree added or removed you walk the heap top to bottom or bottom to top and correct entries along the way. This is the path I mentioned. Has nothing to do with vectors or map positions. So when a tree is added you correct log(n) items in the heap. When you remove a tree you again correct log(n) items in the heap. And it's not the top most log(n) items. It's one item in the top layer, one in the second layer, one in the third, ... one in the log(n) layer.

Also don't forget that when you remove an item from the top of the heap you replace it by the last item in the heap and then push it down till the heap conditions is satisfied again. So every time a ghost is placed and removed from the heap log(n) ghosts are corrected. One in the top layer, one in the second layer, one in the third, ... one in the log(n) layer. That's where the ghosts that are now nearer after the player moved will rise to the top. Those far away will rise slowly as it is unlikely they are visited but those near rise fast as they are visited frequently.

The result might not be 100% sorted by distance but I believe it would be close. And far better than the current slightly random pattern.

Definitely not 1 tile per tick. That would take minutes to grow to the maximum range. I'm talking about increasing the radius by 1 per tick. And yes, that means towards the maximum radius you have more work than at the start. But it isn't that many tiles even for the maximum radius and most of the time the number of ghosts will be even smaller or 0. And you have to move more than 1 tile per tick for the radius to ever go low. It's basically just a way to not waste time scanning millions of tiles while taking a train ride.

So how does this scale to multiple players? a lot of "not that many" is still a lot. And again I can't tell if you have all ghosts in the heap or just local ghosts to the player or what. And at what rate do you shrink the radius? Would it ever effect exoskeleton legs? cars? tanks? is it only trains at certain speeds?

It scales the same way is already scales. The more players you have the more work you have to do to find ghosts in the players roboport range every time the player moves. The only difference is that instead of adding it to a list O(1) per ghost you add it to a heap O(log(n)) per ghost. Although adding m items to a heap in one go is faster than adding each individually. So it's not quite as bad as log(n) times slower.

The heap size is limited by the range of each players personal roboport. You can't have more than one ghost and 4 deconstructions (pickup item from ground) per tile. Ghosts not in range of a player wouldn't be in the players heap.

I didn't say it checks every item every tick. I said it checks every item when you place a blueprint. If it would just add them to the end of the global list then it would take a while for the scan to come around to the new ghosts and see they are in range of a player. Once placed it checks one item in the players range per tick but that would be the same with the heap method. To me it looks like the game already has a per player list of ghosts in range.

So we are talking about limited size heaps right? not all ghosts in one heap that's well managed? all 100% sure about that now?

The heap size would be naturally limited by the roboport size.

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

True, I forgot about chests and belts. But do they get added with one ghost per item to be removed? Or is it actually one ghost that needs many bots to remove? Would make more sense to add just the chest and then keep it at the top of the heap as you send bots to empty it. Only when empty you send the last bot to pick it up and remove it from the heap. So chests and belt would still be just one entry in the heap (same for assembler, furnaces, ...).

And I said top of the global list not end. The top, head, front of the queue, done first before everything else. If you do something anywhere in the player range or elsewhere for that matter it's first done as soon as possible, so obviously you see it get done instantly by your personal robots as the ghost looks and finds you to be the closest roboport available and you have the robots there waiting and the item to construct. That's how it currently works. It acts like an every player has a list of ghosts within their range but it cleverly doesn't need to be so. and thus resource overhead is reduced

Hehe, I once marked 600k alien artifacts for collection. UPS dropped from maybe 50 to 7 in an instance. All the more reason to do nearest first because then ghosts are removed faster and the UPS climbs back up faster (I would like nearest first for all roboports but that might be strethcing it).

Addressed by a Dev but also alien artifacts, a previous version of the game with less optimisation.

[/quote]

[JohnyDL]

And I still disagree. The number of resources needed is fixed when you add a ghost. A ghost never changes what it needs. So you can sum up everything you need at the start. Every time a ghost is processed you remove the resource need. You also know what resources are available and when an item is added or removed from an inventory. The resources missing doesn't change per tick, only when something happens.

So one list, two lists or more?
1 One heap for everything and everything is sorted based on distance to players? How do you manage infrastructure bots taking jobs closest to players?
2 One heap for everything that can be done, one list to store things that can't be done because of resource reasons?
2 One heap for personal roboports (all players lumped together), one list for everything else including personal robots and impossible items, with duplication?
2 One heap for personal roboports, one list for everything else that needs doing, and you need to coordinate the mutual exclusivity?
3 One heap for personal roboports, one list of everything that can be done, one list of everything without items available?
N One heap for each personal roboport, and one list of everything else?
N One heap for each personal roboport, One list for each logistic network (bearing in mind construction can overlap without connecting logistics networks) And one for jobs without items?
N One heap for each roboport static or personal and one for things outside all roboport ranges (and/or a master list of everything)?

Which of these is what you're working with here?
Do you display items that're not in any roboport range as needing item? needing bot? needing Roboport?
How do you deal with the interaction between infrastructure bots and those in the personal roboport range? deliver? don't deliver? override with personal if personal becomes available?
How do you manage overridden items? send them to storage? Have the bots search for the closest place to them to use the item? Have the bot search for the item in the heap that next needs the item on the bot? return to base and put item back in box it came from? How does this bot's time being wasted increase QOL? What if the bot that was overridden was closer to the item to place it? do both go to it and only override when one gets there?
Does the choice you are picking here affect the resources to add ghosts?
Does the choice you make here affect the resources needed with more players?
Does the choice you make here add bug potential?
Does the choice you make here add complaint potential?

Actually if I had to write the code I would have a table of lists of ghosts with resources missing sorted by resource. Every time a resource is added to a logistics network the top of the respective list is added back as active ghost that needs a bot.

Can you provide said code? pseudocode?
Can you demonstrate in practice how this is better?
Can you demonstrate in code the heaps working? Because the theory, and the english language discussion doesn't seem to hold up or explain enough. If you can write code the devs might use it if there's no code then they almost certainly won't consider this idea given what Rseding has already said.
Would that table/list be extra to the heaps and lists above? Per Player? per logistic system? Global?
How is it managed without extra overhead?
How is it coordinated so the best item that can be done is moved to ghosts from limbo?
What happens if logistics grabs the item before construction?

I think you miss the point with piecemeal, let's say you're moving just 30 tiles (staying inside your roboport range), every tile for 60 tiles in every direction has a tree marked for deconstruction and at this point you have a perfect heap (some how) you walk east those thirty tiles the top of the heap is now 15 tiles to your west because only the top items in the heap were processed by the routine and when the items where you're standing now were added to the list "the last time you came across it", they were added to the heap further away than the items that're now 15 tiles away. The point being because they're not close to the top of the heap, with so many items and so few being processed and corrected each tick, they'll take a long long time for the piecemeal approach to get there. You never (re)process the whole heap at any point and only focus on the top items makes the system broken because you only 'come across' things at the edge boundary and not near the player.... Hang on no you say 'along the path' so does that mean you have to add vector distances to all the items? so you know if an item is more east or west and you process every item that's even slightly east of you to see if they get closer, well they will get closer but not in a linear manner, so that's O((N/2)^2) oh but the ones that're west also need to be moved down but I suppose that's less critical. So you don't need to reheap or reprocess every item either periodically or every tick, you just need to do half of them and add a directionality component check to movement and each ghost. So how do you do that in a way that's O(log2(n)) and not O((N/2)^2)? wait that's only if there's one player if you have two moving towards each other that's actually greater than O(N^2) in the cases that their personal heaps overlap, or greater than O(N^2) if you're considering all the ghosts in the same heap and you have to apply the check as well as the distance calculations.

Every entry in the heap would store the distance from when it was last calculated. Then the next time the entry is visited the distance is recalculated and the compared. Nothing in that is O(n^2). It is just a little bigger hidden constant factor in the O(log(n)).

So lets say you are moving 30 tiles. Then you aren't moving 30 tiles, you are moving 1 tile 30 times. Each time a bunch of new trees enter your range and are added to the heap. And a bunch of trees fall out of range and are removed. For each tree added or removed you walk the heap top to bottom or bottom to top and correct entries along the way. This is the path I mentioned. Has nothing to do with vectors or map positions. So when a tree is added you correct log(n) items in the heap. When you remove a tree you again correct log(n) items in the heap. And it's not the top most log(n) items. It's one item in the top layer, one in the second layer, one in the third, ... one in the log(n) layer.

In my example you'd be adding 60 trees each tick and removing 60 more each tick, so is that O(log2(N)) in terms of just the size of the heap?
That's 3600 items in heap and 120 tile scans? 120 scans we haven't even counted in the O number and is non-trivial, but do you have to scan 480 tiles (one on each side of the border) to be sure you scan what's entering and what's leaving the roboport range to add remove them correctly?
60 ghost pushes to the heap and 60 ghost pops from the heap, each tick. Does that mean that's 120*O(log2(3600)) for this situation? cause 120*O(log2(3600)) is awfully close to O(1440) (and we're at O(1) in the current implementation)
Where do popped ghosts get put?

Or do you add and remove each item and correct only log2(N) once each tick cause 3600 items and 30 ticks in my example that's only (12*30) 360 corrected items statistically 180 of the sorted items will have been removed by simply moving them out of the range of the personal roboport and not necessarily the remaining 180 are the ones that you're closest too now. In fact more than one of those 180 will have been moved multiple times, so you still have the problem of a good number of 3600 items in the heap (at least 19/20ths) being unsorted or unhelpfully sorted.

For a 3600 item heap the O(1440) version of things would sort the heap every 3rd tick on average but in O(12) that's 300 ticks on average and relatively small movements put the heap out of order for 5 seconds again which means expectations of this feature and reality are vastly different. Except I'm assuming that each item gets sorted equally frequently but those in the bottom layer of the heap get sorted a fraction as often as those near the top, so with the bottom layer in this case having 1553 items and only 1 getting done each tick it's more like 26 seconds for everything to get sorted the layer above has 1024 items and would be every 17 seconds. So more than half of the heap is unsorted for anywhere from 13-15 seconds. And putting the O(1440) method closer to every 12 ticks to fully sort not every 3 ticks having every item getting sorted which is less than ideal anyway if you can move a tile per tick.

Also don't forget that when you remove an item from the top of the heap you replace it by the last item in the heap and then push it down till the heap conditions is satisfied again. So every time a ghost is placed and removed from the heap log(n) ghosts are corrected. One in the top layer, one in the second layer, one in the third, ... one in the log(n) layer. That's where the ghosts that are now nearer after the player moved will rise to the top. Those far away will rise slowly as it is unlikely they are visited but those near rise fast as they are visited frequently.

So is that an extra O(log2(N)) operation when a bot removes an item from the top of the list? 125 bots (or more for some players) .... well that's about O(Bots*log2(heap)) which comes to about O(1440) again in this situation, maybe not every tick but the first tick at least.

Or again is this operation only done once per tick?
How does that equate to releasing multiple bots since there's no top of the heap for the second bot? or one bot per tick too?

The result might not be 100% sorted by distance but I believe it would be close. And far better than the current slightly random pattern.

But that's 'not perfect' for what seems like an awful lot of computer resources, but it doesn't seem that 'not perfect' in your way of doing it. It seems worse than 'not perfect' it also seems like some wandering around even to 'help' actually reverses the reality of the feature.

It scales the same way is already scales. The more players you have the more work you have to do to find ghosts in the players roboport range every time the player moves. The only difference is that instead of adding it to a list O(1) per ghost you add it to a heap O(log(n)) per ghost. Although adding m items to a heap in one go is faster than adding each individually. So it's not quite as bad as log(n) times slower.

No it doesn't
Right now it's O(1) for doing jobs, not just O(1) to add ghosts to the list but O(1) to send out a robot to do something, if there's 1 player or 1000 players, 1 ghost or 1 billion because it doesn't look in every player's personal roboport, it just doesn't. I'll repeat again from the first page of this thread:

A thing to work on finds a robot not the other way around.

Which means there's no need to look in each roboport. One at a time (again from this thread page 3, and something I know you've read because you've quoted it yourself:)

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.

So the job looks if it's in a roboport? Yes, Can it be done? Yes, do job. Otherwise move to back of the queue.

Which is why there can be noticeable delay between some ghost entering your roboport range and it getting done, seriously I've ran past ghosts that it wasn't their turn in the queue and so even though I had bots and items available the job didn't get done from the time it entered one side of the roboport to when it left the other.

I even had a chance to make this screenshot in one instance, I had the bots, the items you can see everything charged but the order didn't go out for my bots to do any of it

personal roboports taking their time.PNG (2.06 MiB) Viewed 7338 times

Your idea is not "it scales exactly as it scales already" because the more players the more work needs doing, but the more players is it exponentially more work, linearly more work? It depends on how many heaps and lists you have which is a question you still haven't answered
If it grows based on more players how much can it grow before it's a performance problem? 100000 players? 100? 10? 2?
Is it something that's only useful for single player?
Is it something that will be complained about when it's working as designed but not how the players expect?
Do you count items in overlaps for both players or are the lists mutually exclusive? Is that managed? How?
If Alice and Bob are the same distance who gets to do the job? both? who overrides who if distance is identical? or is it in limbo until someone moves?
If it's O(log2(N)) for the heap and you now have 1000 heaps for 1000 players is that scaleable?
If you have 1 heap and you organise it based on distance to closest player will your personal roboport send robots and items halfway across the map because that item in the range of someone else's personal roboport is closer than any ghost in yours?
Is it something that will be complained about bitterly if it's a QOL that doesn't help people or work on multiplayer where it's probably most needed?

The heap size would be naturally limited by the roboport size.

I get that but that doesn't make it scalable, if everyone has their own heap that's a lot of heaps, and if not there're other overheads to consider.

True, I forgot about chests and belts. But do they get added with one ghost per item to be removed? Or is it actually one ghost that needs many bots to remove? Would make more sense to add just the chest and then keep it at the top of the heap as you send bots to empty it. Only when empty you send the last bot to pick it up and remove it from the heap. So chests and belt would still be just one entry in the heap (same for assembler, furnaces, ...).

Honestly I'm not sure how removing chests or belts is even done right now but I think it makes sense that the job requests (Floor(items/carry capacity) + item types + 1) bots to be sent to it but there might be better ways than that. It was just something to keep in mind that a job might be 100s of things to do per tile.


Sorry this took so long to get too I hadn't seen you'd put the formatting right.

[mrvn]

This has gotten to long to quote and since the devs aren't interested in fixing this anyway it's a bit of a waste of time. So just some final comments.

How many lists?

Does it matter? I would make each ghost a list item plus a list/heap item per player. So that a ghost can be in one global list and one list or heap per player. The player can then have a heap of ghosts to build. A List of ghosts with no resources. A list for "the roboport is set to filter power poles and laser turrets". A list for whatever you like. As long a ghost can only be in one of them this costs no memory in the ghost. And yes, this would scale linear with the number of players in both memory and time.

Work per tick

With each player having a heap you couldn't just process one ghost from the global list per tick. You would have to process the ghost at the top of the players heap. Now you could do one ghost per player each tick. Or go through the players in round robin fashion, one player per tick. Or go through the players each tick till you find one that can dispatch a ghost. The per tick costs vary accordingly. But I think you don't have that many players and with more players more bots should be dispatched per tick. Makes no sense that a personal roboport would get half the speed with 2 players compares to single player.

[JohnyDL]

This has gotten to long to quote and since the devs aren't interested in fixing this anyway it's a bit of a waste of time. So just some final comments.

I agree this has gone on quite long enough. You think I'm wrong, I think this idea will prevent me playing the game at my current stages because it will cost too much CPU or RAM or both (since my megabase is already pushing 20UPS) and certainly bar me from entry to multiplayer. We may never agree on this issue.

How many lists?

Does it matter?

Yes it matters because each list adds some overhead, each list requires some processing each and every tick even if it's just "does this list need more than one line of processing this tick"

I would make each ghost a list item plus a list/heap item per player. So that a ghost can be in one global list and one list or heap per player.The player can then have a heap of ghosts to build. A List of ghosts with no resources. A list for "the roboport is set to filter power poles and laser turrets". A list for whatever you like. As long a ghost can only be in one of them this costs no memory in the ghost. And yes, this would scale linear with the number of players in both memory and time.

Except it isn't, with each extra list you add the requirement for extra management, if ghost A is in list 1 and really it belongs in list 1000, you'd need to check it against list 2, and 3 and 4 and n and 999 and 1000 and 1001 and N so it definitely goes in the right list, each check is more processing there may be ways to binary it for some things if you have lists for deconstruction vs construction you only need to check half those lists but there's no way to shorten that check with respect to the number of players, it's always going to have to check against each player one by one. So if the lists are mutually exclusive you make it a processing problem not a memory problem. And remember right now it's not even linear, it is O(1) not O(n) hell it's not even as bad as the perfect O(log2(n)) as you claim infinite heaps are

Work per tick

With each player having a heap you couldn't just process one ghost from the global list per tick. You would have to process the ghost at the top of the players heap.

I agree if it were to be done your way then that'd be the way to do it.

Now you could do one ghost per player each tick.

N times as much work as it does now which you advocate for

Or go through the players in round robin fashion, one player per tick.

which is closer to how it is now anyway

Or go through the players each tick till you find one that can dispatch a ghost.

which has all the costs of the first with none of the benefits

The per tick costs vary accordingly.

Totally and right now the per tick cost is O(1), any solution provided needs to be O(1) or better because if it isn't then it will take some players with computers just good enough to play the game to not able to play the game.

But I think you don't have that many players

What defines 'that many players'? is it 1, 2, 10, 100? cause scalability wise, at least once a month some youtuber or another will hold an MMO event with 100+ people and I don't think it can possibly scale to even that, and removing a cool event/feature of the game would suck.

and with more players more bots should be dispatched per tick.

why? right now 1 per tick is enough for even megabases and tens or even hundreds of thousands of bots

Makes no sense that a personal roboport would get half the speed with 2 players compares to single player.

do you notice that in current multiplayer, cause it happens.

The problem is the idea seems reasonable but the practicalities of it just don't add up.

[mrvn]

This has gotten to long to quote and since the devs aren't interested in fixing this anyway it's a bit of a waste of time. So just some final comments.

I agree this has gone on quite long enough. You think I'm wrong, I think this idea will prevent me playing the game at my current stages because it will cost too much CPU or RAM or both (since my megabase is already pushing 20UPS) and certainly bar me from entry to multiplayer. We may never agree on this issue.

How many lists?

Does it matter?

Yes it matters because each list adds some overhead, each list requires some processing each and every tick even if it's just "does this list need more than one line of processing this tick"

I would make each ghost a list item plus a list/heap item per player. So that a ghost can be in one global list and one list or heap per player.The player can then have a heap of ghosts to build. A List of ghosts with no resources. A list for "the roboport is set to filter power poles and laser turrets". A list for whatever you like. As long a ghost can only be in one of them this costs no memory in the ghost. And yes, this would scale linear with the number of players in both memory and time.

Except it isn't, with each extra list you add the requirement for extra management, if ghost A is in list 1 and really it belongs in list 1000, you'd need to check it against list 2, and 3 and 4 and n and 999 and 1000 and 1001 and N so it definitely goes in the right list, each check is more processing there may be ways to binary it for some things if you have lists for deconstruction vs construction you only need to check half those lists but there's no way to shorten that check with respect to the number of players, it's always going to have to check against each player one by one. So if the lists are mutually exclusive you make it a processing problem not a memory problem. And remember right now it's not even linear, it is O(1) not O(n) hell it's not even as bad as the perfect O(log2(n)) as you claim infinite heaps are

That depends on what the lists are for. As I see it you do not do any work on the lists, they are just there to organize the ghosts. You do work on the ghosts (and players heaps). So the work per tick is defined by how many ghosts / players you handle each tick. Not on how many lists there are. And the list the ghost is in is the state the ghost is in. So if it is missing material for construction it goes into the "missing materials for construction" list. When material becomes available is gets removed from that list and put into a different one (or the heap). So as the state of the ghost changes so does the list membership. And moving a ghost from one list to another is O(1). It's not a per tick work, it's only work when the state of a ghost changes. Worst case a million inserters drop 12 million items in provider chests and 12 million ghosts have to move from one list to another in a single tick. But that's a megabase for you.

Work per tick

With each player having a heap you couldn't just process one ghost from the global list per tick. You would have to process the ghost at the top of the players heap.

I agree if it were to be done your way then that'd be the way to do it.

Now you could do one ghost per player each tick.

N times as much work as it does now which you advocate for

Or go through the players in round robin fashion, one player per tick.

which is closer to how it is now anyway

Or go through the players each tick till you find one that can dispatch a ghost.

which has all the costs of the first with none of the benefits

Except you would dispatch a ghost every tick unless all players have no ghosts to dispatch. And it would be easy to avoid players that have no ghosts pending. So the worst case of all players having to be checked would be rare. They would have to all be moving into ghost territory at the same time or something and lack the materials for construction. Ok, maybe not that rare.

The per tick costs vary accordingly.

Totally and right now the per tick cost is O(1), any solution provided needs to be O(1) or better because if it isn't then it will take some players with computers just good enough to play the game to not able to play the game.

But I think you don't have that many players

What defines 'that many players'? is it 1, 2, 10, 100? cause scalability wise, at least once a month some youtuber or another will hold an MMO event with 100+ people and I don't think it can possibly scale to even that, and removing a cool event/feature of the game would suck.

and with more players more bots should be dispatched per tick.

why? right now 1 per tick is enough for even megabases and tens or even hundreds of thousands of bots

Makes no sense that a personal roboport would get half the speed with 2 players compares to single player.

do you notice that in current multiplayer, cause it happens.

The problem is the idea seems reasonable but the practicalities of it just don't add up.

Unless you watch out for it you probably won't notice a drop from 60 bots/s to 30 bots/s. You run out of bots too fast. But with 60 players it is only 1 bot/s. With 600 players it's one bot every 10 seconds. You might start to notice.

Note: In terms of O(log n) times 100 players really isn't many. At 1000000 players or above I would start to worry.

[JohnyDL]

That depends on what the lists are for. As I see it you do not do any work on the lists, they are just there to organize the ghosts. You do work on the ghosts (and players heaps). So the work per tick is defined by how many ghosts / players you handle each tick. Not on how many lists there are. And the list the ghost is in is the state the ghost is in. So if it is missing material for construction it goes into the "missing materials for construction" list. When material becomes available is gets removed from that list and put into a different one (or the heap). So as the state of the ghost changes so does the list membership. And moving a ghost from one list to another is O(1). It's not a per tick work, it's only work when the state of a ghost changes. Worst case a million inserters drop 12 million items in provider chests and 12 million ghosts have to move from one list to another in a single tick. But that's a megabase for you.

I think we're in the realm of semantics on this one, Yes you work on ghosts, Yes the lists are there to organise the ghosts. More lists still means more overall work. 1 list with 32 items takes 5 operations 2 lists with 16 items each takes 4 if only one is accessed but as likely as not it will be 8 with both being accessed, leading to an average of 6. Thus 2 lists on average take more processing than 1. With bigger numbers and more lists this effect is amplified and we haven't even talked about the management of the ghosts.

"Every time a ghost's state changes" doesn't even have to be ghost's code that changes the state, an inserter placing an item into a box is a state change for the ghost without interacting at all with the code for the ghost, not even a flag is set.

If you have 1000 solar panels in one list (even doable by the logistics network) and 1 solar panel is placed in a passive provider do you pick the solar panel at random from the list to move to 'doable'? first in first out? first in last out? manage it relative to the player(s)? relative to the source? bearing in mind that another box that might get solar panels might be diametrically opposite side of the logistics system so having the list presorted isn't possible. If the player could use the item does it defer to the logistic network first? How about buffer chests and requesters, are they worth deferring the construction orders?

The only way to know if a ghost changes state is to do some work on it/them, the only way to know that 12million ghosts need to change lists in the same tick is to check every ghost every tick, there's not some magic that automatically lets the ghosts know that their state has changed because of something else in a completely different part of memory with 0 cycles. So the "When material becomes available is gets removed from that list and put into a different one" is literally the "work on the lists" or keeping them organised. And as I said those checks aren't strictly linear with more players adding more lists it becomes exponentially harder.

I admit that more lists might help speed this process up but it's not exactly computationally free here's an example model:

Code: Select all

Each Logistic/Personal Network:
GhostsAvailable=[Belt=[],FastBelt=[],ExpressBelt=[].....]
GhostsUnavalable=[Belt=[],FastBelt=[],ExpressBelt=[].....]
Logistics=[Belt=[],FastBelt=[],ExpressBelt=[].....]               // personal storage or logistics storage arranged by items then a list of chests that contain them, in the case of player this is always a list of just the player or a list of nothing if the player has none and no requests for any

for i=0, i<length,i++ {                                           // iterate each type of item O(types*everything below)
 count=0                                                          // O(1) number of ghosts that need moving
 for j=0, j<Logistics[i].length, j++{                             // O(max(2,4,4)) iterate each box with this item's type tag though boxes are definitely not sorted like this
  if Logistics[i][j].box == provider {                            // O(1) if this is a provider
   count += Logistics[i][j].count(Logistics[i].type())            // O(1) count of this box available for use by logistics
  } elseif Logistics[i][j].box == storage {                       // O(1) if this is storage
   count += Logistics[i][j].count(Logistics[i].type())            // O(1) count of this box available for use by logistics
   count += Logistics[i][j].inAir(Logistics[i].type())            // O(1) how many can we consider available
  } elseif Logistics[i][j].box == requester {                     // O(1) if this is a requester
   count -= Logistics[i][j].requests(logistics[i].type())         // O(1) remove requested items from available
  }
 }                                                    
 Count -= GhostsAvailable[i].length(inAir=false)                  // O(lengthA) remove the items in ghosts available list or heap as items allocated and still using up logistic space
 if count>0 {                                                     // O(1) if there are things available
  count = min(count, GhostsUnavalable[i].length())                // O(1+lengthB) prevent underflow exceptions
  for k=0, k<count, k++{                                          // O(count*2) move count ghosts from one list to the other
   tempGhost=GhostsUnavalable.pop()                               // O(1) Pop
   GhostsAvailable.push(tempGhost)                                // O(1) Push
  }
 } elseif count<0 {                                               // O(1) if there are more tasks to do than stuff available
  count = min(-count, GhostsAvailable[i].length())                // O(1+lengthB) prevent underflow exceptions
  for k=0, k<count, k++--{                                        // O(count*2) move count ghosts from one list to the other
   tempGhost=GhostsAvailable.pop()                                // O(1) Pop
   GhostsUnavalable.push(tempGhost)                               // O(1) Push
  }
 }
}

This comes to O(types*(1+4+O(lengthA)+2+O(1+max(lengthA, lengthB))+count*2)) per logistic network
https://wiki.factorio.com/Data.raw gives 232 entity tags in vanilla (not counting any that mods add) And if we assume LengthA+LengthB*number of logistic networks to be number of ghosts of each type (near as makes no difference)
O(1856*number of discrete logistics networks + total ghosts on map + 2*count of how many need to change lists)

And that's whether you heap the personal networks for distance or not, just managing the roboports (not moving) with the items in their logistic network/construction area without the fact a ghost might be in as many as 4 distinct construction networks and that we haven't put in anything to move ghosts from the static networks to the player roboports as they move, or to manage if something should be in player 1 or player 2 if it's in reach of 2 players. Oh and at this point we've already checked touched every ghost with each tick. I suppose you could put a cap on some stuff, like only attempting to count the first 10 items of an array (in some cases) and then dealing with stuff in batches of ten or maybe add a length/size variable to the list/array/heap but that just moves the problem of counting to somewhere else in the code rather than counting when you need the number, since every push or pop changes the count whether or not it's used before it's next changed.

Code: Select all

So swapping networks:

movingInside[] = player.scanIn()                                  // Some magic function that surface scans the area just inside the personal roboport range and returns an array of ghosts at no cost
movingOutside[] = player.scanOut()                                // Some magic function that surface scans the area just outside the personal roboport range and returns an array of ghosts at no cost
foreach ghost in movingInside {
 ghost.getList().remove(ghost)                                    // function removes the ghost from the network it currently belongs to
 player.addGhost(ghost)                                           // function adds the ghost to the player network to either the heap because it can be done or the list of unavailable ghosts because it can't
}
foreach ghost in movingOutside {
 ghost.getList().remove(ghost)                                    // function removes the ghost from the network it currently belongs to (which may or may not be the player initiating the move)
 world.addGhost(ghost)                                            // function adds the ghost to the world or another player that is closer to the item
}

BUG: two players near each other will add the items closest to the other player in any overlapped space (depending on movement)

Frankly I can't put an O number on this set of manipulations and it's broken anyway but world.add ghost is troublesome, the scan functions are definitely not O(0) I'm not sure it's even possible to look at an object and query it to ask what arrays or lists it appears in and so many other problems I see with it. Tear it to pieces, please, then show something that's reasonable to handle this logic.

Except you would dispatch a ghost every tick unless all players have no ghosts to dispatch. And it would be easy to avoid players that have no ghosts pending. So the worst case of all players having to be checked would be rare. They would have to all be moving into ghost territory at the same time or something and lack the materials for construction. Ok, maybe not that rare.

yeah this is kind of the point, and even if it was rare it can be manufactured and abused by trolls which screws with people's QOL anyway. 90% of players don't carry combinators around with them dump a tonne of combinators onto the map with a huge BP, maybe space them all 1-3 chunks apart so everyone is hit by some but not a so many that it'd be impossible to place down without lag and dropping connection.

Unless you watch out for it you probably won't notice a drop from 60 bots/s to 30 bots/s. You run out of bots too fast. But with 60 players it is only 1 bot/s. With 600 players it's one bot every 10 seconds. You might start to notice.

You seem to want this both ways though either every player is trying to issue hundreds of orders at the same time like here or it's the rare exception to the rule to have multiple thousands of canstruction orders :p. Maybe the first few seconds it's slow but players would drop out fast enough in most cases and 99% of the time only a few players will be trying to issue bots at full speed. I don't see it as reasonably plausable to have 60 players all issuing orders at the same tick, if a ghost was placed that covered the whole map or deconstruction orders that effected 60 players in the same instant the code that adds the ghosts to the list in 1 tick the program could do a job search on each entity in that tick before putting in any list world.addGhost() style, so 1 tick the order is placed and all bots are released, probably with noticeable lag, which would mean the only way to have this happen were if players enter the construction zones simultaneously which has a vanishingly small probability of happening, even delays of a few seconds in most cases would have 1 player release a bunch of bots then the next then the next, it could be co-ordinated but any viable co-ordination would have to be done with all the players in the same place (like with trains or proximity) and you couldn't tell your bots apart from the others in the ensuing bot storm.

Note: In terms of O(log n) times 100 players really isn't many. At 1000000 players or above I would start to worry.

O(log100) isn't O(100*log(number of ghosts)) would easily be bigger than O(log2(1000000))

[mrvn]

You are still thinking about processing every list every tick. Think differently. Instead of figuring out the time to handle N lists consider the time to handle M ghosts. If no ghost is processed belonging to some list then that list would not cost any time. So if you had a list of "ghost in reach of a roboport that need an iron plate" and an inserter puts an iron plate into a provider chest you don't process the list but you process the first ghost in the list. Processing the ghost takes O(1) time so overall you get O(number of iron plates produced). That you also have a "ghost in reach of a roboport that need a copper plate" list would not factor into the cost. In that example the number of lists is irrelevant to the runtime. Add a mod with 1000 new item types and putting an iron plate into a provider chest would still cost the same time. It would cost memory for 1000 new lists though.

A lot of specifying O() notations is about how you look at the work you do. Even doing the same work you can totally different O() results depending on how you count things. Don't forget O() is an upper limit. The real work can be way less. It about proving you never have more work. So figure out a way to count the work you need to do that gives the smallest O() expression.

Note: This is just an example. I'm not sure if having such lists would be ideal or not.

[JohnyDL]

I'm thinking what is the most efficient way to process all the ghosts which change state, not all lists. How do you know if a ghost has changed state? you run some code to check it. Using the lists you can bulk check ghosts by looking at each list but it's literally magic to know if a ghost's state has changed with no calculation. I can think of O(N^(1+delta)) ways to do it, on average maybe, but there's nothing that's less than O(N) which is the point I've been making. Distance to player is a state condition, whether it can be done is a state condition, whether it's in range of a player or logistics is a state condition and the states 'probably' won't change every tick but you can't know without 0(N) and after you know you still need to do some, nO(1), operations.

Some 'common' problems:

Expanding a bus you have 4800 belt in a box, 4800 bots and 4800 belt construction orders, you walk over and take all 4800 out of the box You just changed the state of 4800 ghosts, and over the next 4800 ticks the state is likely to be changed back for some of them as more belt is made. Solution now, Don't care about the state, process one at a time, work out the state only of the item at the top of the list when it's its turn to be done. Solution with states as defined by lists, move all 4800 ghosts from one list to another and then over time tick them back to the first list as belts are made, some processing needs to be done to work out which list ghosts should be in every tick.

2 players in close proximity both able to do the same ghost. Current solution, don't care about where the players are until the ghost is at the top of the list then request the item from the closest player. Solution with lists, each tick either player moves query the ghost to find out who is closer and issue construction orders whether or not the job can be done.

Lots of items near a player which need doing. Current solution do something, it will all be done eventually. Solution with lists, have a heap and have it reasonably well sorted, which might change drastically tick to tick.

"it's easy to know what players to skip". Current solution, don't look at any players only look at ghosts. Solution with lists, look at each player's heap size if 0 look at each players 'unavailable' lists and see if anything has had a state change, move it/them, then look at each player's heap size if still 0 skip that player.

etc, etc, etc, etc

each and every example has some work associated with it that's not needed for the perfectly serviceable solution we have at the moment for very little gain per cost

[mrvn]

And that is not how I look at it.

You do not check the list. What happens is that an inserter inserts an item into the logistic network. That action moves a ghost from the list. No checking involved.

But as you mention when a player takes 4800 belts out of a box you want to bulk move 4800 ghosts from one state to the other. That is one option and if you go that way then certainly a list is not a good data structure. No bulk move possible. My initial though was that you just subtrack 4800 from the int for "belts needed for construction". The actual ghosts them self would change one per tick (per player). But if you want to bulk move then maybe a skip list is the way to go, allowing you to bulk move n items in O(log n).

As for knowing which players need ghost processing: You wouldn't check for the heap being empty. Keep all players with something in the heap in a circular list. Then you go through the list till you find a player that actually can do work. When the heap of a player becomes empty you remove it from the list. So you only have to check the players that are likely to have ghost activity.

And when a player picks up 4800 belts you don't have to move 4800 ghosts from the players pending list to the heap. You can do that one per tick if you don't mind that you won't imediatly get nearest first. Only nearest of those already re-inserted into the heap. But re-inserting one per tick is faster than bots do their work, especially if they have to travel far. So on their second run the bots should be back to nearest first. Something I could live with.

[JohnyDL]

You do not check the list. What happens is that an inserter inserts an item into the logistic network. That action moves a ghost from the list. No checking involved

How? Magic? It's a Different part of the code completely separate. Inserters have nothing to do with bots or ghosts. The logistics network doesn't detect changes one tick to the next each tick it just does a sum of all items each tick, it doesn't even compare that to the previous tick so without a check there you're not getting this for free either, production stats are done inside the assembly machines and so can't even be used to tell the bots because what if they don't output to a logistics chest. Where prey tell do you get this information without a check of some sort? An inserter puts an item into a box it doesn't even care what type of box it doesn't notify the other systems it just changes a value in memory and when the other systems come to that bit of memory they work on it as though it was always that way.

Right now I don't think the rest matters without dealing with this. Because I see three things you might suggest A well make the inserters check what type of chest they're placing things in and notify the logistics/construction networks, thus moving where the checks happen or B make the logistics system check and notify the ghosts/bots which was basically my pseudocode above or C pretend like this isn't even the issue and it doesn't matter to the topic. But it's the fundamental flaw of your system, whether it's a player, bot, inserter, loader or duplication chest that makes the item available for construction the constitution bots/ghosts can't know about the item being available without something extra happening per item becoming available, per ghost, per tick, per something O(n)

[mrvn]

You do not check the list. What happens is that an inserter inserts an item into the logistic network. That action moves a ghost from the list. No checking involved

How? Magic? It's a Different part of the code completely separate. Inserters have nothing to do with bots or ghosts. The logistics network doesn't detect changes one tick to the next each tick it just does a sum of all items each tick, it doesn't even compare that to the previous tick so without a check there you're not getting this for free either, production stats are done inside the assembly machines and so can't even be used to tell the bots because what if they don't output to a logistics chest. Where prey tell do you get this information without a check of some sort? An inserter puts an item into a box it doesn't even care what type of box it doesn't notify the other systems it just changes a value in memory and when the other systems come to that bit of memory they work on it as though it was always that way.

Right now I don't think the rest matters without dealing with this. Because I see three things you might suggest A well make the inserters check what type of chest they're placing things in and notify the logistics/construction networks, thus moving where the checks happen or B make the logistics system check and notify the ghosts/bots which was basically my pseudocode above or C pretend like this isn't even the issue and it doesn't matter to the topic. But it's the fundamental flaw of your system, whether it's a player, bot, inserter, loader or duplication chest that makes the item available for construction the constitution bots/ghosts can't know about the item being available without something extra happening per item becoming available, per ghost, per tick, per something O(n)

Yes, and that is the problem. The current system keeps summing up the data over and over. wasteful.

And yes, I'm talking about moving the check. But it wouldn't be O(n). It would still be O(1) for inserting any number of items if all that did is flag the list of ghosts waiting on the items for processing and then you process them one ghost per tick. Or O(log n) when you do bulk transfers. And you can sum up all the items inserted and removed in a tick and do a single bulk transfer at the end.

Anyway, all of that doesn't really have anything to do with the heap idea itself. For that I would simply start with having a heap and a list of bots lacking items. And I would cycle through the list one ghost per tick and check if it should be re-inserted into the heap. So for all players with ghosts: scan tiles if moved, check head of list, check head of heap.

[JohnyDL]

So each inserter inserting items setting flags is O(n)

Flag = Flag or inserter.performscheck()

Which is more efficient:
Previous+alpha-beta+gamma-delta... with no consideration for if alpha beta gamma and delta effect the same box and having to perform checks on all of those and epsilon and lambda and omicron to make sure they're inserting into the logistic system or belts or taking out of the logistics system or direct insertion or player interaction or ...? Or instead let all bots and inserters and loaders and direct insertion do their jobs and than one mass addition at the end

All summing up at the end is much faster in most cases. And those where it isn't it's likely because the number of inserters moving is low.

Take for example you only need 1 inserter per tick to make 2 checks on what they're inserting from and to in order to do the relevant add or subtract from the logistics network(s) given most inserters deal with belts and assemblers not logistics chests for me I have 4 times as many inserters as logistics chests and I have 10 times as many bots as logistics chests. If some bots take items and some inserters move each tick it doesn't take many before the checking of where it's removed from/to is much slower than summing the chests contents which is a single matrix operation.

Anyway, all of that doesn't really have anything to do with the heap idea itself. For that I would simply start with having a heap and a list of bots lacking items. And I would cycle through the list one ghost per tick and check if it should be re-inserted into the heap. So for all players with ghosts: scan tiles if moved, check head of list, check head of heap.

I get this, for single unmoving player it might work, it doesn't interact with static roboports and it doesn't handle interactions between players together it fails when when moving as I've shown but an unknowing isolated player okay this has all the functions as described And is O(16*Radius+1+log2(heapsize)) I fully concede that

Still doesn't handle overlapping roboports, if you move its worse than useless, and if you have 0 in heap and you're checking the wrong items in the list you're still waiting on the O(1) list check to find the items you can do which will result in randomly issued orders not closest first

[mrvn]

So each inserter inserting items setting flags is O(n)

Flag = Flag or inserter.performscheck()

Which is more efficient:
Previous+alpha-beta+gamma-delta... with no consideration for if alpha beta gamma and delta effect the same box and having to perform checks on all of those and epsilon and lambda and omicron to make sure they're inserting into the logistic system or belts or taking out of the logistics system or direct insertion or player interaction or ...? Or instead let all bots and inserters and loaders and direct insertion do their jobs and than one mass addition at the end

All summing up at the end is much faster in most cases. And those where it isn't it's likely because the number of inserters moving is low.

Take for example you only need 1 inserter per tick to make 2 checks on what they're inserting from and to in order to do the relevant add or subtract from the logistics network(s) given most inserters deal with belts and assemblers not logistics chests for me I have 4 times as many inserters as logistics chests and I have 10 times as many bots as logistics chests. If some bots take items and some inserters move each tick it doesn't take many before the checking of where it's removed from/to is much slower than summing the chests contents which is a single matrix operation.

Anyway, all of that doesn't really have anything to do with the heap idea itself. For that I would simply start with having a heap and a list of bots lacking items. And I would cycle through the list one ghost per tick and check if it should be re-inserted into the heap. So for all players with ghosts: scan tiles if moved, check head of list, check head of heap.

I get this, for single unmoving player it might work, it doesn't interact with static roboports and it doesn't handle interactions between players together it fails when when moving as I've shown but an unknowing isolated player okay this has all the functions as described And is O(16*Radius+1+log2(heapsize)) I fully concede that

Still doesn't handle overlapping roboports, if you move its worse than useless, and if you have 0 in heap and you're checking the wrong items in the list you're still waiting on the O(1) list check to find the items you can do which will result in randomly issued orders not closest first

It will always work, it will not always be perfect. I never said I wanted perfect.

Interactions between players that the ghost gets a bot assigned to it by player 1. Then when player 2 checks the ghost it sees the ghost already has a bot on the way and removes it. You don't even have to keep a list of player with the ghost in their heap in each ghost.

When you move ghosts get added the the heap as described earlier in the thread. I don't see why that shouldn't work.

And the list check would process one item per tick. The bots only one item every so often, because they have to travel there and back. So while you don't get perfect you get pretty good I imagine. If the list check produces too much out-of-nearest-first-order cases then that can be refined. But why start complex when simple might already do? Most cases you have 1000 trees to deconstruct. No items in the list.

[JohnyDL]

Your suggestion of not perfect

Here's a setup.

Ghosts.png (832.54 KiB) Viewed 7221 times

Player is at the blue stick figure, not moving and let's assume that full complement of bots and no items to do the ghosts, Some how the list was created such that the numbers represent the order of items in the list, happy so far?

Tick 1: Solar panel arrives, check heap, check list, not issued because list is looking at an accumulator
Tick 2: Nothing arrives, check heap, check list, Player has Solar Panel but not issued because list is looking at an accumulator
Tick 3: Solar Panel Arrives, check heap, check list, Player has Solar Panel but not issued because list is looking at an accumulator
Tick 4: Accumulator Arrives, check heap, check list, Accumulator issued to item 4 because it's in the list next and not 10 or 38 which are closer to the player
Tick 5-10: Nothing arrives, check heap, check list, Player has 2 Solar Panels but not issued because list is looking at an accumulator
Tick 11: Nothing arrives, check heap, check list, Solar panel is issued to item 11 because it's the next in the list and not 16 or 23 which are closer

11 ticks so far 2 operations per tick for 1-11 and 2 jobs issued, and 2 sorts on empty heap attempted

How it works now same set up

Tick 1: accumulator looks for bot to do it, player no item
Tick 2: accumulator looks for bot to do it, player no item
Tick 3: accumulator looks for bot to do it, player no item
Tick 4: accumulator looks for bot to do it, player has accumulator and is in range, player deploys bot
Tick 5-10: accumulator looks for bot to do it, player no item
Tick 11: Solar panel looks for bot to do it, player has solar panel and is in range, player deploys bot

11 ticks 1 operation per tick exactly the same jobs done.

That's 2 item types and 1 player is twice as many operations, add a second player:

Ghosts.png (756.27 KiB) Viewed 7221 times

Tick 1: Player 1: Solar panel arrives, check heap, check list, not issued because list is looking at an accumulator
Tick 1: Player 2: Nothing arrives, check heap, check list, Do nothing
Tick 2: Player 1: Nothing arrives, check heap, check list, Player has Solar Panel but not issued because list is looking at an accumulator
Tick 2: Player 2: Nothing arrives, check heap, check list, Do nothing
Tick 3: Player 1: Solar Panel Arrives, check heap, check list, Player has Solar Panel but not issued because list is looking at an accumulator
Tick 3: Player 2: Nothing arrives, check heap, check list, Do nothing
Tick 4: Player 1: Accumulator Arrives, check heap, check list, Accumulator issued to item 4 because it's in the list next and not 10 or 38 which are closer to the player
Tick 4: Player 2: Nothing arrives, check heap, check list, Do nothing
Tick 5-10: Player 1: Nothing arrives, check heap, check list, Player has 2 Solar Panels but not issued because list is looking at an accumulator
Tick 5-10: Player 2: Nothing arrives, check heap, check list, Do nothing
Tick 11: Player 1: Nothing arrives, check heap, check list, Solar panel is issued to item 11 because it's the next in the list and not 16 or 23 which are closer
Tick 11: Player 2: Nothing arrives, check heap, check list, Do nothing

How it works now same set up

Tick 1: accumulator looks for bot to do it, player no item
Tick 2: accumulator looks for bot to do it, player no item
Tick 3: accumulator looks for bot to do it, player no item
Tick 4: accumulator looks for bot to do it, player 1 has accumulator and is in range, player deploys bot
Tick 5-10: accumulator looks for bot to do it, player no item
Tick 11: Solar panel looks for bot to do it, player 1 has solar panel and is in range, player deploys bot

That's 2 times the QOL produces the same output as the way it works now with more computation

Let's take the example of the player having all the items then?

Ghosts.png (832.54 KiB) Viewed 7221 times

Assuming the Heap is sorted
Tick 1: check heap, issue accumulator 10, sort heap O(Log2(42)), check list
Tick 2: check heap, issue accumulator 38, sort heap O(Log2(41)), check list
Tick 3: check heap, issue accumulator 9, sort heap O(Log2(40)), check list
Tick 4: check heap, issue accumulator 39, sort heap O(Log2(39)), check list
Tick 5: check heap, solar panel 16, sort heap O(Log2(38)), check list
Tick 6: check heap, solar panel 23, sort heap O(Log2(37)), check list
Tick 7: check heap, issue accumulator 8, sort heap O(Log2(36)), check list
Tick 8: check heap, issue accumulator 40, sort heap O(Log2(35)), check list
Tick 9: check heap, solar panel 22, sort heap O(Log2(34)), check list
Tick 10: check heap, issue accumulator 7, sort heap O(Log2(33)), check list
...
Tick 43: check heap, issue solar panel 31, sort heap O(log2(0)), check list
Tick 44: check heap, check list

44 ticks 44 items issued 42 sorts performed to sorted data (that would certainly have been needed if the player had been moving or had recently moved (in the last 20 seconds)) none of which were necessary because all would be launched regardless of order before bots ran out.

How it works now same set up

Tick 1: accumulator 1 looks for bot to do it, player has accumulator and is in range, player deploys bot
Tick 2: accumulator 2 looks for bot to do it, player has accumulator and is in range, player deploys bot
Tick 3: accumulator 3 looks for bot to do it, player has accumulator and is in range, player deploys bot
...
Tick 43: accumulator 43 looks for bot to do it, player has accumulator and is in range, player deploys bot
Tick 44: nothing in list no action

44 ticks 44 operations. 3rd time same result of QOL has no benefit and more computation.

Player moving? that adds surface scan
Moving while having items? would require me to actually show the stepwise sorting process for the heap but it does not look good for the QOL
No items at all? well that's just something that takes more operations taking more operations without a state change
More than 2 types of ghosts? amplifies the delivery problem
Construction and deconstruction at the same time? there are positions where the bots will be placing down items but can't because trees or other items haven't been moved first based on distance rather than 'random'
2 players with enough items? that's the first one where deployment might be faster for the QOL than the current solution, but it takes more than 4 times the processing and because you waste ticks dealing with conflicts rather than issuing orders you only save 4/5 ticks in deployment total (in this case) vs the current solution
And so on, the idea just doesn't add the QOL you think it does with only the computation you're offering it, and if you offer it more it's just not feasible.

[mrvn]

1) prioritizing only helps if you don't have enough bots. Otherwise they dispatch so fast that the order hardly matters.
2) If you keep a list of ghosts needing items then you have to keep a list per item type so that when a solar panel arrives you can put it back into the heap in O(1).
3) Ghosts are moved into those lists from the top of the heap so they are sorted by distance (at the time they get moved, not when the player has moved since)
4) If more items arrive then you have bots then they get sorted again in the heap, otherwise the order isn't the limiting factor

That makes it:

Tick 1: Solar panel arrives, check heap, check solar panel list, issue solar panel 16
Tick 3: Solar Panel Arrives, check heap, check solar panel list, issue solar panel 23
Tick 4: Accumulator Arrives, check heap, check accumulator list, issue accumulator 10
...

[JohnyDL]

Tick 1: Has anything arrived? Yes - Solar panel arrives, check heap, check solar panel list, issue solar panel 16
Tick 2: Has anything arrived? No [but 1 check per player so not O(1) and not O(Log2(n)) scaleable]
...

Moving the check out of the bot code is still a check, and moving it out of the bot code makes it less parallelizable for future improvements.

Doing it without a check anywhere is impossible, "but the bot knows it's adding to the player" nope it adds to an inventory, "but when the player inventory is added to" it's not a special sort of inventory with special code so you need a check every tick, sorry try again.

And even if that weren't the case 2 bots deliver at the same time or one bot delivers 10 items, 1 bot issued per tick so need a check at some point in case of multiple items in previous ticks.

[mrvn]

Tick 1: Has anything arrived? Yes - Solar panel arrives, check heap, check solar panel list, issue solar panel 16
Tick 2: Has anything arrived? No [but 1 check per player so not O(1) and not O(Log2(n)) scaleable]
...

Moving the check out of the bot code is still a check, and moving it out of the bot code makes it less parallelizable for future improvements.

Doing it without a check anywhere is impossible, "but the bot knows it's adding to the player" nope it adds to an inventory, "but when the player inventory is added to" it's not a special sort of inventory with special code so you need a check every tick, sorry try again.

And even if that weren't the case 2 bots deliver at the same time or one bot delivers 10 items, 1 bot issued per tick so need a check at some point in case of multiple items in previous ticks.

But the player inventory is a special inventory because it has the tool belt and the auto trash. You already do have special code that gets triggers whenever something gets added to the players inventory. Now you just add the personal roboport into that code too.

[JohnyDL]

it's a 'special' inventory but in code I'm pretty sure it's just handled as a paired requester chest and active provider chest, there's nothing different about it than any other requester having an item dropped off or requester having an item picked up. The tool belt is entirely within the player model and not acknowledged by the bots at all even if the items are placed there, and the auto trash is internally moving it from the requester set of inventory slots to the provider set of inventory slots. Again not interacting with bot code.

[krafczyk]

I hope the developers plan to make bots complete the nearest tasks first or provide such an option before the final release. Right now they just pick things to build in a print randomly.

It is incredibly annoying when you first get bots since they are slow. They amble from one random location to the next when the player could reduce the distance traveled to each job by moving closer to the uncompleted tiles.

I discussed a while ago here: https://www.reddit.com/r/factorio/comme ... imization/ But I thought I'd bring it up again here.