贪吃蛇自动寻路的尝试


相信大家都对贪吃蛇这个小游戏不陌生吧，那么怎么才能让贪吃蛇吃满全屏呢，通过什么算法可以做到呢，现在让我们来探讨一下。

前提准备

先通过JavaScript写一个贪吃蛇小游戏，一个非常简单的界面，红色为小蛇的头。效果如下：
image.png

过程分析

如果让小蛇吃满屏，大致可以分为以下几种情况：
1、image.png ，小蛇可以吃到食物，并且吃到食物后没有危险，那么就采取最短路径去吃食物。
2、image.png， 小蛇可以吃到食物，但吃到食物后会有危险，那么就采取最短路径去追尾巴。
3、 image.png，小蛇无法吃到食物，但可以追尾巴，那么就采取最远路径去追尾巴。
4、 image.png，小蛇无法吃到食物，也无法追尾巴，那么就按最远路径填补可以通过的空间（一般这种情况可以避免）。

具体算法

现在来完成如何找到最短路径，对此采用BFS算法搜索最短路径
部分代码如下：

  1. //BFS算法寻找最近路径,吃到食物后才再次计算，取消了每步都计算运算量太大的弊端
  2. this.findShortPath = function (snake,aim) {
  3.     let head = snake.body[0];
  4.     let queue = [];//记录搜索节点
  5.     let visited = [];// 记录访问过的节点
  6.     let visitedPath = [];//记录访问过的路径
  7.     if (snake.shortPath.length === 0){
  8.         queue.push(head);//从贪吃蛇的头开始搜索
  9.         while (queue.length !== 0) {
  10.             let n = queue.shift();//取出队首
  11.             if (n.X === aim.X && n.Y === aim.Y) {
  12.                 //如果搜到了食物，开始解析路径
  13.                 let state = aim;
  14.                 while (state !== null && state !== head) {
  15.                     snake.shortPath.push(state);//将目标节点加入最短路径
  16.                     for (let i = 0;i < visitedPath.length;i++){
  17.                         if (state.X === visitedPath[i][0].X && state.Y === visitedPath[i][0].Y){
  18.                             state = visitedPath[i][1];//将目标节点指向上一步节点
  19.                             break;
  20.                         }
  21.                     }
  22.                 }
  23.                 if (snake.shortPath.length === 0){
  24.                     snake.shortPath.push(state);
  25.                 }
  26.                 break;
  27.             }
  28.             let posUp = new Position(n.X, n.Y - 1);
  29.             let posDown = new Position(n.X, n.Y + 1);
  30.             let posLeft = new Position(n.X - 1, n.Y);
  31.             let posRight = new Position(n.X + 1, n.Y);
  32.             let death = Object.assign([],snake.body);
  33.             death.pop();
  34.             //判断搜索节点的四周是否可行或已访问
  35.             if (!snake.contains(death,posUp) && !snake.contains(visited,posUp)
  36.                 && !snake.knockWall(posUp)) {
  37.                 queue.push(posUp);//将节点加入搜索队列
  38.                 visited.push(posUp);//将节点加入已访问组
  39.                 visitedPath.push([posUp,n]);//将节点与搜索节点的路径加入路径组
  40.             }
  41.             if (!snake.contains(death,posDown) && !snake.contains(visited,posDown)
  42.                 && !snake.knockWall(posDown)) {
  43.                 queue.push(posDown);
  44.                 visited.push(posDown);
  45.                 visitedPath.push([posDown,n]);
  46.             }
  47.             if (!snake.contains(death,posLeft) && !snake.contains(visited,posLeft)
  48.                 && !snake.knockWall(posLeft)) {
  49.                 queue.push(posLeft);
  50.                 visited.push(posLeft);
  51.                 visitedPath.push([posLeft,n]);
  52.             }
  53.             if (!snake.contains(death,posRight) && !snake.contains(visited,posRight)
  54.                 && !snake.knockWall(posRight)) {
  55.                 queue.push(posRight);
  56.                 visited.push(posRight);
  57.                 visitedPath.push([posRight,n]);
  58.             }
  59.         }
  60.     }
  61.     return this.getDirection(snake,snake.shortPath);
  62. };



现在来完成如何找到最远路径，对此采用A*算法搜索最远路径
部分代码如下：

  1. //A*算法寻找最远路径
  2. this.findFarPath = function (snake,aim) {
  3.     let openList = [];
  4.     let closeList = [];
  5.     let visitedPath = [];
  6.     let head = snake.body[0];
  7.     if (snake.farPath.length === 0){
  8.         openList.push(head);// 将开始节点放入开放列表;
  9.         head.F = snake.dis(head,aim);
  10.         while(openList.length !== 0){
  11.             let now = new Position();
  12.             let max = 0;
  13.             //找F值最大的(说明离目标最远),如果有相同我们选的排在后面的也就是最新添加的。
  14.             for(let i = 0;i < openList.length;i++){
  15.                 if(openList[i].F >= max){
  16.                     max = openList[i].F;
  17.                     now = openList[i];
  18.                 }
  19.             }
  20.             // 当终点节点被加入到开放列表作为待检验节点时, 表示路径被找到,此时终止循环,返回方向;
  21.             if (now.X === aim.X && now.Y === aim.Y) {
  22.                 let node = aim;
  23.                 while(node != null && node !== head){
  24.                     snake.farPath.push(node);
  25.                     for (let i = 0;i < visitedPath.length;i++){
  26.                         if (node.X === visitedPath[i][0].X && node.Y === visitedPath[i][0].Y){
  27.                             node = visitedPath[i][1];
  28.                             break;
  29.                         }
  30.                     }
  31.                 }
  32.                 break;
  33.             }
  34.             // 把当前节点从开放列表删除, 加入到封闭列表;
  35.             for(let i = 0;i < openList.length;i++){
  36.                 if(openList[i] === now){
  37.                     openList.splice(i,1);
  38.                 }
  39.             }
  40.             closeList.push(now);
  41.             //四个方向的相邻节点
  42.             let posUp = new Position(now.X, now.Y - 1);
  43.             let posDown = new Position(now.X, now.Y + 1);
  44.             let posLeft = new Position(now.X - 1, now.Y);
  45.             let posRight = new Position(now.X + 1, now.Y);
  46.             let temp = [];
  47.             temp.push(posUp);
  48.             temp.push(posRight);
  49.             temp.push(posDown);
  50.             temp.push(posLeft);
  51.             let death = Object.assign([],snake.body);
  52.             death.pop();
  53.             for (let i = 0;i < 4;i++){
  54.                 let n = temp[i];
  55.                 // 如果该相邻节点不可通行或者该相邻节点已经在封闭列表中,则什么操作也不执行,继续检验下一个节点;
  56.                 if (snake.contains(death,n) || snake.contains(closeList,n)
  57.                     || snake.knockWall(n)) {
  58.                     continue;
  59.                 }
  60.                 // 如果该相邻节点不在开放列表中,则将该节点添加到开放列表中,
  61.                 // 并将该相邻节点的父节点设为当前节点,同时保存该相邻节点的G和H值,F值
  62.                 if(!snake.contains(openList,n)){
  63.                     visitedPath.push([n,now]);
  64.                     n.F = snake.dis(n,aim);
  65.                     openList.push(n);
  66.                 }
  67.                 // 如果该相邻节点在开放列表中,
  68.                 // 则判断若经由当前节点到达该相邻节点的G值是否大于或小于(这里找最远用大于)原来保存的G值,若大于或小于,则将该相邻节点的父节点设为当前节点,并重新设置该相邻节点的G和F值.
  69.                 if (snake.contains(openList,n)) {
  70.                     if (this.dis(n,aim) > now.F) {
  71.                         for (let i = 0;i < visitedPath.length;i++){
  72.                             if (n.X === visitedPath[i][0].X && n.Y === visitedPath[i][0].Y){
  73.                                 visitedPath[i][1] = now;
  74.                                 break;
  75.                             }
  76.                         }
  77.                         n.F = this.dis(n,aim);
  78.                     }
  79.                 }
  80.             }
  81.         }
  82.     }
  83.     return this.getDirection(snake,snake.farPath);
  84. };


结果总结

但由于本人能力不足，寻找最远路径部分还存在缺陷，贪吃蛇无法吃满全屏。最终会出现死循环:image.png，但也有一定几率可以吃满全屏:image.png。

总结，算法有待改进、完善，争取做到贪吃蛇每次都可以吃满全屏。