华容道游戏（上）
此为《算法的乐趣》读书笔记，我用javascript（ES6）重新实现算法。
华容道游戏看似简单，但求解需要设计的数据结构比较复杂，还牵涉到棋类游戏的棋局判断，所以整个过程还是挺费劲的。我尽量用面向对象的思想来进行封装，整个过程将分成几个部分记录下来，今天是第一部分，数据结构的定义与初始化。
华容道游戏介绍
华容道游戏据说来源于三国故事“诸葛亮智算华容，关云长义释曹操”。在一个5×4的棋盘上布置多名蜀国大将和军士作为棋子，将曹操围困在中间，通过滑动各个棋子，帮助曹操移动到出口位置逃走。
算法原理
华容道的数学原理尚未研究清楚，还没有数学方法可以一劳永逸的解决它，因此我们只能用计算机来穷举所有的可能解，并找出最优解。
代码及思路
棋局包括棋盘的状态和棋子的状态两部分，我们是要用计算机来演化和搜索棋局。对于一个棋局，如果有一种或多种移动武将的方法，这个棋局就可以演化成一个或多个新的棋局，每个新棋局又可以根据移动武将的方式演化成更多的棋局。
常量定义
const MAX_WARRIOR_TYPE = 5; //格子被武将占据的状态，空或武将序号，1+4const HRD_GAME_ROW = 5; //棋盘实际行数const HRD_GAME_COL = 4; //棋盘实际列数const HRD_BOARD_WIDTH = 6; //棋盘定义宽度const HRD_BOARD_HEIGHT = 7; //棋盘定义高度const BOARD_CELL_EMPTY = 0; //格子空置代码const BOARD_CELL_BORDER = -1; //哨兵代码const DIRECTION = [ [0, -1], [1, 0], [0, 1], [-1, 0] ] //移动方向定义移动操作定义
class MoveAction{ constructor(heroIdx, dirIdx){ this.heroIdx = heroIdx || 0 //武将序号 this.dirIdx = dirIdx || 0 //移动方向 }}武将类型定义
const WARRIOR_TYPE = { HT_BLOCK : 1, //1x1 HT_VBAR : 2, //1x2 HT_HBAR : 3, //2x1 HT_BOX : 4 //2x2}武将定义
class Warrior { constructor(type, left, top){ this.type = type this.left = left this.top = top }}棋局对象定义
二维数组表示棋盘（7×6），扩大了一圈，在外围设置了“哨兵”；棋盘上各点为零表示空，数字代表武将的序号。
class HrdGameState { constructor(){ this.board = [] //棋盘 for(let i = 0; i<HRD_BOARD_HEIGHT; i++){ //棋盘初始化，放置哨兵 this.board.push([]) for(let j=0; j<HRD_BOARD_WIDTH; j++){ this.board[i].push([]) if(i==0 || j==0 || i==HRD_BOARD_HEIGHT-1 || j==HRD_BOARD_WIDTH-1){ this.board[i][j] = BOARD_CELL_BORDER }else{ this.board[i][j] = BOARD_CELL_EMPTY } } } this.parent = null; //演化树上的“父亲” this.step = 0; //演化计数 this.move = new MoveAction() //演化方式（武将移动方式） this.heroes = [] //武将列表 } initState(heroes){ //武将列表初始化 for(let i = 0; i < heroes.length; i++) { if(!addGameStateHero(this, i, heroes[i])) //将武将放置到棋盘上 { return false; } } return true; }}武将放置函数
function addGameStateHero(gameState, heroIdx, hero){ if(isPositionAvailable(gameState, hero.type, hero.left, hero.top)) //检测给定位置是否能放置该武将 { takePosition(gameState, heroIdx, hero.type, hero.left, hero.top); //放置武将到棋盘上 gameState.heroes.push(hero); //将武将存入列表中 return true; } return false;}检测能否放置武将函数
function isPositionAvailable(gameState, type, left, top){ let isOK = false; switch(type) { case WARRIOR_TYPE.HT_BLOCK: isOK = (gameState.board[top + 1][left + 1] == BOARD_CELL_EMPTY); break; case WARRIOR_TYPE.HT_VBAR: isOK = (gameState.board[top + 1][left + 1] == BOARD_CELL_EMPTY) && (gameState.board[top + 2][left + 1] == BOARD_CELL_EMPTY); break; case WARRIOR_TYPE.HT_HBAR: isOK = (gameState.board[top + 1][left + 1] == BOARD_CELL_EMPTY) && (gameState.board[top + 1][left + 2] == BOARD_CELL_EMPTY); break; case WARRIOR_TYPE.HT_BOX: isOK = (gameState.board[top + 1][left + 1] == BOARD_CELL_EMPTY) && (gameState.board[top + 1][left + 2] == BOARD_CELL_EMPTY) && (gameState.board[top + 2][left + 1] == BOARD_CELL_EMPTY) && (gameState.board[top + 2][left + 2] == BOARD_CELL_EMPTY); break; default: isOK = false; break; } return isOK;}放置武将函数
function takePosition(gameState, heroIdx, type, left, top){ switch(type) { case WARRIOR_TYPE.HT_BLOCK: gameState.board[top + 1][left + 1] = heroIdx + 1; break; case WARRIOR_TYPE.HT_VBAR: gameState.board[top + 1][left + 1] = heroIdx + 1; gameState.board[top + 2][left + 1] = heroIdx + 1; break; case WARRIOR_TYPE.HT_HBAR: gameState.board[top + 1][left + 1] = heroIdx + 1; gameState.board[top + 1][left + 2] = heroIdx + 1; break; case WARRIOR_TYPE.HT_BOX: gameState.board[top + 1][left + 1] = heroIdx + 1; gameState.board[top + 1][left + 2] = heroIdx + 1; gameState.board[top + 2][left + 1] = heroIdx + 1; gameState.board[top + 2][left + 2] = heroIdx + 1; break; default: break; }}棋局对象测试
测试代码
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)]var gameState = new HrdGameState() //新建棋局对象gameState.initState(hs) //初始化棋局，往空棋盘上摆开局console.dir(gameState.board) //输出棋局测试结果
结果符合预期
[ [ -1, -1, -1, -1, -1, -1 ], [ -1, 1, 2, 2, 3, -1 ], [ -1, 1, 2, 2, 3, -1 ], [ -1, 4, 5, 5, 6, -1 ], [ -1, 4, 8, 9, 6, -1 ], [ -1, 7, 0, 0, 10, -1 ], [ -1, -1, -1, -1, -1, -1 ] ]完整代码
代码托管在开源中国，其中的hyd.js即华容道解法。
https://git.oschina.net/zhoutk/test.git小结
尽量使用面向对象的思想来解决问题，让数据和操作绑定在一起，努力使代码容易看懂。
赞 (0)