Build Queues for every entity and tile type

[darklich14]

I know that it would require a bit more overhead, but imagine a round robin whereby the ghosts were serviced X at a time per tick PER entity type. This way, no particular item type starves, and especially beneficial is that power and robot infrastructure can be built in parallel with all the other entities under the construction zone. The limitations of ghosts outside build range are still acceptable and appropriate, but now solar won't jam assembling machines. Landfill won't jam concrete. Again, I acknowledge that there is overhead to this but even in the most complex mods, we're talking about a few hundred lists instead of 2 lists. For the benefit in multiplayer experience, this seems like a worthwhile algorithmic pivot.

Thoughts?

[NotRexButCaesar]

This would be very useful and solve a really unintuitive problem. The only question is what goes in each group.

[darklich14]

This would be very useful and solve a really unintuitive problem. The only question is what goes in each group.

Put each new construction request at the beginning of each queue to give it a preemption opportunity. Literally a separate list for every entity type in the game no matter whether it's a mod or base game. Additional entity gets additional queue. Then the rest of the game dynamics apply from there on out.

[mrvn]

Not a few hundred lists. Make a hashtable of lists. Each item goes into their own list. If no such list exists yet it gets added to the hashtable. When it becomes empty it gets removed.

The hashtable would allow finding the list for each item in O(1) and also allow iterating through the used entries in O(1) [assuming the table grows/shrinks dynamically]. That way you don't have to worry about the number of lists or about items with no ghosts. The order of the lists might change as lists are added or removed to the hashtable but all that would mean is that sometimes you might get 2 chemical plants build in a row or so.

[darklich14]

Not a few hundred lists. Make a hashtable of lists. Each item goes into their own list. If no such list exists yet it gets added to the hashtable. When it becomes empty it gets removed.

The hashtable would allow finding the list for each item in O(1) and also allow iterating through the used entries in O(1) [assuming the table grows/shrinks dynamically]. That way you don't have to worry about the number of lists or about items with no ghosts. The order of the lists might change as lists are added or removed to the hashtable but all that would mean is that sometimes you might get 2 chemical plants build in a row or so.

That's fine. The underlying data structure can be optimized. Round robin doesn't care about O(1) performance though. The list for an entity could be removed if there are no construction requests. These are all marginal implementation details compared to the overarching goal of preventing starvation of any particular type of entity.