A* (A-Star)是一种高效、简洁的寻路算法，它在地图应用和游戏应有中很常见，下面是用aadio语言的实现，抛砖引玉了，希望aardio在AI的加持下，应用场景越来越多！
//A* 寻路算法演示
import win.ui;
import gdip;
/*DSG{{*/
var winform = win.form(text="aardio - A* 寻路算法演示（By: Mr-MAO）";right=640;bottom=680)
winform.add(
btnFind={cls="button";text="开始寻路 (A*)";left=130;top=10;right=230;bottom=40;dl=1;dt=1;z=3};
btnGenMap={cls="button";text="随机生成地图";left=20;top=10;right=120;bottom=40;dl=1;dt=1;z=2};
plusMap={cls="plus";left=10;top=50;right=630;bottom=670;bgcolor=0xFFFFFF;db=1;dl=1;dr=1;dt=1;z=1};
txtInfo={cls="static";text="（绿色: 起点 | 红色: 终点 | 黑色: 墙 | 蓝色: 路径）";left=240;top=16;right=610;bottom=41;center=1;dl=1;dr=1;dt=1;transparent=1;z=4}
)
/*}}*/
import win.ui.minmax;
win.ui.minmax(winform, 500, 500);
// ---------------------------------------------------------
// A* 算法核心类
// ---------------------------------------------------------
class AStar {
ctor( mapData, width, height ){
this.map = mapData;
this.width = width;
this.height = height;
}
// 计算曼哈顿距离 H
getH = function(node, endNode){
return ..math.abs(node.x - endNode.x) + ..math.abs(node.y - endNode.y);
}
// 查找路径
findPath = function(startP, endP){
var openList = {}; // 待考察列表
var closedList = {}; // 已考察列表
// 辅助函数：生成由于坐标组成的唯一key
var getKey = function(x,y){ return x + "," + y; }
// 将起点加入 openList
var startNode = {x=startP.x; y=startP.y; g=0; h=0; f=0; parent=null};
..table.push(openList, startNode);
while(#openList > 0){
// 1. 从 openList 中取出 F 值最小的节点
..table.sort(openList, function(b){
return owner.f < b.f;
});
var current = openList[1];
..table.remove(openList, 1);
// 加入 closedList
closedList[getKey(current.x, current.y)] = true;
// 2. 判断是否到达终点
if(current.x == endP.x && current.y == endP.y){
// 回溯路径
var path = {};
var temp = current;
while(temp){
..table.push(path, {x=temp.x; y=temp.y});
temp = temp.parent;
}
return path; // 返回找到的路径
}
// 3. 检查四周相邻节点 (上下左右)
var neighbors = {
{x=0; y=-1}; {x=0; y=1}; {x=-1; y=0}; {x=1; y=0}
};
for(i=1; #neighbors; 1){
var nx = current.x + neighbors[i].x;
var ny = current.y + neighbors[i].y;
// 越界检查
if(nx < 1 || nx > this.width || ny < 1 || ny > this.height) continue;
// 障碍物检查
if(this.map[nx][ny] == 1) continue;
// 是否在 closedList 中
if(closedList[getKey(nx, ny)]) continue;
// 计算 G, H, F
var gScore = current.g + 1; // 假设每步移动成本为 1
//***可以将hScore改为0，变为Dijkstra 算法***
var hScore = this.getH({x=nx;y=ny}, endP);
var fScore = gScore + hScore;
// 检查是否已在 openList 中
var existingNode = null;
for(k,v in openList){
if(v.x == nx && v.y == ny) { existingNode = v; break; }
}
if(!existingNode){
// 不在 openList，添加进去
var newNode = {x=nx; y=ny; g=gScore; h=hScore; f=fScore; parent=current};
..table.push(openList, newNode);
} elseif(gScore < existingNode.g) {
// 在 openList 但发现了更优路径，更新它
existingNode.g = gScore;
existingNode.f = gScore + existingNode.h;
existingNode.parent = current;
}
}
}
return null; // 无路可走
}
}
// 参数设置
var mapSize = 20; // 地图大小 20x20
var blockSize = 30; // 每个格子像素大小
var map = {}; // 地图数据
var path = {}; // 最终路径
var startNode = {x=1; y=1}; // 起点
var endNode = {x=mapSize; y=mapSize}; // 终点
// 初始化地图（0:空地, 1:墙）
var initMap = function(){
map = {};
path = {}; // 清空路径
for(x=1; mapSize; 1){
map[x] = {};
for(y=1; mapSize; 1){
// 30% 概率生成墙
if(math.random(1,100) <= 30 && !(x==startNode.x && y==startNode.y) && !(x==endNode.x && y==endNode.y)){
map[x][y] = 1;
} else {
map[x][y] = 0;
}
}
}
winform.plusMap.redraw();
}
winform.plusMap.onDrawForegroundEnd = function(graphics,rc,rcContent){
// 动态计算每个格子的大小
var cellW = rc.width / mapSize;
var cellH = rc.height / mapSize;
var brushWall = gdip.solidBrush(0xFF000000);
var brushStart = gdip.solidBrush(0xFF00FF00);
var brushEnd = gdip.solidBrush(0xFFFF0000);
var brushPath = gdip.solidBrush(0xFF0000FF);
var penGrid = gdip.pen(0xFFCCCCCC, 1);
for(x=1; mapSize; 1){
for(y=1; mapSize; 1){
// 根据动态宽高计算坐标
var rectX = (x-1) * cellW;
var rectY = (y-1) * cellH;
// 画网格
graphics.drawRectangle(penGrid, rectX, rectY, cellW, cellH);
// 画格子内容
var pad = 1;
if(x==startNode.x && y==startNode.y){
graphics.fillRectangle(brushStart, rectX+pad, rectY+pad, cellW-pad*2, cellH-pad*2);
} elseif(x==endNode.x && y==endNode.y){
graphics.fillRectangle(brushEnd, rectX+pad, rectY+pad, cellW-pad*2, cellH-pad*2);
} elseif(map[x][y] == 1){
graphics.fillRectangle(brushWall, rectX, rectY, cellW, cellH); // 墙填满
}
}
}
// 画路径
if(path && #path){
for(i=1; #path; 1){
var node = path[i];
// 不覆盖起点和终点
if( (node.x==startNode.x && node.y==startNode.y) || (node.x==endNode.x && node.y==endNode.y) ) {
continue;
}
var rectX = (node.x-1) * cellW;
var rectY = (node.y-1) * cellH;
// 路径画小一点
var pathPadX = cellW * 0.25;
var pathPadY = cellH * 0.25;
graphics.fillRectangle(
brushPath,
rectX+pathPadX,
rectY+pathPadY,
cellW - pathPadX*2,
cellH - pathPadY*2
);
}
}
brushWall.delete(); brushStart.delete(); brushEnd.delete(); brushPath.delete(); penGrid.delete();
}
winform.btnGenMap.oncommand = function(id,event){
initMap();
}
winform.btnFind.oncommand = function(id,event){
var finder = AStar(map, mapSize, mapSize);
var result = finder.findPath(startNode, endNode);
if(result){
path = result;
winform.plusMap.redraw();
} else {
winform.msgbox("未找到路径！可能是被墙封死了。");
}
}
// 启动初始化
initMap();
winform.show();
win.loopMessage();
最新回复 (0)