快捷導(dǎo)航

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

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

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

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

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

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

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

【隨機(jī)迷宮算法】

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

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

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

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

得到當(dāng)前訪問(wèn)格子四周（上、下、左、右）的格子，在這些格子中隨機(jī)選擇一個(gè)沒(méi)有在訪問(wèn)列表中的格子，如果找到，則把該格子和當(dāng)前訪問(wèn)格子中間的墻"打通"置0，把該格子作為當(dāng)前訪問(wèn)的格子，并放入訪問(wèn)列表。
如果周?chē)械母褡佣家言L問(wèn)過(guò)，則從已訪問(wèn)列表中隨機(jī)選取一個(gè)作為當(dāng)前訪問(wèn)的格子。

通過(guò)以上的迷宮生成算法，可以生成一個(gè)自然隨機(jī)的迷宮。

下面的代碼根據(jù)以上的算法將產(chǎn)生一個(gè)R行N列大小的迷宮，需要注意的是R行表示的是剛開(kāi)始空白格子的行數(shù)，由于要算上墻壁的數(shù)據(jù)，最終產(chǎn)生二維數(shù)組實(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_隨機(jī)迷宮算法</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">點(diǎn)擊更新</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ū)域隨機(jī)數(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ù)只有一個(gè)的時(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存放已訪問(wèn)隊(duì)列，noacc存放沒(méi)有訪問(wèn)隊(duì)列
        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];
        //隨機(jī)從noacc取出一個(gè)位置
        var pos = randInt(count);
        noacc[pos] = 1;
        acc.push(pos);
        while (acc.length < count) {
          var ls = -1, offPos = -1;
          offPos = -1;
          //找出pos位置在二維數(shù)組中的坐標(biāo)
          var pr = pos / c | 0, pc = pos % c, co = 0, o = 0;
          //隨機(jī)取上下左右四個(gè)單元
          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;
      //返回一個(gè)二維數(shù)組，行的數(shù)據(jù)為2r+1個(gè),列的數(shù)據(jù)為2c+1個(gè)
    }
    //柵格線條
    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代碼運(yùn)行工具：http://tools.jb51.net/code/HtmlJsRun 測(cè)試上述代碼運(yùn)行效果如下：