魔塔小游戏中的AI(二)

从这篇博客开始,我们将对单层塔的算法进行分析。本分析主要是基于【高等魔塔学】对魔塔结构的初步理论分析 这篇帖子,阅读本文前请先阅读此帖。

建图

要写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. 如果都是消耗节点,且其中某个节点相连的其他所有节点,不是两两相连,则不合并。

下面逐一进行分析:

(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.comckcz12345@gmail.com与我联系,也可以在魔塔吧官方交流QQ群里搜索“小艾”联系到我。期待对于AI,有与您的进一步交流~