JS/HTML5游戲常用算法之路徑搜索算法 隨機迷宮算法詳解【普里姆算法】
本文實例講述了JS/HTML5游戲常用算法之路徑搜索算法 隨機迷宮算法。分享給大家供大家參考，具體如下：
路徑搜索算法在游戲中非常常見，特別是在 RPG、SLG 中經(jīng)常用到。在這些游戲中，通過鼠標(biāo)指定行走目的地，人物或者NPC就會自動行走到目標(biāo)地點，這就是通過路徑搜索或者稱為尋路算法來實現(xiàn)的。通俗地說，就是在一張地圖中，如何讓主角自動行走到指定的地點，如圖6-21所示，假設(shè)主角在A處，然后玩家在地圖中點擊B處，要求主角能夠從A點自動找尋一條到 B 點的路徑，然后自動移動到 B處，要求就這么簡單。
在前面的碰撞檢測算法中，我們提到，現(xiàn)在的游戲中的地圖一般采用格子的方式，雖然表面地圖上無法看到實際的格子，但在地圖的結(jié)構(gòu)中專門有一個邏輯層，這個層和地圖大小等大，劃分出很多小的格子，然后在可以通過的地方使用0表示，有障礙的且不能通過的地方使用 1 或其他數(shù)字表示。如下圖所示，左邊的游戲中的地圖，程序中會以右邊的一個二維數(shù)組保存一個邏輯層，專門用來設(shè)定障礙。有了這個邏輯層之后，實際上自動尋路就轉(zhuǎn)化成了，如何在一個二維的數(shù)組中找到一條從邏輯值為 0 的地點移動到目標(biāo)地點的路徑。
在介紹如何使用自動尋路算法前，我們先來看另外一個游戲常用的算法，即隨機產(chǎn)生地圖（迷宮）算法，用于結(jié)合尋路算法。
【隨機迷宮算法】
根據(jù)前面的地圖的理論，本質(zhì)上，地圖的障礙邏輯層是由一個二維數(shù)組保存，障礙標(biāo)記在二維數(shù)組中的數(shù)據(jù)值以0或1表示，我們需要做的就是隨機產(chǎn)生這個二維的數(shù)組。當(dāng)然，最簡單的辦法就是循環(huán)這個二維數(shù)組然后在每一個位置隨機地產(chǎn)生 0 或者 1，但這種算法產(chǎn)生的圖形比較難看，并且不一定保證圖中的任意兩點可以相連通。
（1）下圖所示為一個6×6的迷宮，先假設(shè)迷宮中所有的通路都是完全封閉的，白色的格子表示可以通過，黑色的表示墻壁，表示無法通過。
（2）隨機選擇一個白色的格子作為當(dāng)前正在訪問的格子，同時，把該格子放進一個表示已經(jīng)訪問的列表。
（3）循環(huán)以下操作直到所有的格子都被訪問。
- 得到當(dāng)前訪問格子四周（上、下、左、右）的格子，在這些格子中隨機選擇一個沒有在訪問列表中的格子，如果找到，則把該格子和當(dāng)前訪問格子中間的墻"打通"置0，把該格子作為當(dāng)前訪問的格子，并放入訪問列表。
- 如果周圍所有的格子都已訪問過，則從已訪問列表中隨機選取一個作為當(dāng)前訪問的格子。
通過以上的迷宮生成算法，可以生成一個自然隨機的迷宮。
下面的代碼根據(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ù)組中的坐標(biāo)
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 測試上述代碼運行效果如下：
github地址：https://github.com/krapnikkk/JS-gameMathematics
更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)學(xué)運算用法總結(jié)》、《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)組操作技巧總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯誤與調(diào)試技巧總結(jié)》
希望本文所述對大家JavaScript程序設(shè)計有所幫助。
相關(guān)文章
在VSCode中進行JavaScript調(diào)試的詳細流程
在JavaScript開發(fā)中,調(diào)試是一個關(guān)鍵的過程,它幫助我們理解和修復(fù)代碼中的問題,Visual Studio Code（VSCode）以其豐富的擴展和內(nèi)置調(diào)試工具,為JavaScript開發(fā)者提供了強大的支持,本文將詳細介紹如何在VSCode中進行JavaScript調(diào),需要的朋友可以參考下2024-07-07
這篇文章主要為大家詳細介紹了微信小程序?qū)崿F(xiàn)搜索框功能，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
用于節(jié)點操作的API，顛覆原生操作HTML DOM節(jié)點的API
敏捷開發(fā)是一種以人為核心、迭代、循序漸進的開發(fā)方法。在敏捷開發(fā)中，軟件項目的構(gòu)建被切分成多個子項目，各個子項目的成果都經(jīng)過測試，具備集成和可運行的特征。2010-12-12
這篇文章主要介紹了一個完美的bootstrap分頁查詢，如何利用bootstrap實現(xiàn)分頁查詢，本文將為大家進行揭曉2015-12-12
本文將利用微信小程序制作一個簡易的圖片處理小工具（自制低配版美圖秀秀），有濾鏡、效果圖和動態(tài)濾鏡三個功能，快跟隨小編一起學(xué)習(xí)學(xué)習(xí)吧2022-06-06
這篇文章主要為大家詳細介紹了js實現(xiàn)滑塊區(qū)間組件，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-01-01
這篇文章主要介紹了Bootstrap實現(xiàn)的表格合并單元格,涉及bootstrap界面布局相關(guān)操作技巧,需要的朋友可以參考下2018-02-02
