从这篇博客开始,我们将对单层塔的算法进行分析。本分析主要是基于【高等魔塔学】对魔塔结构的初步理论分析 这篇帖子,阅读本文前请先阅读此帖。
建图
要写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,有与您的进一步交流~