本文實例講述了JS/HTML5游戲常用算法之路徑搜索算法 隨機迷宮算法。分享給大家供大家參考，具體如下：
路徑搜索算法在游戲中非常常見，特別是在 RPG、SLG 中經常用到。在這些游戲中，通過鼠標指定行走目的地，人物或者NPC就會自動行走到目標地點，這就是通過路徑搜索或者稱為尋路算法來實現的。通俗地說，就是在一張地圖中，如何讓主角自動行走到指定的地點，如圖6-21所示，假設主角在A處，然后玩家在地圖中點擊B處，要求主角能夠從A點自動找尋一條到 B 點的路徑，然后自動移動到 B處，要求就這么簡單。
在前面的碰撞檢測算法中，我們提到，現在的游戲中的地圖一般采用格子的方式，雖然表面地圖上無法看到實際的格子，但在地圖的結構中專門有一個邏輯層，這個層和地圖大小等大，劃分出很多小的格子，然后在可以通過的地方使用0表示，有障礙的且不能通過的地方使用 1 或其他數字表示。如下圖所示，左邊的游戲中的地圖，程序中會以右邊的一個二維數組保存一個邏輯層，專門用來設定障礙。有了這個邏輯層之后，實際上自動尋路就轉化成了，如何在一個二維的數組中找到一條從邏輯值為 0 的地點移動到目標地點的路徑。
在介紹如何使用自動尋路算法前，我們先來看另外一個游戲常用的算法，即隨機產生地圖（迷宮）算法，用于結合尋路算法。
【隨機迷宮算法】
根據前面的地圖的理論，本質上，地圖的障礙邏輯層是由一個二維數組保存，障礙標記在二維數組中的數據值以0或1表示，我們需要做的就是隨機產生這個二維的數組。當然，最簡單的辦法就是循環這個二維數組然后在每一個位置隨機地產生 0 或者 1，但這種算法產生的圖形比較難看，并且不一定保證圖中的任意兩點可以相連通。
（1）下圖所示為一個6×6的迷宮，先假設迷宮中所有的通路都是完全封閉的，白色的格子表示可以通過，黑色的表示墻壁，表示無法通過。
（2）隨機選擇一個白色的格子作為當前正在訪問的格子，同時，把該格子放進一個表示已經訪問的列表。
（3）循環以下操作直到所有的格子都被訪問。
通過以上的迷宮生成算法，可以生成一個自然隨機的迷宮。
下面的代碼根據以上的算法將產生一個R行N列大小的迷宮，需要注意的是R行表示的是剛開始空白格子的行數，由于要算上墻壁的數據，最終產生二維數組實際上的的行數為2R+1，列數為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;
//取區域隨機數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;//參數只有一個的時候，st = 0;
var result ;
result = st+(Math.ceil(Math.random()*step))-1;
return result;
}
//普里姆算法生成連通圖的二維數組
// row 行 column 列
function primMaze(r, c) {
//初始化數組
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;
}
//處理數組，產生最終的數組
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位置在二維數組中的坐標
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;
//返回一個二維數組，行的數據為2r+1個,列的數據為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);
//根據地圖二維數組創建色塊
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 測試上述代碼運行效果如下：
github地址：https://github.com/krapnikkk/JS-gameMathematics
更多關于JavaScript相關內容感興趣的讀者可查看本站專題：《JavaScript數學運算用法總結》、《JavaScript數據結構與算法技巧總結》、《JavaScript數組操作技巧總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調試技巧總結》
希望本文所述對大家JavaScript程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
