前言
華容道是啥玩意？
這種數(shù)字拼圖游戲大家都玩過吧，他就是典型的華容道之一。
華容道是古老的中國民間益智游戲，以其變化多端、百玩不厭的特點與魔方、獨立鉆石棋一起被國外智力專家并稱為“智力游戲界的三個不可思議”。
今天咱們就來了解一下這個華容道。
正文
今天咱們主要以3*3的布局來進(jìn)行，菜鳥用cocos creator 寫了一個簡單的demo，下面咱們逐步說一下
1.面板
首先咱們隨機生成一個面板排列
2.華容道求解
思路：
窮舉法：大家都知道這種游戲的玩法，滑動其中可以滑動的方格，將打亂的方格按照上邊數(shù)字從小到大的順序依次排列即可通關(guān)。在這里菜鳥利用了窮舉法，在每種可能的情況中去查找最優(yōu)解。
在窮舉法中我們常見的有：
- 廣度搜索：廣度優(yōu)先搜索，會優(yōu)先搜索所有方向的第一步，然后再接著搜索每一個可行的方向的第二步，以此類推
- 深度搜索：深度優(yōu)先搜索，會在一個方向一直搜下去，直到這條路走不通，才會考慮第二個方向
在這里我們用的是廣度優(yōu)先搜索，我們只需要拿到最優(yōu)解，也就是步數(shù)最少的。
具體操作如圖：
我們以前三步為例，
- 第一步我們有三種走法，
- 第二步我們需要在第一步的基礎(chǔ)上再移動方塊，每一種又會延伸出更多的可能性，
- 我們需要把每一種可能性都存儲起來，
- 下一步的移動是基于上一步所有可能性的基礎(chǔ)再去移動
- 在第三步的時候我們會發(fā)現(xiàn) 會出現(xiàn)重復(fù)的情況，所有我們要進(jìn)行減支，將重復(fù)的分支及時的處理掉，
- 雖然處理掉了重復(fù)的分支，但是分支的數(shù)量也會成倍的增加，就拿示例中的排列，隨著步數(shù)的增加，分支的數(shù)量如圖顯示
- 一旦有分支檢測到了已通關(guān)，那么廣度搜索就結(jié)束了
- 最終會的得到每一步的一個移動過程
得到了解，我們可以應(yīng)用到demo，檢測是否可以通關(guān)
點擊demo中的自動排列
3.代碼
//循環(huán)遍歷求解
while (true) {
let steps: Array<any> = [];
let lastGrad: Array<any> = this.mMapData[this.mMapData.length - 1];
console.log(lastGrad.length);
//遍歷作最后一個梯度中所有的結(jié)果，求解下一步
for (let i = 0; i < lastGrad.length; i++) {
let matrix = lastGrad[i]["matrix"];
let answer = lastGrad[i]["answer"];
let result: Array<any> = this.move(matrix, answer, steps);
if (result) {
console.log("結(jié)果：", result);
resolve(result);
return;
}
}
if(steps.length<=0){
console.log("查詢結(jié)果失敗，");
resolve(null);
return;
}
this.mMapData.push(steps);
}
private move(matrix: Array<number>, answer: Array<any>, steps: Array<any>): Array<any> {
for (let i = 0; i < matrix.length; i++) {
if (matrix[i] != -1) { //不是空位，檢測是否可移動，獲取可移動結(jié)果
//檢測上下左右是否可以移動，
let result0: Array<any> = this.moveUp(i, matrix, answer, steps);
let result1: Array<any> = this.moveDown(i, matrix, answer, steps);
let result2: Array<any> = this.moveLeft(i, matrix, answer, steps);
let result3: Array<any> = this.moveRight(i, matrix, answer, steps);
if (result1) {
return result1;
}
if (result2) {
return result2;
}
if (result0) {
return result0;
}
if (result3) {
return result3;
}
}
}
return null;
}
private moveRight(i: number, matrix: Array<number>, answer: Array<any>, steps: Array<any>): Array<any> {
let line: number = i % this.mLine;
let row: number = Math.floor(i / this.mLine);
if (line + 1 >= this.mLine) return null; //超出邊界
let targetIndex: number = row * this.mLine + (line + 1);
if ( matrix[targetIndex] != -1) return null; //不可移動
//移動
//移動
//復(fù)制新的數(shù)組進(jìn)行修改
let newMatrix: Array<number> = JSON.parse(JSON.stringify(matrix));
let newAnswer: Array<any> = JSON.parse(JSON.stringify(answer));
//互換位置
let temp: number = newMatrix[i];
newMatrix[i] = newMatrix[targetIndex];
newMatrix[targetIndex] = temp;
newAnswer.push({ "index": i, "dic": 3 });
if (this.checkIsExist(newMatrix)) {
return null;
}
if (this.checkPass(newMatrix)) {
return newAnswer;
}
let step: any = {};
step["matrix"] = newMatrix;
step["answer"] = newAnswer;
steps.push(step);
}
/**
* 檢測是否通關(guān)
*/
private checkPass(matrix: Array<number>): boolean {
if (matrix[this.mRow * this.mLine - 1] != -1) return false;
for (let i = 0; i < this.mRow * this.mLine - 1; i++) {
if (matrix[i] != i + 1) {
return false;
}
}
console.log(matrix)
return true;
}
/**
* 檢測是否重復(fù)
*/
private checkIsExist(matrix): boolean {
if (this.mMapMatrixS[JSON.stringify(matrix)]) {
return true;
}
this.mMapMatrixS[JSON.stringify(matrix)] ="1";
return false;
}
4.注意
demo中是3 * 3的排列，使用瀏覽器勉強可以跑出結(jié)果，但是4 * 4或者5 * 5的就不行了，因為分支太多。后續(xù)有時間菜鳥會用python腳本實現(xiàn)4 * 4，5 * 5或更多的排列，最終導(dǎo)出json關(guān)卡信息。
以上就是詳解CocosCreator華容道數(shù)字拼盤的詳細(xì)內(nèi)容，更多關(guān)于CocosCreator華容道的資料請關(guān)注服務(wù)器之家其它相關(guān)文章！
原文鏈接：https://blog.csdn.net/carlos13207/article/details/108663593
