So for jigsaw structures such as villages or outposts, they have what are called template pools and in these pools are pieces of the structure with a weight of how often they get picked. What has been reported is that if someone's datapack sets a piece's weight to a very high value by datapack or a mod, the game will lag hard when loading up the world and when going to the structure. If the weight is high enough, the JVM will run out of memory!
The reason for this is that StructureTemplatePool (mojmap) constructor makes a list. Then makes a new instance of the element x number of times where x is the weight's number. And then add those elements to the list so that they can do a rand.nextInt to grab a random element. Now, going back a bit, making a new instance x number of times means the game's memory gets eaten up very fast and lag will occur from that loop. If too high, the game cannot start at all until the datapack is removed.
Attached is a datapack to reproduce the issue and a pretty picture of the JVM running out of memory despite being given 8GB.
[media]Attachments
Comments 6
This actually incurs quite a performance cost when generating Jigsaw structures, even for only moderate weight sums. A smarter approach can fix the issue altogether.
The following algorithm can be used as an effective replacement for the current JigsawPlacement functionality:
StructurePoolElement processList(List<Pair<StructurePoolElement, Integer>> candidatePiecesList, ...) {
// The sum of all weights in the pool
int totalCount = candidatePieces.stream().mapToInt(Pair::getSecond).reduce(0, Integer::sum);
// Temp var for the piece we are attempting to add
Pair<StructurePoolElement, Integer> chosenPiecePair;
// Iterate the list of possible pieces in this pool
while (candidatePieces.size() > 0) {
// Select a random weight value from 1 to the sum of all weights in the pool.
// We will subtract subsequent pool elements' weights from this number.
// Once chosenWeight <= 0, we will select the pool element we are currently checking as the element to process.
int chosenWeight = rand.nextInt(totalCount) + 1;
// Iterate the candidate pieces (this will be the rawTemplates field in a StructureTemplatePool)
for (Pair<StructurePoolElemen, Integer> candidate : candidatePieces) {
int currentElementWeight = candidate.getSecond();
chosenWeight -= currentElementWeight;
if (chosenWeight <= 0) {
// We have found the element we will attempt to generate
chosenPiecePair = candidate;
break;
}
}
// Here, you should attempt to add the StructurePoolElement contained in chosenPiecePair, as JigsawPlacement$Placer#tryPlacingChildren already does.
// If we successfully place the piece, we can return it (or a bool, or whatever) from this method to indicate successful placement.
...
// If we fail to place this piece, simply do the following.
// This will prepare us to grab another random element from the pool and try again.
totalCount -= chosenPiecePair.getSecond(); // Remove this piece's weight from the total weight sum
candidatePieces.remove(chosenPiecePair); // Remove this piece from the list so we don't attempt to add it again
}
}
This function eliminates the need to create and reshuffle a huge list, while still providing the same functionality. All we need is the pool's rawTemplates field, which is what should be passed in as the candidatePiecesList. Instead of constructing n instances of an element for weight n, we simply subtract n from an integer - no need to allocate and randomize a bunch of objects.
The function can be called directly from JigsawPlacement$Placer#tryPlacingChildren in the following manner to replicate vanilla behavior:
public void tryPlacingChildren(...) {
// Process the pool pieces, randomly choosing different pieces from the pool to spawn
if (depth != this.maxDepth) {
JigsawPiece generatedPiece = this.processList(new ArrayList<>(poolOptional.get().rawTemplates), ...);
if (generatedPiece != null) continue; // Stop here since we've already generated the piece. No need to look at fallback pieces.
}
// Attempt to place one of the fallback pieces in the event none of the pool pieces worked
this.processList(new ArrayList<>(fallbackOptional.get().rawTemplates), ...);
}Overall, this change has pretty drastic performance improvements even for pools with only moderate weight sums.
For a modified version of the JigsawPlacement$Placer#tryPlacingChildren function which includes these changes, see here.
We've limited the weight input for now to prevent the game from crashing. This is obviously not an ideal solution, and further work on this is on our radar.
Can't you assign a number to each structure and then use the random function to select one of the numbers and only then create the instance? Why do all instances have to be created already if only one of them is randomly selected?
It's not even necessary to assign a number. The StructureTemplatePool class already has a rawTemplates field, containing a list of Pairs matching each of the pool's elements with their respective weights.
To state my aforementioned algorithm more simply:
1. Compute the sum of weights (let's call this number s) for all elements in the pool, using the rawTemplates field.
2. Pick a random number between 1 and s inclusive. Let's call this number c, for the chosen weight.
3. Iterate the rawTemplates list. For each element, subtract its weight from c. If c is now less than or equal to zero, choose the current element as the candidate element to place. If c is still positive, continue iterating.
4. Attempt to place the chosen candidate element. If it successfully places, then we're done. If not, then remove its entry from the rawTemplates field, and start at step 1 again.
Hopefully this makes some sense. Let me know if I need to elaborate on something.
I'm gonna agree with Yung that the workaround of restricting the pool weight to 150 is not a good solution. In fact, 150 is way too low and broke a lot of datapacks and my own mods as we use weights around 1000-3000 to try and get the piece ratios correct. So now we have to duplicate the pool entries a ton of times with 150 as the weight to get back to the same old ratios. I think raising the limit to 5000 would be best as the issue described above tends to occur when people try for several 1 in a million ratio for their pieces.
Of course, the best solution would be to just change net/minecraft/world/level/levelgen/feature/structures/StructureTemplatePool's rawTemplates field to be a list of WeighedRandom$WeighedRandomItem that each entry holds the element entry + weight, add an int totalWeight field that is calculated in the constructors for StructureTemplatePool, and get rid of the templates field entirely. Then simply just change getRandomTemplate to be return net/minecraft/util/WeighedRandom.getRandomItem(random, rawTemplates, totalWeight);. Basically, Minecraft already has a class dedicated to getting a random element from a weighted list and changing the pool class to use it would be ideal. Hopefully this helps!
I did some code analysis in the hopes of fixing this in lithium. Sadly it seems impossible to avoid allocating a list/array containing all the elements without changing how current structures would generate in the new codebase.
In
net.minecraft.world.level.levelgen.feature.structures.JigsawPlacement$Placer#tryPlacingChildren(net.minecraft.world.level.levelgen.structure.PoolElementStructurePiece,org.apache.commons.lang3.mutable.MutableObject,int,int,boolean)2 calls are made to
net.minecraft.world.level.levelgen.feature.structures.StructureTemplatePool#getShuffledTemplates(java.util.Random)This method uses
ObjectArrays.shuffle. It's impossible to generate any chunk of this array without generating the whole array.This could be fixed if 1.17 causes worlds to generate differently then in 1.16 in which case changing how structures are generated might be on the table.