资讯专栏INFORMATION COLUMN

华容道游戏(上)

xi4oh4o / 3274人阅读

摘要:华容道游戏看似简单,但求解需要设计的数据结构比较复杂,还牵涉到棋类游戏的棋局判断,所以整个过程还是挺费劲的。华容道游戏介绍华容道游戏据说来源于三国故事诸葛亮智算华容,关云长义释曹操。

此为《算法的乐趣》读书笔记,我用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)重新实现算法。 华容道游戏看似简单,但求解需要设计的数据结构比较复杂,还牵涉到棋类游戏的棋局判断,所以整个过程还是挺费劲的。我尽量用面向对象的思想来进行封装,整个过程将分成几...

    Jason 评论0 收藏0
  • 容道游戏(下)

    摘要:华容道游戏看似简单,但求解需要设计的数据结构比较复杂,还牵涉到棋类游戏的棋局判断,所以整个过程还是挺费劲的。 此为《算法的乐趣》读书笔记,我用javascript(ES6)重新实现算法。 华容道游戏看似简单,但求解需要设计的数据结构比较复杂,还牵涉到棋类游戏的棋局判断,所以整个过程还是挺费劲的。我尽量用面向对象的思想来进行封装,整个过程将分成几个部分记录下来,今天是最后一部分,棋局的广...

    BicycleWarrior 评论0 收藏0
  • 用React写一个数字容道,你需要知道的秘密

    摘要:还在上班很无聊数字华容道畅玩地址开发源码地址这个叫前言年末了。光随机生成一个乱序数列是不够的,还得保证这个数列的逆序数为偶数,嗦嘎。所以,我们直接将交换的次数,记为数列逆序数个数,就达到了想要的效果。 还在上班?很无聊?数字华容道畅玩地址 开发源码地址 这个叫前言 年末了。哦,不,要过年了。以前只能一路站到公司的我,今早居然是坐着过来的。新的一年,总要学一个新东西来迎接新的未来吧,所以...

    Jason 评论0 收藏0
  • 一只青蛙跳下水

    这是一个关于独立钻石的游戏 独立钻石起源于法国,是一种风靡世界的益智游戏与中国发明的华容道、匈牙利人发明的魔方, 并称为智力游戏界的三大不可思议它类似于跳棋,但不能走步,只能跳。走棋时棋子跳过相邻的棋子到空位上,并把跳过的棋子吃掉。棋子可以沿棋盘的格线横跳、纵跳,但不能斜跳 了解更多 游戏截图 showImg(https://segmentfault.com/img/bVAdq3); 游戏地址 游...

    邹强 评论0 收藏0
  • “云”必有一战,商业诱惑的第一颗棋子就是游戏

    摘要:不难理解,近两年云计算技术如风暴一般席卷了世界的每一个角落,游戏市场自然也不会例外。同样不难猜测,收购与云服务器也成为沃尔玛进入这部分市场的惯用筹码,电商对云技术应用的把控成为他们想要进一步挑战游戏的动力所在。不久前,谷歌在今年举行的游戏开发者大会上宣布了自家的云游戏服务平台:Stadia,随后亚马逊也表示自己正在搭建云游戏服务,甚至连零售业巨头沃尔玛都表示计划启动自己的云游戏平台,大佬们的...

    JaysonWang 评论0 收藏0

发表评论

0条评论

xi4oh4o

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<