魔塔为什么不能用 BFS 求最优
魔塔（Magic Tower）是一款典型的”资源管理型 RPG 地牢”：上楼需要钥匙，打赢怪物需要足够的攻击/防御/血量，而三者都由金币和道具驱动。它有一个非常反直觉的性质——先打哪个怪会永久改变你的能力曲线。
用 BFS 逐层探索看似可行，但 BFS 只优化”移动步数”，而魔塔真正的最优目标是”通关所需总代价最小“（通常是最少血量消耗，或者最少金币）。同一个格子在不同资源状态下价值完全不同，所以状态必须包含：
state = (楼层, 位置, 血量, 攻击, 防御, 金币, 钥匙×3色, 已击败怪物集合, 已拾取道具集合)
这个状态空间的规模是天文数字。BFS/DFS 在这种”资源耦合”问题上必然爆炸，正确的框架是分支限界（Branch and Bound，B&B）：用可采纳的（admissible）上界函数一次性砍掉整棵子树。
核心工具一：战斗结算的闭式公式
魔塔的战斗是纯数值对抗，不需要模拟每一回合。设我方攻击 A、防御 D、血量 H，怪物攻击 ma、防御 md、血量 mh：
我方每回合伤害 = max(1, A - md)
击杀所需回合数 = ceil(mh / (A - md))
怪物每回合伤害 = max(0, ma - D)
战斗总损血 = (回合数 - 1) × max(0, ma - D)
减 1 是因为我方先手，最后击杀的那回合怪物无法反击。这个闭式公式把”一次战斗”从模拟循环降成 O(1)，是整篇算法能跑起来的前提。
public final class Combat {
/** 返回战斗损失血量；若我方无法获胜返回 -1 */
public static long bloodLoss(long atk, long def, long hp, Monster m) {
long dmg = atk - m.def;
if (dmg <= 0) return -1; // 打不动
long turns = (m.hp + dmg - 1) / dmg; // ceil
long taken = Math.max(0, m.atk - def);
long loss = (turns - 1) * taken;
return loss >= hp ? -1 : loss; // 损血超过现有血量则打不过
}
}
注意 m.hp 与 dmg 都要用 long：后期魔塔数值常破亿，int 会静默溢出导致”以为是必胜，结果打不过”。
核心工具二：可采纳上界（admissible bound）
分支限界的效率完全取决于上界函数的质量。上界必须满足：bound(s) ≤ trueCost(s)，绝不能高估，否则会把最优解剪掉。
魔塔的上界可以从三个互相独立的角度构造，取最大值（更紧）：
上界 A：剩余楼层的最小血量消耗下界
对每一层 f 到顶层，剩余必须击败的怪物集合中，每个怪物的”在当前能力下的最小损血”求和，就是该层下界。防御提升能降低这个值，所以更紧的下界要考虑”用剩余金币最多能买到多少防御”：
/**
* 上界A：假设所有剩余金币立刻换成防御（最理想情况），
* 计算剩余怪物造成的总损血下界。
*/
static long boundByCombat(State s, Map<Integer, List<Monster>> remaining, long defPrice) {
long maxBuyableDef = s.gold / defPrice; // 金币全买防御
long bestDef = s.def + maxBuyableDef;
long total = 0;
for (int f = s.floor; f <= TOP_FLOOR; f++) {
for (Monster m : remaining.getOrDefault(f, List.of())) {
long loss = Combat.bloodLoss(s.atk, bestDef, Long.MAX_VALUE, m);
if (loss < 0) return Long.MAX_VALUE; // 攻击不足，此路不通
total += loss;
if (total >= s.hp) return Long.MAX_VALUE; // 必然死亡
}
}
return total;
}
上界 B：钥匙与门的必经数量下界
每一层的门所需钥匙数是个硬约束。允许”跨层共享”钥匙是过松的，但可以按层递推：
need[f] = 该层必须开的门所需钥匙数
boundKey = Σ_f max(0, need[f] - 到第 f 层时可获得钥匙数)
上界 C：道具增益的乐观估算
每个尚未拾取的道具在”最理想时机”拾取，其增益上界为：
boundItem = Σ_{未拾取道具 p} value(p) 用最大值替换当前能力
三者取 max(A, B, C)：只要有一个能证明”这条路达不到当前最优”，就剪枝。
核心工具三：状态压缩与置换表
魔塔的状态里，”已击败怪物集合””已拾取道具集合”都属于位集合。把它们压成位图后可以用 Zobrist 哈希做置换表，把”同资源状态走到同一格”的重复搜索解掉。
public final class StateCodec {
/** 把 (位置, 资源, 两个位集合) 压成 64 位指纹 */
public static long hash(int floor, int y, int x, long hp, long atk, long def,
long gold, int[] keys, long monsterMask, long itemMask,
long[][] key) {
long h = key[0][floor * 64 + y * 8 + x];
h ^= key[1][(int) (atk % 64)] ^ key[2][(int) (def % 64)];
h ^= key[3][(int) (hp & 63)] ^ key[4][(int) (gold & 63)];
h ^= key[5][keys[0]] ^ key[6][keys[1]] ^ key[7][keys[2]];
// 位集合用逐位异或，保证增量更新 O(1)
for (long m = monsterMask; m != 0; m &= m - 1) h ^= key[8][Long.numberOfTrailingZeros(m)];
for (long m = itemMask; m != 0; m &= m - 1) h ^= key[9][Long.numberOfTrailingZeros(m)];
return h;
}
}
置换表按”资源向量支配”判定：若 s1.hp ≥ s2.hp 且 atk/def/gold/keys 全部不劣，且位集合相同，则 s2 完全劣于 s1，可直接丢弃。这比单纯哈希去重更强。
主循环：深度优先 + 上界剪枝
public final class MagicTowerSolver {
private long bestCost = Long.MAX_VALUE; // 当前最优通关血量消耗
private final Map<Long, State> transTable = new HashMap<>();
private final Deque<int[]> bestPath = new ArrayDeque<>();
public void search(State s) {
if (s.floor > TOP_FLOOR) { // 到达顶层：更新最优
if (s.cost < bestCost) { bestCost = s.cost; recordPath(s); }
return;
}
// ---- 剪枝 1：上界 vs 当前最优 ----
long bound = Math.max(Math.max(
boundByCombat(s, remaining, defPrice),
boundByKeys(s)), boundByItems(s));
if (s.cost + bound >= bestCost) return;
// ---- 剪枝 2：置换表支配 ----
long code = StateCodec.hash(s.floor, s.y, s.x, s.hp, s.atk, s.def,
s.gold, s.keys, s.monsterMask, s.itemMask, zob);
State old = transTable.get(code);
if (old != null && old.dominates(s)) return;
transTable.put(code, s.copy());
// ---- 扩展：移动 / 战斗 / 拾取 / 用钥匙 ----
for (Action a : successors(s)) {
State next = apply(s, a);
next.cost = s.cost + costOf(a); // 例如战斗损血或钥匙消耗
if (next.hp > 0) search(next);
}
// ---- 回溯：恢复状态 ----
undo(s);
}
}
successors 的扩展顺序也很关键：先扩展”必走的无偿动作”（纯移动、拾取金币、开必经门），再扩展战斗——这样上界函数会更早生效。
一个具体的剪枝例子
假设当前最优 bestCost = 120，你正处在第 8 层，血量 500。
- 剩余怪物（8~10 层）在当前能力下总损血下界 = 260；
- 未拾取道具的乐观增益上界折算血量 = 80；
- 现有
cost = 30。
则 30 + 260 = 290 > 120，整棵子树直接剪掉。注意这个下界是”金币全买防御”的理想情况，实际只会更差，所以必然安全。
完整项目结构
magic-tower-bb/
├── pom.xml
└── src/main/java/com/daily/algorithm/magictower/
├── Monster.java // 怪物属性表
├── Combat.java // 闭式战斗公式
├── State.java // 资源状态 + 支配判定
├── StateCodec.java // 位集合 + Zobrist 指纹
├── Bounds.java // 三种可采纳上界
├── MagicTowerSolver.java // B&B 主循环
└── Main.java // 内置示例地图
复杂度与实测
- 无剪枝的朴素 DFS：分支因子约 4（四方向），深度可达
3 层 × 40 步，状态数不可估； - 加上界 A：实测在 10 层小地图上把节点数从 10^7 降到 10^4 量级；
- 加置换表支配：再降一个数量级，典型 10 层关卡 200ms 内出最优解；
- 上界函数本身：
O(剩余怪物数 + 剩余道具数)，对状态数不产生指数影响。
三代剪枝的贡献是乘法关系：上界让搜索树变窄，置换表让重复路径消失，闭式战斗公式让单个节点变便宜。三者叠加才有可用的性能。
小结
魔塔是”资源耦合型搜索”的教科书案例：单纯的最短路算法在这里完全失效，因为路径长度不等于代价。正确做法是把战斗闭式化，把”已击败/已拾取”压成位集，再用三种互相独立的上界（战斗损血、钥匙缺口、道具增益）取最大值做分支限界。这套思路同样适用于 RPG 自动战斗规划、资源采集路线优化、以及任何”状态含多个耦合资源”的搜索问题。
