[WIP]Stronghold Nav Simulator

[ClearColdWater]

This post is just a trailer, more technical detail coming later; release is coming s∞n(I just have to post something so I keep motivated to finish idk)

UI design(I know nothing, gemini carried)¹

Rough visualization of the current sota² model making decisions on a stronghold, performing a 45.66 +~7 seconds³⁴ average with simpified old nav rules⁵ on a stronghold test set with a sample size of 1000

---

This is what originally motivated me to start this project, I consistently get better end average than stronghold average in my last 50s which is not ok
I spent 70+ hours in the stronghold trainer instance, but I am still so bad, which I guess I can only blame myself for having goldfish working memory*

I did wanted to include stuff like preeptive, but by then with 0 knowledge of Reinforcement Learning making a model on standard strongholds is already a big enough challenge of its own. Still, to actually become helpful for modern players, the preemptive part(and preferably wormholes, silverfish, etc.) has to be made, I already have some vague ideas as to how to make the models but none will necessarily work idk

I don’t speak javascript or pytorch, matplotlib, etc. so 99%+ of the code is generated by gemini and other ai models, I only did some debugging and code review (I don’t like writing code, I’m just here to provide ideas)

*(goldfish doesn’t actually have bad memory, but i do)

¹ i do wish to integrate the model to the Stronghold Trainer mod, but

1. i don’t really speak java either nor did i ever touch mod developing so i will have to spend a lot of time studying the api and stuff
2. the mod says in the release that it doesn’t support custom models and it has not been updated for the last 2 years
3. i saw no elegant way to import some of the data required for the current model; future models that i plan to make involving preemptive, wormholes and stuff will just not work with the mod

basically what i’m saying is i’m lazy.

² if you have ever tried to use the hints from the built in model from Stronghold Trainer, you know that they are not smart. ~20% of the time, all the models with backtracking just leads you wander back and forth, never finding the portal room, which just makes them average ∞ seconds. if you’re curious, a ‘staged dfs’ model that i used to pretrain, which dfs all rooms with depth at or below 8, then 13, then 20, then 50, averages 70.62s on the same test set; i myself(i am really really bad at nav) averaged 55.26s(raw data is 50.83s, the time shown is calibrated by the ‘time gain/loss against Feinberg’ given by Stronghold Trainer, which is another average of 4.43 seconds because i kept doing headhitters everywhere) on another set of 50 strongholds in Stronghold Trainer.
³ every 128 seconds is -1 point of reward, with finding the portal room be a reward of 1, giving 46.66 +~7 seconds; the model counts the time it walks off the starter stairs, i kept that logic for simplicity sake, bringing the real average time to 45.66 +~7 seconds. the model found the portal room in all of the 1000 samples, with the one that took the longest estimated to be taking around 700 steps.
⁴ using the data of ‘average time feinberg spending in a room’ from the og Stronghold Trainer mod by Matthew Bolan.
⁵ that is, no preemptive, no wormholes, no digging, the model can only see direct neighbours of rooms it visited with 2 exceptions⁶, timer starts when the model steps into the initial five way and stops when it steps into the portal room.
⁶ 50% of the time, a wood or iron door generates between two rooms, and i claim that when that happens there is no way to distinguish whether a room is left turn, right turn, straight or spiral stairs until you go in. if a room is hidden behind a wall in five ways, you don’t know what the room behind is at all.

[ClearColdWater]

‘technical details’

---

0. Minecraft Stronghold Generation

0.1 Core Generation Code

This is the stronghold structure generation method:

public void func_230364_a_(ChunkGenerator p_230364_1_, TemplateManager p_230364_2_, int p_230364_3_, int p_230364_4_, Biome p_230364_5_, NoFeatureConfig p_230364_6_) {
   int i = 0;

   while(true) {
      this.components.clear();
      this.bounds = MutableBoundingBox.getNewBoundingBox();
      this.rand.setLargeFeatureSeed(this.field_236364_e_ + (long)(i++), p_230364_3_, p_230364_4_);
      StrongholdPieces.prepareStructurePieces();
      StrongholdPieces.Stairs2 strongholdpieces$stairs2 = new StrongholdPieces.Stairs2(this.rand, (p_230364_3_ << 4) + 2, (p_230364_4_ << 4) + 2);
      this.components.add(strongholdpieces$stairs2);
      strongholdpieces$stairs2.buildComponent(strongholdpieces$stairs2, this.components, this.rand);
      List<StructurePiece> list = strongholdpieces$stairs2.pendingChildren;

      while(!list.isEmpty()) {
         int j = this.rand.nextInt(list.size());
         StructurePiece structurepiece = list.remove(j);
         structurepiece.buildComponent(strongholdpieces$stairs2, this.components, this.rand);
      }

      this.recalculateStructureSize();
      this.func_214628_a(p_230364_1_.func_230356_f_(), this.rand, 10);
      if (!this.components.isEmpty() && strongholdpieces$stairs2.strongholdPortalRoom != null) {
         break;
      }
   }

}

The generation repeats if strongholdpieces$stairs2.strongholdPortalRoom != null is not satisfied, this.rand.setLargeFeatureSeed(this.field_236364_e_ + (long)(i++), p_230364_3_, p_230364_4_); makes so that it restarts an attempt with the next seed, and while(true) ensures the process won’t stop until a stronghold with portal room is generated.

(p_230364_3_ << 4) + 2, (p_230364_4_ << 4) + 2 makes the starter stairs structure’s min-min coords align with 2,2 in the chunk.

List<StructurePiece> list = strongholdpieces$stairs2.pendingChildren;

while(!list.isEmpty()) {
   int j = this.rand.nextInt(list.size());
   StructurePiece structurepiece = list.remove(j);
   structurepiece.buildComponent(strongholdpieces$stairs2, this.components, this.rand);
}

This is the key generation code and is the cause of the so called ‘Forsen’s Law’. When a piece is generated, it doesn’t immediately generate it’s branches, instead it is added to a pool of pieces, and can only generate new branches once it’s been sampled from the pool. This makes the stronghold generation somewhat Breadth First, since a deeply generated room could only generate with its parent room was chosen more times to branch. Note that all pieces have the same odds of being chosen, but some rooms can generate more branch pieces than others.

The core code for deciding what new room to generate:

private static StrongholdPieces.Stronghold generatePieceFromSmallDoor(StrongholdPieces.Stairs2 p_175955_0_, List<StructurePiece> p_175955_1_, Random p_175955_2_, int p_175955_3_, int p_175955_4_, int p_175955_5_, Direction p_175955_6_, int p_175955_7_) {
   if (!canAddStructurePieces()) {
      return null;
   } else {
      if (strongComponentType != null) {
         StrongholdPieces.Stronghold strongholdpieces$stronghold = findAndCreatePieceFactory(strongComponentType, p_175955_1_, p_175955_2_, p_175955_3_, p_175955_4_, p_175955_5_, p_175955_6_, p_175955_7_);
         strongComponentType = null;
         if (strongholdpieces$stronghold != null) {
            return strongholdpieces$stronghold;
         }
      }

      int j = 0;

      while(j < 5) {
         ++j;
         int i = p_175955_2_.nextInt(totalWeight);

         for(StrongholdPieces.PieceWeight strongholdpieces$pieceweight : structurePieceList) {
            i -= strongholdpieces$pieceweight.pieceWeight;
            if (i < 0) {
               if (!strongholdpieces$pieceweight.canSpawnMoreStructuresOfType(p_175955_7_) || strongholdpieces$pieceweight == p_175955_0_.lastPlaced) {
                  break;
               }

               StrongholdPieces.Stronghold strongholdpieces$stronghold1 = findAndCreatePieceFactory(strongholdpieces$pieceweight.pieceClass, p_175955_1_, p_175955_2_, p_175955_3_, p_175955_4_, p_175955_5_, p_175955_6_, p_175955_7_);
               if (strongholdpieces$stronghold1 != null) {
                  ++strongholdpieces$pieceweight.instancesSpawned;
                  p_175955_0_.lastPlaced = strongholdpieces$pieceweight;
                  if (!strongholdpieces$pieceweight.canSpawnMoreStructures()) {
                     structurePieceList.remove(strongholdpieces$pieceweight);
                  }

                  return strongholdpieces$stronghold1;
               }
            }
         }
      }

      MutableBoundingBox mutableboundingbox = StrongholdPieces.Corridor.findPieceBox(p_175955_1_, p_175955_2_, p_175955_3_, p_175955_4_, p_175955_5_, p_175955_6_);
      return mutableboundingbox != null && mutableboundingbox.minY > 1 ? new StrongholdPieces.Corridor(p_175955_7_, mutableboundingbox, p_175955_6_) : null;
   }
}

First the function calls canAddStructurePieces().

private static boolean canAddStructurePieces() {
   boolean flag = false;
   totalWeight = 0;

   for(StrongholdPieces.PieceWeight strongholdpieces$pieceweight : structurePieceList) {
      if (strongholdpieces$pieceweight.instancesLimit > 0 && strongholdpieces$pieceweight.instancesSpawned < strongholdpieces$pieceweight.instancesLimit) {
         flag = true;
      }

      totalWeight += strongholdpieces$pieceweight.pieceWeight;
   }

   return flag;
}

So it is clear that there are different weights for different pieces to generate, which I will cover in the details part. Focus on
if (strongholdpieces$pieceweight.instancesLimit > 0 && strongholdpieces$pieceweight.instancesSpawned < strongholdpieces$pieceweight.instancesLimit). There are limits for generation count for certain rooms, but others don’t, which is marked as having a limit of 0, hence the strongholdpieces$pieceweight.instancesLimit > 0. The code checks if all limited rooms are at limit, and if a single one is not then the generation continues. If they all are, generatePieceFromSmallDoor exits immediately, and no more branches can ever generate. In a sense, the whole stronghold generation is based around the generation of these special rooms. This also means if the early stronghold generation didn’t stop itself by collision, almost always all the limited rooms have to generate before the generation completely stops, resulting in a relatively stable distribution of rooms count across strongholds.

Then it checks for strongComponentType != null. This is only used once in the code that the starter stairs (in the code I got it is named ‘stairs2’ which is really weird) have it’s exit branch a five way crossing room. Note that this particular room did not take a spot in the total amount of five way crossing that could spawn
(no ++strongholdpieces$pieceweight.instancesSpawned;).

Then it runs 5 attempts to generate a new piece. The totalWeight is calculated in the canAddStructurePieces() call.

if (!strongholdpieces$pieceweight.canSpawnMoreStructures()) {
   structurePieceList.remove(strongholdpieces$pieceweight);
}

public boolean canSpawnMoreStructures() {
   return this.instancesLimit == 0 || this.instancesSpawned < this.instancesLimit;
}

If a limited piece is at limit, it will be removed from the structurePieceList, which prevents them from taking the spot of other valid pieces to spawn.

for(StrongholdPieces.PieceWeight strongholdpieces$pieceweight : structurePieceList) {
   i -= strongholdpieces$pieceweight.pieceWeight;
   if (i < 0) {

The code repeatedly subtract the piece’s weight until it reaches below zero, which I suppose is supposed to pick one particular piece and check its ability to spawn, but if the generation fails it doesn’t break and start another generation loop, but instead keeps cycling pieces in a set order which is really confusing. What I think happens is originally the break is there and the mojang people gets annoyed that too many strongholds fails as dead ends and ultimately they just remove it so a new piece almost always get generated.

if (!strongholdpieces$pieceweight.canSpawnMoreStructuresOfType(p_175955_7_) || strongholdpieces$pieceweight == p_175955_0_.lastPlaced) {
   break;
}

public boolean canSpawnMoreStructuresOfType(int p_75189_1_) {
   return this.instancesLimit == 0 || this.instancesSpawned < this.instancesLimit;
}

new StrongholdPieces.PieceWeight(StrongholdPieces.Library.class, 10, 2) {
   public boolean canSpawnMoreStructuresOfType(int p_75189_1_) {
      return super.canSpawnMoreStructuresOfType(p_75189_1_) && p_75189_1_ > 4;
   }
},
new StrongholdPieces.PieceWeight(StrongholdPieces.PortalRoom.class, 20, 1) {
   public boolean canSpawnMoreStructuresOfType(int p_75189_1_) {
      return super.canSpawnMoreStructuresOfType(p_75189_1_) && p_75189_1_ > 5;
   }
}

So libraries can only spawn at depth > 4, and portal rooms can only spawn at depth > 5. Also if the loop reaches the library and depth > 4 is not satisfied, it will break instead of keep looping and attempt to generate a portal room, which makes sense since if depth > 4 is false depth > 5 can’t be true.

Then it calls findAndCreatePieceFactory() to try generate the chosen piece in the spot. The factory then calls the createPiece() method of the corresponding piece type. Take the createPiece() method of Straight for example:

public static StrongholdPieces.Straight createPiece(List<StructurePiece> p_175862_0_, Random p_175862_1_, int p_175862_2_, int p_175862_3_, int p_175862_4_, Direction p_175862_5_, int p_175862_6_) {
   MutableBoundingBox mutableboundingbox = MutableBoundingBox.getComponentToAddBoundingBox(p_175862_2_, p_175862_3_, p_175862_4_, -1, -1, 0, 5, 5, 7, p_175862_5_);
   return canStrongholdGoDeeper(mutableboundingbox) && StructurePiece.findIntersecting(p_175862_0_, mutableboundingbox) == null ? new StrongholdPieces.Straight(p_175862_6_, p_175862_1_, mutableboundingbox, p_175862_5_) : null;
}

protected static boolean canStrongholdGoDeeper(MutableBoundingBox p_74991_0_) {
   return p_74991_0_ != null && p_74991_0_.minY > 10;
}

It seems that the Y coordnate of the stronghold is only relative, I’m not really sure, since in practice clearly rooms can generate below y11. Then it checks if the new piece intersects with existing pieces via findIntersecting(). If not, a new piece is created.

The rest of the logic was already covered above except

p_175955_0_.lastPlaced = strongholdpieces$pieceweight;

It effectively makes the loop start from a randomly chosen piece and stop at the last placed piece. This is made presumably to componsate for not breaking out of the loop, though it doesn’t really do much (I tested removing it when I was collecting stats for stronghold generation, and it barely changed).

Finally, if no piece type was chosen, a corridor is attempted to generate as a fallback.

public static MutableBoundingBox findPieceBox(List<StructurePiece> p_175869_0_, Random p_175869_1_, int p_175869_2_, int p_175869_3_, int p_175869_4_, Direction p_175869_5_) {
   int i = 3;
   MutableBoundingBox mutableboundingbox = MutableBoundingBox.getComponentToAddBoundingBox(p_175869_2_, p_175869_3_, p_175869_4_, -1, -1, 0, 5, 5, 4, p_175869_5_);
   StructurePiece structurepiece = StructurePiece.findIntersecting(p_175869_0_, mutableboundingbox);
   if (structurepiece == null) {
      return null;
   } else {
      if (structurepiece.getBoundingBox().minY == mutableboundingbox.minY) {
         for(int j = 3; j >= 1; --j) {
            mutableboundingbox = MutableBoundingBox.getComponentToAddBoundingBox(p_175869_2_, p_175869_3_, p_175869_4_, -1, -1, 0, 5, 5, j - 1, p_175869_5_);
            if (!structurepiece.getBoundingBox().intersectsWith(mutableboundingbox)) {
               return MutableBoundingBox.getComponentToAddBoundingBox(p_175869_2_, p_175869_3_, p_175869_4_, -1, -1, 0, 5, 5, j, p_175869_5_);
            }
         }
      }

      return null;
   }
}

The Corridor has a flexible width of 3 max, shown in the findPieceBox method above. This is to connect a potential close room at the same floor level as the corridor with its parent room.

0.2 Details

private static final StrongholdPieces.PieceWeight[] PIECE_WEIGHTS = new StrongholdPieces.PieceWeight[]{
new StrongholdPieces.PieceWeight(StrongholdPieces.Straight.class, 40, 0), 
new StrongholdPieces.PieceWeight(StrongholdPieces.Prison.class, 5, 5), 
new StrongholdPieces.PieceWeight(StrongholdPieces.LeftTurn.class, 20, 0), 
new StrongholdPieces.PieceWeight(StrongholdPieces.RightTurn.class, 20, 0), 
new StrongholdPieces.PieceWeight(StrongholdPieces.RoomCrossing.class, 10, 6), 
new StrongholdPieces.PieceWeight(StrongholdPieces.StairsStraight.class, 5, 5), 
new StrongholdPieces.PieceWeight(StrongholdPieces.Stairs.class, 5, 5), 
new StrongholdPieces.PieceWeight(StrongholdPieces.Crossing.class, 5, 4), 
new StrongholdPieces.PieceWeight(StrongholdPieces.ChestCorridor.class, 5, 4), 

new StrongholdPieces.PieceWeight(StrongholdPieces.Library.class, 10, 2) {
      public boolean canSpawnMoreStructuresOfType(int p_75189_1_) {
         return super.canSpawnMoreStructuresOfType(p_75189_1_) && p_75189_1_ > 4;
      }
   }, 

new StrongholdPieces.PieceWeight(StrongholdPieces.PortalRoom.class, 20, 1) {
      public boolean canSpawnMoreStructuresOfType(int p_75189_1_) {
         return super.canSpawnMoreStructuresOfType(p_75189_1_) && p_75189_1_ > 5;
      }
   }};

The first number after piece class name denotes the weight in the piece type choosing process, and the second denotes the limit count the piece type can spawn.

public Crossing(int p_i45580_1_, Random p_i45580_2_, MutableBoundingBox p_i45580_3_, Direction p_i45580_4_) {
...
   this.leftLow = p_i45580_2_.nextBoolean();
   this.leftHigh = p_i45580_2_.nextBoolean();
   this.rightLow = p_i45580_2_.nextBoolean();
   this.rightHigh = p_i45580_2_.nextInt(3) > 0;
}

In case it isn’t obvious already, Crossing is the name of 5 ways in the code. The front branch always generates; leftLow, leftHigh and rightLow all generates \frac{1}{2} of the time; rightHigh generates \frac{2}{3} of the time, presumably because the previous branches take up all the space and they want the last generated branch to have a higher chance.
In comparison, RoomCrossing always tries to generate all 3 branches; Straight always generates front branch, and the left and right side branch generates independently \frac{1}{2} of the time each.

public void buildComponent(StructurePiece componentIn, List<StructurePiece> listIn, Random rand) {
   int i = 3;
   int j = 5;
   Direction direction = this.getCoordBaseMode();
   if (direction == Direction.WEST || direction == Direction.NORTH) {
      i = 8 - i;
      j = 8 - j;
   }

   this.getNextComponentNormal((StrongholdPieces.Stairs2)componentIn, listIn, rand, 5, 1);
   if (this.leftLow) {
      this.getNextComponentX((StrongholdPieces.Stairs2)componentIn, listIn, rand, i, 1);
   }

   if (this.leftHigh) {
      this.getNextComponentX((StrongholdPieces.Stairs2)componentIn, listIn, rand, j, 7);
   }

   if (this.rightLow) {
      this.getNextComponentZ((StrongholdPieces.Stairs2)componentIn, listIn, rand, i, 1);
   }

   if (this.rightHigh) {
      this.getNextComponentZ((StrongholdPieces.Stairs2)componentIn, listIn, rand, j, 7);
   }
}

public boolean func_230383_a_(ISeedReader p_230383_1_, StructureManager p_230383_2_, ChunkGenerator p_230383_3_, Random p_230383_4_, MutableBoundingBox p_230383_5_, ChunkPos p_230383_6_, BlockPos p_230383_7_) {
   this.fillWithRandomizedBlocks(p_230383_1_, p_230383_5_, 0, 0, 0, 9, 8, 10, true, p_230383_4_, StrongholdPieces.STRONGHOLD_STONES);
   this.placeDoor(p_230383_1_, p_230383_4_, p_230383_5_, this.entryDoor, 4, 3, 0);
   if (this.leftLow) {
      this.fillWithBlocks(p_230383_1_, p_230383_5_, 0, 3, 1, 0, 5, 3, CAVE_AIR, CAVE_AIR, false);
   }

   if (this.rightLow) {
      this.fillWithBlocks(p_230383_1_, p_230383_5_, 9, 3, 1, 9, 5, 3, CAVE_AIR, CAVE_AIR, false);
   }

   if (this.leftHigh) {
      this.fillWithBlocks(p_230383_1_, p_230383_5_, 0, 5, 7, 0, 7, 9, CAVE_AIR, CAVE_AIR, false);
   }

   if (this.rightHigh) {
      this.fillWithBlocks(p_230383_1_, p_230383_5_, 9, 5, 7, 9, 7, 9, CAVE_AIR, CAVE_AIR, false);
   }
...

In the buildComponent method, when the direction of the room is west or north, the direction is flipped to match their name:

if (direction == Direction.WEST || direction == Direction.NORTH) {
   i = 8 - i;
   j = 8 - j;
}

But when digging the doorway on the wall, no such logic is applied, which makes the doorway for one branch dug on the other, resulting what’s know as the ‘hidden rooms’.

while(!list.isEmpty()) {
   int j = this.rand.nextInt(list.size());
   StructurePiece structurepiece = list.remove(j);
   structurepiece.buildComponent(strongholdpieces$stairs2, this.components, this.rand);
}

After a piece is selected from the pool to branch, its buildComopnent method is called. For example, this is the buildComopnent method of a Straight piece:

public void buildComponent(StructurePiece componentIn, List<StructurePiece> listIn, Random rand) {
   this.getNextComponentNormal((StrongholdPieces.Stairs2)componentIn, listIn, rand, 1, 1);
   if (this.expandsX) {
      this.getNextComponentX((StrongholdPieces.Stairs2)componentIn, listIn, rand, 1, 2);
   }

   if (this.expandsZ) {
      this.getNextComponentZ((StrongholdPieces.Stairs2)componentIn, listIn, rand, 1, 2);
   }

}

Here it calls for getNextComponentNormal, getNextComponentX and getNextComponentZ, corrisponding respectively to a front, left and right branch. They are all pretty much the exact same thing, the only differnece is the way they calculate where the branch exit is positioned with respect to the room. After the position is calculated, it calls for generateAndAddPiece.

private static StructurePiece generateAndAddPiece(StrongholdPieces.Stairs2 p_175953_0_, List<StructurePiece> p_175953_1_, Random p_175953_2_, int p_175953_3_, int p_175953_4_, int p_175953_5_, @Nullable Direction p_175953_6_, int p_175953_7_) {
   if (p_175953_7_ > 50) {
      return null;
   } else if (Math.abs(p_175953_3_ - p_175953_0_.getBoundingBox().minX) <= 112 && Math.abs(p_175953_5_ - p_175953_0_.getBoundingBox().minZ) <= 112) {
      StructurePiece structurepiece = generatePieceFromSmallDoor(p_175953_0_, p_175953_1_, p_175953_2_, p_175953_3_, p_175953_4_, p_175953_5_, p_175953_6_, p_175953_7_ + 1);
      if (structurepiece != null) {
         p_175953_1_.add(structurepiece);
         p_175953_0_.pendingChildren.add(structurepiece);
      }

      return structurepiece;
   } else {
      return null;
   }
}

Rooms can never generate more than 50 rooms deep, or further than 112 blocks from the starter stairs. There are no other constraints as to how deep a room can generate, so 50 deep portal rooms are theoreticaly possible. And finally, generateAndAddPiece calls for generatePieceFromSmallDoor.

protected StrongholdPieces.Stronghold.Door getRandomDoor(Random p_74988_1_) {
   int i = p_74988_1_.nextInt(5);
   switch(i) {
      case 0:
      case 1:
      default:
         return StrongholdPieces.Stronghold.Door.OPENING;
      case 2:
         return StrongholdPieces.Stronghold.Door.WOOD_DOOR;
      case 3:
         return StrongholdPieces.Stronghold.Door.GRATES;
      case 4:
         return StrongholdPieces.Stronghold.Door.IRON_DOOR;
   }
}

\frac{2}{5} of the time the door is just an opening; other 3 types of doors generate \frac{1}{5} each.

0.3 Takeaways

Strongholds generates in a tree structure, the root being the starter stairs, every step a leaf is randomly chosen to branch more rooms, rooms will fail to generate if they collide with existing rooms, all generation is shut down if all special limited rooms are at limit. Every stronghold will have a portal room.

---

If it isn’t obvious this is becoming a cs class
I will add an * to note things that weren’t implemented by code yet because I’m stupid
and a # to note ones that I didn’t implement for other reasons

1. Naive thoughts

1.1 How to Model the Stronghold

Understanding the stronghold generation logic is one thing, making an ai understand it is another thing. To my knowledge, there are two ways to model the stronghold, one is to feed the model block by block, which preserves all collision information, but is incredibly bulky and the model is likely not gonna be trained in another century; one is to abstract every room as nodes in graph theory, and connections between rooms edges. If we only model the connections between parent rooms and child rooms, the stronghold forms a nice tree structure, where there are no cycles and there is exactly one path from one room to the next.

(writing with a mouse is actually impossible)

This gives us the ability to aggrigate the potentials of every child node to its parent node, which itself could be a child of another node. One way to utilize this is to let the aggrigation unfold, ultimately aggrigeting to the neighbour nodes of the player, letting the player decide which neighbour node is better. Another important thing is we can assign the potential of every unseen node to its first seen parent node. In other words, the leaves of the player observed stronghold tree is responsable for every potential node that might generate with that leaf node as its ancestor.

Although modeling strongholds as trees have all these very nice properties, it is not exactly accurate. The path between parent and child is not the only way to move from one room to the other. It isn’t even the only way to move as the stronghold structure intended, for the 1~3 block wide corridors that generates between rooms at same floor level when all other rooms fail because of collision. Caves and ravines can corrupt the stronghold (technically, most stronghold blocks aren’t programmed to overwrite the cave, so only lava pools, ruined portals, etc. counts as corruption), giving ways to wormhole from rooms.
Further more, you can straight up dig from one room to the other when you hear silverfish, or just swim without any bounds if the stronghold is ocean exposed.

• I’ve included a virtual ‘cave’ node and ‘ocean’ node for simplicity, but in reality the distance from one node and the other will not be the same as it suggests, so to be precise every node that is exposed to the cave/ocean have to have an edge connected to each other. This makes the edge count skyrocket from E = V - 1 to E = O(V^{2}).

Preemptive nav is not covered in this model either but I think we can all agree we have to understand basic nav before we move on to that.

1.2 Toy Models

1.2.1 Nav knowing literally the entire stronghold structure

The best strat is just follow the fastest path to the portal room, which in the tree model there is only one path to the portal room.

1.2.2 Nav knowing the entire stronghold structure but not leaf room types, without backtracking (unless subtree is completely explored)

(Let’s ignore the fact that in the example portal rooms can’t generate at depth <= 5, or you can imagine that it is a subtree)

Let’s say we have a way to make the model predict the probability of a leaf node being the portal room. We also know the time cost of moving along an edge. If have to depth-first search the tree, meaning we ban backtracking unless the subtree is completely explored, the decision to make is only between child nodes branched by the current node. There is actually a very nice theorm which states that you should always choose the subtree with the most cost effectiveness, \max\limits_{v \in child(u)}(\dfrac{P_v}{C_v}), in which P_u = \sum\limits_{v \in child(u)} P_v is the probability of subtree of x has portal room, and C_u = \sum\limits_{v \in child(u)} C_v + 2w_{uv} is the time cost of entirely exploring the subtree of x and returning to its parent node. The proof is as follows:

---

Let’s say we are at node u, and we are deciding between moving to v_1, v_2, \dots, v_n first.

Let P_u be the probability the portal room is in some child subtree of u, and let P_{\text{out}} = 1 - P_u be the probability it is not in u 's subtree.
If the portal is not in u 's subtree, we must eventually explore all subtrees, incurring a fixed total cost \sum_{i=1}^n C_i regardless of order. Thus this case contributes a constant term P_{\text{out}} \cdot \sum_{i=1}^n C_i to the expected cost, which does not affect the optimal ordering.

Hence, minimizing the total expected cost is equivalent to minimizing the expected cost conditioned on the portal room being in u 's subtree. Under this condition, the conditional probability for subtree v_i is p_i = \frac{P_i}{P_u}.

Without loss of generality, assume \frac{p_1}{C_1} \geq \frac{p_2}{C_2} \geq \dots \geq \frac{p_n}{C_n}. Suppose that visiting v_k first is an optimal decision, meaning there exists an optimal order \sigma where v_k is the first child visited. We will show that visiting v_1 first is at least as good, i.e., the order \sigma' with v_1 first and the remaining children in the same relative order as in \sigma (after removing v_1 and v_k) has expected cost no greater than that of \sigma.

For any two children a and b, if \frac{p_a}{C_a} < \frac{p_b}{C_b}, then swapping their order from a, b to b, a decreases the expected cost. This can be derived by comparing the contributions of a and b to the total expected cost.

Let T_i be the expected time to find the portal room given it is in subtree v_i. Then, for an order where a is visited before b, the contribution of a and b to the expected cost is p_a T_a + C_a (p_b + R) + p_b T_b + C_b R ,
where R is the total probability of subtrees visited after b. If we swap to visit b before a, the contribution becomes
p_b T_b + C_b (p_a + R) + p_a T_a + C_a R .
The difference \Delta between the first and second is
\Delta = C_a p_b - C_b p_a .
Thus, if \frac{p_a}{C_a} \leq \frac{p_b}{C_b}, then C_a p_b - C_b p_a \geq 0, so swapping does not increase the expected cost.

Now, in the optimal order \sigma with v_k first, consider the position of v_1. Since \frac{p_1}{C_1} \geq \frac{p_i}{C_i} for all i, including v_k, we can move v_1 to the front by repeatedly swapping it with the child immediately before it. Each such swap involves a pair (a, v_1) where a is the child currently before v_1, and since \frac{p_1}{C_1} \geq \frac{p_a}{C_a}, swapping does not increase the expected cost. After a finite number of swaps, v_1 becomes the first child, resulting in order \sigma'. The expected cost of \sigma' is no greater than that of \sigma.

Therefore, if visiting v_k first is optimal, visiting v_1 first is also optimal (or better). This implies that the optimal strategy is always to choose the child with the highest ratio \frac{p_v}{C_v}, completing the proof.

---

1.2.3 Nav without backtracking (unless subtree is completely explored)

Now we can’t know ahead of time the structure of the stronghold, instead let’s say we can only see full information of direct neighbours of currently explored nodes, so we can’t just see the leaves of the stronhold. Fortunately, thanks to the aggrigation property of a tree, we don’t have to make the model predict the average subtree and leaves of a node u, instead we can make it directly predict P_u and C_u and that’s it.

I've originally assigned 5 days in this project and it has gone massively, massively over due. During the past month I probably averaged more than 6 hours doing this project, probably more in the past 2 weeks because I felt irresponsable to not finish it after releasing a trailer, and it has made me incredibly ill both physically and mentally. Yesterday I finally made the decision to take a long break, but I still wanted to at least finish a report on the ai model. Unfortunately after a full day of writing it wasn't even half way done, and I will have to leave it as is. I will finish the report somewhat soon and release cleaned code currently written, but there will be no guaranteed date for a working release or anything further like preemptive.

[r0hkx]

wow, even though a lot of this went over my head this looks really exciting. definitely will be the most in depth analysis of strongholds by far, and it seems certain that it will motivate better preemptive and non-preemptive nav principles

and no pressure to finish this any time soon. take your time and pace yourself, mcsr will still be here

[ClearColdWater]

1.3 Approaches to Making the AI Model

For now I’ve been refering to the ai model as a black box, and now is the time to unbox it. What information should we provide to the model? What architecture of ai model should we try? How exactly would we expect such an ai model to predict the probability of portal room spawning in the subtree of a node given those information?

1.3.-1

I am really stupid and did not actually implement pretty much anything I analyized here into the made AI model, I only found most of these being an issue after I started writing the report. For the current models, I later found out all the measures to solving the issues below either don’t exist or function at all or could be so much better. AND ALSO ALL THE AVERAGE TIMES PERFORMED BY THE MODEL ADVERTISED WERE INFLATED BY ~7 SECONDS BECAUSE I COPIED THE DATA DIRECTLY FROM THE WEB VERSION WHICH I SUBTRACTED 0.2 SECONDS EVERY STEP FOR DECISION MAKING IM REALLY SORRY ;-;
though somehow with all the issues it is still better than me, maybe i'm chopped
also i'm semi-confident that if the theoretical model is made it will go way pass that

1.3.0 Softmax and Probability Mass

Before diving in, there is one quick thing that I want to mention. Every stronghold successfully generated consists of a portal room, which means that the sum of probability of portal room spawning in all leaf nodes’ should be 1. But outputs of a neural network can be any real number, some might be negative, some might be bigger than 1, and they almost certainly don’t add up to 1. So instead of trying the impossible task to make it learn to have all its output probability land in [0,1] and have them add up to 1, we instead make it predict the log of its probablily mass, and pass it through what’s known as a softmax function to unify the sum back to 1.

• instead of directly predicting P_1, P_2, \cdots, P_n \in [0, 1] that satisfies P_1 + P_2 + \cdots + P_n = 1, have it predict z_1, z_2, \cdots, z_n \in (-\infty,+\infty) (commonly refered to as logits) and calculate P_i = softmax(z_i) which softmax(x_i) = \frac{exp(x_i)}{\sum\limits_{j=1}^{n}exp(x_j)}.

1.3.1 Space and Branches

Let’s go over the stronghold’s generating algorithm.
Assume that at some point of the generation process the stronghold looks like this:

Here, all rooms that have a chance to be selected from the pool to branch are circled in white, They are the leaves of the stronghold tree (in the context that the starter stairs being the root). Note that the rooms circled in gray are also leaves of the tree, but they can’t be selected, because they have already been selected before and failed to branch for whatever reason (collision, depth constraints, etc.). The algorithm selects one of them randomly and tries to create a room for all its branches. Note that there are hard coded orders as to which branches gets generated first, for example if a RoomCrossing room generates in the front branch of a Straight room, then \frac{1}{2} of the time its left branch tries to generate immediately after, it cannot generate another RoomCrossing room due to both the lastPlaced logic and collision. However, after the branched rooms are generated, they all go back to the same pool of random selection, in which they have the exact same chance of being selected again, so there are no more priorities between branches once their rooms are already generated.

Since the smallest unit of branch generation are the exit branches of observed leaf rooms, we may very reasonably split our objective of predicting the expected probability mass of a leaf room into that of its exit branches (which may or may not be decided to generate by the leaf room itself), which from now on I will call them leaf branches.

instead of predicting for each leaf room:

predict for each leaf branch:

Side Note: In the current web version you can see the doorways of 5 ways w/o entering them. In reality, you can see doorways of a lot of rooms w/o entering but not for 5 ways. This is likely going to be fixed.

This comes with a lot of benefits:

• Every leaf branch has its distinct position and direction, and are equivalent across different room types.
• The leaf rooms can now be treated as and only as a box for collision, just like all other observed rooms.
• We can explicitly encode for the model to understand the fact that there are priorities of generation between sibling rooms.

Take a look at the following case which we assume shows the earlier stages of a stronghold’s generation.

You can see on top, a Straight room, not only has its exit branch far more space for another room to generate (which gives chances for RoomCrossing or Crossing(commonly refered to as 5 ways) to generate), but also has more room for those branches to expand on, whereas for the bottom LeftTurn room has far less space. This gives rise to the ‘room tier list’ theory that states rooms that rooms that are large which blocks other branches from spawning, that take you further away from the currently generated stronghold, should be prioritized in the generation(better).

This is a good rule of thumb but in some cases it falls short. Take this as an example:

Here, a RightTurn room has much more space to generate than a Straight room.

So it is clear that the room type is only half the story. What we want for the model to detect is when there are (or can be) rooms that could potentially block the space for a leaf branch’s subtree to generate.

How we may actually achieve that is another story.

1.3.2 Depth and Priority

For now, let’s focus on how the depth of the rooms affects things.

Depth

We already know in chapter 0.1 that When a piece is generated, it doesn’t immediately generate it’s branches, instead it is added to a pool of pieces, and can only generate new branches once it’s been sampled from the pool. This makes the stronghold generation somewhat Breadth First, since a deeply generated room could only generate with its parent room was chosen more times to branch. is the cause of the ‘Forsen’s Law’.

But what I didn’t say is that is also due to the relatively high weight assigned to portal rooms in random selection (which is 20). Here I ran a few more tests with portal room weights tweaked to 5(= StairsStraight, Stairs, Crossing, ChestCorridor), 10(= RoomCrossing, Library), 40(= Straight) and 200(sum of every other room type is 125) respectively, along with the original results from 20( = LeftTurn, RightTurn, PortalRoom):

You can see that the higher the weight is assigned to the portal room, the more motivated it is to spawn in lower depths. When the weight is low, it tends to spread out across the generation of the entire stronghold; whereas when the weight is high, it tends to get immediately spawned by branches that reaches the minimum depth requirement of 6. You can also see that the probability of the portal room generating in higher depths decays exponentially(mostly).

So why is that? We already know that stronghold generation is somewhat breadth first, so let’s see what actually happens when it is entirely breadth first.
(Again, let’s ignore the fact that in the example portal rooms can’t generate at depth <= 5, or you can imagine that it is a subtree)

Let X be the actual depth of the portal room, and \lambda be the probability of any chosen room being chosen as portal room. To make the generation process entirely breadth first, a node cannot be chosen to branch before every node with lower depth was.

So for the 1 node at depth 1, probability for portal room not spawning is P(X>1)=(1-\lambda)^{n_d} = (1-0.1)^1 = 0.9,
leaving probability for portal room to spawn
P(X=1)=1-(1-\lambda)^{n_d} = 0.1;

if for P(X>1)=0.9 portal room did not spawn at depth 1,
for the 3 nodes at depth 2, probability for portal room not spawning is P(X>2)=P(X>1) \cdot (1-\lambda)^{n_d} = 0.9 \times (1-0.1)^3 = 0.656,
leaving probability for portal room to spawn
P(X=2)=P(X>1) \cdot [1-(1-\lambda)^{n_d}] = 0.9 \times [1-(1-0.1)^3] = 0.244
and so on.

Notice what happens if we expand P(X>d).
P(X>1) = (1-\lambda)^{n_1};
P(X>2) = P(X>1) \cdot (1-\lambda)^{n_2} = (1-\lambda)^{n_1} \cdot (1-\lambda)^{n_2} = (1-\lambda)^{n_1 + n_2};
P(X>3) = P(X>2) \cdot (1-\lambda)^{n_3} = (1-\lambda)^{n_1 + n_2} \cdot (1-\lambda)^{n_3} = (1-\lambda)^{n_1 + n_2 + n_3};

P(X>d) = P(X>d-1) \cdot (1-\lambda)^{n_d} = (1-\lambda)^{\sum\limits_{i=1}^{d-1}n_i} \cdot (1-\lambda)^{n_d} = (1-\lambda)^{\sum\limits_{i=1}^{d}n_i}.

So if the amount of branches n_d for each depth d stays roughly the same(n_d \approx c), P(X>d) \approx (1-\lambda)^{\sum\limits_{i=1}^{d}c} = (1-\lambda)^{cd} = [(1-\lambda)^{c}]^d, meaning that P(X>d) decays exponentially at a rate of (1-\lambda)^{c}.

P(X=d)=P(X>d-1) \cdot [1-(1-\lambda)^{n_d}] \approx [(1-\lambda)^{c}]^{d-1} \cdot [1-(1-\lambda)^{c}]. The only term relavent to d is [(1-\lambda)^{c}]^{d-1}, meaning that P(X=d) also decays exponentially at a rate of (1-\lambda)^{c}.

In real strongholds, node count pass the depth of 6 grows relatively slow but non negligable, which is why you can see in the logarithmic scaled graph that the decay is slightly even faster in higher depths.

Okay great but this is all about when the stronghold generation is entirely breadth first. Why should we believe that the actual stronghold generation is anywhere even close to this? And more importantly, what does that tell us?

Priority

Let’s say we magically know the structure of the entire stronghold tree, and it look like this(you know what I want to say):

Let d_i be the depth of node i (we define the depth of the root to be 0),
and O_i be the order that node i is chosen to branch.

For a breadth first generation process, a node cannot be chosen to branch before every node with lower depth was. To write that formally, d_i < d_j \implies O_i < O_j \implies P(O_i < O_j) = 1.
Adding on top of that, every node has an equal probability of being chosen first on the same layer, formally
d_i = d_j \implies P(O_i < O_j) = \frac{1}{2}.
Combining these two, we can get
d_i \leq d_j \implies P(O_i < O_j) \geq \frac{1}{2}.
So the sequence 123456 and 132546 are valid, but not 213456 or 124536, and every valid sequence have an equal probability of being the actual sequence.

That is not true for the actual stronghold generation process.

Above is the generation process of sequence 124356, in which d_3 < d_4 but O_3 > O_4. You can also see that the probability of this sequence occuring is \frac{1}{24}. (Every step the \color{Green}\text{green} boxed chosen node is uniformly sampled from the \color{Red}\text{red} boxed nodes, except in step 1 I did not draw the original state of which there is only a \color{Red}\text{red} boxed node 1 and I don’t want to ruin the effort of drawing such a good arrow in ms paint.)
But sequence 124536 for example, have a different probability of occuring \frac{1}{12}:

So we’ve proven d_i < d_j \nRightarrow O_i < O_j, and every valid sequence does not have an equal probability of being the actual sequence.

What about d_i = d_j \implies P(O_i < O_j) = \frac{1}{2} and d_i \leq d_j \implies P(O_i < O_j) \geq \frac{1}{2} ?

Spoiler alert: Both these two statements are true. But not d_i \leq d_j \implies E[O_i] \leq E[O_j].
Let node a be the Lowest Common Ancestor(LCA) of node i and j, P(O_i < O_j) is also only dependent on D_i = d_i - d_a and D_j = d_j - d_a, and we can compute P(O_i < O_j) for every i, j pair in O(n^2).
The proof is complicated and requires math tools that I still don’t fully understand yet, so it will be put in Chapter 3 where I go into detail for the mathematically best model. For now, we can just take that as a given.

D_i = row, D_j = column, P(O_i < O_j) = P(Bin(D_i + D_j - 1, \frac{1}{2}) \geq D_i) =

You can see in the graph that even we don’t have a sharp distinction d_i < d_j \implies O_i < O_j \implies P(O_i < O_j) = 1,
(peer-reviewed by multiple LLMs, I’m not knowledgable enough yet to fact check this)
“we still have that the mistake probability 1 - P(O_i < O_j) decreases exponentially with the distance gap due to the concentration of measure. Specifically, by Chernoff bounds, if d_i < d_j, the probability of error is bounded by \exp(-\frac{(d_j - d_i)^2}{2(d_j + d_i - 2d_a)}), showing a sharp exponential decay as d_i decreases and d_j increases.”

Or in simple terms, nodes at a lower depth are still exponentially more likely to be chosen to branch before that of a higher depth. This also backs up the statement that stronghold generation is somewhat breadth first.

1.3.3 A Full Picture

to be continued...

[Alexander51413]

Bit late to the party but I’ve had some ideas on modelling portal room depth. I’ve really enjoyed reading what you’ve written about so far - I think I agree with your description of all the stronghold generation code. Your stronghold simulator seems great for stronghold statistics and heuristic nav strategy testing - I’m jealous.

What nerd-sniped me though was calculating a closed-form expression for the distribution of portal room depth, beyond the BFS model. I have a probabilistic model that I think better approximates actual stronghold generation than BFS placement - it is probably the best I can come up with using only high-school mathematics. This exercise is a bit academic and I think has no practical/useful implications, but I couldn’t find anything elsewhere working through this so thought I’d write it up here.

Recap

Quick recap for those unclear about stronghold generation (lots of detail omitted):

Stronghold generation can be thought of as generating a tree, with the root node being the starter staircase. We know a 5-way must follow as the next node, but then after that, the generator:

1. Gets a list of all room exits
2. Randomly selects one of those exits
3. Tries to place a random^[1] room at that exit:
   a) If this fails (e.g., if the candidate room would intersect existing rooms), it removes that exit from the list
   b) If this succeeds, it adds the new room’s exits (if it has any) to the list

This whole process repeats until it has exhausted its quota for each type of room, or it cannot place any more rooms due to space constraints.

Model Description and Example

My simple model retains the random-exit-selection feature, but does not allow branching. It starts with b branches from the outset and, at every step, selects one random leaf node (i.e., a node at the end of a random branch, a terminal node) from which is generated exactly one child node (i.e., each room has only one exit, and when selected, always makes one new room). I think it decently simulates, for our purposes, tree generation processes which have an average branching factor of around 1, which I believe reflects stronghold generation behaviour for nodes at depth 6 or greater.^[2]

Below is a table that gives an example of the model initialised with b=4 branches (you could think of this as a starter 5-way with 4 exits). Each entry under the branch leaf node columns represents the depth of the leaf (terminal) node of that branch. All branches start with leaf nodes with labels of depth 0. Then, every generation step, a random branch (here, 1 in 4) is chosen to be extended by one room (this increments the column’s leaf node depth entry by 1)

1. At step 1, branch 2 is picked, and so a room of depth 1 is added to it (before the branch had maximum depth 0, now it has increased by 1)
2. At step 2, branch 1 is picked, and so a room of depth 1 is added to that branch
3. At step 3, branch 2 is picked, and so a room of depth 2 is added to that branch
4. And so on down the table…

Step count	Branch 1 leaf node depth	Branch 2 leaf node depth	Branch 3 leaf node depth	Branch 4 leaf node depth
0	0	0	0	0
1	0	1	0	0
2	1	1	0	0
3	1	2	0	0
4	1	2	1	0
5	1	2	2	0
6	1	2	2	1
7	2	2	2	1

Proof for Model’s Portal Room Depth Distribution

Everywhere below, i can be any integer from 1 to b, n\ge 0 is any natural number, and p is the chance that the room added is the portal room:

We see that the chance of the leaf node in branch i having depth 0 at step n is (1-1/b)^n, and that the chance of the leaf node in branch i having depth 1 at step n is n(1-\frac{1}{b})^{n-1} (\frac{1}{b}).

In general, the chance of the leaf node in branch i having depth x at step n is \binom{n}{x}(1-\frac{1}{b})^{n-x}(\frac{1}{b})^x - from the PMF of the binomial distribution requiring x selections of that branch, and n-x selections of any other branch, ordered in any way.

Therefore the chance that step n leads to the creation of a room of depth x is \binom{n-1}{x-1}(1-\frac{1}{b})^{n-x} (\frac{1}{b})^{x-1}, as you are requiring the branch in the previous step, n-1, to have a leaf node of depth x-1.

We also know that the chance of generating the portal room on step n is (1-p)^{n-1} p.

So, at any given step n, the chance of the portal room generating in a room of depth x is thus the above two probabilities multiplied, as they are independent events. To get the total probability the portal room generates in a room of depth x, we must then add up these probabilities for all steps n>0, which gives us:

\begin{align*} P_x&=\sum_{n=1}^\infty\binom{n-1}{x-1}\left(1-\frac{1}{b}\right)^{n-x}\left(\frac{1}{b}\right)^{x-1}\left(1-p\right)^{n-1}p\\ &=\left(1-\frac{1}{b}\right)^{-x}\left(\frac{1}{b}\right)^{x-1}\frac{p}{1-p}\sum_{n=1}^\infty\binom{n-1}{x-1}\left(\left(1-\frac{1}{b}\right)\left(1-p\right)\right)^{n}\\ &=\left(\frac{1}{b-1}\right)^{x-1}p\cdot\sum_{n=0}^\infty\binom{n}{x-1}\left(\left(1-\frac{1}{b}\right)\left(1-p\right)\right)^{n}\\ &=\left(\frac{1}{b-1}\right)^{x-1}\cdot p\cdot\frac{\left(\left(1-\frac{1}{b}\right)\left(1-p\right)\right)^{x-1}}{\left(1-\left(1-\frac{1}{b}\right)\left(1-p\right)\right)^{x}}=\frac{p\cdot\left(\frac{1-p}{b}\right)^{x-1}}{\left(1-\left(1-\frac{1}{b}\right)\left(1-p\right)\right)^{x}}\\ &=\frac{bp}{1-p}\left(\frac{1-p}{1+bp-p}\right)^{x}. \end{align*}

The sum on the third line can be evaluated straightforwardly in many ways and is related to the negative binomial distribution.

Discussion

The PMF is an exponential, a great surprise to me - the same as under the no-branching BFS model! This makes the distribution a geometric one (thankfully \sum_{x=1}^\infty P_x does indeed equal 1). Additionally if we eliminate all outcomes where the portal room would generate at depth 5 or earlier and renormalise, it still remains an exponential with the exact same PMF.

We can compare the exponential bases given by my model vs BFS - it transpires that \frac{1-p}{1+bp-p} \geq \left(1-p\right)^b for b\geq1, since (1-p+p)^b\geq(1-p)^b+b(1-p)^{b-1}p. Another interesting note is that \frac{1-p}{1+bp-p} can be written as 1/(b\cdot O-1), where O represents the odds of the portal room being picked, p/(1-p).

Now for the parameters, I guessed that b=5 and p=1/8 were reasonable values; this gave an exponent base of 7/12=0.583, which I found out was quite close to log-linear regressions ran from people’s simulation data. The regression from ClearColdWater’s data gave a base of 0.616 and R^2=0.9992; the regression from LSD Gaga’s data gave a base of 0.607 and R^2=0.9974.

Actually I checked the weights and the portal room has a 20/145=0.1379 chance of generating - but I’m guessing the actual effective chance it generates off an exit is lower as it has a big bounding box. Nonetheless, my model, using that figure, and a base of 0.616 from the regression, predicts that b=3.8917. I would be interested to see if the running list of unevaluated exits indeed hovers above a length of 4 during most of stronghold generation!

I still don’t think the model tells us much we didn’t know from the data already, but I suppose it reminds us that actually the tail of the distribution of portal room depth is quite fat (geometric distributions are quite leptokurtic) - you need to check all rooms up to depth 10 to cover 90% of portal rooms. So although the modal and mean portal room depth are 6 and 7.6 respectively, turning back at a depth of say 8 may be too aggressive.

Additionally another thought I’ve had is that memorylessness of geometric distributions means that if you have cleared out all rooms up to a certain depth, the expected additional depth you’ll need to explore will still be 7.6-5 = 2.6, the PMF’s mean. I believe the memorylessness of Bernoulli processes also means that if you have fully cleared a branch (say top-right of the starter 5-way), this should not change your heuristics/pruning aggressiveness for the remaining branches. This is all probably irrelevant if using preemptive navigation though.

A final comment is that given the relative simplicity of the PMF, I would not be surprised if it has an easier proof that I’ve missed - or if there is some nice generalisation that means we can say many related models have geometric distributions. I would also not be surprised if I’ve made any errors, please point out any if you spot them!

---

^1 All room types have weights and quotas, e.g., the portal room has a 10-20% chance to be chosen as a candidate, and a quota of 1. So after it has been successfully placed, the quota is filled, and the portal room is removed from the draw pool, forbidding any more portal rooms from being subsequently placed.

^2 Depth is how far a given node is from the root node. I mention 6 here, as portal rooms can only generate at depth 6 or greater, and at earlier depths I think the average branching factor is probably fairly high - at greater depths I would guess rooms dead-end more often, bringing the average branching factor down to closer to 1. I would love to hear if your simulation gives average branching factor data for nodes of a given depth.

The reason why I think this model is better than approximating stronghold generation than the BFS model is because, for portal room depth calculations, we only care about the sequence corresponding to the depth of each room in generation order. The previous BFS model would correspond to a sequence of something like [1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, …], whereas this model gives sequences like [1, 1, 1, 2, 1, 2, 2, 1, 2, 1, 3, 2, 3, 3, 4, 3, 4, 4, 4, …] where the numbers appear a bit shuffled. The actual sequence given by stronghold generation probably looks quite like the second, as all the additional nuances in the generation code probably don’t entail much macroscopic difference - the depth numbers are still just going to be somewhat shuffled around from the BFS sequence.

---

1. All room types have weights and quotas, e.g., the portal room has a 10-20% chance to be chosen as a candidate, and a quota of 1. So after it has been successfully placed, the quota is filled, and the portal room is removed from the draw pool, forbidding any more portal rooms from being subsequently placed. ↩︎

2. Depth is how far a given node is from the root node. I mention 6 here, as portal rooms can only generate at depth 6 or greater, and at earlier depths I think the average branching factor is probably fairly high - at greater depths I would guess rooms dead-end more often, bringing the average branching factor down to closer to 1. I would love to hear if your simulation gives average branching factor data for nodes of a given depth.

   The reason why I think this model is better than approximating stronghold generation than the BFS model is because, for portal room depth calculations, we only care about the sequence corresponding to the depth of each room in generation order. The previous BFS model would correspond to a sequence of something like [1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, …], whereas this model gives sequences like [1, 1, 1, 2, 1, 2, 2, 1, 2, 1, 3, 2, 3, 3, 4, 3, 4, 4, 4, …] where the numbers appear a bit shuffled. The actual sequence given by stronghold generation probably looks quite like the second, as all the additional nuances in the generation code probably don’t entail much macroscopic difference - the depth numbers are still just going to be somewhat shuffled around from the BFS sequence. ↩︎

[ClearColdWater]

No the party hasn’t even started yet, I had just restarted working on this project for the past few days. The simulator is basically done but I had always wanted to have the ai integrated before publishing it, and finish the logic for eyesight like in real game rather than only being able to see neighbour rooms.

However the reason why I spent so many words explaining why the random leaf selection yields a portal room probability distribution that gives exponential decay just like a pure BFS generation is not because I want to justify using a pure BFS generation based model for the ai, but rather just a sanity check to make sure that it matches what people already know.

---

What I was trying to build is a model that can take the information of every node observed in the stronghold tree, and give the mathematically best estimate of probabililty of each leaf branch being the first of all leaf branches that was selected(more accurately, had its parent selected) to generate a new room, so we can capture the difference of expected generation order of nodes even in the same depth, as shown in the ‘Priority’ part of chapter 1.3.2 .

What I had been picturing is a model that depends on generating a bunch of potential strongholds given the current observation(with no bias), which requires calculating that exact probability. But then I ran into a couple of problems, because beyond just the structure of the tree there is more information that affects the generation order, for example, I found that the presence of highly weighted limited rooms like Libraries brings down the average generation order of nearby rooms, and dead ends do the opposite. Today I even found out that even if that wasn’t a problem, calculating the integrals that was required for that probability will still be too slow.

The current sota model that is at 52 seconds average while being near sighted is not exactly bad, after being given more sight I think it should probably be at the same level as the best human player without preemptive (local_tortilla). But the more I think about it the more I feel like no part of that model is really optimized, so I became more and more demotivated to continue writing the techical details part about that model and instead put my time on developing a new generation of model.

I should briefly summerize how that model works.

It keeps track of the currently explored stronghold tree and runs an evaluation of every leaf room. An MLP was fed whether every room was visited, the raw depth of the room(was now found out not at all used by the model), 0.62226 raised to the depth of the room, the relative coordnates of each rooms’ -x-y-z corner to the starter staircase(was now found out not at all used by the model), and the probability distribution of its type(so the model can’t X-ray through the wall to see what the room is behind a hidden wall). The result of that is the initial potential vector of that room.

Then that potential vector is passed through 3 different GAT layers to make the nearby rooms on the tree pass information to each other and update their own potential vector. In each GAT layer, the normalized coordnates of each room is fed with their potential vector(was now found out not at all used by the model).

After that, all non-leaf nodes’ potential vectors are set to zero. Then the potentials of every leaf node gets recursively passed up, each non-leaf node combines its childs with a GAT(the sota technically uses a home made ‘channelwiseLpAggregator’ but that was way too dank and although it is 1 second faster on average I don’t want to waste time explaining it. It is just not the way to go)(every node uses the same GAT) and then gets passed through a GRU cell(which, before starting to work on the new model it was already suspected to be limiting performance). Such recursive aggregation runs until the potential vectors reach the players’ neighbours.

Then the aggregated potential vector of every single neighbour gets combined with a sum pooling and then concatenated with their own potential vector. That combined vector is finally passed through two seperate MLPs, both predicting the expected time for finding the portal room if the player takes that path (Double DQN). It is trained with epsilon greedy.

So this model alone will be very stuck when it cannot predict that expected time accurately. More precisely, let’s say the model starts from node A, and predicts node B as the one that has fastest expected time. Now the model moves to node B, and now it predicts node A to be the one with the fastest expected time. Such behavior that the model going back and forth happens in every other model that was trained in the stronghold trainer mod.

In order to prevent this, we notice that the optimal sequence of the player
exploring a stronghold is always directly moving from a current leaf node to the other, because the navigation is never progressed (you don’t get any useful information) unless you hit a leaf node. So what you can do is limit the model from backtracking unless a) the last step was also backtracking b) the last step was at a leaf node. This way the model will always be able to find the portal room regardless how bad its strategy is. You might think this is cheating but it is the crucial step to prevent the model from degrading by repeatedly learning from the useless data that it goes in circles.

But even if you don’t really understand what was just described here, you can probably see why I find it not very reliable from the way I am describing it. There are too many parts of the model that I cannot explain exactly how it works, and a lot that I feel like can be estimated way better with just an analytic model than an ML one. From observing how the model works with the visualization I also found that the model sometimes just crashes out when the stronghold is big, where it decides to go into libraries or randomly decide to explore a branch really deep despite there are more branches outside.

I would hopefully update on how the design on paper of how the new generation of model should work once I finalize a few more things.

---

oh two things i forgot to mention also forgive me for writing with caps while talking so aimlessly

first is that the old model was not given the input of which branch each room was branching from(so, it can’t differentiate a branch mid or top left or bottom right and stuff). i kind of hoped that the model can learn that more efficiently by seeing the relative coordnates but it apperentely cannot utilize coordnates at all(because from what i read additive attention cannot really handle directions also it can’t really do anything when its rotated) so it is stupid in that way as well

second is how the model can hopefully utilize preemptive information. currently what i know is that preeptive results should change the relavent chunks’ probability of having portal room / chests and affect the chance of each leaf branch spawning portal room with that by calculating how much more likely every leaf branch is to spawn portal rooms in those chunks. it also affects chance of dungeons / mineshafts in those chunks

[ClearColdWater]

Progress is steady, in the past few weeks i was able to pull together another stronghold generator that is able to generate strongholds efficiently given an observation with particle filtering. With the current optimizations it is able to generate a reasonable amount of strongholds (effectively 500 from rejection sampling) (using unique ancestors for effective N here) per second given a ~60 room observation on my 12400f, which should be able to cover the vast majority of strongholds with the optimal strategy.

There are still a few more optimizations in my head that I would try to implement within the next few days, but I choose to post it now because the optimization that made it step from being able to handle ~20 room observations to ~60 room observations actually worked which made me finally believe that this is actually going to work.

With this system in place, adding in preeptive information seems trivial - just estimate the likelihood of each stronghold generated matching the preemptive observation, and optimize it with taking that into account in the proposal distribution. As for how to estimate the likelihood of each stronghold generated matching the preemptive observation… thats a problem for future me.

(It is noteworthy that the strongholds it is producing are not strongholds that you can generate with a structure seed within the game, otherwise there might only be 1 seed that satisfies the observation given enough rooms observed, bringing the goal of it to just seed cracking. But obviously seed cracking your stronghold does not give you any insight about dealing with another stronghold, nor do you have enough computational resources to run a seed cracking program in your brain. What this program does is it takes some sampling magic and generate strongholds with effectively the same random process while speeding it up far far beyond what you can do with just repeatedly guessing a stronghold and checking if it meets the observation.)

[ClearColdWater]

↑ Now open source on github:

GitHub - ClearColdWater/SMC-Stronghold-Generator: Generates imaginary minecraft strongholds that...

ok i admit the data that was given yesterday was a bit optimistic because all the tests i’ve done is on seed 42 which turned out to be really friendly for the sampler

also you need to build it yourself someone can make a CLI for it if they want or/and integrate it into their tool

[ClearColdWater]

A CLI was released and a report of some insights from the results it generated should be coming later today (out now, link)

The more I look into it the more I feel there is really limited ways I can improve the sampling, and they all require massive code changes and I need a break before working on this for another month.

That said I’m really glad how this turned out, the original ML model does very poorly in terms of evaluating each branch. Something I’ve been thinking about is, out of 100 marks of making a stronghold nav AI, 40 is for evaluating leaf nodes and 60 is for the agent policy, the original model gets something like a 20/40 for the former and 40/60 for the latter. But I know in my heart that I’m not satisfied with either of those, now with this generator I would say it is able to score at least 35/40 for evaluating leaf nodes, the 5 points for not being effective enough for really bad strongholds but still for the ones that it is effective enough it is the best possible solution that no machine learning model can reach with any amount of training.

What really interests me in this project is that it provides endless things to learn and math problems to solve and I really enjoy that.

[Shardzzz]

you said that there arent any constraints other than being 50 rooms deep or 112 away from the staring staircase. but for some reason i see that many times it stops before 112, it could even generate a whole portal room which is 16 width and still fit within the 112 blocks away requirement and still have 4 more blocks left over. is this because of the repeating. i didnt understand you explaination with the min min coords, do you mean that it chooses 2,2 or does it choose the closest to 0,0 of the box of the starting staircase?

[ClearColdWater]

I’m sorry I didn’t really understand the first question

• Verbally what you are saying is that many strongholds stops generating before they even hit that constraint, and that is because, well, just because there is a constraint to be hit doesn’t mean that all strongholds have to hit it. There are 2 reasons that a strongholds halts its generation completely,
  • It has expanded all of its leaf nodes, but they never spawned more children (whether it is because of the 50 rooms limit, 112 blocks away from starter limit, collision with existing pieces, repeatedly choosing the piece that was last placed, or a combination between the last two), either way the stronghold has no leaf piece it can expand next so it finishes generating.
  • It has placed all of the interesting pieces that has a limit as to how many they can be spawned in a stronghold. In which case, all further generation is stopped, a new room generation process starts and immediately hits this limit and fail, as a result old leaves are getting out of the queue but no new leaves join the queue, in the end the stronghold has no leaf piece it can expand next so it finishes generating.
  • Having a room that is 50 rooms deep or 112 blocks away from starter does not trigger the effect of all interesting pieces being placed if that’s what you’re asking.
• But technically it can actually generate pass 50 rooms and 112 blocks from starter (I noticed this watching the k4 & bolan stream), because that is the check for the parent room of the new piece to be generated and not the room itself. So technically you can get rooms up to 51 deep, or something around up to 123(?) blocks away from starter.

As for the second question

• You know that a bounding box has format [minX -> maxX, minY -> maxY, minZ -> maxZ] ? That is just how you can describe a rectangle’s shape and position in a predefined space.
• So The starter stairs has minX = 2, minZ = 2 as its chunk coordinates, which means the rest of it is on the +X, +Z direction of that position (because if there is any part of it on the -X direction of it for example, then it means the minX coordinate of that part must be smaller than 2, contradicting the fact that position has minX).