AI for Magic Tower (Part IV)

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来解决单层塔问题。

在这篇博客里,我将对更多细节进行介绍。

多层塔(低层塔)

对于多层塔(低层塔),其实和单层塔区别并不大,唯一有区别的就是多了个楼梯,因此寻路算法需要有一定改变。

我们需要对于每一层,记录下上楼梯和下楼梯的位置信息。然后在判断连通性时,如果两个节点在不同的楼层,实际就是判断楼上的节点到下楼梯的位置,和楼下的节点到上楼梯的位置是否同时连通,即可。

[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
// 多层塔的判断连通性
private boolean isLinked(int f1, int x1, int y1, int f2, int x2, int y2) {
    // 保证f1>=f2
    if (f1<f2) return isLinked(f2,x2,y2,f1,x1,y1);
    if (f1!=f2)
        // (f1,x1,y1)到f1楼层的下楼梯位置
        // 和(f2,x2,y2)到f1-1楼层的上楼梯位置需要同时连通
        return isLinked(f1,x1,y1,f1,stair[f1][2],stair[f1][3])
            && isLinked(f1-1,stair[f1-1][0],stair[f1-1][1],f2,x2,y2);
   
    if (x1==x2 && y1==y2) return true;
    boolean[][] visited=new boolean[row][col];
    visited[x1][y1]=true;
    // 标准BFS
    Queue<Integer> queue=new LinkedList<>();
    queue.offer(x1); queue.offer(y1);
    while (!queue.isEmpty()) {
        int x=queue.poll(), y=queue.poll();
        for (int[] dir: new int[][] {{-1,0},{0,1},{1,0},{0,-1}}) {
            int nx=x+dir[0], ny=y+dir[1];
            if (nx<0 || nx>=row || ny<0 || ny>=col) continue;
            if (nx==x2 && ny==y2) return true;
            if (visited[nx][ny] || (map[f1][nx][ny]!=ROAD &&
                    map[f1][nx][ny]!=UPSTAIR && map[f1][nx][ny]!=DOWNSTAIR))
                continue;
            visited[nx][ny]=true;
            queue.offer(nx); queue.offer(ny);
        }
    }
    return false;
}

除此以外,基本没有任何变化。

特殊道具:破墙镐、炸药

遗憾地说,对于破墙镐(消耗道具:可以破开一堵墙)和炸药(消耗道具:可以无伤炸死一个怪物)并没有一个很好的解决方案。

但是,我们可以采用如下办法:

对于破墙镐,其实际上可以看成是绿钥匙,而所有的墙壁都是绿门。当然我们不可能所有的墙壁都去破一破,因此首先需要对于具体的塔具体分析,觉得哪些点可能是破点,然后把所有的破点全部改成绿门。

对于炸药,其实际上可以看成是紫钥匙。由于我们不可能所有的怪物都炸,因此我们需要对于具体的塔具体分析,哪些怪物是可能炸的;然后选择炸药数目的怪物,将怪物改成紫门即可。如果有X种怪物是可能炸的,炸药有Y个,那么实际上我们有C(X,Y)种可能改成紫门,对于小数目直接每个都尝试一遍即可。

对于特殊道具,中心对称飞行器,很遗憾的表示,是完全无法处理的。中心对称飞的存在会改变整张图的拓扑结构,使得AI的计算变得不可行。

吸血怪物

对于吸血怪物(怪物会按照你的当前生命值等比例进行吸血);就要涉及到“留血瓶”之类的操作,而这个是不被我们的算法所兼容的。(我们的算法中,只要出现宝物就必直接获取)

那么,如果我们实际上要处理吸血怪物,我们只能,将所有血瓶全部变成固定的负伤怪物(也就是宝物节点变成消耗节点);而且,建图还不能进行节点合并操作。

这样虽然可以处理吸血怪物,但会让消耗节点数量进一步增加,使得计算复杂度进一步升高。

但其并不适用于夹击怪;夹击怪会改变通路状态,进而改变整张图的结构,导致AI的计算变得不可行。

地图生成器&可视化程序

当我们实现AI后,我们更多地是需要将其投入实战,使用它。

为此,我写了两个辅助程序;一个是地图生成器,一个是可视化程序。

地图生成器(参见https://github.com/ckcz123/magic-tower-AI/tree/master/map_generator),基于C#所写,它可以从剪切板或文件中读取图片,进行图片比较并自动生成地图文件。有关此地图生成器的更多说明参见github上的ReadMe。

可视化程序(参见https://github.com/ckcz123/magic-tower-AI/tree/master/program),使用C++,基于hge库所写,它可以读取地图信息,并打印出来。

如对于这座单层塔:

使用地图生成器将其录入地图后,再用可视化程序读出来:

同时左上角会显示勇士当前的坐标,可以根据AI的输出,在此可视化程序中找寻其算出来的路线。

地图生成器可以大大减少录入地图的时间;而可视化程序对于AI的结果分析十分有帮助。

对于它们的更多信息,可以参见github上的描述。

AI使用方法

对于一个实际的塔,按照如下流程来处理就好了:

  1. 制定终止条件(比如以打败哪个怪物,还是碰到什么NPC作为终止?),修改State中的shouldStop函数。
  2. 使用地图生成器录入地图。在录入地图的过程中,可以对原地图进行适当的修改,例如将绝对不能打的怪物以及绝对不会开的门标上墙。这样可以大大减少状态数。同时,像一个黄钥匙紧挨着一个必开黄门这种,可以将它们都删掉,也可以大大减少状态数。
  3. 使用可视化程序确认录入的地图无误。
  4. 使用AI建图,检查消耗节点个数。一般消耗节点数不要超过50,否则十分难以计算。
  5. 使用AI计算最佳路径MAX。如果状态数太多无法计算,回到2并重新设置地图(手动剪枝)。
  6. 在可视化程序中检查一遍MAX路线是否可行。
  7. 在原塔中实际解决问题。

 

 

大家可以关注我的开源项目https://github.com/ckcz123/magic-tower-AI/,star或fork一下,感谢支持~

如果您有什么意见建议,或者比较好的想法的话,欢迎邮件至ckcz123@126.comckcz12345@gmail.com与我联系,也可以在魔塔吧官方交流QQ群里搜索“小艾”联系到我。期待对于AI,有与您的进一步交流~