脚本宝典收集整理的这篇文章主要介绍了华容道游戏（下），脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
此为《算法的乐趣》读书笔记，我用javascript（ES6）重新实现算法。
华容道游戏看似简单，但求解需要设计的数据结构比较复杂，还牵涉到棋类游戏的棋局判断，所以整个过程还是挺费劲的。我尽量用面向对象的思想来进行封装，整个过程将分成几个部分记录下来，今天是最后一部分，棋局的广度搜索。
广度搜索
棋局的搜索空间是一个树状关系空间，广度优先搜索能够首先找到最优解，因为首先找到的解深度是最浅的。
游戏定义
我们对算法的要求是：给定一个华容道游戏的开局布局，可以得到这个开局的所有解决方法以及相应的武将移动步骤，要求算法具有能用性，能处理任何一种开局的华容道游戏。
class hrdGame{
constructor(caoIdx, heroes){
this.caoIdx = caoIdx; //曹操在武将列表中的序号
VAR startstate = new HrdGameState(); //新建开局棋局
startState.inITState(heroes) //开局棋局初始化
this.states = [] //存储所有棋局状态，广度搜索的状态空间
this.zhash = {} //棋局及其镜像哈希，判重空间
this.result = 0; //解的总数
addNewStatePattern(this,startState) //开局处理，相当于游戏初始化
}
}游戏的求解过程就是棋局的搜索过程，每移动一个棋子就会生成一个新的棋局，对每一个棋局我们都要生成其所有的后续棋局。结束条件：在生成每一个新棋局时，判断是否为解，是则该状态终止；另一方面，每一个棋局若其后续棋局数为空，也自动终止。
解的判定
function isEscaPEd(game, gameState){ //曹操的位置到达（1，3）
return (gameState.heroes[game.caoIdx -1].left == CAO_ESCAPE_LEFT) && (gameState.heroes[game.caoIdx - 1].top == CAO_ESCAPE_TOP)
}棋局搜索
function resolveGame(game) //广度搜索主函数
{
let index = 0;
while(index < game.states.length){
gameState = game.states[index]; //依次选定棋局状态
if(isEscaped(game, gameState)){ //找到解，输出
game.result++;
console.LOG('result:'+game.result+' step--'+gameState.step+' index:'+index)
}
else{
seArchNewGameStates(game, gameState); //选定棋局搜索所有新棋局
}
index++;
}
return (game.result > 0);
}搜索新棋局
武将移动产生新棋局。
function searchNewGameStates(game, gameState) //搜索新棋局
{
for(let i = 0; i < gameState.heroes.length; i++) //遍历武将
{
for(let j = 0; j < MAX_MOVE_DIRECTION; j++) //遍历所有方向
{
trySearchHeroNewState(game, gameState, i, j); //移动武将产生新棋局
}
}
}新棋局生成
根据华容道规则，对一个武将棋子连续移动只算一步，因此在每一步移动成功后，需要继续对该棋子尝试移动，但是移动的方向有限制，不能向原方向移动。
function trySearchHeroNewState(game, gameState, heROIdx, dirIdx)
{
let newState = moveHeroToNewState(gameState, heroIdx, dirIdx); //新棋局产生
if(newState) {
if(addNewStatePattern(game, newState)) //处理新棋局，判重，添加到状态链中
{
/*尝试连续移动，根据华容道游戏规则，连续的移动也只算一步*/
tryHeroContinueMove(game, newState, heroIdx, dirIdx);
return;
}
}
}移动武将
function moveHeroToNewState(gameState, heroIdx, dirIdx)
{
if(canHeromove(gameState, heroIdx, dirIdx)) //能够移动
{
var newState = new HrdGameState(); //新建棋局
if(newState)
{
copyGameState(gameState, newState); //用父棋局初始化新棋局
var hero = newState.heroes[heroIdx]; //取得武将
const dir = DIRECTION[dirIdx]; //取得方向
clearPosition(newState, hero.type, hero.left, hero.top); //清除父棋局信息
takePosition(newState, heroIdx, hero.type, hero.left + dir[0], hero.top + dir[1]); //新棋局数据生成
hero.left = hero.left + dir[0]; //武将新位置设定
hero.top = hero.top + dir[1];
newState.step = gameState.step + 1; //移动步数加一
newState.parent = gameState; //形成因果链
newState.move.heroIdx = heroIdx; //记录移动方法
newState.move.dirIdx = dirIdx;
return newState; //返回新棋局
}
}
return null;
}处理棋局
function addNewStatePattern(game, gameState)
{
var l2rHash = getZobristHash(zobHash, gameState); //计算棋局哈希值
if(!game.zhash[l2rHash]) //棋局不存在
{
game.zhash[l2rHash] = l2rHash; //棋局哈希存储
var r2lHash = getMirrorZobristHash(zobHash, gameState);
game.zhash[r2lHash] = r2lHash; //棋局镜像哈希存储
game.states.push(gameState); //棋局存储
return true;
}
return false; //棋局已经存在，忽略
}开局及解
横刀立马
定义：
var hs =[new Warrior(WARRIOR_TYPE.HT_vbAR,0,0),
new Warrior(WARRIOR_TYPE.HT_BOX,1,0),
new Warrior(WARRIOR_TYPE.HT_VBAR,3,0),
new Warrior(WARRIOR_TYPE.HT_VBAR,0,2),
new Warrior(WARRIOR_TYPE.HT_HBAR,1,2),
new Warrior(WARRIOR_TYPE.HT_VBAR,3,2),
new Warrior(WARRIOR_TYPE.HT_BLOCK,0,4),
new Warrior(WARRIOR_TYPE.HT_BLOCK,1,3),
new Warrior(WARRIOR_TYPE.HT_BLOCK,2,3),
new Warrior(WARRIOR_TYPE.HT_BLOCK,3,4)
]四个解：
result:1 step--81 index:11930
result:2 step--85 index:12123
result:3 step--98 index:12337
result:4 step--101 index:12348指挥若定
定义：
var hs = [new Warrior(WARRIOR_TYPE.HT_VBAR,0,0), //构建武将列表，初始棋局
new Warrior(WARRIOR_TYPE.HT_BOX,1,0),
new Warrior(WARRIOR_TYPE.HT_VBAR,3,0),
new Warrior(WARRIOR_TYPE.HT_BLOCK,0,2),
new Warrior(WARRIOR_TYPE.HT_HBAR,1,2),
new Warrior(WARRIOR_TYPE.HT_BLOCK,3,2),
new Warrior(WARRIOR_TYPE.HT_VBAR,0,3),
new Warrior(WARRIOR_TYPE.HT_BLOCK,1,3),
new Warrior(WARRIOR_TYPE.HT_BLOCK,2,3),
new Warrior(WARRIOR_TYPE.HT_VBAR,3,3)
]四个解：
result:1 step--73 index:11391
result:2 step--84 index:12207
result:3 step--86 index:12263
result:4 step--89 index:12306兵分三路
定义：
var hs = [new Warrior(WARRIOR_TYPE.HT_BLOCK,0,0), //构建武将列表，初始棋局
new Warrior(WARRIOR_TYPE.HT_BOX,1,0),
new Warrior(WARRIOR_TYPE.HT_BLOCK,3,0),
new Warrior(WARRIOR_TYPE.HT_VBAR,0,1),
new Warrior(WARRIOR_TYPE.HT_HBAR,1,2),
new Warrior(WARRIOR_TYPE.HT_VBAR,3,1),
new Warrior(WARRIOR_TYPE.HT_VBAR,0,3),
new Warrior(WARRIOR_TYPE.HT_BLOCK,1,3),
new Warrior(WARRIOR_TYPE.HT_BLOCK,2,3),
new Warrior(WARRIOR_TYPE.HT_VBAR,3,3)
]四个解：
result:1 step--74 index:7767
result:2 step--80 index:9212
result:3 step--94 index:10921
result:4 step--97 index:11157完整代码
文中是主要代码分析，完整代码托管在开源中国，其中的hyd.js即华容道解法。
https://gitee.COM/zhoutk/test小结
终于完成了，其中遇到一个坑，就是zobrist的空间问题，《算法的乐趣》书中是说用32位整数，但其提供的源码是左移15位，我觉得也应该够，就用了15位整数。结果搜索不到解，各种调试、跟踪，感觉哪哪都是对的，曹操就是下不来，郁闷一晚。突然想到会不会是zobrist空间太小，若空间太小，新的棋局会与旧棋局冲突，这样应该会导致很多状态被忽略。清晨起床一试，爽！
以上是脚本宝典为你收集整理的华容道游戏（下）全部内容，希望文章能够帮你解决华容道游戏（下）所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。