在学习A算法之前，很好奇的是A为什么叫做A*。在知乎上找到一个回答，大致意思是说，在A算法之前有一种基于启发式探索的方法来提高Dijkstra算法的速度，这个算法叫做A1。后来的改进算法被称为A。*这个符号是从统计文献中借鉴来的，用来表示相对一个旧有标准的最优估计
.
博客图有一篇文章介绍原理：
https://www.cnblogs.com/iwiniwin/p/10793654.html
说有比较通俗易懂，大家参考一下。
游戏效果在我博客这里：https://www.dongee.net/static/a.html 大家可以玩一下。
以下是html5+javascript的代码，大家直接复制到浏览器上就可以运行：
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>游戏自动寻路算法</title>
</head>
<style>
* {
margin: 0;
padding: 0;
}
.map {
margin: 0 auto;
border: 1px solid #aaa;
display: flex;
flex-wrap: wrap;
}
.btn {
width: 100%;
text-align: center;
margin-bottom: 5px;
display: flex;
justify-content: center;
}
.item {
width: 20px;
height: 20px;
display: inline-block;
border: 1px solid #aaa;
color: #eee;
line-height: 20px;
text-align: center;
}
.item-start {
background-color: #f00;
font-weight: bold;
color: #eee;
}
.item-end {
background-color: rgb(103, 243, 47);
font-weight: bold;
color: #eee;
}
.item-block {
background-color: #666;
}
.item-found {
background-color: rgb(248, 89, 89)
}
.item-map {
background-color: #eee;
}
</style>
<body>
<div class="btn">
<div>游戏自动寻路算法</div>
<div style="margin-left: 10px;">
地图行数<input id="txtNumber1" type="number" value="80" max="86" min="20" placeholder="地图行数" />
地图列数<input id="txtNumber2" type="number" value="40" max="42" min="20" placeholder="地图列数" />
障碍出现机率<input id="txtBlock" type="number" value="30" max="100" min="10" placeholder="障碍出现机率" />
<label for="chkDiagonal">是否可以对角走</label><input id="chkDiagonal" type="checkbox" checked />
<button onclick="buildMap()">生成地图</button>
<button onclick="start()">开始寻路</button>
</div>
<!-- <button onclick="reStart()">重新寻路</button> -->
</div>
<div id="dvMap" class="map">
</div>
</body>
<script>
let itemCountX = 0;
let itemCountY = 0;
let itemBlockCount = 0;
let itemWidth = 0;
let itemHeight = 0;
let itemIsDiagonal = true;
let itemX = 0;
let itemTemp = "<div class='item item-map'></div>";
let mapdiv = document.getElementById("dvMap");
let itemData = { i: 0, f: 0, g: 0, h: 0, p: {} };
let itemDatas = [];
let mapData = [];
let openList = [];
let closeList = [];
let startIndex = 0;
let endIndex = 0;
let isFinding = false;
function reset() {
itemCountX = parseInt(document.getElementById("txtNumber1").value);
itemCountY = parseInt(document.getElementById("txtNumber2").value);
itemBlockCount = parseInt(document.getElementById("txtBlock").value);
itemIsDiagonal = document.getElementById("chkDiagonal").checked
itemWidth = 0;
itemHeight = 0;
itemX = 0;
itemDatas = [];
mapData = [];
openList = [];
closeList = [];
startIndex = 0;
endIndex = 0;
mapdiv.innerHTML = "";
isFinding = false;
}
function buildMap(el) {
reset();
if (itemCountX < 20 || itemCountY < 20) {
alert("行列数不要小于20")
return
}
if (itemCountX > 200 || itemCountY > 200) {
alert("行列数不要大于200")
return
}
randomMap();
let count = mapData.length
for (let i = 0; i < count; i++) {
let itemData = { i, f: 0, g: 0, h: 0, p: {} };
let item = document.createElement('div')
item.id = "item" + i
if (mapData[i] == 0) {
item.className = "item item-map";
}
if (mapData[i] == 1) {
item.className = "item item-start";
addOpen(buildItem(i, null))
item.innerText = "入";
}
if (mapData[i] == 2) {
item.className = "item item-end";
item.innerText = "出";
}
if (mapData[i] == 3) {
item.className = "item item-block";
addClose(buildItem(i, null))
}
mapdiv.appendChild(item);
}
let first = mapdiv.getElementsByClassName("item")[0];
itemWidth = first.clientWidth;
itemHeight = first.clientHeight;
itemX = itemWidth + Math.floor(itemWidth / 2);
mapdiv.style.width = itemCountX * (itemWidth + 2) + 'px'
mapdiv.style.height = itemCountY * (itemHeight + 2) + 'px'
}
function randomMap() {
let len = itemCountX * itemCountY
for (let i = 0; i < len; i++) {
let r = randomNum(0, 100)
if (r < itemBlockCount) {
mapData.push(3);
}
else {
mapData.push(0);
}
}
let mid = len / 2;
startIndex = randomNum(0, mid);
endIndex = randomNum(mid, len);
mapData[startIndex] = 1;
mapData[endIndex] = 2;
}
function addOpen(item) {
let ri = openList.findIndex(r => r.i == item.i);
if (ri == -1) {
openList.push(item)
}
}
function removeOpen(item) {
let ri = openList.findIndex(r => r.i == item.i);
if (ri > -1) {
openList.splice(ri, 1)
}
}
function addClose(item) {
let ri = closeList.findIndex(r => r.i == item.i);
if (ri == -1) {
closeList.push(item)
}
}
function getParentLength(w, p) {
return itemCountX
}
function getParentLength2(w, p) {
w = w || 0
let result = w
if (p && p.g) {
result += p.g
}
return result
}
function getH(i) {
let x = Math.abs(endIndex % itemCountX - i % itemCountX)
let y = Math.abs(Math.floor(i / itemCountX) - Math.floor(endIndex / itemCountX))
return x * itemWidth + y * itemHeight;
}
function getAround(i, p) {
let len = itemCountX * itemCountY
let items = [];
let left = i - 1;
let right = i + 1;
let up = i - itemCountX;
let down = i + itemCountX;
let leftup = up - 1
let leftdown = down - 1
let rightup = up + 1
let rightdown = down + 1;
let row = Math.floor(i / itemCountX) + 1
if (left >= 0) {
let tmp = Math.floor(left / itemCountX) + 1;
if (tmp == row) {
items.push(buildItem(left, p, itemWidth));
if (itemIsDiagonal && leftdown <= len) {
items.push(buildItem(leftdown, p, itemX));
}
if (itemIsDiagonal && leftup > 0) {
items.push(buildItem(leftup, p, itemX));
}
}
}
if (right < len) {
let tmp = Math.floor(right / itemCountX) + 1;
if (tmp == row) {
items.push(buildItem(right, p, itemWidth));
if (itemIsDiagonal && rightdown <= len) {
items.push(buildItem(rightdown, p, itemX));
}
if (itemIsDiagonal && rightup > 0) {
items.push(buildItem(rightup, p, itemX));
}
}
}
if (up >= 0) {
items.push(buildItem(up, p, itemWidth));
}
if (down < len) {
items.push(buildItem(down, p, itemWidth));
}
return items;
}
function getFirstItem(items) {
if (items && items.length > 0) {
items = items.sort((n1, n2) => {
return n1.f - n2.f;
});
return items[0]
}
return null
}
function start() {
if (isFinding) {
alert("正在分板路线，请稍等");
}
else {
isFinding = true;
startFind()
}
}
function reStart() {
openList = []
closeList = []
openList.push(buildItem(startIndex, null))
mapData.map((c, i) => {
if (c == 3) {
addClose(buildItem(i, null))
}
})
isFinding = false;
start()
}
function startFind(a) {
a = a || openList[0]
console.log("开始寻找：" + a.i)
let aroundsItems = getAround(a.i, a);
if (aroundsItems.findIndex(r => r.i == endIndex) > -1) {
let item = buildItem(endIndex, a);
console.log("找完路径")
console.log(item);
printPath(item)
isFinding = false;
return
}
for (let c of closeList) {
let v = c.i
let ri = aroundsItems.findIndex(r => r.i == v);
if (ri > -1) {
aroundsItems.splice(ri, 1)
}
}
removeOpen(a)
addClose(a)
if (aroundsItems.length > 0) {
for (let ai of aroundsItems) {
addOpen(ai)
}
}
if (openList.length < 1) {
alert("找不到路径")
isFinding = false;
printPath(a)
return
}
let best = getFirstItem(openList)
startFind(best)
// console.log(best);
// console.log(openList);
// console.log(closeList);
}
function buildItem(i, parent, g) {
if (1 == mapData[i]) {
return { i, f: 0, g: 0, h: 0, p: {} }
}
let item = { i, f: 0, g: 0, h: 0, p: parent }
item.h = getH(i)
item.g = getParentLength2(g, parent)
item.f = item.g + item.h
return item;
}
function printPath(p) {
let result = [];
result.push(p.i)
let p1 = p.p;
while (p1) {
if (p1.i) {
result.push(p1.i)
}
p1 = p1.p
}
// result.reverse()
setTimeout(printDiv, 100, result)
// setTimeout()
// result.map(r => {
// if (mapData[r] == 0) {
// document.getElementById("item" + r).className = "item item-found"
// }
// })
}
function printDiv(result) {
let i = result.pop()
if (i) {
if (i != startIndex && i != endIndex) {
document.getElementById("item" + i).className = "item item-found"
}
setTimeout(printDiv, 50, result)
}
}
function init() {
buildMap();
}
function randomNum(minNum, maxNum) {
switch (arguments.length) {
case 1:
return parseInt(Math.random() * minNum + 1, 10);
break;
case 2:
return parseInt(Math.random() * (maxNum - minNum + 1) + minNum, 10);
break;
default:
return 0;
break;
}
}
function test() {
let items = getAround(parseInt(document.getElementById("txtNumber1").value))
console.log(items);
}
setTimeout(init, 0);
</script>
<script>
// let arr = [2,1,3,5,4];
// arr= arr.sort((n1,n2)=>{
// return n2-n1;
// });
// console.log(arr);
</script>
</html>