在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移动/物流逻辑。
网友评论