兔子零-A酱

欢迎来到我的个人博客，我会在这里记录下关于学习和生活的点点滴滴

首页 归档

围住神经猫——广度优先搜索的妙用

2017年10月03日
算法 JavaScript Canvas

通过打砖块这个Demo的练习，差不多算是把Canvas的基本用法又重新过了一遍，但是算法方面并没有多少干货，那么这次就来个稍微有点挑战性的Demo——围住神经猫。

演示地址：SurroundCat
Github：SurroundCat
不要吝啬你的Star哦~(〃'▽'〃)

对象构建

要编写面向对象的程序，第一步当然是先分析清楚程序有哪些基本对象了，就像打砖块那个项目一样，让我们从这个程序的界面开始，分析下组成这个程序的有哪些基本的对象。

Grid

定义

游戏的界面是由一个一个圆圈组成的，所以游戏的基本要素之一就是这些“圆圈”了，不过我更喜欢叫它“格子”Grid这个名字。虽然更抽象了，但是从程序的角度来看，反而更利于我们去抽取它应该具有的属性和方法了。

一个格子要呈现在画面上，无论如何我们也要知道它的位置吧，所以它此时在整个画面上所处的行数gridRow和列数gridCol就是必不可少的了。（将画布上的坐标映射成行列数能大大简化后面的运算操作）

然后在游戏的进行过程中，格子会有猫和障碍这两种状态，如果再加上它自己默认的状态的话，就会有三种基本状态了。因此，必须为格子增加类型type这个属性。（还剩一个属性，在后面介绍搜索算法时再给出定义）

这样，程序中最重要的Grid对象就定义好了：

/* 定义格子 */
var Grid = function(gridRow, gridCol, type, isWalkable) {
    this.gridRow = gridRow; // 格子所处行数
    this.gridCol = gridCol; // 格子所处列数
    this.gridType = type; // 格子类型 0默认 1障碍 2猫
    this.isWalkable = isWalkable; // 格子是否可行   true可行 false不可行
};

方法

Grid应该有哪些方法呢？
我们想在界面上看到一个Grid，总要先把它“画”出来吧，这样才能在界面上成功看到它。所以第一个方法就是用于画格子的drawGrid()方法：

drawGrid: function(game, context) {
    context.beginPath();
    context.arc(this.getGridPosition(game).gridPositionX, 
    this.getGridPosition(game).gridPositionY, this.gridRadius, 0, Math.PI * 2, true);
    context.fillStyle = this.gridColor[this.gridType];
    context.fill();
    context.closePath();
}

要画出圆形，调用的是arc这个canvas方法，我们需要控制的参数其实只有坐标和半径。
半径很简单，直接在原型上定义gridRadius就行了，而坐标则需要我们单独用一个方法去计算，这便是getGridPosition()方法：

getGridPosition: function (game) {
    var gridPosition = {};
    // 如果为偶数行 从左向右边开始画  否则从右向左
    if (this.gridRow % 2 == 0) {
        gridPosition.gridPositionX = this.gridRadius * 6 / 4
        + this.gridCol * (this.gridRadius * 2 + this.gridGap);
        gridPosition.gridPositionY = this.gridRadius
        + this.gridRow * (this.gridRadius * 2 + this.gridGap);
    } else {
        gridPosition.gridPositionX = game.gameCanvasWidth - (this.gridRadius * 6 / 4 
        + (game.gameGridColCount - 1 - this.gridCol) * (this.gridRadius * 2 + this.gridGap));
        gridPosition.gridPositionY = this.gridRadius + this.gridRow * (this.gridRadius * 2 + this.gridGap);
    }
    return gridPosition;
}

由于在画面上要看到一种交错的效果，所以还必须给格子在它的原型上定义间隙gridGap这个属性，以及还需要定义一个数组gridColor来表示格子的颜色。
有了格子的间隙，格子的半径及格子的行列数，那么此时它在画布上的位置坐标就能表示了。计算的时候需要考虑交错的间隔值，所以稍微比较麻烦，而且这里还有改进的余地，读者不必参考。
最后，我们要取得画布区域的高度和宽度，因此还需要后面定义的Game对象的实例，这里当做参数传递给这个函数就行了。

Barrier

定义

界面上生成的障碍，显然也需要坐标值，我们也用映射好的行列数来表示它的位置。至于类型，因为我们的抽象思路已经把类型定义在Grid对象上了，所以Barrier就不需要单独定义了：（对象的抽象思路多种多样，可自行考虑最佳实现方案）

/* 定义障碍 */
var Barrier = function(x, y) {
    this.barrierX = x; // 障碍X坐标
    this.barrierY = y; // 障碍Y坐标
};

方法

暂时没有抽象出方法，只留出接口，读者可自行实现。

Barrier.prototype = {};

Cat

猫的性质和障碍是类似的，直接给出定义：

/* 定义神经猫 */
var Cat = function(x, y) {
    this.catX = x; // 猫X坐标
    this.catY = y; // 猫Y坐标
};
Cat.prototype = {};

Game

定义

和打砖块那个例子一样，这个游戏同样需要一个Game对象来管理程序中出现的基本属性和方法。
游戏是否开始、本局所用步数和历史最短步数，这三个就是需要定义的基本属性了：（也许叫它们游戏的状态更合适）

/* 定义游戏状态 */
var Game = function(gameStart, gameSteps, gameMinSteps) {
    this.gameStart = gameStart; // 游戏是否开始
    this.gameSteps = gameSteps;
    this.gameMinSteps = gameMinSteps;
};

剩下的还有一些基本的属性，我们定义在原型上：

Game.prototype = {
    gameGridRowCount: 9, // 游戏格子行数
    gameGridColCount: 9, // 游戏格子列数
    gameBarrierCount: 6, // 游戏障碍个数
    gameCanvasWidth: 0, // 游戏画布宽度
    gameCanvasHeight: 0, // 游戏画布高度
};

方法

如你所料，Game一定需要定义一些重要的方法，具体有哪些呢，从定义入手就能窥得端倪了。

既然在构造函数中定义了步数和最小步数，那当然需要方法来设置这个步数了，所以我们需要两个设置步数的方法：

// 设置游戏当前所用步数
setGameSteps: function(gameSteps) {
    document.getElementById("steps").innerHTML = gameSteps;
},
// 设置游戏最短所用步数
setGameMinSteps: function(gameMinSteps) {
    document.getElementById("minSteps").innerHTML = gameMinSteps;
},

要改变DOM元素的内容，这里用到的是元素的innerHTML属性，将程序中当前所用的步数传入方法即可。

在getGridPosition()方法中需要取得游戏画布的尺寸，因此，我们需要一个方法来设置画布的尺寸：

// 设置游戏画布尺寸
setGameCanvasSize: function() {
    // 获取格子数据
    var gridData = this.getGameGridData();
    // 定义画布宽度
    this.gameCanvasWidth = gridData.gridRadius * 2 * this.gameGridRowCount + 
    gridData.gridGap * (this.gameGridRowCount - 1) + gridData.gridRadius * 2 + gridData.gridGap / 2;
    // 定义画布高度                       
    this.gameCanvasHeight = gridData.gridRadius * 2 * this.gameGridColCount + 
    gridData.gridGap * (this.gameGridColCount - 1);
    // 设置canvas宽度
    document.getElementById("canvas").setAttribute("width", this.gameCanvasWidth);
    // 设置canvas高度
    document.getElementById("canvas").setAttribute("height", this.gameCanvasHeight);
},

因为要达到响应式的效果，所以画布的高度和宽度要根据当前屏幕下格子的半径和间隙大小来计算，我们用getGameGridData()方法来根据屏幕宽度动态改变格子的属性：

// 获取游戏格子半径及间隔
getGameGridData: function() {
    var gridData = {};
    // 根据当前屏幕宽度来动态适配格子半径及间隔
    var clientWidth = document.body.clientWidth;
    if (clientWidth > 1023 && clientWidth < 1440) {
        gridData.gridRadius = 24;
        gridData.gridGap = 6;
    } else if (clientWidth > 768 && clientWidth < 1024) {
        gridData.gridRadius = 20;
        gridData.gridGap = 5;
    } else if (clientWidth > 480 && clientWidth < 769) {
        gridData.gridRadius = 16;
        gridData.gridGap = 4;
    } else if (clientWidth < 481) {
        gridData.gridRadius = 12;
        gridData.gridGap = 3;
    } else {
        gridData.gridRadius = 24;
        gridData.gridGap = 6;
    }
    return gridData;
},

屏幕窗口宽度的标准值可以自行设定，这里只适配常规屏幕宽度。

游戏画布有了，接下来就需要初始化游戏格子了：

// 初始化游戏格子
initGameGrids: function(girdData, gameBarriers, cat) {
    var gridType, grid, isWalkable;
    var gameGrids = [];
    var game = this;
    for (var i = 0; i < this.gameGridRowCount; i++) {
        gameGrids[i] = [];
        for (var j = 0; j < this.gameGridColCount; j++) {
            gridType = 0;
            isWalkable = true;
            for (var k = 0; k < gameBarriers.length; k++) {
                if (gameBarriers[k].barrierX == i && gameBarriers[k].barrierY == j) {
                    gridType = 1;
                    isWalkable = false;
                    break;
                }
            }
            if (cat.catX == i && cat.catY == j) {
                gridType = 2;
                isWalkable = false;
            }
            grid = new Grid(i, j, gridType, isWalkable);
            grid.gridRadius = girdData.gridRadius;
            grid.gridGap = girdData.gridGap;
            grid.drawGrid(game, context);
            gameGrids[i][j] = grid;
        }
    }
    return gameGrids;
},

这个方法其实个人觉得写得并不好，临时变量过多、方法调用比较混乱，不过勉强能用。
主体逻辑很简单，利用两个循环遍历游戏的每行每列，然后初始化grid对象，比较麻烦的是我们需要单独对传入构造函数的参数进行判断，比如当前格子的类型等属性。这里需要用到的一个变量是gameBarriers，在后面全局的初始化方法initGame()中会将它传入，同样，我们将返回一个初始化后的数组gameGrids供后面的一些全局方法调用。

游戏障碍的初始化，其实也是在initGame()中调用它，并且把结果当做参数传入了initGameGrids()方法：

// 初始化障碍
initGameBarriers: function() {
    var x = [], y = [];
    var gameBarriers = [];
    for (var i = 0; i < this.gameGridRowCount; i++) {
        x.push(i);
    }
    for (var j = 0; j < this.gameGridColCount; j++) {
        y.push(j);
    }
    for (var k = 0; k < this.gameBarrierCount; k++) {
        var randomX = Math.floor(Math.random() * this.gameGridRowCount);
        var randomY = Math.floor(Math.random() * this.gameGridColCount);
        while ((x[randomX] == -1 && y[randomY] == -1) || (randomX == 4 && randomY == 4)) {
            randomX = Math.floor(Math.random() * this.gameGridRowCount);
            randomY = Math.floor(Math.random() * this.gameGridColCount);
        }
        gameBarriers.push(new Barrier(randomX, randomY));
        x[randomX] = -1;
        y[randomY] = -1;
    }
    return gameBarriers;
},

障碍的生成是利用Math.floor来实现随机化的，需要注意的是，这里必须用一个数组来记录位置的状态，避免在同一个位置重复生成的bug出现。
当然，如果这个位置的状态已经是猫了，我们也让程序重新循环一次去获得新的位置。

猫的位置初始化在中心位置就行了，取行数和列数的一半即是它的坐标值：

// 初始化神经猫
initGameCat: function() {
    var catPosX = (game.gameGridRowCount - 1) / 2;
    var catPosY = (game.gameGridColCount - 1) / 2;
    return (new Cat(catPosX, catPosY));
}

程序需要的基本对象构建好了，下一步就是用一些定义在全局的方法去调用它们了。

游戏初始化

既然有了Game对象，以及定义在它上面的初始化方法，那么我们就可以正式初始化游戏了：

var initGame = function() {
    // 游戏对象初始化
    game = new Game(true, 0, 0);
    // 获取缓存中的游戏记录数据
    var gameData = JSON.parse(window.localStorage.getItem("gameData"));
    // 判断缓存里是否有值
    if (gameData != null && gameData != undefined) {
        game.setGameMinSteps(gameData.gameMinSteps);
    } else {
        game.setGameMinSteps(game.gameMinSteps);
    }
    // 初始化当前游戏步数
    game.setGameSteps(game.gameSteps);
    // 设置当前游戏画布大小
    game.setGameCanvasSize();
    // 初始化神经猫
    cat = game.initGameCat();
    // 初始化格子
    gameGrids = game.initGameGrids(game.getGameGridData(), game.initGameBarriers(), cat);
};

在初始化之前，还需要一些定义在全局的变量配置，以供后面一些全局的函数使用：

/* 程序基本配置 */
var canvas = document.getElementById("canvas"); // 获得canvas元素
var context = canvas.getContext("2d"); // 获得context对象
var game; // 创建游戏对象
var gameGrids = []; // 创建格子集合
var cat; // 创建神经猫对象
var isVisited; // 记录节点是否搜索的二维数组
var searchDepth; // 记录节点搜索深度

在initGame()中，首先需要定义全局的游戏对象game，然后是游戏的各种初始化，最后是游戏缓存的获取。这里顺便讲讲游戏的缓存机制：

  1. 每次初始化（刷新网页）会去读取浏览器的localStorage，并判断是否有值
  2. 如果有值就把缓存中的值设置给当前游戏的最小步数
  3. 如果没有值就初始化当前游戏的最小步数

初始化后，应该能看到一个基本的界面了：
SurroundCat

事件绑定

不论是一般的网页或是游戏程序都会有交互操作，而点击事件算是最常见的交互之一了，我们的程序里也需要绑定这么一个事件函数：

/* canvas点击事件 */
canvas.addEventListener("click", function (e) {
    for (var i = 0; i < game.gameGridRowCount; i++) {
        for (var j = 0; j < game.gameGridColCount; j++) {
            if (isInPath(e.offsetX, e.offsetY, gameGrids[i][j])) {
                if (gameGrids[i][j].gridType == 0) {
                    // 清除默认格子痕迹
                    clearGridView(i, j, 1, true);
                    // 让格子变为障碍
                    updateGameGrid(i, j, 1, false);
                    // 重置节点搜索的访问状态
                    resetGridVisited();
                    resetGridDepth();
                    // 重置当前节点的搜索深度
                    searchDepth = 0;
                    // 移动猫
                    moveCat();
                    // 增加游戏所用步数
                    game.gameSteps++;
                    game.setGameSteps(game.gameSteps);
                }
                return;
            }
        }
    }
}, false);

这个函数应该才算是程序所有逻辑的真正“入口”，让我们一步步来拆解它：

  1. 事件直接绑定在canvas画布对象上，通过鼠标点击画布区域触发
  2. 点击后，判断是否在画布的格子区域内
  3. 如果点击在格子内，判断格子类型是否是默认类型
  4. 如果点击的是默认类型，开始执行正式的游戏逻辑

点击事件的绑定，我们可以使用addEventListener来完成。值得一提的是，这里的判断条件涉及到了第一个我们封装的函数isInPath()：

/* 判断点是否在路径内 */
var isInPath = function(x, y, grid){
    var gridPosition = grid.getGridPosition(game);
    context.beginPath();
    context.arc(gridPosition.gridPositionX, gridPosition.gridPositionY, 
                grid.gridRadius, 0, Math.PI * 2, true);
    context.closePath();
    return context.isPointInPath(x, y);
};

在这个函数中我们利用了canvas封装的一个API：isPointInPath，它能帮助我们判断一个点是否在一个绘制对象的路径中。（通俗点解释，其实就是一个点是否包含在一个2d图形之内）我们要做的是将这个点在画布上的x、y坐标传入这个函数，具体到程序中，即是点击的坐标，可以用event对象获取：e.offsetX、e.offsetY，而在context对象之上必须还要调用一次arc函数绘制出当前grid的路径，这样isPointInPath函数才能返回判断的结果。

前两步的判断都通过后，就应该执行正式的游戏逻辑了，它也分为如下几步：

  1. 清除默认类型的格子痕迹
  2. 让当前被点击的格子变成障碍的类型
  3. 重置每个格子节点的访问状态以及搜索深度
  4. 重置当前节点的搜索深度
  5. 改变神经猫的位置
  6. 增加游戏所用步数

因为涉及到搜索算法，所以这里的步骤只能大概解释下：
在每次绘制之前利用clearRect清除掉画布上当前区域的绘制痕迹，代码中已经把它封装到clearGridView()中了：（搜索算法中，清除猫的痕迹也利用了这个函数）

/* 清除格子显示痕迹 */
var clearGridView = function(girdRow, gridCol, gridType, isWalkable) {
    // 获得猫所处的格子
    var grid = new Grid(girdRow, gridCol, gridType, isWalkable);
    grid.gridRadius = game.getGameGridData().gridRadius;
    grid.gridGap = game.getGameGridData().gridGap;
    // 清除痕迹
    context.clearRect(grid.getGridPosition(game).gridPositionX - grid.gridRadius, 
    grid.getGridPosition(game).gridPositionY - grid.gridRadius,
    grid.gridRadius * 2, grid.gridRadius * 2);
};

清除痕迹后就可以让当前被点击的格子变为游戏障碍的类型了，我们利用的是updateGameGrid()函数：

/* 更新格子状态 */
var updateGameGrid = function(x, y, type, isWalkable) {
    gameGrids[x][y].gridType = type;
    gameGrids[x][y].drawGrid(game, context);
    gameGrids[x][y].isWalkable = isWalkable;
};

注意，这里必须为格子的isWalkable属性赋值，以便让我们知道当前节点是否“可行走”，也就是让神经猫在搜索的时候判断格子是否可以移动。

搜索时会用到每个格子的searchDepth属性，所以每次搜索之前必须在这里初始化它：

/* 重置节点搜索深度 */
var resetGridDepth = function() {
    for (var i = 0; i < game.gameGridRowCount; i++) {
        for (var j = 0; j < game.gameGridColCount; j++) {
            if (gameGrids[i][j].isWalkable) {
                gameGrids[i][j].searchDepth = 1;
            }
        }
    }
};

前面在全局配置的变量中还定义了一个isVisited变量，在搜索过程中它可以记录节点是否已经访问过了，每次点击时也应该初始化它的值：

/* 重置记录节点访问状态的数组 */
var resetGridVisited = function() {
    isVisited = [];
    for (var i = 0; i < game.gameGridRowCount; i++) {
        isVisited[i] = [];
        for (var j = 0; j < game.gameGridColCount; j++) {
            isVisited[i][j] = false;
        }
    }
};

全局还有一个记录每一步搜索到的最短路径的searchDepth变量需要在这里初始化，赋值为0即可。

最后的步骤就是让猫移动了，移动成功后，让游戏所用步数增加，这样我们就完成了一次事件绑定了操作流程，所以接下来的重点便是猫的移动moveCat()了。

移动神经猫

猫的移动函数如下：

/* 移动猫的位置 */
var moveCat = function() {
    // 找到当前节点周围所有可走的相邻节点
    var nextGrids = getNextGrids(searchDepth, gameGrids[cat.catX][cat.catY]);
    // 获得相邻节点的搜索结果
    var gridsSearchResult = getSearchResults(nextGrids);
    console.log(gridsSearchResult);
    // 让猫移动到周围路径最短的那个格子
    if (gridsSearchResult.length != 0) {
        var moveGrids = [];
        for (var m = 0; m < gridsSearchResult.length; m++) {
            if (gridsSearchResult[m].gridDepth == sortSearchDepth(gridsSearchResult)) {
                moveGrids.push(gridsSearchResult[m].grid);
            }
        }
        var randomMoveGrid = moveGrids[Math.floor(Math.random() * moveGrids.length)];
        // 清除猫的痕迹
        clearGridView(cat.catX, cat.catY, 2, false);
        // 格子重置为默认状态
        updateGameGrid(cat.catX, cat.catY, 0, true);
        // 让猫移动到下一个格子
        cat.catX = randomMoveGrid.gridRow;
        cat.catY = randomMoveGrid.gridCol;
        // 让格子状态变为猫
        updateGameGrid(cat.catX, cat.catY, 2, false);
        // 判断是否lose
        isGameLose();
    } else {
        // 判断是否win
        isGameWin();
    }
};

非常长的一个函数，其中用到的功能点我们一个一个来介绍，先梳理一下整体流程：

  1. 找到当前猫所在节点周围所有可走的相邻节点
  2. 获得相邻节点的搜索结果
  3. 如果搜索结果为空，表示已经没有可以移动到边缘的节点了，游戏结束，玩家胜利
  4. 如果搜索结果不为空，就让猫移动到周围所有节点中路径最短的那个点（最短路径不唯一就随机取一个点）
  5. 移动完成后，判断猫是否到达边缘，如果到达了，游戏结束，玩家失败

我们先不提具体的实现流程，而是来看看神经猫的移动思路和搜索算法是怎样的。

要让猫移动到边缘，光是移动到有解的一个节点显然是不够的，我们应该采取一种最佳（优）策略，比如：让猫每次移动的节点都是距离边缘路径最短的，当然这样也不是全局最优解，我们甚至可以实现一种必胜策略，在这种策略下人类可能永远也不能围住它。（本文暂不讨论这种可能的实现）

本程序采用的就是局部最优的实现，也就是保证每一步的移动都是最短路径，这样虽然不是真正的最优，但是在一定范围内的实现效果也不是很差。

要找到最短路径，就会涉及到搜索算法了，而游戏中常用的搜索算法不外乎A*寻路、BFS、DFS、启发式搜索、AB剪枝这几大类，这次我们利用的就是BFS的特性来实现最短路径的搜索。（最开始是用DFS实现了，但是发现只能找到一个解，连当前最短都不能保证，所以换为BFS实现）

搜索算法

深度优先搜索

虽然最终采用了BFS来实现最短路径的搜索，但是在实现DFS的过程中让笔者初步认识了搜索时遍历节点的过程，这里也简单介绍一下。

施工ing...

JavaScript 面向对象 算法 Canvas
上一篇文章 下一篇文章