應(yīng)用場景

? ? ? ? ? 棋盤類的路徑選擇。? ? ?

作用效果??

? ? ? ? 從棋盤上隨機或指定位置中選擇一個起點，按照規(guī)定好的數(shù)量和方向（例如：上、下、左、右）去隨機的選擇相鄰的模塊，每個模塊只會選擇一次，如果數(shù)量未達(dá)到指定要求時返回找到的最大的路線。

實現(xiàn)原理

? ? ? ? 主要用棧的方法實現(xiàn)

? ? ? ? 選擇好第一個節(jié)點后，節(jié)點進(jìn)棧，

????????按照規(guī)定好的方向去搜索下一個節(jié)點，

????????????????找到后進(jìn)棧，刪除來時方向，標(biāo)記為不可選，加入到備選返回隊列中

? ? ? ? ? ? ? ? 未找到，棧內(nèi)元素出棧，檢查棧是否為空，

? ? ? ? ? ? ? ? ? ? ? ? 不為空，棧頂元素搜索下一節(jié)點

? ? ? ? ? ? ? ? ? ? ? ? 空，將此次遍歷的所有節(jié)點置為不可選，從新選擇開始節(jié)點，如無開始節(jié)點結(jié)束查找。

?代碼實現(xiàn)

var Utils = require('geoUtils');

/**

* createMap函數(shù)將返回這樣的數(shù)據(jù)類型的二維數(shù)組

* @param {*} item

* @param {*} canSelect

* @param {*} directions //此數(shù)據(jù)將在選擇路徑時再賦值? ? createMap時不進(jìn)行賦值

*/

function MapInformation(item, canSelect, position, directions) {

? ? this.item = item;

? ? this.canSelect = canSelect;

? ? this.position = position;

? ? this.directions = directions;

}

var MapUtils = {

? ? DirectionEnum: {

? ? ? ? UP: { x: -1, y: 0 },

? ? ? ? DOWN: { x: 1, y: 0 },

? ? ? ? LEFT: { x: 0, y: -1 },

? ? ? ? RIGHT: { x: 0, y: 1 },

? ? ? ? UPPER_LEFT: { x: -1, y: -1 },

? ? ? ? UPPER_RIGHT: { x: -1, y: 1 },

? ? ? ? LOWER_LEFT: { x: 1, y: -1 },

? ? ? ? LOWER_RIGHT: { x: 1, y: 1 },

? ? },

? ? /**

? ? * 根據(jù)給定的道具集合，創(chuàng)建二維數(shù)據(jù)集

? ? * @param {*} items 道具集合（1維）

? ? * @param {*} numCols 行數(shù)

? ? * @param {*} numVols 列數(shù)

? ? * @returns 返回包裝了items的二維數(shù)據(jù)集，用于搜索功能。

? ? */

? ? createMap(items, numCols, numVols) {

? ? ? ? //將要返回的對象

? ? ? ? var ret = {

? ? ? ? ? ? //用于探索的二維數(shù)組

? ? ? ? ? ? array: [],

? ? ? ? ? ? //用于記錄步數(shù)不足maxSteps的item的數(shù)組

? ? ? ? ? ? notEnough: [],

? ? ? ? };

? ? ? ? //記錄數(shù)組items當(dāng)前位置的變量

? ? ? ? var index = 0;

? ? ? ? for (var i = 0; i < numCols; i++) {

? ? ? ? ? ? ret.array.push([]);

? ? ? ? ? ? for (var j = 0; j < numVols; j++) {

? ? ? ? ? ? ? ? //獲得item? 同時index更新

? ? ? ? ? ? ? ? var item = items[index++];

? ? ? ? ? ? ? ? var mapObj = new MapInformation(item, true, { x: i, y: j });

? ? ? ? ? ? ? ? ret.array[i].push(mapObj);

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? return ret;

? ? },

? ? /**

? ? *

? ? * @param {*} map createMap函數(shù)返回的對象

? ? * @param {*} directions 可以選擇的方向

? ? * @param {*} maxSteps 想要走幾步

? ? * @param {*} useStrict 當(dāng)步數(shù)不足maxSteps時是否返回選到的其它的最大步數(shù)

? ? * @param {*} start 起點對象數(shù)組[{col:0,vol:0},{col:1,vol:1}]

? ? * @example

? ? * var result = MapUtils.serachMap(map,

? ? ? ? *? [MapUtils.DirectionEnum.up, MapUtils.DirectionEnum.down],

? ? ? ? *? 2, true);

? ? ? ? */

? ? searchMap(map, directions, maxSteps, useStrict, start) {

? ? ? ? var mapObjArray = this._localSearchMap(map, directions, maxSteps, useStrict, start);

? ? ? ? var itemArray = this._mapObjArrayToItemArray(mapObjArray);

? ? ? ? return itemArray;

? ? },

? ? /**

? ? *

? ? * @param {*} map

? ? * @param {*} PreinstallObjs [{directions:dir,maxSteps:num,useStrict,start:{}},{directions:dir,maxSteps:num,start:{}}]

? ? */

? ? searchMapByPreinstall(map, PreinstallObjs) {

? ? ? ? var pObj = Utils.array.random(PreinstallObjs, 1, true)[0];

? ? ? ? return this.searchMap(map, pObj.directions, pObj.maxSteps, pObj.useStrict, pObj.start);

? ? },

? ? /**

? ? *

? ? * @param {*} map createMap函數(shù)返回的對象

? ? * @param {*} directions 可以選擇的方向

? ? * @param {*} maxSteps 想要走幾步

? ? * @param {*} useStrict 當(dāng)步數(shù)不足maxSteps時是否返回選到的其它的最大步數(shù)

? ? * @example

? ? * var result = MapUtils.serachMap(map,

? ? *? [MapUtils.DirectionEnum.up, MapUtils.DirectionEnum.down],

? ? *? 2, true);

? ? */

? ? _localSearchMap(map, directions, maxSteps, useStrict, start) {

? ? ? ? var ret = [];

? ? ? ? //記錄本次便利未達(dá)到指定步數(shù)的路線

? ? ? ? var notEnough = [];

? ? ? ? //用于判斷item的棧

? ? ? ? var storehouse = new Array(maxSteps);

? ? ? ? //棧指針 指向棧頂元素

? ? ? ? var s = -1;

? ? ? ? //用于記錄當(dāng)前已經(jīng)選擇的mapObj的數(shù)組

? ? ? ? var selectMapObj = [];

? ? ? ? //添加可選擇的方向

? ? ? ? this._addDirections(map.array, directions);

? ? ? ? var canSelectMapObjs = this._getCanSelectObj(map.array, start);

? ? ? ? do {

? ? ? ? ? ? //每次循環(huán)前清空數(shù)組

? ? ? ? ? ? selectMapObj = [];

? ? ? ? ? ? //回復(fù)數(shù)據(jù)記錄

? ? ? ? ? ? this._recoverNotEnough(notEnough);

? ? ? ? ? ? this._addDirections(notEnough, directions);

? ? ? ? ? ? // notEnough = [];

? ? ? ? ? ? //選擇第一個節(jié)點

? ? ? ? ? ? var firstMapObj = this._selectFirstObj(canSelectMapObjs);

? ? ? ? ? ? if (firstMapObj == false)

? ? ? ? ? ? ? ? break;

? ? ? ? ? ? //入棧

? ? ? ? ? ? storehouse[++s] = firstMapObj;

? ? ? ? ? ? //加入選擇隊列

? ? ? ? ? ? selectMapObj.push(firstMapObj);

? ? ? ? ? ? var lastMapObj = firstMapObj;

? ? ? ? ? ? for (var i = 0; i < maxSteps - 1; i++) {

? ? ? ? ? ? ? ? lastMapObj = this._selectNextObj(map.array, lastMapObj);

? ? ? ? ? ? ? ? if (lastMapObj != null) {

? ? ? ? ? ? ? ? ? ? //入棧

? ? ? ? ? ? ? ? ? ? storehouse[++s] = lastMapObj;

? ? ? ? ? ? ? ? ? ? //加入選擇隊列

? ? ? ? ? ? ? ? ? ? selectMapObj.push(lastMapObj);

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? else {

? ? ? ? ? ? ? ? ? ? //棧內(nèi)元素為空本次尋找結(jié)束? 將當(dāng)前記錄的item數(shù)組添加到notEnough中

? ? ? ? ? ? ? ? ? ? if (--s < 0) {

? ? ? ? ? ? ? ? ? ? ? ? notEnough.push(selectMapObj);

? ? ? ? ? ? ? ? ? ? ? ? break;

? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? ? ? //棧不為空 棧頂元素出棧 新的棧頂元素繼續(xù)尋找

? ? ? ? ? ? ? ? ? ? lastMapObj = storehouse[s];

? ? ? ? ? ? ? ? ? ? //本次未選到mapObj? i-- 保證總量達(dá)到maxSteps

? ? ? ? ? ? ? ? ? ? i--;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? ? ? if (selectMapObj.length == maxSteps) {

? ? ? ? ? ? ? ? ret = selectMapObj;

? ? ? ? ? ? ? ? break;

? ? ? ? ? ? }

? ? ? ? } while (canSelectMapObjs.length > 0);

? ? ? ? if (ret.length == 0 && useStrict == true) {

? ? ? ? ? ? ret = this._findLongestArrayInNotEnough(notEnough);

? ? ? ? }

? ? ? ? this._recoverNotEnough(notEnough);

? ? ? ? return ret;

? ? },

? ? /**

? ? * 撤銷本次查找的不足路線的canSelect

? ? * @param {*} notEnough

? ? */

? ? _recoverNotEnough(notEnough) {

? ? ? ? notEnough.forEach(notEnoughArray => {

? ? ? ? ? ? notEnoughArray.forEach(element => {

? ? ? ? ? ? ? ? element.canSelect = true;

? ? ? ? ? ? });

? ? ? ? });

? ? },

? ? /**

? ? * 添加方向

? ? * @param {*} mapArray

? ? * @param {*} directions

? ? */

? ? _addDirections(mapArray, directions) {

? ? ? ? mapArray.forEach(mapObjArray => {

? ? ? ? ? ? mapObjArray.forEach(mapIns => {

? ? ? ? ? ? ? ? mapIns.directions = directions.concat();

? ? ? ? ? ? });

? ? ? ? });

? ? },

? ? /**

? ? * 獲得map中可以選擇的所有mapObj

? ? * @param {*} mapArray

? ? */

? ? _getCanSelectObj(mapArray, start) {

? ? ? ? //獲得可選擇的obj

? ? ? ? var ret = [];

? ? ? ? if (start == null) {

? ? ? ? ? ? var numCols = mapArray.length;

? ? ? ? ? ? var numVols = mapArray[0].length;

? ? ? ? ? ? for (var i = 0; i < numCols; i++) {

? ? ? ? ? ? ? ? for (var j = 0; j < numVols; j++) {

? ? ? ? ? ? ? ? ? ? var mapObj = mapArray[i][j];

? ? ? ? ? ? ? ? ? ? if (mapObj.canSelect == true) {

? ? ? ? ? ? ? ? ? ? ? ? ret.push(mapObj);

? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? else {

? ? ? ? ? ? var mapObj = mapArray[start.col][start.vol];

? ? ? ? ? ? if (mapObj.canSelect == true) {

? ? ? ? ? ? ? ? ret.push(mapObj);

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? return ret;

? ? },

? ? /**

? ? * 隨機選擇一個item為初始節(jié)點

? ? * @param {*} canSelectMapObjs

? ? */

? ? _selectFirstObj(canSelectMapObjs) {

? ? ? ? if (canSelectMapObjs.length == 0)

? ? ? ? ? ? return false;

? ? ? ? var firstMapObj = Utils.array.random(canSelectMapObjs, 1, true)[0];

? ? ? ? firstMapObj.canSelect = false;

? ? ? ? return firstMapObj;

? ? },

? ? /**

? ? * 根據(jù)lastMapObj中記錄的directions選擇下一個mapObj選擇失敗返回null

? ? * @param {*} mapArray

? ? * @param {*} lastMapObj

? ? */

? ? _selectNextObj(mapArray, lastMapObj) {

? ? ? ? for (var i = 0; i < lastMapObj.directions.length;) {

? ? ? ? ? ? //隨機選擇一個方向并且刪除使用過的方向

? ? ? ? ? ? var d = Utils.array.random(lastMapObj.directions, 1, true)[0];

? ? ? ? ? ? var nextX = lastMapObj.position.x + d.x;

? ? ? ? ? ? var nextY = lastMapObj.position.y + d.y;

? ? ? ? ? ? //判斷是否出界

? ? ? ? ? ? if (nextX >= 0 && nextY >= 0 && nextX < mapArray.length && nextY < mapArray[0].length) {

? ? ? ? ? ? ? ? var mapObj = mapArray[nextX][nextY];

? ? ? ? ? ? ? ? //判斷是否可選

? ? ? ? ? ? ? ? if (mapObj.canSelect == true) {

? ? ? ? ? ? ? ? ? ? mapObj.canSelect = false;

? ? ? ? ? ? ? ? ? ? //刪除來時的方向

? ? ? ? ? ? ? ? ? ? this._removeDirection(mapObj.directions, { x: -d.x, y: -d.y });

? ? ? ? ? ? ? ? ? ? return mapObj;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? return null;

? ? },

? ? /**

? ? * 第一個參數(shù)是對象數(shù)組objArray

? ? * 第二個參數(shù)是自己定義的對象obj

? ? * 刪除對象數(shù)組中屬性值等于obj中的屬性值的對象

? ? * 例如? ? objArray[{a:1,b:1,c:1},{a:1,b:2,c:1}]

? ? *? ? ? ? obj{b:1}

? ? * 函數(shù)運行完畢后objArray[{a:1,b:2,c:1}]

? ? * @param {*} directions

? ? * @param {*} dir

? ? */

? ? _removeDirection(directions, dir) {

? ? ? ? for (var i = 0; i < directions.length; i++) {

? ? ? ? ? ? var element = directions[i];

? ? ? ? ? ? var isRemove = true;

? ? ? ? ? ? for (var attr in dir) {

? ? ? ? ? ? ? ? if (element[attr] != dir[attr]) {

? ? ? ? ? ? ? ? ? ? isRemove = false;

? ? ? ? ? ? ? ? ? ? break;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? ? ? if (isRemove) {

? ? ? ? ? ? ? ? directions.splice(i, 1);

? ? ? ? ? ? ? ? return true;

? ? ? ? ? ? }

? ? ? ? }

? ? },

? ? /**

? ? * 返回notEnough數(shù)組中的最長的一項

? ? * @param {*} notEnough

? ? */

? ? _findLongestArrayInNotEnough(notEnough) {

? ? ? ? var ret = [];

? ? ? ? for (var i = 0; i < notEnough.length; i++) {

? ? ? ? ? ? if (notEnough[i].length > ret.length) {

? ? ? ? ? ? ? ? ret = notEnough[i];

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? Utils.array.remove(notEnough, ret);

? ? ? ? return ret;

? ? },

? ? _mapObjArrayToItemArray(mapObjArray) {

? ? ? ? var ret = [];

? ? ? ? mapObjArray.forEach(element => {

? ? ? ? ? ? ret.push(element.item);

? ? ? ? });

? ? ? ? return ret;

? ? },

};

module.exports = MapUtils;

? ??????????

? ??