Maze reachability can take very long to compute

[sfPlayer1]

Sometimes Recurrent Complex features take excessively long to generate, we had 5 instances in excess of 30 seconds in the past few hours. Sometimes it takes over 4 minutes at once as shown in the following stack trace. It's unclear whether it'd have completed at all since the server was restarted before it could finish.

The version used is 1.3.1 on MC 1.11.2.

"Server thread" #17 prio=5
RUNNABLE
        at com.google.common.collect.AbstractMapBasedMultimap$WrappedCollection.refreshIfEmpty(AbstractMapBasedMultimap.java:382)
        at com.google.common.collect.AbstractMapBasedMultimap$WrappedCollection$WrappedIterator.validateIterator(AbstractMapBasedMultimap.java:471)
        at com.google.common.collect.AbstractMapBasedMultimap$WrappedCollection$WrappedIterator.hasNext(AbstractMapBasedMultimap.java:479)
        at java.lang.Iterable.forEach(Iterable.java:74)
        at ivorius.reccomplex.world.gen.feature.structure.generic.maze.rules.ReachabilityStrategy.traverse(ReachabilityStrategy.java:127)
        at ivorius.reccomplex.world.gen.feature.structure.generic.maze.rules.ReachabilityStrategy.approximateCanReach(ReachabilityStrategy.java:211)
        at ivorius.reccomplex.world.gen.feature.structure.generic.maze.rules.ReachabilityStrategy.canPlace(ReachabilityStrategy.java:291)
        at ivorius.ivtoolkit.maze.components.MazePredicateMany.lambda$canPlace$37(MazePredicateMany.java:48)
        at ivorius.ivtoolkit.maze.components.MazePredicateMany$$Lambda$920/1796262850.test(Unknown Source)
        at java.util.stream.MatchOps$1MatchSink.accept(MatchOps.java:90)
        at java.util.ArrayList$ArrayListSpliterator.tryAdvance(ArrayList.java:1351)
        at java.util.stream.ReferencePipeline.forEachWithCancel(ReferencePipeline.java:126)
        at java.util.stream.AbstractPipeline.copyIntoWithCancel(AbstractPipeline.java:498)
        at java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:485)
        at java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:471)
        at java.util.stream.MatchOps$MatchOp.evaluateSequential(MatchOps.java:230)
        at java.util.stream.MatchOps$MatchOp.evaluateSequential(MatchOps.java:196)
        at java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234)
        at java.util.stream.ReferencePipeline.allMatch(ReferencePipeline.java:454)
        at ivorius.ivtoolkit.maze.components.MazePredicateMany.canPlace(MazePredicateMany.java:48)
        at ivorius.ivtoolkit.maze.components.MazeComponentConnector.lambda$connectMulti$18(MazeComponentConnector.java:59)
        at ivorius.ivtoolkit.maze.components.MazeComponentConnector$$Lambda$894/562816918.test(Unknown Source)
        at java.util.function.Predicate.lambda$and$0(Predicate.java:69)
        at java.util.function.Predicate$$Lambda$848/651829477.test(Unknown Source)
        at ivorius.ivtoolkit.maze.components.MazeComponentConnector.connectMulti(MazeComponentConnector.java:118)
        at ivorius.ivtoolkit.maze.components.MazeComponentConnector.connect(MazeComponentConnector.java:45)
        at ivorius.reccomplex.world.gen.script.WorldScriptMazeGenerator.getPlacedRooms(WorldScriptMazeGenerator.java:267)
        at ivorius.reccomplex.world.gen.script.WorldScriptMazeGenerator.prepareInstanceData(WorldScriptMazeGenerator.java:208)
        at ivorius.reccomplex.world.gen.script.WorldScriptMazeGenerator.prepareInstanceData(WorldScriptMazeGenerator.java:49)
        at ivorius.reccomplex.world.gen.script.WorldScriptMulti.prepareInstanceData(WorldScriptMulti.java:43)
        at ivorius.reccomplex.block.TileEntityBlockScript.doPrepareInstanceData(TileEntityBlockScript.java:59)
        at ivorius.reccomplex.block.TileEntityBlockScript.prepareInstanceData(TileEntityBlockScript.java:54)
        at ivorius.reccomplex.block.TileEntityBlockScript.prepareInstanceData(TileEntityBlockScript.java:25)
        at ivorius.reccomplex.world.gen.feature.structure.generic.GenericStructure.lambda$null$62(GenericStructure.java:352)
        at ivorius.reccomplex.world.gen.feature.structure.generic.GenericStructure$$Lambda$810/472079193.accept(Unknown Source)
        at ivorius.reccomplex.world.gen.feature.structure.generic.GenericStructure.asGeneratingTileEntity(GenericStructure.java:123)
        at ivorius.reccomplex.world.gen.feature.structure.generic.GenericStructure.lambda$prepareInstanceData$63(GenericStructure.java:350)
        at ivorius.reccomplex.world.gen.feature.structure.generic.GenericStructure$$Lambda$762/889017994.accept(Unknown Source)
        at java.util.ArrayList.forEach(ArrayList.java:1249)
        at ivorius.reccomplex.world.gen.feature.structure.generic.GenericStructure.prepareInstanceData(GenericStructure.java:348)
        at ivorius.reccomplex.world.gen.feature.structure.generic.GenericStructure.prepareInstanceData(GenericStructure.java:70)
        at ivorius.reccomplex.world.gen.feature.StructureGenerator.lambda$instanceData$71(StructureGenerator.java:450)
        at ivorius.reccomplex.world.gen.feature.StructureGenerator$$Lambda$749/2146714473.apply(Unknown Source)
        at java.util.Optional.map(Optional.java:215)
        at ivorius.reccomplex.world.gen.feature.StructureGenerator.instanceData(StructureGenerator.java:450)
        at ivorius.reccomplex.world.gen.feature.StructureGenerator.generate(StructureGenerator.java:117)
        at ivorius.reccomplex.world.gen.feature.WorldGenStructures.planStructureInChunk(WorldGenStructures.java:118)
        at ivorius.reccomplex.world.gen.feature.WorldGenStructures.lambda$planStructuresInChunk$688(WorldGenStructures.java:75)
        at ivorius.reccomplex.world.gen.feature.WorldGenStructures$$Lambda$688/1147676204.accept(Unknown Source)
        at java.util.stream.ForEachOps$ForEachOp$OfRef.accept(ForEachOps.java:184)
        at java.util.stream.ReferencePipeline$2$1.accept(ReferencePipeline.java:175)
        at java.util.ArrayList$ArrayListSpliterator.forEachRemaining(ArrayList.java:1374)
        at java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:481)
        at java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:471)
        at java.util.stream.ForEachOps$ForEachOp.evaluateSequential(ForEachOps.java:151)
        at java.util.stream.ForEachOps$ForEachOp$OfRef.evaluateSequential(ForEachOps.java:174)
        at java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234)
        at java.util.stream.ReferencePipeline.forEach(ReferencePipeline.java:418)
        at ivorius.reccomplex.world.gen.feature.WorldGenStructures.planStructuresInChunk(WorldGenStructures.java:75)
        at ivorius.reccomplex.world.gen.feature.WorldGenStructures.decorate(WorldGenStructures.java:194)
        - locked ivorius.reccomplex.world.gen.feature.WorldStructureGenerationData@6f0f6583
        at ivorius.reccomplex.events.handlers.RCForgeEventHandler.onPreChunkDecoration(RCForgeEventHandler.java:84)
        at net.minecraftforge.fml.common.eventhandler.ASMEventHandler_245_RCForgeEventHandler_onPreChunkDecoration_Pre.invoke(.dynamic)
        at net.minecraftforge.fml.common.eventhandler.ASMEventHandler.invoke(ASMEventHandler.java:90)
        at net.minecraftforge.fml.common.eventhandler.EventBus.post(EventBus.java:185)
        at net.minecraftforge.event.ForgeEventFactory.onChunkPopulate(ForgeEventFactory.java:666)
        at ttftcuts.atg.generator.ChunkProviderBasic.func_185931_b(ChunkProviderBasic.java:198)
        at net.minecraft.world.chunk.Chunk.func_186034_a(Chunk.java:1001)
        at net.minecraft.world.chunk.Chunk.func_186030_a(Chunk.java:968)
        at net.minecraft.world.gen.ChunkProviderServer.func_186025_d(ChunkProviderServer.java:158)
        at net.minecraft.server.management.PlayerChunkMapEntry.func_187268_a(PlayerChunkMapEntry.java:126)
        at net.minecraft.server.management.PlayerChunkMap.func_72693_b(SourceFile:147)
        at net.minecraft.world.WorldServer.func_72835_b(WorldServer.java:221)
        at net.minecraft.server.MinecraftServer.func_71190_q(MinecraftServer.java:709)
        at net.minecraft.server.dedicated.DedicatedServer.func_71190_q(DedicatedServer.java:384)
        at net.minecraft.server.MinecraftServer.func_71217_p(MinecraftServer.java:624)
        at net.minecraft.server.MinecraftServer.run(MinecraftServer.java:482)
        at java.lang.Thread.run(Thread.java:745)

[Ivorforce]

Was it better before 1.3.1? Because sometimes that's to be expected (although not quite as extreme) - on my computer some structures take up to 20 seconds to generate, and if it causes chained chunk generation if can be another 20 seconds.

[sfPlayer1]

I don't have any comparison since we started with 1.3.1. 20 seconds sounds extreme, we saw > 240 in this instance with no directly apparent chained generation. Since all my data is a Sampler stall report, I pretty much just have this thread state dump.

Feel free to contact me on IRC (Player, esper) if you need some help profiling the problem. It does however feel like the underlying algorithm has fundamental issues to converge quickly, but I haven't looked at your code so far. I acknowledge that this is by no means an easy problem and that the task at hand is quite complex.

[Ivorforce]

For now you can reduce mazePlacementReversesPerRoom a bit if you want to trade performance for less consistent maze generation. I'm constantly working on improving both performance and determinability of maze reachability (to 'converge' quicker) but it's quite the long task.

[Ivorforce]

As a side note: Apparently structures never saved their instance data - which meant that structures would re-calculate mazes for each chunk generated later. As of 43d85aa, this is no longer the case, so it's possible this will speed up generation for you by a factor of 2 to 20 sometimes.

[Ivorforce]

Update 2: As of 182e59b, maze generation is limited to 20s (configurable) to avoid indefinite freezes.