Creep移动原理和对穿的应用 - Screep技术

在Screeps游戏中，寻路是最基本、最重要也最需要细致优化的事情。

在前期游戏中你可能会遇到两个Creep在对向寻路时，一个Creep会绕着另一个Creep移动，这样的事情看起来并不是很完美。

然而在Screep中，游戏是允许两个Creep相互“对穿”移动的，正如开头GIF中你看到的那样。

那么我们如何更好实现这样的移动，原理又是如何的呢？

首先你要注意以下几件事情

• 避免单独或依赖使用自带的寻路
• 重新定义物流/移动全局逻辑

---

实现简单对穿

找来两只creep，让他们紧靠，一个在左一个在右

//在控制台
let t1 = Game.creeps.t1;//在左边的creep
let t2 = Game.creeps.t2;//在右边的creep

t1.move(LEFT);
t2.move(RIGHT);

这样两个creep就相互对穿了。

在继续讲解对穿之前你需要知道几个基本原理逻辑，这里不再剖析源代码，我直接告诉你结果和过程。

首先你需要了解几个概念

纳入计划

在Screeps的文档中找到Creep的move方法返回值列表中，对返回值OK的描述是这个操作已经成功纳入计划。但您要记得，纳入计划并不代表creep本tick结束时一定会移动到那里，如果遇到预定冲突，被调用的creep可能是不会移动的。

预定

预定，creep在移动到一个坐标前会尝试去预定这个坐标，预定成功后，这个位置就是下一个tick该creep的位置，且永远不会被其他creep抢占，如果预定失败，那么该creep会预定原来自己的位置，下一tick也就在原来的位置。

预定冲突

当一个creep的move在被纳入计划后，即将被预定的位置上却有了其他creep的位置预定，那么这个creep的位置预定将会在它原来的位置。也就是说，谁先预定一个位置，谁就能移动到那个位置。

---

基本移动规律：

• 调用api后，这个移动会被纳入计划表(也叫做intent)
• 代码的先后调用顺序不能完全决定Creep在预定时遇到冲突的优先权
• Creep在预定时会进行递归，递归判断对自己预定有直接或间接影响的Creep，从而判断自己的预定
• 每个Creep在预定位置后，它将不再有其他的位置改变

具体流程如下(我用js写流程方便大家理解)：

let intent = (...);//拿到本tick的计划表，这个表存放了这个tick所有的creep.move调用每个数据包括creep和direction，表中的每一个数据一旦取出(pop)就会消失，直到取完
let perPos = (...);//预定二维数组，每个数据包含了两个数据，pos和creep分别表示被预定了的位置和预定这个位置的creep

function reserve(creep){
  //从计划表中取出数据，这个操作会让计划表中该数据无法再次pop，既消失
  let data = intent.popByCreep(creep);

  //从data中获取要移动的方向
  let direction = data.direction

  //根据direction获取将要移动到的坐标
  let nextPos = getPos(creep.pos,direction);

  //判断这个坐标是否能够前往，如果是地图边缘或者不能踩creep的建筑就直接预定失败
  if(!isTouchable(nextPos)){
    //只能预定自己原来的位置
    perPos.set(creep.pos,creep);
    return false;//返回预定失败
  }

  //查询这个位置上有没有其他的预定
  if(perPos.exist(nextPos)){
    //如果有，只能待在原地，预定自己原来的位置
    perPos.set(creep.pos,creep);
    return false;//返回预定失败
  }
  //如果没有其他的预定

  //获取要移动到的位置上的Creep，注意，是获取本tick地图上某个位置的creep，并不是预定移动后的creep
  //并且也无法获取到此次迭代中的上级creep
  let nextCreep = getCreep(nextPos);

  if(!nextCreep){//如果那个位置上没有creep
    //直接预定
    perPos.set(nextPos,creep);
    return true;//返回预定成功
  }else{//如果那个位置上有creep
    //判断nextCreep是否已经成功预定了其他位置，且这个位置不是要移动的creep的nextPos
    if(perPos.exist(nextCreep)
    && perPos.getPos(nextCreep) != nextPos){
      //无法移动，因为这个creep已经有了预定且它预定的位置就是它原来的位置，要移动的creep不能移动到它的头上
      perPos.set(creep.pos,creep);
      return false;//返回预定失败
    }

    //判断该nextCreep该tick是否有移动计划
    if(!intent.exist(nextCreep)){//如果nextCreep没有移动计划
      //则要移动的creep无法移动只能预定原来自己的位置
      perPos.set(creep.pos,creep);
      return false;//返回预定失败
    }else{//如果nextCreep有移动的计划
        if(reserve(nextCreep)){//递归处理这个creep
          //如果nextCreep预定成功了，要移动的creep也能成功预定，因为那个位置已经被腾出来了
          perPos.set(nextPos,creep);
          return true;//返回预定成功
        }else{//如果nextCreep没能成功预定
          //要移动的creep只能待在原地
          perPos.set(creep.pos,creep);
          return false;//返回预定失败
        }
    }
  }
}

//判断计划表是否为空来循环
while(!intent.isEmpty()){
  //越早调用api的creep越先进入递归
  reserve(intent.popEarliest().creep);
}

//通过预定数组，更新下一个tick的creep位置
updateGame(perPos);

注：上面的流程模型并不是最终模型，这个模型并没有得到源代码的印证和官方的认可，仅限于直白的了解移动机制。

为了检查你是否能意会这些概念，我们做一个情境练习。

这是一个线性坐标上Creep的分布

POS	1	2	3
Creep	t1	t2	t3

t1.move(RIGHT);
t2.move(LEFT);
t3.move(LEFT);

当执行上面的代码时，creep的移动情况如何？

答案是

POS	1	2	3
Creep	t2	t1	t3

这个过程是这样的

因为是t1最早进行的调用，所以递归从t1开始

t1预定位置2时发现上面有个t2，于是便进入递归对t2进行预定，结果在计划中发现t2是向位置1移动，而位置1没有被预定，所以t2预定了位置1

POS	1	2	3
Creep	t1		t3
PER	t2

因为t2的成功预定，所以t1也能够预定到它想去的位置---位置2，并结束了递归

POS	1	2	3
Creep			t3
PER	t2	t1

此时t1和t2都预定完成了，计划表中还剩t3，所以让t3开始递归
t3想预定位置2，发现位置2已经被t1预定了 ,此时发生了预定冲突，所以t3只能预定自己原来的位置即位置3

POS	1	2	3
Creep
PER	t2	t1	t3

所以在下一个tick时，三个creep的位置就是

POS	1	2	3
Creep	t2	t1	t3

---

还是同样的情况

POS	1	2	3
Creep	t1	t2	t3

那接下来这段代码呢

t3.move(LEFT);
t2.move(LEFT);
t1.move(RIGHT);

结果是

POS	1	2	3
Creep	t2	t1	t3

再来进行一次分析，这次递归会有点深度
首先还是对最先调用api的t3进行递归

t3想预定位置2，发现位置2上有t2，于是对t2进行递归

t2想预定位置1，发现位置1上有t1，于是对t1进行递归

t1想预定位置2，但虽然位置2上有t2，但t2是t1的上级递归，所以按照流程t1是看不见它的。t1就认为位置2上没有其他creep，且没有其他预定，所以t1成功预定了位置2

POS	1	2	3
Creep		t2	t3
PER		t1

因为t1的预定成功，所以t2也能预定成功，所以t2预定到了位置1

这里就解释了为什么creep能完成对穿

POS	1	2	3
Creep			t3
PER	t2	t1

由于t2的预定成功，所以t3本来也该预定成功，但t3想预定位置2时发现位置2已经被t1预定了，发生了预定冲突，所以t3只能预定自己原来的位置

POS	1	2	3
Creep
PER	t2	t1	t3

所以在下一个tick时，三个creep的位置就是

POS	1	2	3
Creep	t2	t1	t3

经过多次在sim中的验证，以上的流程逻辑是能够得到正确的结果的。你可以把它作为参考来定制和优化你的Creep移动/物流逻辑。