JS/HTML5游戲常用算法之路徑搜索算法 A*尋路算法完整實(shí)例
更新時(shí)間：2018年12月14日 09:44:16 作者：krapnik
這篇文章主要介紹了JS/HTML5游戲常用算法之路徑搜索算法 A*尋路算法,結(jié)合完整實(shí)例形式分析了A*尋路算法的具體實(shí)現(xiàn)技巧,代碼備有詳盡的注釋便于理解,需要的朋友可以參考下
本文實(shí)例講述了JS/HTML5游戲常用算法之路徑搜索算法 A*尋路算法。分享給大家供大家參考，具體如下：
原理可參考：http://www.dhdzp.com/article/152744.htm
完整實(shí)例代碼如下：
<!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>A*尋路算法</title>
<style>
#stage {
border: 1px solid lightgray;
}
</style>
</head>
<body>
<canvas id="stage"></canvas>
</body>
<script>
window.onload = function () {
var stage = document.querySelector('#stage'),
ctx = stage.getContext('2d');
stage.width = 600;
stage.height = 600;
var row = 7, column = 7, r = 40;
//取區(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存放已訪問隊(duì)列，noacc存放沒有訪問隊(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();
}
}
//方塊創(chuàng)造方法
function createRect(x, y, r, c) {
ctx.beginPath();
ctx.fillStyle = c;
ctx.rect(x, y, r, r);
ctx.fill();
}
//定義點(diǎn)對(duì)象【a*點(diǎn)對(duì)象】
function Point(x, y) {
this.x = x;
this.y = y;
this.parent = null;
this.f = 0;
this.g = 0;
this.h = 0;
//當(dāng)前點(diǎn)狀態(tài)，0：表示在openlist 1:表示closelist,-1表示還沒處理
this.state = -1;
//flag表明該點(diǎn)是否可通過
this.flag = 0;
}
//把普通二維數(shù)組(全部由1，0表示)的轉(zhuǎn)換成a*所需要的點(diǎn)數(shù)組
function convertArrToAS(arr) {
var r = arr.length, c = arr[0].length;
var a = new Array(r);
for (var i = 0; i < r; i++) {
a[i] = new Array(c);
for (var j = 0; j < c; j++) {
var pos = new Point(i, j);
pos.flag = arr[i][j];
a[i][j] = pos;
}
}
return a;
}
//A*算法,pathArr表示最后返回的路徑
function findPathA(pathArr, start, end, row, col) {
//添加數(shù)據(jù)到排序數(shù)組中
function addArrSort(descSortedArr, element, compare) {
var left = 0;
var right = descSortedArr.length - 1;
var mid = (left + right) >> 1;
while (left <= right) {
var mid = (left + right) >> 1;
if (compare(descSortedArr[mid], element) == 1) {
left = mid + 1;
}
else if (compare(descSortedArr[mid], element) == -1) {
right = mid - 1;
}
else {
break;
}
}
for (var i = descSortedArr.length - 1; i >= left; i--) {
descSortedArr[i + 1] = descSortedArr[i];
}
descSortedArr[left] = element;
}
//判斷兩個(gè)點(diǎn)是否相同
function pEqual(p1, p2) {
return p1.x == p2.x && p1.y == p2.y;
}
//獲取兩個(gè)點(diǎn)距離，采用曼哈頓方法
function posDist(pos, pos1) {
return (Math.abs(pos1.x - pos.x) + Math.abs(pos1.y - pos.y));
}
function between(val, min, max) {
return (val >= min && val <= max)
}
//比較兩個(gè)點(diǎn)f值大小
function compPointF(pt1, pt2) {
return pt1.f - pt2.f;
}
//處理當(dāng)前節(jié)點(diǎn)
function processCurrpoint(arr, openList, row, col, currPoint, destPoint) {
//get up,down,left,right direct
var ltx = currPoint.x - 1;
var lty = currPoint.y - 1;
for (var i = 0; i < 3; i++){
for (var j = 0; j < 3; j++) {
var cx = ltx + i;
var cy = lty + j;
if ((cx === currPoint.x || cy === currPoint.y) && between(ltx, 0, row - 1) && between(lty, 0, col - 1)) {
var tp = arr[cx][cy];
if (tp.flag === 0 && tp.state !== 1) {
if (pEqual(tp, destPoint)) {
tp.parent = currPoint;
return true;
}
if (tp.state === -1) {
tp.parent = currPoint;
tp.g = 1 + currPoint.g;
tp.h = posDist(tp, destPoint);
tp.f = tp.h + tp.f;
tp.state = 0;
addArrSort(openList, tp, compPointF);
}
else {
var g = 1 + currPoint.g;
if (g < tp.g) {
tp.parent = currPoint;
tp.g = g;
tp.f = tp.g + tp.h;
openList.quickSort(compPointF);
}
}
}
}
}
}
return false;
}
//定義openList
var openList = [];
//定義closeList
var closeList = [];
start = pathArr[start[0]][start[1]];
end = pathArr[end[0]][end[1]];
//添加開始節(jié)點(diǎn)到openList;
addArrSort(openList, start, compPointF);
var finded = false;
while ((openList.length > 0)) {
var currPoint = openList.pop();
currPoint.state = 1;
closeList.push(currPoint);
finded = processCurrpoint(pathArr, openList, row, col, currPoint, end);
if (finded) {
break;
}
}
if (finded) {
var farr = [];
var tp = end.parent;
farr.push(end);
while (tp != null) {
farr.push(tp);
tp = tp.parent;
}
return farr;
}
else {
return null;
}
}
//定位屏幕坐標(biāo)到數(shù)組位置
function mapSCPos(i, j) {
return [i / r | 0, j / r | 0];
}
//檢測(cè)數(shù)組中的位置是否存在方塊
function mapHasRect(map, i, j) {
return (map[i][j]);
}
var mapArr = primMaze(row, column);
var startRect = {
x: function () {
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]) {
return j * r;
break;
}
}
}
}(),
y: function () {
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]) {
return i * r;
break;
}
}
}
}(),
pos: function () {
return [this.x, this.y];
}
},
endRect = {
hasCreate:false,
x:null,
y:null,
pos: function () {
return [this.x, this.y];
}
},
startPoint = mapSCPos(startRect.pos()[1], startRect.pos()[0]),
endPoint,
path = null,
next = null;
//計(jì)算路經(jīng)
function update() {
ctx.clearRect(0, 0, 600, 600);
drawGrid(ctx, 'lightgray', r, r);
//根據(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(j * r, i * r, r, "black");
}
}
}
//繪制開始方塊
createRect(startRect.x, startRect.y, r, "red");
if (endRect.hasCreate) {
//繪制跟隨方塊
createRect(endRect.pos()[0], endRect.pos()[1], r, "blue");
endPoint = mapSCPos(endRect.pos()[1], endRect.pos()[0]);
if(path === null){
var ASmap = convertArrToAS(mapArr);
path = findPathA(ASmap, startPoint, endPoint, ASmap.length, ASmap.length);
}else{
next = path.pop();
startRect.y = next.x * r;
startRect.x = next.y * r;
if(path.length===0){
startPoint = mapSCPos(startRect.pos()[1], startRect.pos()[0]);
path = null;
endRect.hasCreate = false;
}
}
}
requestAnimationFrame(update);
}
update();
stage.addEventListener('click', function () {
//標(biāo)準(zhǔn)的獲取鼠標(biāo)點(diǎn)擊相對(duì)于canvas畫布的坐標(biāo)公式
var x = event.clientX - stage.getBoundingClientRect().left,
y = event.clientY - stage.getBoundingClientRect().top;
var endRectPos = mapSCPos(y, x);//[i,j]
endRect.x = endRectPos[1]*r;
endRect.y = endRectPos[0]*r;
if (mapHasRect(mapArr, endRectPos[0], endRectPos[1])) {
console.log('這個(gè)位置已經(jīng)有方塊啦！');
} else {
endRect.pos();
endRect.hasCreate = true;
}
})
};
</script>
</html>
使用在線HTML/CSS/JavaScript代碼運(yùn)行工具：http://tools.jb51.net/code/HtmlJsRun，測(cè)試運(yùn)行上述代碼，可得到如下運(yùn)行效果：
更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)組操作技巧總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)》
希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。
您可能感興趣的文章:
- 解決Vue項(xiàng)目打包后打開index.html頁面顯示空白以及圖片路徑錯(cuò)誤的問題
- JS/HTML5游戲常用算法之路徑搜索算法 隨機(jī)迷宮算法詳解【普里姆算法】
- Python基于lxml模塊解析html獲取頁面內(nèi)所有葉子節(jié)點(diǎn)xpath路徑功能示例
- nginx配置訪問圖片路徑以及html靜態(tài)頁面的調(diào)取方法
- 如何使用php腳本給html中引用的js和css路徑打上版本號(hào)
- python輸出當(dāng)前目錄下index.html文件路徑的方法
- asp.net獲取HTML表單File中的路徑的方法
- C#正則表達(dá)式匹配HTML中的圖片路徑，圖片地址代碼
- HTML 絕對(duì)路徑與相對(duì)路徑概念詳細(xì)
相關(guān)文章
JavaScript中去掉數(shù)組中的重復(fù)值的實(shí)現(xiàn)方法
百度面試時(shí)問的一道題目，蠻常規(guī)的，但是當(dāng)時(shí)自己的回答挺差勁的。現(xiàn)在總結(jié)記錄下~2011-08-08
基于javascript canvas實(shí)現(xiàn)五子棋游戲
這篇文章主要介紹了基于javascript canvas實(shí)現(xiàn)的五子棋游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-07-07
javascript實(shí)現(xiàn)移動(dòng)端輪播圖
這篇文章主要為大家詳細(xì)介紹了javascript實(shí)現(xiàn)移動(dòng)端輪播圖，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-12-12
雖然js是基于對(duì)象的，但在很多時(shí)候會(huì)使用到new這個(gè)操作符。2010-12-12
這篇文章主要為大家詳細(xì)介紹了js實(shí)現(xiàn)拖拽元素選擇和刪除，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-08-08
前面已經(jīng)講解了 引用，函數(shù)重載，作用域和上下文，接下來，講解JavaScript中另一個(gè)重要的知識(shí)——閉包。2009-09-09
這篇文章主要介紹了javascript事件冒泡實(shí)原理,實(shí)例分析了事件冒泡的定義及實(shí)現(xiàn)技巧,需要的朋友可以參考下2015-05-05
使用js實(shí)現(xiàn)按鈕控制文本框加1減1應(yīng)用于小時(shí)+分鐘
正如標(biāo)題所言使用js實(shí)現(xiàn)按鈕控制文本框加1減1，此類主要應(yīng)用于小時(shí)+分鐘，下面有個(gè)不錯(cuò)的示例，喜歡的朋友可以參考下2013-12-12
bootstrap精簡教程_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理
這篇文章主要介紹了bootstrap精簡教程，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-07-07
Google (Local) Search API的簡單使用介紹
這篇文章主要介紹了Google (Local) Search API的簡單使用。需要的朋友可以過來參考下，希望對(duì)大家有所幫助2013-11-11