在Screeps游戲中肴甸，尋路是最基本、最重要也最需要細(xì)致優(yōu)化的事情。
在前期游戲中你可能會(huì)遇到兩個(gè)Creep在對(duì)向?qū)ぢ窌r(shí)崩侠，一個(gè)Creep會(huì)繞著另一個(gè)Creep移動(dòng)，這樣的事情看起來(lái)并不是很完美坷檩。
然而在Screep中却音，游戲是允許兩個(gè)Creep相互“對(duì)穿”移動(dòng)的，正如開(kāi)頭GIF中你看到的那樣矢炼。
那么我們?nèi)绾胃脤?shí)現(xiàn)這樣的移動(dòng)系瓢，原理又是如何的呢？
首先你要注意以下幾件事情
- 避免單獨(dú)或依賴(lài)使用自帶的尋路
- 重新定義物流/移動(dòng)全局邏輯
實(shí)現(xiàn)簡(jiǎn)單對(duì)穿
找來(lái)兩只creep句灌，讓他們緊靠夷陋，一個(gè)在左一個(gè)在右
//在控制臺(tái)
let t1 = Game.creeps.t1;//在左邊的creep
let t2 = Game.creeps.t2;//在右邊的creep
t1.move(LEFT);
t2.move(RIGHT);
這樣兩個(gè)creep就相互對(duì)穿了。
在繼續(xù)講解對(duì)穿之前你需要知道幾個(gè)基本原理邏輯胰锌，這里不再剖析源代碼骗绕，我直接告訴你結(jié)果和過(guò)程。
首先你需要了解幾個(gè)概念
納入計(jì)劃
在Screeps的文檔中找到Creep的move方法返回值列表中资昧，對(duì)返回值
OK的描述是這個(gè)操作已經(jīng)成功納入計(jì)劃酬土。但您要記得，納入計(jì)劃并不代表creep本tick結(jié)束時(shí)一定會(huì)移動(dòng)到那里格带，如果遇到預(yù)定沖突撤缴，被調(diào)用的creep可能是不會(huì)移動(dòng)的。
預(yù)定
預(yù)定叽唱，creep在移動(dòng)到一個(gè)坐標(biāo)前會(huì)嘗試去預(yù)定這個(gè)坐標(biāo)屈呕，預(yù)定成功后，這個(gè)位置就是下一個(gè)tick該creep的位置尔觉，且永遠(yuǎn)不會(huì)被其他creep搶占凉袱，如果預(yù)定失敗，那么該creep會(huì)預(yù)定原來(lái)自己的位置，下一tick也就在原來(lái)的位置专甩。
預(yù)定沖突
當(dāng)一個(gè)creep的move在被納入計(jì)劃后钟鸵，即將被預(yù)定的位置上卻有了其他creep的位置預(yù)定，那么這個(gè)creep的位置預(yù)定將會(huì)在它原來(lái)的位置涤躲。也就是說(shuō)棺耍，誰(shuí)先預(yù)定一個(gè)位置，誰(shuí)就能移動(dòng)到那個(gè)位置种樱。
基本移動(dòng)規(guī)律：
- 調(diào)用api后蒙袍，這個(gè)移動(dòng)會(huì)被納入計(jì)劃表(也叫做intent)
- 代碼的先后調(diào)用順序不能完全決定Creep在預(yù)定時(shí)遇到?jīng)_突的優(yōu)先權(quán)
- Creep在預(yù)定時(shí)會(huì)進(jìn)行遞歸，遞歸判斷對(duì)自己預(yù)定有直接或間接影響的Creep嫩挤，從而判斷自己的預(yù)定
- 每個(gè)Creep在預(yù)定位置后害幅，它將不再有其他的位置改變
具體流程如下(我用js寫(xiě)流程方便大家理解)：
let intent = (...);//拿到本tick的計(jì)劃表，這個(gè)表存放了這個(gè)tick所有的creep.move調(diào)用每個(gè)數(shù)據(jù)包括creep和direction岂昭，表中的每一個(gè)數(shù)據(jù)一旦取出(pop)就會(huì)消失以现，直到取完
let perPos = (...);//預(yù)定二維數(shù)組，每個(gè)數(shù)據(jù)包含了兩個(gè)數(shù)據(jù)约啊，pos和creep分別表示被預(yù)定了的位置和預(yù)定這個(gè)位置的creep
function reserve(creep){
//從計(jì)劃表中取出數(shù)據(jù)邑遏，這個(gè)操作會(huì)讓計(jì)劃表中該數(shù)據(jù)無(wú)法再次pop，既消失
let data = intent.popByCreep(creep);
//從data中獲取要移動(dòng)的方向
let direction = data.direction
//根據(jù)direction獲取將要移動(dòng)到的坐標(biāo)
let nextPos = getPos(creep.pos,direction);
//判斷這個(gè)坐標(biāo)是否能夠前往恰矩，如果是地圖邊緣或者不能踩creep的建筑就直接預(yù)定失敗
if(!isTouchable(nextPos)){
//只能預(yù)定自己原來(lái)的位置
perPos.set(creep.pos,creep);
return false;//返回預(yù)定失敗
}
//查詢(xún)這個(gè)位置上有沒(méi)有其他的預(yù)定
if(perPos.exist(nextPos)){
//如果有记盒，只能待在原地，預(yù)定自己原來(lái)的位置
perPos.set(creep.pos,creep);
return false;//返回預(yù)定失敗
}
//如果沒(méi)有其他的預(yù)定
//獲取要移動(dòng)到的位置上的Creep外傅，注意纪吮，是獲取本tick地圖上某個(gè)位置的creep，并不是預(yù)定移動(dòng)后的creep
//并且也無(wú)法獲取到此次迭代中的上級(jí)creep
let nextCreep = getCreep(nextPos);
if(!nextCreep){//如果那個(gè)位置上沒(méi)有creep
//直接預(yù)定
perPos.set(nextPos,creep);
return true;//返回預(yù)定成功
}else{//如果那個(gè)位置上有creep
//判斷nextCreep是否已經(jīng)成功預(yù)定了其他位置栏豺，且這個(gè)位置不是要移動(dòng)的creep的nextPos
if(perPos.exist(nextCreep)
&& perPos.getPos(nextCreep) != nextPos){
//無(wú)法移動(dòng)彬碱，因?yàn)檫@個(gè)creep已經(jīng)有了預(yù)定且它預(yù)定的位置就是它原來(lái)的位置，要移動(dòng)的creep不能移動(dòng)到它的頭上
perPos.set(creep.pos,creep);
return false;//返回預(yù)定失敗
}
//判斷該nextCreep該tick是否有移動(dòng)計(jì)劃
if(!intent.exist(nextCreep)){//如果nextCreep沒(méi)有移動(dòng)計(jì)劃
//則要移動(dòng)的creep無(wú)法移動(dòng)只能預(yù)定原來(lái)自己的位置
perPos.set(creep.pos,creep);
return false;//返回預(yù)定失敗
}else{//如果nextCreep有移動(dòng)的計(jì)劃
if(reserve(nextCreep)){//遞歸處理這個(gè)creep
//如果nextCreep預(yù)定成功了奥洼，要移動(dòng)的creep也能成功預(yù)定，因?yàn)槟莻€(gè)位置已經(jīng)被騰出來(lái)了
perPos.set(nextPos,creep);
return true;//返回預(yù)定成功
}else{//如果nextCreep沒(méi)能成功預(yù)定
//要移動(dòng)的creep只能待在原地
perPos.set(creep.pos,creep);
return false;//返回預(yù)定失敗
}
}
}
}
//判斷計(jì)劃表是否為空來(lái)循環(huán)
while(!intent.isEmpty()){
//越早調(diào)用api的creep越先進(jìn)入遞歸
reserve(intent.popEarliest().creep);
}
//通過(guò)預(yù)定數(shù)組晚胡，更新下一個(gè)tick的creep位置
updateGame(perPos);
注：上面的流程模型并不是最終模型灵奖，這個(gè)模型并沒(méi)有得到源代碼的印證和官方的認(rèn)可，僅限于直白的了解移動(dòng)機(jī)制估盘。
為了檢查你是否能意會(huì)這些概念瓷患，我們做一個(gè)情境練習(xí)。
這是一個(gè)線(xiàn)性坐標(biāo)上Creep的分布
| POS | 1 | 2 | 3 |
|---|---|---|---|
| Creep | t1 | t2 | t3 |
t1.move(RIGHT);
t2.move(LEFT);
t3.move(LEFT);
當(dāng)執(zhí)行上面的代碼時(shí)遣妥，creep的移動(dòng)情況如何擅编？
答案是
| POS | 1 | 2 | 3 |
|---|---|---|---|
| Creep | t2 | t1 | t3 |
這個(gè)過(guò)程是這樣的
因?yàn)槭莟1最早進(jìn)行的調(diào)用，所以遞歸從t1開(kāi)始
t1預(yù)定位置2時(shí)發(fā)現(xiàn)上面有個(gè)t2，于是便進(jìn)入遞歸對(duì)t2進(jìn)行預(yù)定爱态，結(jié)果在計(jì)劃中發(fā)現(xiàn)t2是向位置1移動(dòng)谭贪，而位置1沒(méi)有被預(yù)定，所以t2預(yù)定了位置1
| POS | 1 | 2 | 3 |
|---|---|---|---|
| Creep | t1 | t3 | |
| PER | t2 |
因?yàn)閠2的成功預(yù)定锦担，所以t1也能夠預(yù)定到它想去的位置---位置2俭识，并結(jié)束了遞歸
| POS | 1 | 2 | 3 |
|---|---|---|---|
| Creep | t3 | ||
| PER | t2 | t1 |
此時(shí)t1和t2都預(yù)定完成了，計(jì)劃表中還剩t3洞渔，所以讓t3開(kāi)始遞歸
t3想預(yù)定位置2套媚，發(fā)現(xiàn)位置2已經(jīng)被t1預(yù)定了 ,此時(shí)發(fā)生了預(yù)定沖突，所以t3只能預(yù)定自己原來(lái)的位置即位置3
| POS | 1 | 2 | 3 |
|---|---|---|---|
| Creep | |||
| PER | t2 | t1 | t3 |
所以在下一個(gè)tick時(shí)磁椒，三個(gè)creep的位置就是
| POS | 1 | 2 | 3 |
|---|---|---|---|
| Creep | t2 | t1 | t3 |
還是同樣的情況
| POS | 1 | 2 | 3 |
|---|---|---|---|
| Creep | t1 | t2 | t3 |
那接下來(lái)這段代碼呢
t3.move(LEFT);
t2.move(LEFT);
t1.move(RIGHT);
結(jié)果是
| POS | 1 | 2 | 3 |
|---|---|---|---|
| Creep | t2 | t1 | t3 |
再來(lái)進(jìn)行一次分析堤瘤，這次遞歸會(huì)有點(diǎn)深度
首先還是對(duì)最先調(diào)用api的t3進(jìn)行遞歸
t3想預(yù)定位置2，發(fā)現(xiàn)位置2上有t2浆熔，于是對(duì)t2進(jìn)行遞歸
t2想預(yù)定位置1本辐，發(fā)現(xiàn)位置1上有t1，于是對(duì)t1進(jìn)行遞歸
t1想預(yù)定位置2蘸拔，但雖然位置2上有t2师郑，但t2是t1的上級(jí)遞歸，所以按照流程t1是看不見(jiàn)它的调窍。t1就認(rèn)為位置2上沒(méi)有其他creep宝冕，且沒(méi)有其他預(yù)定，所以t1成功預(yù)定了位置2
| POS | 1 | 2 | 3 |
|---|---|---|---|
| Creep | t2 | t3 | |
| PER | t1 |
因?yàn)閠1的預(yù)定成功邓萨，所以t2也能預(yù)定成功地梨，所以t2預(yù)定到了位置1
這里就解釋了為什么creep能完成對(duì)穿
| POS | 1 | 2 | 3 |
|---|---|---|---|
| Creep | t3 | ||
| PER | t2 | t1 |
由于t2的預(yù)定成功，所以t3本來(lái)也該預(yù)定成功缔恳，但t3想預(yù)定位置2時(shí)發(fā)現(xiàn)位置2已經(jīng)被t1預(yù)定了宝剖，發(fā)生了預(yù)定沖突，所以t3只能預(yù)定自己原來(lái)的位置
| POS | 1 | 2 | 3 |
|---|---|---|---|
| Creep | |||
| PER | t2 | t1 | t3 |
所以在下一個(gè)tick時(shí)歉甚，三個(gè)creep的位置就是
| POS | 1 | 2 | 3 |
|---|---|---|---|
| Creep | t2 | t1 | t3 |
經(jīng)過(guò)多次在sim中的驗(yàn)證万细，以上的流程邏輯是能夠得到正確的結(jié)果的。你可以把它作為參考來(lái)定制和優(yōu)化你的Creep移動(dòng)/物流邏輯纸泄。
