aliens needs multithreading :/

[Rseding91]

All these theories about fish but everyone's missing this little bit of info:

• On an average save there are 0 active fish.
• When there *are* active fish there are 50-200 at a time
• 170 active fish take 0.007 MS/tick

There's zero reason to even start to think about paralleling the update of fish. The exercise wasn't about "how would you do it" (because there's no reason *to* do it) but what data sets do you think are being mutated during Fish::update().

[kingarthur]

All these theories about fish but everyone's missing this little bit of info:

• On an average save there are 0 active fish.
• When there *are* active fish there are 50-200 at a time
• 170 active fish take 0.007 MS/tick

There's zero reason to even start to think about paralleling the update of fish. The exercise wasn't about "how would you do it" (because there's no reason *to* do it) but what data sets do you think are being mutated during Fish::update().

ok ill give it a shoot as im curious to know.

going back to the original question of what data sets the biters are mutating during their update().

the short answer: all of them.

longer answer.

at any given moment a biter could be walking. attacking. sleeping, colonizing, or dying.

Walking state:
they probably would affect other moving entities. say other biters/ spitters, trains, the player.

Attacking:
would have affects on the given entities health they are hitting which could then effect the power network, turrets, belts, trains, pipes.

Sleeping:
nothing i would assume if this is even an actual state they can be in

Colonizing;
would affect Chunks, map, pollution, other ai entities, turrets.

Dying:
turrets, other biters, possibly chunks/ decorative depending on how the game handles the corpses.

there a pretty solid chance im missing things and/or a million light-years off the mark

[kingarthur]

forgot the minimum and maximum.

id say 0-10 different data sets

[Rseding91]

Biters:

The short answer: everything. Since biters can trigger Lua events that means literally all mutable data is up for mutation.

The long answer:

• Just like fish: as the biter moves it mutates its position and bounding box which other biters will use for collision detection
• Just like fish: biters will effect the active entities list as they move between chunks. They will also activate turrets/other biters as they move around
• As a biter wanders it will use the random generator to randomly wander and possibly if it wanders too close to an enemy go to attack them mutating its current state.
• As a biter goes to move it uses the surface path finder which caches paths for performance reasons. Using the paths mutates them so the path system doesn't delete a path in use by mistake.
• As a biter attacks it can trigger any number of trigger effects (such as creating other entities/firing lua events) and even killing itself if its attack trigger is setup to do damage to itself. If the biter spawns a projectile the projectile will add the calcualted damage it's going to do to the target so other things looking to attack don't over-attack a single target.
• As a biter updates if it's looking to spawn a new base it will effect the surface expansion-canididate-chunks list so the next time the game goes to expand biters it doesn't expand into areas the biters are already around.
• If the biter prototype is configured to do so: it will open any nearby gates.
• If the biter prototype is configured to do so: it will chart any chunks around it.

Fish:

• The Fish position, bounding box (mutated by the fish as it moves and read by other fish as they move to avoid hitting other fish)
• The Map random generator (mutated by the rish as it randomly rotates, read and mutated by other fish as they move)
• The chunk the fish is on (mutated by the fish on the chunk as it moves and read by other fish as they move)
• The Surface the fish is on (mutated by the fish as it moves between chunks and causes chunks to go active/inactive)

[mrvn]

Biters:

The short answer: everything. Since biters can trigger Lua events that means literally all mutable data is up for mutation.

The long answer:

• Just like fish: as the biter moves it mutates its position and bounding box which other biters will use for collision detection
• Just like fish: biters will effect the active entities list as they move between chunks. They will also activate turrets/other biters as they move around
• As a biter wanders it will use the random generator to randomly wander and possibly if it wanders too close to an enemy go to attack them mutating its current state.
• As a biter goes to move it uses the surface path finder which caches paths for performance reasons. Using the paths mutates them so the path system doesn't delete a path in use by mistake.
• As a biter attacks it can trigger any number of trigger effects (such as creating other entities/firing lua events) and even killing itself if its attack trigger is setup to do damage to itself. If the biter spawns a projectile the projectile will add the calcualted damage it's going to do to the target so other things looking to attack don't over-attack a single target.
• As a biter updates if it's looking to spawn a new base it will effect the surface expansion-canididate-chunks list so the next time the game goes to expand biters it doesn't expand into areas the biters are already around.
• If the biter prototype is configured to do so: it will open any nearby gates.
• If the biter prototype is configured to do so: it will chart any chunks around it.

Fish:

• The Fish position, bounding box (mutated by the fish as it moves and read by other fish as they move to avoid hitting other fish)
• The Map random generator (mutated by the rish as it randomly rotates, read and mutated by other fish as they move)
• The chunk the fish is on (mutated by the fish on the chunk as it moves and read by other fish as they move)
• The Surface the fish is on (mutated by the fish as it moves between chunks and causes chunks to go active/inactive)

And what subset of those takes role in bitters planning their revenge on an artillery shot?

Because everything is fine up until the artillery shoots. So only that single action seems worth considering for multithreading.

And the same design I suggested for fish applies to the bitter to. Do a planning phase and and update phase. Group bitters together and create a random number generator per group in a deterministic way. Then each group can plan independently. And the part that seems to kill the UPS is when all the bitters are at their nest and start moving. So none of the other triggers should happen, at least not for a while.

The one item above that seems relevant to the planning phase is that using a path increments its reference count so it doesn't get deleted. That could cause congestion in multithreading but 1) an atomic increment is pretty fast, 2) if aliens close together are grouped together and handled by a single core than no two cores should have the same path. There shouldn't be any collisions on incrementing the reference counts.

All the others would fall into the update phase I think. Plan: I will kill myself. Update: I kill myself and need to mutate a ton of data.

[TheTom]

i.e. all Artillery could scan the areas for posible targets at the same time, add them to a list whiech then is combined and multiple removed, single threaded, possibly at the same time, i.e. as fluid runs. Whether a specific coordinate is a posible target is not depending on other artillery.

You are in fact wrong. What a given artillery is targeting does effect what the next artillery can target. It's what prevents artillery from over-shooting at any given set of targets.

No, I am not - and that is what I meant with bad programmers. You fail to read.

What an artillery TARGES depends on other artillery. What an artillery CAN target does not.

So, you can construct a list of all possible targets for each artillery in a thread per cannon.

THEN you can combine thm into ONE list in one thread / task.

THEN you must go through this list in ONE thread and assign targets, I agree.

But if you would bother to read my post, I was talking explicitly about making the list of POSSIBLE targets, and those are totally independent between each artillery piece.

[TheTom]

Biters:

The short answer: everything. Since biters can trigger Lua events that means literally all mutable data is up for mutation.

The long answer:

• Just like fish: as the biter moves it mutates its position and bounding box which other biters will use for collision detection
• Just like fish: biters will effect the active entities list as they move between chunks. They will also activate turrets/other biters as they move around
• As a biter wanders it will use the random generator to randomly wander and possibly if it wanders too close to an enemy go to attack them mutating its current state.
• As a biter goes to move it uses the surface path finder which caches paths for performance reasons. Using the paths mutates them so the path system doesn't delete a path in use by mistake.
• As a biter attacks it can trigger any number of trigger effects (such as creating other entities/firing lua events) and even killing itself if its attack trigger is setup to do damage to itself. If the biter spawns a projectile the projectile will add the calcualted damage it's going to do to the target so other things looking to attack don't over-attack a single target.
• As a biter updates if it's looking to spawn a new base it will effect the surface expansion-canididate-chunks list so the next time the game goes to expand biters it doesn't expand into areas the biters are already around.
• If the biter prototype is configured to do so: it will open any nearby gates.
• If the biter prototype is configured to do so: it will chart any chunks around it.

Fish:

• The Fish position, bounding box (mutated by the fish as it moves and read by other fish as they move to avoid hitting other fish)
• The Map random generator (mutated by the rish as it randomly rotates, read and mutated by other fish as they move)
• The chunk the fish is on (mutated by the fish on the chunk as it moves and read by other fish as they move)
• The Surface the fish is on (mutated by the fish as it moves between chunks and causes chunks to go active/inactive)

And what subset of those takes role in bitters planning their revenge on an artillery shot?

Because everything is fine up until the artillery shoots. So only that single action seems worth considering for multithreading.

And the same design I suggested for fish applies to the bitter to. Do a planning phase and and update phase. Group bitters together and create a random number generator per group in a deterministic way. Then each group can plan independently. And the part that seems to kill the UPS is when all the bitters are at their nest and start moving. So none of the other triggers should happen, at least not for a while.

The one item above that seems relevant to the planning phase is that using a path increments its reference count so it doesn't get deleted. That could cause congestion in multithreading but 1) an atomic increment is pretty fast, 2) if aliens close together are grouped together and handled by a single core than no two cores should have the same path. There shouldn't be any collisions on incrementing the reference counts.

All the others would fall into the update phase I think. Plan: I will kill myself. Update: I kill myself and need to mutate a ton of data.

Exactly. The PLANNED (!) move of byter X in group Xg is not dependeng on the PLANNED move of byter Y in group Yg that is a couple of chunks away at all. The executed move may be - agreed - but not the planning.

[Rseding91]

The planned movement of a given biter does in fact depend on the planned movement of another biter. Because "planned" is as final as "done". There is no such thing as "planned movement" - only "I want to move here" and then it checks against the biters around it, the entities around it, the group it's in, and adjusts it's position accordingly. If It fails to move too many times it eventually kills itself to prevent getting stuck forever and draining CPU.

The slow part of that is calculating the new position after accounting for all of the other biters/spawners/entities in the way and all of that is outside of this theoretical planning where to move stage.

[ratchetfreak]

most of those biter things sound like a "(hostile) entity made an action" problem rather than a "lets move a biter" problem.

The charting system only needs to know the location, range and force of each charting entity. IOW give it a std::vector holding a struct{bool alive;int range; Location loc; Force* force;} and each charting entity gets a index into that vector (-1 for non charting) on move it can update the position in the corresponding index without locking at all. Spawning and despawning will need modifing access

turrets and gates only need to know location, speed and force of nearby non-neutral entities. Gates only need to know it for the grounded entities. Same with other entities with an agro range.

Also there is a difference between planning the motion and doing the motion. Planning the motion touches entirely different things than doing the motion.

[mrvn]

The planned movement of a given biter does in fact depend on the planned movement of another biter. Because "planned" is as final as "done". There is no such thing as "planned movement" - only "I want to move here" and then it checks against the biters around it, the entities around it, the group it's in, and adjusts it's position accordingly. If It fails to move too many times it eventually kills itself to prevent getting stuck forever and draining CPU.

The slow part of that is calculating the new position after accounting for all of the other biters/spawners/entities in the way and all of that is outside of this theoretical planning where to move stage.

I think you took that "planned" wrong. It's just a way to serialize the updates to the bitters data structure.

The big change would be that a bitters movement would only depend on the position/movement of other bitters in the last tick. Not what nearby biters will do this tick. That change allows processing all the bitters in any order and the result will always be the same. Splitting the code into planning and updating is just a way to ensure all bitters have finished calculating what they will do before they all change their data structures atomically.

What this also means is that bitters have to think a bit ahead. They can't say: "I want to move to (x,y). Is there a bitter at (x,y)? No? Ok, I will move there". Another bitter could decide to move to the same position in the same tick. The bitter has to check: "Could another bitter reach (x,y)?". Luckily one can just increase the bounding box a bit on the collision check. A side effect of this is that bitters that are bunched close together will spread out leaving some room between them. They will stay further apart from each other than their bounding boxes if they have a choice.

[Inglonias]

Unfortunately, multithreading is not a magic wand. As an analogy, in Factorio, it doesn't matter how long you make an express belt. If some section of it is a regular conveyor, you're only delivering 15 items/second on that belt. A computer works the same way. You can multithread all you want, but what Rseding was getting at with his quiz (I think) is that each biter is ultimately going to have to do some waiting to write relevant changes to necessary data fields.

[EpicSlayer7666]

all of this seem fascinating... all of the biters are trying to go through ALL of it's possible states each tick when path finding? at that stage when you shoot an artillery, they want to go to the target but do not know where it is... so they go crazy and try to path find to the target... now it is out of bound (their field of view) and they start the path finding thread but with no target... then the thread goes on until it finds the artillery (and do not naturally) spamming the map with paths that leads nowhere... wow...

a quick hack to fix that would be for the artillery to signal them that it fired and force them to not look around... that will improve performance but make no sense.

a better fix might be for a fix limit of paths to be created from a artillery shot. so they will still look around but not spam new paths...

for multi-threading i am not too knowledgeable... but why could there not be a path index and a thread per core for paths and the biters read from the path index no matter the core that created it?

they will read a path and no matter the core, when path finding, it reads mostly static objects up to target, when "performing the action of moving" IN the path, they move WAY slower than the computer can calculate a path (and correct one) firstly and they only need to consider non-static object when "performing" the path and not during the initial creation of it. so you create first, acknowledging only static objects. and then modify the path during the performing stage (acknowledging moving objects) after the planning.

so in short, it feels like one million biters are trying to create one million paths all at once with a few thousands of way points and revalidating the paths continuously... since they have no target, they probably have a search function that puts waypoints at random... problem is you have a million of biters that are all using that one pathfinder thread for each of them that did a waypoint, then when reached the process continues...

they should have firstly a waypoint limit and second, there should be a thread per core on the waypoint path finding in the planning stage, and then you let the main thread do the correction in the performing stage. (and let the rest of the core's path finding thread ditch the least relevant paths in the index...)

all that said, i AM ignorant, i never did a hello world yet so... but from an obvious perspective, finding the path and performing the path should be separate and a waypoint limit should be imposed. (and maybe a number of active enemies... you could send them in groups while letting the inactive ones sleep waiting for the scouts to find a target and engage or conclude nothing to be found... or simple die and free up active slots.)

[ratchetfreak]

a better fix might be for a fix limit of paths to be created from a artillery shot. so they will still look around but not spam new paths...

One quick hack for that is to make all responders of a artillery shot into a single attack squad with a single path to follow.

[EpicSlayer7666]

a better fix might be for a fix limit of paths to be created from a artillery shot. so they will still look around but not spam new paths...

One quick hack for that is to make all responders of a artillery shot into a single attack squad with a single path to follow.

that could work, since the essence of the problem multi-thread or not is that ALL the biters have no idea where to go and tries all sorts of waypoints at once... heck i think a secondary problem from that in a other forum post was a 500+MB save file... biters and logistics bots tend to spam waypoints.

[Oxyd]

all of the biters are trying to go through ALL of it's possible states each tick when path finding?

No.

at that stage when you shoot an artillery, they want to go to the target but do not know where it is... so they go crazy and try to path find to the target... now it is out of bound (their field of view) and they start the path finding thread but with no target... then the thread goes on until it finds the artillery (and do not naturally) spamming the map with paths that leads nowhere...

No.

for multi-threading i am not too knowledgeable... but why could there not be a path index and a thread per core for paths and the biters read from the path index no matter the core that created it?

Are you trying to multithread literally the easiest path of the whole system here? That is, accessing the path given that you know the path's ID?

they will read a path and no matter the core, when path finding,

How can you read a path when you haven't found it yet?

it reads mostly static objects up to target, when "performing the action of moving" IN the path, they move WAY slower than the computer can calculate a path (and correct one) firstly and they only need to consider non-static object when "performing" the path and not during the initial creation of it. so you create first, acknowledging only static objects. and then modify the path during the performing stage (acknowledging moving objects) after the planning.

Right now, the pathfinder ignores all dynamic objects, except those in the immediate vicinity of the starting position. So you are suggesting doing more work than we currently are doing.

so in short, it feels like one million biters are trying to create one million paths all at once

That's not what's happening.

with a few thousands of way points and revalidating the paths continuously...

That's definitely not what's happening.

since they have no target, they probably have a search function that puts waypoints at random...

Are you joking at this point?

they should have firstly a waypoint limit

They do, but obviously it can't be too low, otherwise they'd hit it too often.

and second, there should be a thread per core on the waypoint path finding in the planning stage, and then you let the main thread do the correction in the performing stage. (and let the rest of the core's path finding thread ditch the least relevant paths in the index...)

Parallel pathfinding would be nice, but, like all things in Factorio, it's not easy to implement.

all that said, i AM ignorant, i never did a hello world yet so...

It shows.

Also, you are missing a crucial piece of information here. The pathfinder will only perform a certain amount of work per tick – this means that long pathfinds simply take many ticks, but the pathfinder itself doesn't take much CPU time every tick. In other words, excessive pathfinding isn't the cause of your UPS drop.

[Oxyd]

a better fix might be for a fix limit of paths to be created from a artillery shot. so they will still look around but not spam new paths...

One quick hack for that is to make all responders of a artillery shot into a single attack squad with a single path to follow.

They do. Although it's more like a dozen of squads at this point, but still – they do group together. Which is pretty apparent because they arrive at your artillery's location in groups.

[EpicSlayer7666]

a better fix might be for a fix limit of paths to be created from a artillery shot. so they will still look around but not spam new paths...

One quick hack for that is to make all responders of a artillery shot into a single attack squad with a single path to follow.

They do. Although it's more like a dozen of squads at this point, but still – they do group together. Which is pretty apparent because they arrive at your artillery's location in groups.

so in the end... if it is not path finding that clogs the Original Poster's map or case... what could be a rough guess at cause of the 90% performance loss after shooting at the biters? (considering no performance is lost when shooting a a lower number of them?)

also while playing with a mod AAI Vehicles, it uses the biter path finding A.I. and it really has a hard time deciding it's true path and can sometimes add a ton of unnecessary turns... so from what i experienced with 1, i though if a thousands biters said: "wow we got shot but we can't tell from where!" that they would just put waypoints away from the spawner in effort to get the biters in view range of the shooter... but seeing how 1 line got full of zigzags, then "1000 destination" having from "10 to 100 zigzags" meant all those are ALL waypoints in between it and the destination.

also i thought that all waypoints were permutable in constant... meaning all those 100 waypoints per destination(at 1000 destination) were being recalculated, continually eating processing power on one thread. so i though, finding new paths could be parallel as long as the main conclusive thread is the one performing the act of traveling and correcting only one main valid path (or used ones). (while other threads would find new ones or better valid ones to add to the index. that the main thread could use.)

[Oxyd]

a better fix might be for a fix limit of paths to be created from a artillery shot. so they will still look around but not spam new paths...

One quick hack for that is to make all responders of a artillery shot into a single attack squad with a single path to follow.

They do. Although it's more like a dozen of squads at this point, but still – they do group together. Which is pretty apparent because they arrive at your artillery's location in groups.

so in the end... if it is not path finding that clogs the Original Poster's map or case... what could be a rough guess at cause of the 90% performance loss after shooting at the biters? (considering no performance is lost when shooting a a lower number of them?)

Rest of the AI. Possibly just moving the biters around. Moving requires a collision check; it requires deciding where to go (you have a path, but you're not necessarily on the path if someone bumps you off); it requires looking at other biters around to keep some distance between them. If there is a truly massive number of moving biters, that could add up. But this is just a guess, I haven't seen the save.

also while playing with a mod AAI Vehicles, it uses the biter path finding A.I. and it really has a hard time deciding it's true path and can sometimes add a ton of unnecessary turns...

I don't know how AAI Vehicles is implemented. I've seen some mods that would continuously change a unit's goal position, but I don't know if that's AAI's case.

For biter pathfinding, we use weighted A*, so it will find paths that sometimes have unnecessary turns in them. The upside is that it finds paths faster than ordinary A*, which finds a shortest path.

so from what i experienced with 1, i though if a thousands biters said: "wow we got shot but we can't tell from where!"

They always know where they got shot from. There is no fog of war or anything for biters, they can see the entire map, and they know where exactly the projectile that hit them came from.

also i thought that all waypoints were permutable in constant... meaning all those 100 waypoints per destination(at 1000 destination) were being recalculated, continually eating processing power on one thread. so i though, finding new paths could be parallel as long as the main conclusive thread is the one performing the act of traveling and correcting only one main valid path (or used ones). (while other threads would find new ones or better valid ones to add to the index. that the main thread could use.)

I don't understand what you mean. You find a path, give it to the biter, and the biter follows it. Once a path is found, it's found and there are no changes happening to it.

[EpicSlayer7666]

I don't understand what you mean. You find a path, give it to the biter, and the biter follows it. Once a path is found, it's found and there are no changes happening to it.

well i mean, if the path finding did it's thing, it started the biter on the path it found and, for example, a player entity or a train or even an other biter crosses it's path and blocks it's route, the waypoints would have to be adjusted to go around the obstacle...

like when you line trace a clear path in a 3D game, the A.I. knows it can pass up to where the line hits. but while the long line trace was done once, if the short line trace hits an obstacle (player or other A.I.) it has to do steps to go around. (all tho old games just brute force walk it's way around... lol)

i was imagining the A.I. was doing some kind of line trace like, point A at X,Y, and it self at X,Y, and had an array of tiles in that line kind of selected, checked on each of them if they contain a impassible object, mark the impassible ones, put extra waypoints to go around them and back on the strait line, while this was the "predicted path", while executing it, if a dynamic object gets in the way like an other biter or anything, it would recalculate those affected points that are after the current position to still be able to reach the destination while leaving the unaffected ones alone.

well if the waypoints are not constantly being re-evaluated, then the actual path finding would not benefit as much as i was imagining it. (imagine a swarm of bees trying to avoid them self... that is what i was picturing...)

[Oxyd]

I don't understand what you mean. You find a path, give it to the biter, and the biter follows it. Once a path is found, it's found and there are no changes happening to it.

well i mean, if the path finding did it's thing, it started the biter on the path it found and, for example, a player entity or a train or even an other biter crosses it's path and blocks it's route, the waypoints would have to be adjusted to go around the obstacle...

like when you line trace a clear path in a 3D game, the A.I. knows it can pass up to where the line hits. but while the long line trace was done once, if the short line trace hits an obstacle (player or other A.I.) it has to do steps to go around. (all tho old games just brute force walk it's way around... lol)

i was imagining the A.I. was doing some kind of line trace like, point A at X,Y, and it self at X,Y, and had an array of tiles in that line kind of selected, checked on each of them if they contain a impassible object, mark the impassible ones, put extra waypoints to go around them and back on the strait line, while this was the "predicted path", while executing it, if a dynamic object gets in the way like an other biter or anything, it would recalculate those affected points that are after the current position to still be able to reach the destination while leaving the unaffected ones alone.

well if the waypoints are not constantly being re-evaluated, then the actual path finding would not benefit as much as i was imagining it. (imagine a swarm of bees trying to avoid them self... that is what i was picturing...)

Nah, that would be super slow. If something blocks the path after it's found, then that's simply ignored. The obstacle might move away before the biter even reaches it, or it might not, in which case the biter will bump into it. If a biter does bump into an obstacle, it will try to go around on its own. After a while, if it detects it can't go around without any help, it asks the pathfinder for a path around the obstacle.