華容道游戲（上）

xi4oh4o 發(fā)布于2019-08-19 18:13 / 3383人閱讀

摘要：華容道游戲看似簡單，但求解需要設(shè)計的數(shù)據(jù)結(jié)構(gòu)比較復(fù)雜，還牽涉到棋類游戲的棋局判斷，所以整個過程還是挺費(fèi)勁的。華容道游戲介紹華容道游戲據(jù)說來源于三國故事諸葛亮智算華容，關(guān)云長義釋曹操。

此為《算法的樂趣》讀書筆記，我用javascript（ES6）重新實現(xiàn)算法。

華容道游戲看似簡單，但求解需要設(shè)計的數(shù)據(jù)結(jié)構(gòu)比較復(fù)雜，還牽涉到棋類游戲的棋局判斷，所以整個過程還是挺費(fèi)勁的。我盡量用面向?qū)ο蟮乃枷雭磉M(jìn)行封裝，整個過程將分成幾個部分記錄下來，今天是第一部分，數(shù)據(jù)結(jié)構(gòu)的定義與初始化。

華容道游戲介紹

華容道游戲據(jù)說來源于三國故事“諸葛亮智算華容，關(guān)云長義釋曹操”。在一個5×4的棋盤上布置多名蜀國大將和軍士作為棋子，將曹操圍困在中間，通過滑動各個棋子，幫助曹操移動到出口位置逃走。

算法原理

華容道的數(shù)學(xué)原理尚未研究清楚，還沒有數(shù)學(xué)方法可以一勞永逸的解決它，因此我們只能用計算機(jī)來窮舉所有的可能解，并找出最優(yōu)解。

代碼及思路

棋局包括棋盤的狀態(tài)和棋子的狀態(tài)兩部分，我們是要用計算機(jī)來演化和搜索棋局。對于一個棋局，如果有一種或多種移動武將的方法，這個棋局就可以演化成一個或多個新的棋局，每個新棋局又可以根據(jù)移動武將的方式演化成更多的棋局。

常量定義

const MAX_WARRIOR_TYPE = 5;                                //格子被武將占據(jù)的狀態(tài)，空或武將序號，1+4
const HRD_GAME_ROW = 5;                                    //棋盤實際行數(shù)
const HRD_GAME_COL = 4;                                    //棋盤實際列數(shù)
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
    }
}

棋局對象定義

二維數(shù)組表示棋盤（7×6），擴(kuò)大了一圈，在外圍設(shè)置了“哨兵”；棋盤上各點為零表示空，數(shù)字代表武將的序號。

class HrdGameState {
    constructor(){
        this.board = []                              //棋盤
        for(let i = 0; i
武將放置函數(shù)
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;
}
檢測能否放置武將函數(shù)
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;
}
放置武將函數(shù)
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),          //構(gòu)建武將列表，初始棋局
          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)                              //輸出棋局
測試結(jié)果
結(jié)果符合預(yù)期
[ [ -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
小結(jié)
盡量使用面向?qū)ο蟮乃枷雭斫鉀Q問題，讓數(shù)據(jù)和操作綁定在一起，努力使代碼容易看懂。