摘要:华容道游戏看似简单,但求解需要设计的数据结构比较复杂,还牵涉到棋类游戏的棋局判断,所以整个过程还是挺费劲的。华容道游戏介绍华容道游戏据说来源于三国故事诸葛亮智算华容,关云长义释曹操。
此为《算法的乐趣》读书笔记,我用javascript(ES6)重新实现算法。
华容道游戏看似简单,但求解需要设计的数据结构比较复杂,还牵涉到棋类游戏的棋局判断,所以整个过程还是挺费劲的。我尽量用面向对象的思想来进行封装,整个过程将分成几个部分记录下来,今天是第一部分,数据结构的定义与初始化。华容道游戏介绍
华容道游戏据说来源于三国故事“诸葛亮智算华容,关云长义释曹操”。在一个5×4的棋盘上布置多名蜀国大将和军士作为棋子,将曹操围困在中间,通过滑动各个棋子,帮助曹操移动到出口位置逃走。
算法原理华容道的数学原理尚未研究清楚,还没有数学方法可以一劳永逸的解决它,因此我们只能用计算机来穷举所有的可能解,并找出最优解。
代码及思路棋局包括棋盘的状态和棋子的状态两部分,我们是要用计算机来演化和搜索棋局。对于一个棋局,如果有一种或多种移动武将的方法,这个棋局就可以演化成一个或多个新的棋局,每个新棋局又可以根据移动武将的方式演化成更多的棋局。
常量定义const MAX_WARRIOR_TYPE = 5; //格子被武将占据的状态,空或武将序号,1+4 const 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武将放置函数 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://gitee.com/zhoutk/test小结尽量使用面向对象的思想来解决问题,让数据和操作绑定在一起,努力使代码容易看懂。
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/79346.html
摘要:华容道游戏看似简单,但求解需要设计的数据结构比较复杂,还牵涉到棋类游戏的棋局判断,所以整个过程还是挺费劲的。 此为《算法的乐趣》读书笔记,我用javascript(ES6)重新实现算法。 华容道游戏看似简单,但求解需要设计的数据结构比较复杂,还牵涉到棋类游戏的棋局判断,所以整个过程还是挺费劲的。我尽量用面向对象的思想来进行封装,整个过程将分成几个部分记录下来,今天是最后一部分,棋局的广...
摘要:还在上班很无聊数字华容道畅玩地址开发源码地址这个叫前言年末了。光随机生成一个乱序数列是不够的,还得保证这个数列的逆序数为偶数,嗦嘎。所以,我们直接将交换的次数,记为数列逆序数个数,就达到了想要的效果。 还在上班?很无聊?数字华容道畅玩地址 开发源码地址 这个叫前言 年末了。哦,不,要过年了。以前只能一路站到公司的我,今早居然是坐着过来的。新的一年,总要学一个新东西来迎接新的未来吧,所以...
摘要:不难理解,近两年云计算技术如风暴一般席卷了世界的每一个角落,游戏市场自然也不会例外。同样不难猜测,收购与云服务器也成为沃尔玛进入这部分市场的惯用筹码,电商对云技术应用的把控成为他们想要进一步挑战游戏的动力所在。不久前,谷歌在今年举行的游戏开发者大会上宣布了自家的云游戏服务平台:Stadia,随后亚马逊也表示自己正在搭建云游戏服务,甚至连零售业巨头沃尔玛都表示计划启动自己的云游戏平台,大佬们的...
阅读 549·2023-04-25 16:00
阅读 1567·2019-08-26 13:54
阅读 2454·2019-08-26 13:47
阅读 3306·2019-08-26 13:39
阅读 1017·2019-08-26 13:37
阅读 2717·2019-08-26 10:21
阅读 3511·2019-08-23 18:19
阅读 1577·2019-08-23 18:02