Sorry, this entry is only available in 中文. For the sake of viewer convenience, the content is shown below in the alternative language. You may click the link to switch the active language.
从这篇博客开始，我们将对单层塔的算法进行分析。本分析主要是基于【高等魔塔学】对魔塔结构的初步理论分析 这篇帖子，阅读本文前请先阅读此帖。
建图
要写AI，我们遇到的第一个问题就是：如何建图？所谓建图，就是将整个地图的拓扑关系描述出来，以方便下面具体的搜索过程。
以如下最简单的单层塔为例：
首先，我们将所有非门、非路的点（宝石、门、怪物）都设置为一个节点，并使用广度优先搜索，将每两个相邻的节点连接起来。
在上图中，绿色节点是门，红色节点是怪物，蓝色节点是宝物，紫色节点是BOSS。黑色是连通路径。
因此我们可以如下定义节点类。
| [java] | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | // 节点类的定义 public class Node { // 节点的ID，节点的类型 int id, type; // 节点坐标 int f,x,y; // 当前各种属性 Hero hero=null; Item item=null; ArrayList<Integer> doors; ArrayList<Monster> monsters; // 邻接表记录所有相邻节点 HashSet<Node> linked; } |
注意上述定义中，门和怪物我们使用的都是List而不是单个对象来记录，其原因在后面会给出说明。
定义节点类后，我们就可以遍历地图，对于每个非路非墙的节点，初始化一个Node，记录节点坐标，并加入到一个List中；然后遍历List，对于List中任意两个节点，通过BFS来判断这两点之间是否仅由路进行连通，如果是则加入到邻接表中进行记录。
| [java] | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | public void addLinks(List<Node> list) { // 建图 int len=list.size(); for (int i=0;i<len;i++) { for (int j=i+1;j<len;j++) { Node n1=list.get(i), n2=list.get(j); // BFS判断两点在地图上是否通过路径相连 if (isLinked(n1.f, n1.x, n1.y, n2.f, n2.x, n2.y)) { n1.addNode(n2); n2.addNode(n1); } } } } |
合并节点
在建图完后，我们需要进行合并节点的操作，从而减少节点的数量以方便后面的搜索。为了更好地理解合并节点的意义，我们还是以此图为例：
我们可以看到，右上角两个黄门是两个节点，但是事实上它们是等价于一个“消耗两个钥匙的”大黄门。这是因为，如果我开了一个黄门，我就必须要去开第二个，不然是没有理由去开它的。
同样的道理也适用于左上角两个史莱姆王，如果我打了一个，就必须要去打第二个，不然是没有理由去打它的。同样，右下角的一个红史莱姆和一个怪王也是可以合并的。
事实上，除了怪物和怪物合并，门与门合并以外，怪物和门也是可以合并的，例如左下的黑色史莱姆和黄门，也是可以进行合并的。
那么现在问题是：两个节点可以合并的条件是什么？
我们可以总结出如下要点：
- 如果这两个节点不相连，则不合并。
- 如果这两个节点都是宝物节点，则直接合并。
- 如果一个是宝物节点，另一个是消耗节点，则不合并。
- 如果都是消耗节点，且存在第三个节点同时和这两个节点相连，则不合并。
- 如果都是消耗节点，且其中某个节点相连的其他所有节点，不是两两相连，则不合并。
下面逐一进行分析：
(1)(2)(3) 都是很显然的。
(4) 也很显然，如果存在第三个节点同时和这两个消耗节点相连，那么打死一个怪物后，完全可以前往第三个节点（拾取宝物等），从而这两个节点并不能进行合并。
(5) 这个就不那么显然了，事实上在这里让我错了不少次。这个条件存在的意义，是保证其中某个节点的存在不是为了“挡路”。还是以上面的那个图为例，我们看中间的黑色史莱姆和其右下的那个黄门。这两个节点是完全满足前三个条件的，但是这两个节点并不能合并，这是因为黑色史莱姆实际上是挡住了勇士往下的通路。因此我们需要加上这样一个条件，以确保节点存在的意义只是为了和另一个节点相连。
上述合并条件可以用如下代码进行表述：
| [java] | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | // 两个节点是否应该合并？ private boolean shouldMerge(Node n1, Node n2) { // 不相邻，不合并 if (!n1.linked.contains(n2) || !n2.linked.contains(n1)) return false; // 同为宝物节点，直接合并 if (n1.item!=null && n2.item!=null) return true; // 一个是宝物，另一个不是宝物节点 if (n1.item!=null || n2.item!=null) return false; // BOSS节点，不合并 if (n1.type==BOSS_INDEX || n2.type==BOSS_INDEX) return false; // 存在第三个节点同时和这两个节点相邻，不合并 for (Node node: n2.linked) if (n1.linked.contains(node)) return false; // 如果存在某个节点相邻的其他节点不是两两相邻 for (Node u: new Node[] {n1, n2}) { Node v=u==n1?n2:n1; for (Node x: u.linked) { for (Node y: u.linked) { if (x.equals(y) || x.equals(v) || y.equals(v)) continue; if (!x.linked.contains(y)) return false; } } } return true; } |
知道什么情况下合并节点后，接下来就可以正式进行合并了。
首先对于List中任意两个节点，判断是否应该合并，如果应该，则将后者合并到前者，然后为了避免冲突，从List中删除后者，再重新进行遍历。
| [java] | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | private void mergeNode(List<Node> list) { for (int i=1;i<list.size();i++) { Node n1=list.get(i); for (int j=i+1;j<list.size();j++) { Node n2=list.get(j); if (shouldMerge(n1, n2)) { n1.merge(n2); list.remove(j); mergeNode(list); return; } } } } |
而实际的合并过程则非常简单。
| [java] | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | public void merge(Node another) { // 合并宝物 if (item!=null) item.merge(another.item); // 合并门 doors.addAll(another.doors); // 合并怪物 monsters.addAll(another.monsters); // 合并邻接表节点 for (Node to: another.linked) { if (!to.equals(this)) { linked.add(to); to.addNode(this); } to.linked.remove(another); } } |
这也是为什么在Node的定义中，我们使用List来进行记录了。
经过上述建图以及合并节点后，我们就成功把整个魔塔的地图使用邻接表给描述出来。
还是以此地图为例：
建图并合并后，我们可以输出所有的节点：
| [text] | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | (0,0,5) -- Hero: (470,9,4,0,0,0,0) -- 2 Linked Id=1: (0,0,1) -- Items: atk+1;yellow+1; -- 1 Linked Id=2: (0,0,7) -- Doors: [1, 1] -- Monsters: [(101,50,7,3,0)] -- 3 Linked Id=3: (0,1,2) -- Monsters: [(104,80,10,5,0), (104,80,10,5,0)] -- 4 Linked Id=4: (0,1,5) -- Items: yellow+1; -- 5 Linked Id=5: (0,1,9) -- Items: hp+275;atk+1; -- 1 Linked Id=6: (0,3,1) -- Items: hp+75;atk+1;yellow+1; -- 1 Linked Id=7: (0,3,5) -- Monsters: [(102,70,11,1,0)] -- 5 Linked Id=8: (0,4,6) -- Monsters: [(103,45,5,5,2)] -- 6 Linked Id=9: (0,4,10) -- Items: hp+75;def+1; -- 2 Linked Id=10: (0,5,3) -- Monsters: [(105,100,17,2,0)] -- 4 Linked Id=11: (0,5,7) -- Doors: [1] -- 3 Linked Id=12: (0,5,9) -- Monsters: [(103,45,5,5,2)] -- 2 Linked Id=13: (0,6,5) -- Monsters: [(101,50,7,3,0)] -- 5 Linked Id=14: (0,7,0) -- Items: hp+200;def+1; -- 1 Linked Id=15: (0,7,3) -- Doors: [1] -- Monsters: [(103,45,5,5,2)] -- 3 Linked Id=16: (0,7,7) -- Items: hp+75; -- 1 Linked Id=17: (0,7,10) -- Monsters: [(102,70,11,1,0), (104,80,10,5,0)] -- 2 Linked Id=18: (0,8,2) -- Items: def+1;yellow+2; -- 2 Linked Id=19: (0,9,1) -- Monsters: [(104,80,10,5,0)] -- 2 Linked Id=20: (0,9,5) -- Monsters: [(105,100,17,2,0)] -- 3 Linked Id=21: (0,10,5) -- Monsters: [(199,50,20,12,0)] -- 1 Linked Id=22: (0,10,7) -- Items: atk+1;def+1; -- 1 Linked 13/23 nodes in total. |
其中ID=0的节点为活跃节点，有关活跃节点的定义可参见下一篇博客。
我们注意到，(0,0,1)实际上合并了一个攻击宝石和一个黄钥匙；(0,0,7)实际上合并了两个黄门和一个绿色史莱姆的怪物，等等。
这实际上确实说明了合并节点是有效的，可以大幅减少图中节点数目。
注意，将节点合并确实是可以进行很大的剪枝，但是可能会导致，存在商店的情况下（第五篇博客进行了讨论）结果不是最优的。因为可能合并的某些怪物之后需要打掉以赚金币值。所以，对于带有商店的图，可以不对节点进行合并。
下一步，就是实际对这个图进行具体的搜索计算了。在下一篇博客里，将具体对于AI的算法进行描述。
大家可以关注我的开源项目https://github.com/ckcz123/magic-tower-AI/，star或fork一下，感谢支持~
如果您有什么意见建议，或者比较好的想法的话，欢迎邮件至ckcz123@126.com或ckcz12345@gmail.com与我联系，也可以在魔塔吧官方交流QQ群里搜索“小艾”联系到我。期待对于AI，有与您的进一步交流~