Blueprint chunking for bot batch placement of entities

[VuiMuich]

I already sketched this idea in the #318 FFF thread, but I figured it was not quite understandable, what my idea actually was, so here I want to propose it again in a proper way.

TL;DR:

the basic idea is to subdivide a blueprint into chunks. Bots don't get assigned to build entities directly, but get assigned to chunks.

Details:

Each chunk has four properties:

• a chunk ID (not assigned until placed)
• the chunk coordinates (maybe the chunks center of area)
• the entity type
• a list with the coordinates of the entities (max length being the cargo size of construction bots)

The general chunk map creation could be run on blueprint creation and be stored with the blueprint, so even if this would be somewhat expensive on the CPU for really big blueprints it wouldn't matter to hard, because it will only be run once and once again, after cargo size changes and the blueprint gets loaded, simply check if the chunk length missmatches with cargo size and update adequately.
Also the upgrade planer could run chunk creation for its selected area.

On Memory cost this might increase the size of a blueprint. But it also might even open a way to actually compress blueprint byte length, if chunks only store relative coordinates (either as unsigned integer with the chunk coords as origin, or with signed int and the origin being the center of area of the chunk) with adjusted byte length.

When creating a chunk it should be checked, that its entities are within reasonable range; when they are not, they get assigned to different chunks, possibly of smaller then max length.
For manually placed ghosts, ghosts from destroyed entities etc. chunks of the length one get created.
From time to time one could go through the list of chunks if there are any of a length shorter then the current maximum and try to merge smaller chunks to maximised ones. This way the chunk map would automatically become updated and optimised if research changes cargo size, ghosts get deleted from a placed chunk etc.
There is no need to do this on a expensive pace since the worst case scenario is basically the same as it is now, but in the end long bot builds might be actually sped up by chunked ghost maps.

"The Roboports" simply need to maintain a list of each, assigned and unassigned chunks, which again is worst case the same length as the list of all placed ghosts.
When a bot gets assigned to a chunk to build and it can't get all items to build the whole chunk at once it just builds as much as it could get items from a single chest and the rest of the chunk becomes a new chunk. If a bot gets destroyed or picked up by player before it can place all entities of the chunk it just changes the state of the chunk back to unassigned.

I'm not sure if any vast changes to bot pathing would be needed, but possibly it might be sufficient to start by moving to the chunks origin and refining the path to each entity within the chunk during travel time.

The optimal advantage would be more efficient bots resulting in lesser numbers of bots active at any given time, which might result in a noticeable performance boost instead of an expected performance loss, if each bot needs to check on assignment, if they could build multiple entities with a single journey.

Why?

The FFF#318 introduced the idea of batch placement of tiles by bots. This is an attempt to provide a computational inexpensive solution to batch placing entities.

Inspiration and terminoligy

Obviously the term chunk might be a bit misleading in the factorio context. Probably "ghost group" would have been a better fit.
But my inspration lies within the realm of video encoding (especially the hap codec) and since I imagined it to somewhat work like a bitmap to store the ghost groups inside the blueprint the term chunk made a lot of sense to me.

[ssilk]

Sorry, I tried to find WHY you want to do assign bots to chunks. I also think there is a “not so good” usage of the word “chunk” which means in a Factorio an area of 32x32 tiles.
Do you think you can explain your idea in two sentences?

[foamy]

Sorry, I tried to find WHY you want to do assign bots to chunks. I also think there is a “not so good” usage of the word “chunk” which means in a Factorio an area of 32x32 tiles.
Do you think you can explain your idea in two sentences?

They want to do it so's a construction bot can place more than one thing per trip, as they will soon be able to do with tiles. The chunking is a method whereby everything within a small portion of a blueprint can be assigned to a single bot as opposed to one for each individual object in it getting a separate one.

[mrvn]

If I understand this right then a better name might be ghost-group.

When the blueprint places 4 assembler a ghost-group is created containing the coordinates of the 4 assemblers. A construction bot will be assigned to the ghost-group, pick up 4 assemblers and place them.

Problems I can think of with this:

1) There might not be 4 assemblers available (or not in one place)

Split the ghost-group into the amount available and the rest (create a new ghost-group for the rest).

2) Parts of a ghost-group might be in different construction networks.

Usually there is no overlap between construction networks so this would be easy to check on placement and then split the ghost-group. But roboports can be added and removed. So further splits might be necessary. Worse might be the personal roboport. It can move a lot. So any ghost-group at the border might get split and then the player moves and no batching happens anymore because everything has been split too much.

Might I suggest a modification?

I would add a pointer to each ghost to the ghost-group they belong too and the ghost-group have pointers to all ghosts. Then when a bot is assigned a ghost it can check all ghosts in a group. If some are unreachable, not buildable or exceed the capacity of the bot the group is split. Make the ghost groups bigger than the cargo capacity and limit them by size on the map. E.g. everything in the same chunk. Or if the bounding box exceeds N tiles split the group in the middle.

Instead of doing this grouping in the blueprint do it on placement. Every placement. When a ghost is placed look for nearby ghosts of the same entity in the same construction network. If any is found join the ghost-group of the existing ghost if possible. Otherwise create a new single-entity ghost-group. If ghost-groups are limited to a chunk the chunk could have a list of ghost-groups in that chunk making it easy to find it without having to scan all entities. Otherwise scan a region with radius (3 times the entities size + 2) or so.

For blueprints the ghost entities in the region of the blueprint can be cached for lower cost of mass placement of ghosts (if not having groups per chunk).

PS: can we group deconstructions too please?

[VuiMuich]

Sorry, I tried to find WHY you want to do assign bots to chunks. I also think there is a “not so good” usage of the word “chunk” which means in a Factorio an area of 32x32 tiles.
Do you think you can explain your idea in two sentences?

Ok, maybe I should have elaborated more on what a chunk would be in this context. Will edit this into the original post.
@foamy got it correct.

If I understand this right then a better name might be ghost-group.

I'm gonna split your quote to answer on specific sections.
'ghost-group' explains what its gonna do quite well, the term chunk was chosen, by inspiration of video-/texture-codecs.

When the blueprint places 4 assembler a ghost-group is created containing the coordinates of the 4 assemblers. A construction bot will be assigned to the ghost-group, pick up 4 assemblers and place them.

Problems I can think of with this:

1) There might not be 4 assemblers available (or not in one place)

Split the ghost-group into the amount available and the rest (create a new ghost-group for the rest).

To explain my solution I want to change your example a little bit. Say the ghost-group is 5 assemblers but the bot can only pick up 3. It then automatically splits of the remaining two ghosts into a new group.
Ghosts cannot be too far apart, since the group-creation has a max radius.

2) Parts of a ghost-group might be in different construction networks.

Usually there is no overlap between construction networks so this would be easy to check on placement and then split the ghost-group. But roboports can be added and removed. So further splits might be necessary. Worse might be the personal roboport. It can move a lot. So any ghost-group at the border might get split and then the player moves and no batching happens anymore because everything has been split too much.

Indeed, when ghosts of one group would located in different not connected networks they should become split into separeate groups indeed.
As for the player network the handling would not differ to much from what it is now I think.

Might I suggest a modification?

I would add a pointer to each ghost to the ghost-group they belong too and the ghost-group have pointers to all ghosts. Then when a bot is assigned a ghost it can check all ghosts in a group. If some are unreachable, not buildable or exceed the capacity of the bot the group is split. Make the ghost groups bigger than the cargo capacity and limit them by size on the map. E.g. everything in the same chunk. Or if the bounding box exceeds N tiles split the group in the middle.

Instead of doing this grouping in the blueprint do it on placement. Every placement. When a ghost is placed look for nearby ghosts of the same entity in the same construction network. If any is found join the ghost-group of the existing ghost if possible. Otherwise create a new single-entity ghost-group. If ghost-groups are limited to a chunk the chunk could have a list of ghost-groups in that chunk making it easy to find it without having to scan all entities. Otherwise scan a region with radius (3 times the entities size + 2) or so.

For blueprints the ghost entities in the region of the blueprint can be cached for lower cost of mass placement of ghosts (if not having groups per chunk).

The whole idea, was to get the grouping done independent of bot logic, to avoid excessive computing with rising numbers of active bots. That is why it happens in the blueprint and gets optimized slowly over time and why the max number is "semihardcoded" by cargo-size.
The idea behind doing it on blueprint creation was, that really big blueprints of like half a factory might take some time on its own. So I thought of a way, where I don't have to do it everytime I use the bleuprint. If the creation of a huge blueprint might lag for a bit, this might feel quite natural, but isn't getting in the way of placing the blueprint.
To check on single ghost placement, if there are any groupable ghosts nearby is a good idea. Whithout this check, it just would be as fast as it works now, and would become optimized over time.

PS: can we group deconstructions too please?

of course, I already thought of it, too. Wouldn't be to different from what the construction palnner would do.

[mrvn]

The whole idea, was to get the grouping done independent of bot logic, to avoid excessive computing with rising numbers of active bots. That is why it happens in the blueprint and gets optimized slowly over time and why the max number is "semihardcoded" by cargo-size.
The idea behind doing it on blueprint creation was, that really big blueprints of like half a factory might take some time on its own. So I thought of a way, where I don't have to do it everytime I use the bleuprint. If the creation of a huge blueprint might lag for a bit, this might feel quite natural, but isn't getting in the way of placing the blueprint.

Sure. It would be nice to do this once for a blueprint and the reuse it a million times. Some pre processing might still be useful.

But I think there is too much work that can only be done at placement time. Like checking which parts of the blueprint are in what construction network. On the other hand if you simply group all ghosts in the same chunk you get a nice benefit for any large building projects at little to no cpu cost and a bit of memory per ghost and chunk.


The way I think about it is this: Sure, bots will take 1% more cpu time. So 100 minutes of real time will only have 99 minutes of game time. BUt also bots will finish building my mega factory in 49.5 minutes games time. Or 50 minutes real time. Why should I care about the slowdown?

[VuiMuich]

But I think there is too much work that can only be done at placement time. Like checking which parts of the blueprint are in what construction network. On the other hand if you simply group all ghosts in the same chunk you get a nice benefit for any large building projects at little to no cpu cost and a bit of memory per ghost and chunk.

I don't think the work at placement time is that much actually. Though I like your idea to use "factorio chunks" to better organize all the ghost groups (but would assign them to the chunk based on the groups origin coordinates).
Maybe I should specify how I think this works out in my head in more detail:

Blueprint creation:

1. blueprint gets created as it is right now
2. the blueprint gets lists of entities of the same type
3. going through these list "create ghost group" gets called
4. a map of the ghost groups is stored along with the the rest of the blueprint

Ghost group creation:

1. check bot cargo size -> length of group
2. (maybe sort "group able entities list" by distance of entities)
3. select entities from "groupable entities list"
4. check if distance is within max group radius

Manual Ghost placement creates Group of length 1 and calls "optimization routine" (see below) on a radius of "max group radius" once.

Blueprint load (either through editing or putting it to the hand):

1. load blueprint
2. check if "ghost group length" matches cargo size
3. (if needed call group creation and store blueprint)

Blueprint placement:

1. for each ghost group assign a global ghost group id
2. place ghosts of each group
3. check if group got placed completely (like loosing ghost through tiles or overlapping entities)
4. if needed update group list

Upgrade Planner/Deconstruction:

1. get list of entities to upgrade/deconstruct
2. make lists of same entity types
3. going through this lists call "group creation"
4. assign IDs to groups

slow pace optimization (run only every now and then, probably every 5sec or something might be sufficient):

1. go through list of ghost groups (default radius 1 chunk) and check if there are any shorter then max lenght
2. for those check if there are possible merges (include ghost groups along the border of neighboring chunks)
3. merge ghost groups by calling "create ghost group" and free obsolete group IDs

Each roboport network maintains its own list of which ghost groups are within in its range, and which groups are assigned to be built by a specific bot.
Since you can place ghosts independent of any robot network I guess there is already a routine on how to attach ghosts to networks and how and when roboports assigned bots to ghosts, so I will ignore this part for now. Of course this will need to be changed to assigned groups and not single ghosts anymore.

Bot assignment and ghost group build:

1. bot with ID gets assigned to build ghost group with ID
2. ghost group gets marked as assigned
3. bot paths a chest to pick up desired items
4. bot travels to chest
5. when bot arrives at chest it checks ghost group length and tries to pick up needed amount of items
6. if needed items > items picked up, determine entities to build and call "group creation" for the rest of entities with a new group ID
7. travel to ghost group
8. place entities on ghosts (possibly with efficient pathing)
9. remove entity from group list

When the bot dies or gets picked up by player while assigned check if it is assigned to a group ID and change the groups state back to unassigned.

The way I think about it is this: Sure, bots will take 1% more cpu time. So 100 minutes of real time will only have 99 minutes of game time. BUt also bots will finish building my mega factory in 49.5 minutes games time. Or 50 minutes real time. Why should I care about the slowdown?

I'm just so keen on saving on computational cost, since it was explicitly mentioned in the FFF, that this was the main concern when approaching batch placement for tens of thousands of bots.
So I tried to find a way that the cost per bot would increase insignificantly, so even at vast numbers it wouldn't become to expensive.
Yet I have to admit I'm far from being expert enough to actually estimate the effective cost, if it would be in the range of fractions or multiples.

[mrvn]

The way I think about it is this: Sure, bots will take 1% more cpu time. So 100 minutes of real time will only have 99 minutes of game time. BUt also bots will finish building my mega factory in 49.5 minutes games time. Or 50 minutes real time. Why should I care about the slowdown?

I'm just so keen on saving on computational cost, since it was explicitly mentioned in the FFF, that this was the main concern when approaching batch placement for tens of thousands of bots.
So I tried to find a way that the cost per bot would increase insignificantly, so even at vast numbers it wouldn't become to expensive.
Yet I have to admit I'm far from being expert enough to actually estimate the effective cost, if it would be in the range of fractions or multiples.

Here is another thing to consider: If you batch 2 entities together that means one less bot has to do work. If the batching costs as much as a bot finding a ghost now you still break even.

[VuiMuich]

Yup, that’s exactly the point why I deemed the optimization might as well happen in a “very slow” pace which is extremely cpu efficient because in the worst case for a while you could be as slow as without ghost groups, but could end up way faster in the end.