幅優先アルゴリズム

幅優先検索アルゴリズム (Breadth-First Search,BFS) は、グラフ内のすべてのノードをシステム的に展開して検査し、結果を検索するブラインド検索方法です。 つまり、結果の可能な場所を考慮し、結果が見つかるまでグラフ全体を徹底的に検索します。 BFS は経験則アルゴリズムを使用しません。

幅優先検索では、2 つのもの間の最短距離を見つけることができますが、最短距離には多くの意味があります。 幅優先検索では、次の機能を実行できます:

• 国際的なチェッカーAIを書き、勝つために少なくとも何歩歩くかを数えます
• スペル チェックを記述し、READED を READER に変更すると、1 つの場所を編集する必要があるなど、スペル ミスの単語を正しい単語に変換するために、編集する場所の数を計算します。
• あなたの関係ネットワークに基づいて、最も近い医師を見つける

  详情

/**
 * 获取角色移动范围
 * @param __actorSite__ 角色位置
 * @param __moveRange__ 角色可移动范围，
 */
XXX.prototype.getMovingRangeSites = function (__actorSite__, __moveRange__) {
    // 地图大小
    let mapSize = this._battleAPI._battleData.getMapSize();
    // 初始化
    let siteHasBeenChosenArr = new Array(mapSize.width);
    for (let i = 0; i < siteHasBeenChosenArr.length; ++i) {
        siteHasBeenChosenArr[i] = new Array(mapSize.height);
    }
    // 检索site是否被选择的临时用数组，标记全地图的site是否被使用
    for (let i = 0; i < mapSize.width; ++i) {
        for (let j = 0; j < mapSize.height; ++j) {
            siteHasBeenChosenArr[i][j] = 0;
        }
    }

    // 初始化结果数组
    let rangeSitesArr = [];

    // 判断range范围是否合法
    if (__moveRange__ >= 1 && __moveRange__ <= 20) {
        //
        let cellsToBeCheckArr = [];
        cellsToBeCheckArr.push(__actorSite__);

        // 根据角色移动的步数检索几次
        for (let index = 1; index <= __moveRange__; index++) {

            // 临时保存本次检查出来的site
            let tempArr = [];

            // 当前步数能走到的site
            for (const iterator of cellsToBeCheckArr) {
                // 检索顺序：左 上 右 下
                // 相邻节点坐标
                let siteLeft = {
                    x: iterator.x - 1,
                    y: iterator.y
                };

                // 判断是否满足逻辑要求的条件 及 检索时是否已经选择过该点
                if (this._checkSiteEnable(siteLeft) && !this._checkSiteHasBeenChosen(siteLeft, siteHasBeenChosenArr)) {
                    // 将该点设置成一倍检索状态
                    siteHasBeenChosenArr[siteLeft.x][siteLeft.y] = 1;
                    // 保存该点到结果数组
                    rangeSitesArr.push(siteLeft);
                    // 保存该点到临时数组，作为下次循环的根节点
                    tempArr.push(siteLeft);
                }

                let siteUp = {
                    x: iterator.x,
                    y: iterator.y + 1,
                };

                if (this._checkSiteEnable(siteUp) && !this._checkSiteHasBeenChosen(siteUp, siteHasBeenChosenArr)) {
                    siteHasBeenChosenArr[siteUp.x][siteUp.y] = 1;
                    rangeSitesArr.push(siteUp);
                    tempArr.push(siteUp);
                }

                let siteRight = {
                    x: iterator.x + 1,
                    y: iterator.y
                };

                if (this._checkSiteEnable(siteRight) && !this._checkSiteHasBeenChosen(siteRight, siteHasBeenChosenArr)) {
                    siteHasBeenChosenArr[siteRight.x][siteRight.y] = 1;
                    rangeSitesArr.push(siteRight);
                    tempArr.push(siteRight);
                }

                let siteDown = {
                    x: iterator.x,
                    y: iterator.y - 1,
                };

                if (this._checkSiteEnable(siteDown) && !this._checkSiteHasBeenChosen(siteDown, siteHasBeenChosenArr)) {
                    siteHasBeenChosenArr[siteDown.x][siteDown.y] = 1;
                    rangeSitesArr.push(siteDown);
                    tempArr.push(siteDown);
                }
            }

            // 将本次循环检索出来的site 放入待检查数组，以便下次循环使用
            cellsToBeCheckArr = tempArr;
        }
    } else {
        // range不合法时直接返回null
        rangeSitesArr = null;
    }

    return rangeSitesArr;
};