JS/HTML5游戲常用算法之路徑搜索算法隨機迷宮算法詳解【普里姆算法】

更新時間：2018年12月13日 10:03:52 作者：krapnik

這篇文章主要介紹了JS/HTML5游戲常用算法之路徑搜索算法隨機迷宮算法,結(jié)合實例形式詳細分析了針對迷宮游戲路徑搜索算法的普里姆算法相關(guān)原理、實現(xiàn)方法及操作注意事項,需要的朋友可以參考下

本文實例講述了JS/HTML5游戲常用算法之路徑搜索算法隨機迷宮算法。分享給大家供大家參考，具體如下：

路徑搜索算法在游戲中非常常見，特別是在 RPG、SLG 中經(jīng)常用到。在這些游戲中，通過鼠標指定行走目的地，人物或者NPC就會自動行走到目標地點，這就是通過路徑搜索或者稱為尋路算法來實現(xiàn)的。通俗地說，就是在一張地圖中，如何讓主角自動行走到指定的地點，如圖6-21所示，假設(shè)主角在A處，然后玩家在地圖中點擊B處，要求主角能夠從A點自動找尋一條到 B 點的路徑，然后自動移動到 B處，要求就這么簡單。

在前面的碰撞檢測算法中，我們提到，現(xiàn)在的游戲中的地圖一般采用格子的方式，雖然表面地圖上無法看到實際的格子，但在地圖的結(jié)構(gòu)中專門有一個邏輯層，這個層和地圖大小等大，劃分出很多小的格子，然后在可以通過的地方使用0表示，有障礙的且不能通過的地方使用 1 或其他數(shù)字表示。如下圖所示，左邊的游戲中的地圖，程序中會以右邊的一個二維數(shù)組保存一個邏輯層，專門用來設(shè)定障礙。有了這個邏輯層之后，實際上自動尋路就轉(zhuǎn)化成了，如何在一個二維的數(shù)組中找到一條從邏輯值為 0 的地點移動到目標地點的路徑。

在介紹如何使用自動尋路算法前，我們先來看另外一個游戲常用的算法，即隨機產(chǎn)生地圖（迷宮）算法，用于結(jié)合尋路算法。

【隨機迷宮算法】

根據(jù)前面的地圖的理論，本質(zhì)上，地圖的障礙邏輯層是由一個二維數(shù)組保存，障礙標記在二維數(shù)組中的數(shù)據(jù)值以0或1表示，我們需要做的就是隨機產(chǎn)生這個二維的數(shù)組。當然，最簡單的辦法就是循環(huán)這個二維數(shù)組然后在每一個位置隨機地產(chǎn)生 0 或者 1，但這種算法產(chǎn)生的圖形比較難看，并且不一定保證圖中的任意兩點可以相連通。

（1）下圖所示為一個6×6的迷宮，先假設(shè)迷宮中所有的通路都是完全封閉的，白色的格子表示可以通過，黑色的表示墻壁，表示無法通過。

（2）隨機選擇一個白色的格子作為當前正在訪問的格子，同時，把該格子放進一個表示已經(jīng)訪問的列表。

（3）循環(huán)以下操作直到所有的格子都被訪問。

得到當前訪問格子四周（上、下、左、右）的格子，在這些格子中隨機選擇一個沒有在訪問列表中的格子，如果找到，則把該格子和當前訪問格子中間的墻"打通"置0，把該格子作為當前訪問的格子，并放入訪問列表。
如果周圍所有的格子都已訪問過，則從已訪問列表中隨機選取一個作為當前訪問的格子。

通過以上的迷宮生成算法，可以生成一個自然隨機的迷宮。

下面的代碼根據(jù)以上的算法將產(chǎn)生一個R行N列大小的迷宮，需要注意的是R行表示的是剛開始空白格子的行數(shù)，由于要算上墻壁的數(shù)據(jù)，最終產(chǎn)生二維數(shù)組實際上的的行數(shù)為2R+1，列數(shù)為2N+1：

<!DOCTYPE html>
<html lang="en">
<head>
  <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0">
  <meta charset="UTF-8">
  <title>01_隨機迷宮算法</title>
  <style>
    #stage {
      border: 1px solid lightgray;
    }
    .rebuild{
      width:160px;
      height:40px;
      line-height: 40px;
      text-align: center;
      background-color:#000000;
      color:#fff;
      font-size: 24px;
      margin-bottom: 20px;
      cursor: pointer;
    }
  </style>
</head>
<body>
<div class="rebuild">點擊更新</div>
<canvas id="stage"></canvas>
</body>
<script>
  window.onload = function () {
    var stage = document.querySelector('#stage'),
      ctx = stage.getContext('2d');
    stage.width = 600;
    stage.height = 600;
    //取區(qū)域隨機數(shù)x>=min && x<max
    function randInt(min,max)
    {
      max=max||0;
      min=min||0;
      var step=Math.abs(max-min);
      var st = (arguments.length<2)?0:min;//參數(shù)只有一個的時候，st = 0;
      var result ;
      result = st+(Math.ceil(Math.random()*step))-1;
      return result;
    }
    //普里姆算法生成連通圖的二維數(shù)組
    // row 行 column 列
    function primMaze(r, c) {
      //初始化數(shù)組
      function init(r, c) {
        var a = new Array(2 * r + 1);
        //全部置1
        for (let i = 0, len = a.length; i < len; i++) {
          var cols = 2 * c + 1;
          a[i] = new Array(cols);
          for(let j=0,len1=a[i].length;j<len1;j++)
          {
            a[i][j]=1;
          }
        }
        //中間格子為0
        for (let i = 0; i < r; i++)
          for (let j = 0; j < c; j++) {
            a[2 * i + 1][2 * j + 1] = 0;
          }
        return a;
      }
      //處理數(shù)組，產(chǎn)生最終的數(shù)組
      function process(arr) {
        //acc存放已訪問隊列，noacc存放沒有訪問隊列
        var acc = [], noacc = [];
        var r = arr.length >> 1, c = arr[0].length >> 1;
        var count = r * c;
        for (var i = 0; i < count; i++) {
          noacc[i] = 0;
        }
        //定義空單元上下左右偏移
        var offs = [-c, c, -1, 1], offR = [-1, 1, 0, 0], offC = [0, 0, -1, 1];
        //隨機從noacc取出一個位置
        var pos = randInt(count);
        noacc[pos] = 1;
        acc.push(pos);
        while (acc.length < count) {
          var ls = -1, offPos = -1;
          offPos = -1;
          //找出pos位置在二維數(shù)組中的坐標
          var pr = pos / c | 0, pc = pos % c, co = 0, o = 0;
          //隨機取上下左右四個單元
          while (++co < 5) {
            o = randInt(0, 5);
            ls = offs[o] + pos;
            var tpr = pr + offR[o];
            var tpc = pc + offC[o];
            if (tpr >= 0 && tpc >= 0 && tpr <= r - 1 && tpc <= c - 1 && noacc[ls] == 0) {
              offPos = o;
              break;
            }
          }
          if (offPos < 0) {
            pos = acc[randInt(acc.length)];
          }
          else {
            pr = 2 * pr + 1;
            pc = 2 * pc + 1;
            //相鄰空單元中間的位置置0
            arr[pr + offR[offPos]][pc + offC[offPos]] = 0;
            pos = ls;
            noacc[pos] = 1;
            acc.push(pos);
          }
        }
      }
      var a = init(r, c);
      process(a);
      return a;
      //返回一個二維數(shù)組，行的數(shù)據(jù)為2r+1個,列的數(shù)據(jù)為2c+1個
    }
    //柵格線條
    function drawGrid(context, color, stepx, stepy) {
      context.strokeStyle = color;
      context.lineWidth = 0.5;
      for (var i = stepx + 0.5; i < context.canvas.width; i += stepx) {
        context.beginPath();
        context.moveTo(i, 0);
        context.lineTo(i, context.canvas.height);
        context.stroke();
      }
      for (var i = stepy + 0.5; i < context.canvas.height; i += stepy) {
        context.beginPath();
        context.moveTo(0, i);
        context.lineTo(context.canvas.width, i);
        context.stroke();
      }
    }
    function createRect(x, y, r, c) {
      ctx.beginPath();
      ctx.fillStyle = c;
      ctx.rect(x, y, r, r);
      ctx.fill();
    }
    function update() {
      ctx.clearRect(0, 0, 600, 600);
      drawGrid(ctx, 'lightgray', 40, 40);
      var mapArr = primMaze(7,7);
      console.log(mapArr);
      //根據(jù)地圖二維數(shù)組創(chuàng)建色塊
      for (var i = 0, len = mapArr.length; i < len; i++) {
        for (var j = 0, len1 = mapArr[i].length; j < len1; j++) {
          if (mapArr[i][j]) {
            createRect(i * 40, j * 40, 40, "black");
          }
        }
      }
    }
    update();
    document.querySelector('.rebuild').addEventListener('click', update);
  };
</script>
</html>

這里使用在線HTML/CSS/JavaScript代碼運行工具：http://tools.jb51.net/code/HtmlJsRun 測試上述代碼運行效果如下：