魔塔小游戏中的AI(四)

在上面几篇博客中,详细介绍了如何去实现一个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,有与您的进一步交流~