‘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.