背景
一个朋友请我帮忙在他的手动版贪吃蛇的基础上，改进一个AI贪吃蛇
我查找了一些资料,AI贪吃蛇主要用到的是A星算法
目前的算法比较简单,即计算从蛇头到食物的路径,按路径去移动即可
所以还比较笨,演示如下
代码及博客路径:
算法原理:
Astar算法项目 https://github.com/wangqqiyue/Astar
Astar算法博客 https://www.cnblogs.com/studentWangqy/p/18059817
AI贪吃蛇项目 https://github.com/wangqqiyue/snake_easy
代码解释
//TODO
//解释一下代码为什么这么写
关键点
代码中比较关键的几个点是
优先队列类(PriorityQueue)
节点类和地图类(Node, neibors)
获取路径的函数getPath
PriorityQueue
优先队列的代码是我从网上找的现成的代码
我认为如无必要，勿增实体,既然已经有了现成的经过测试的代码,我没有必要重新写
class PriorityQueue {
constructor(compare) {
if (typeof compare !== "function") {
throw new Error("compare function required!");
}
this.data = [];
this.compare = compare;
this.length = 0;
}
//二分查找 寻找插入位置
search(target) {
let low = 0,
high = this.data.length;
while (low < high) {
let mid = low + ((high - low) >> 1);
if (this.compare(this.data[mid], target) > 0) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
//添加
push(elem) {
// console.log("elem=", elem);
// console.log("data.length=", this.data.length);
let index = this.search(elem);
this.data.splice(index, 0, elem);
// console.log("data.length=", this.data.length);
this.length = this.data.length;
return this.data.length;
}
//取出最优元素
pop() {
// console.log("this.data=", this.data);
// console.log("data.length=", this.data.length);
// for (var i = 0; i < this.data.length; i++) {
// console.log("data[", i, "]=", this.data[i]);
// }
this.length--;
return this.data.pop();
}
//判断是否为空
empty() {
return 0 === this.data.length;
}
}
Map
地图存放了所有地图节点,并且提供了计算指定节点的邻居节点的方法
class Node {
constructor(x, y) {
this.x = x;
this.y = y;
this.g = 0;
this.h = 0;
this.f = 0;
this.open = false;
this.close = false;
this.parent = null;
this.walkable = true;
}
moveToClose() {
this.open = false;
this.close = true;
}
moveToOpen() {
this.open = true;
this.close = false;
}
}
class Map {
constructor() {
//创建二维地图,用于规划贪吃蛇路径
this.mapForAI = new Array(ROWS);
for (var i = 0; i < ROWS; i++) {
this.mapForAI[i] = new Array(COLS);
for (var j = 0; j < COLS; j++) {
this.mapForAI[i][j] = new Node(j, i); //x是COL,y是ROW,别弄错了
}
}
//初始化不可通行节点
snakes.forEach((curr) => {
this.mapForAI[curr.y][curr.x].walkable = false;
});
//console.log(this.mapForAI);
}
getNeibors(center) {
var r, c, i;
var neibors = new Array(NEIBOR_NUM_MAX);
for (i = 0; i < NEIBOR_NUM_MAX; i++) {
neibors[i] = null;
}
r = center.y;
c = center.x;
if (r > 0) neibors[UP] = this.mapForAI[r - 1][c];
if (r < ROWS - 1) neibors[DOWN] = this.mapForAI[r + 1][c];
if (c > 0) neibors[LEFT] = this.mapForAI[r][c - 1];
if (c < COLS - 1) neibors[RIGHT] = this.mapForAI[r][c + 1];
//console.log(neibors);
return neibors;
}
}
getPath
getPath是计算蛇头到食物的路径
这里的代码的结构全部来自我的Astar项目(https://github.com/wangqqiyue/Astar)
//获取从起点到终点的路径,如果存在则返回路径数组，不存在则返回空数组
function getPath(src, dst) {
let havePath = false;
var path = [];
var neibors;
//初始化mapForAI
map = new Map();
//构建优先队列
var openList = new PriorityQueue((n1, n2) => n1.f - n2.f);
//调用A星算法
// console.log("src=", src);
// console.log("dst=", dst);
var current = map.mapForAI[src.y][src.x];
// console.log("current=", current);
openList.push(current);
current.moveToOpen();
while (false === openList.empty()) {
// console.log("openList=", openList);
current = openList.pop();
// console.log("current=", current);
current.moveToClose();
if (current.x === dst.x && current.y === dst.y) {
havePath = true;
break;
}
neibors = map.getNeibors(current);
for (i = 0; i < NEIBOR_NUM_MAX; i++) {
if (
null === neibors[i] ||
false === neibors[i].walkable ||
true === neibors[i].close
) {
continue;
}
if (false === neibors[i].open) {
neibors[i].g = getManhattan(neibors[i], src);
neibors[i].h = getManhattan(neibors[i], dst);
neibors[i].f = neibors[i].g + neibors[i].h;
neibors[i].moveToOpen();
neibors[i].parent = current;
// console.log("neibors[i]=", neibors[i]);
openList.push(neibors[i]);
// console.log("openList=", openList);
} else if (true === neibors[i].open) {
g = getManhattan(neibors[i], current) + neibors[i].g;
if (g < neibors[i].g) {
neibors[i].g = g;
neibors[i].f = neibors[i].g + neibors[i].h;
neibors[i].parent = current;
}
}
}
}
// console.log("havePath=", havePath);
//返回路径数组
if (havePath) {
current = map.mapForAI[dst.y][dst.x];
while (null != current.parent) {
path.unshift(current);
current = current.parent;
}
}
drawPath(path);
return path;
}
调试过程记录
javascript
这个项目原型代码是html的,算法实现是使用javascript
我对javascript其实并不熟悉
还学习了一下
学习javascript记录:
javascript中的函数式编程 https://www.cnblogs.com/studentWangqy/p/18086252
在VSCode调试js代码 https://blog.csdn.net/qq_42235030/article/details/112801656
有调试功能是真的很方便,帮我发现了好几处错误,比如x和y分别对应的应该是col和row
