双人贪吃蛇@botzone算法设计_botzone贪吃蛇

单人贪吃蛇游戏的一般算法思路是进行前向预测，寻找空间最大的可能走法。
双人对战中，对方的走法不确定，必须加以预测。此外，还可以堵截对方的权值。
为了实现以上目的，需要对于己方蛇体、对方蛇体、地图障碍物进行建模。建立局面对象包含全部信息，每移动一个回合递归复制局面对象，以某种规则预测对手行为进行更新。

需要传递的数据有：
- 地图信息（本游戏中为静态，故传全局指针单一对象）
- 对方蛇所在位置
- 我方蛇所在位置
- 蛇历史运动数据*

可以供决策的技术指标：
1. 近步成杀。即按照这一走法，己方不死，对方无论怎么走都会死。该情况属于硬性胜利条件，只要存在即实施，无须再看其他指标。
2. 自己不死的自由度大小，对方可假设为路径贪心：适用于敌人的模型，假设对手(我)为不动，选取可行步数最长的方向
3. 连通性分析寻找关键通道，力求将对方包围在尽量小的封闭区域内。应用最短路径算法，对于每个方格假设按最短路径到达，则令对方到达各方格最曲折甚至不能到达的就是最优路径。
有一点需要注意，即不同的路径有不同的长度，我们在评价最优的时候需要排除单纯由于走的路线长占据的格点多而使得对方无路可走。这种“最优”是被动的，因为会轻易被对方的移动所搅乱，故不具有实用性。解决方法是将评价函数S设置为：
S=SUM(1/(1+对方的可行方格数的步数))+自身步数/6

然后取MAXS-S最大的前几个方案，按照初始方向累加，返回最大的方向和对应权值。
其中MAXS是S的最大值，超过此值就没意义了不合格。
4. 贴近对方，并且自己能逃脱

---

搜索最短路径使用dijistra算法，使用小顶堆寻找未放入连通子图的最近的顶点。
从堆顶取出顶点时，关心的是其值和坐标；
在更新顶点的值的时候，需要修改指定坐标顶点的值，然后修正堆(也可以删除指定顶点，修改值后重新插入)。需要通过坐标索引小顶堆的位置；
于是，我们需要一个数据结构具有双向指向功能

为了加快移动速度，节省空间，小顶堆中存储的都是指针

typedef struct _Block
{
    int val;  //地图中的距离
    int index;  //堆中的索引值
    //int xy=x*MAX_MAP+y;  //地图中的坐标 直接用数组索引值替代了
}Block;
Block *heap[MAX_MAP*MAX_MAP];
1
2
3
4
5
6
7

小顶堆的精髓在于，使用数组顺序存储时，若以1作为堆顶索引号，则任意一个节点i，父节点索引为i/2，左子节点索引为2*i

添加节点时从数组尾部，不断比较大小上浮即可

for(i = ++Size; Elements[i/2]>X; i/=2)
        Elements[i]=H->Elements[i/2 ];  
 Elements[i]=X;
1
2
3

移除堆顶时，也是同样的策略从上到下将小元素逐个上浮。有一个特殊情况需要处理：设堆最后一个元素是L，在推进到倒数第二层时，可能使得最后一层的某个孩子被换上去而产生一个洞。为了保持堆的结构，必须把最后一个元素运过去补上，此时如果L比那个孩子小的话就不能保证堆序的性质了。例如：

   []       4       3     ______\      6        4       3   ______\     6      4      3  
 6    6   7   7   4   4   ______/    6    []  7   7  4   4  ______/   6   4  7   7  4   [] 
1
2

解决方法是每一级判断子元素是否大于最后一个元素，如果大于，则应该直接把最后一个元素移动上来，然后终止向下过程返回。

MinElement=Elements[1];
LastElement=Elements[Size--];

for(i=1;i*2<=Size;i=Child)
{
        /* Find smaller child */
    Child =i*2;
    if(Child!=Size && Elements[Child+1] <Elements[Child])
            Child++;
        /* Percolate one level */
    if(LastElement>Elements[Child])
        Elements[i]=Elements[Child];
    else
        break;
    }
    Elements[i]=LastElement;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

最短路径算法中，频繁出现的是对于堆中元素的修改操作，相应的调整堆算法如下:

void ChangeAt(int index)
if(Elements[i]<Elements[i/2])
{
    //改小了，应该上浮
    for(ChangedElement=Elements[i]; ChangedElement<Elements[i/2]; i/=2)
        Elements[i]=Elements[i/2];  
     Elements[i]=ChangedElement;
}else if(i*2>size)
{   
    return;  //下面没东西 不用改
}
else if(Elements[i]>
    (   Size==i*2 ? 
        Elements[i*2]
        :
        MIN(Elements[i*2],Elements[i*2+1])
    )  )
{
    //改大了，应该下沉
    for(ChangedElement=Elements[i]; i*2<=Size;i=Child)
    {
        /* Find smaller child */
        Child =i*2;
        if(Child!=Size && Elements[Child+1] <Elements[Child])
                Child++;
        /* Percolate one level */
        if(ChangedElement > Elements[Child])
        {
            Elements[i]=Elements[Child];
        }else
        {
            break;
        }
    }
    Elements[i]=ChangedElement;
}
else
{
    //没改多少，不用修正
    return;
}
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
33
34
35
36
37
38
39
40
41

以上算法均为针对常规数值，本程序中需要改写为指针数据进行访问，且每次数据移动都需要增加相应修改index的步骤。例如，insert()中

        for(i = ++heap_size; heap[i/2]->val > x->val; i/=2)
        {
             heap[i]=heap[i/2];
             heap[i]->index=i;

        }
        heap[i]=x;
        heap[i]->index=i;
1
2
3
4
5
6
7
8

代码见 https://github.com/merfii/DoubleSnakeAI