A寻路算法(Delphi)

eyLife富翁笔记
作者　: kikyo
标题　: A* 算法寻路(delphi)
关键字: A* 算法寻路(delphi)
分类　: 个人专区
密级　: 公开
(评分: , 回复: 0, 阅读: 1369) ??
A* 算法寻路(delphi)

{--------------------------------------------------------------------
函数：FindRoad
功能：采用A* 算法进行寻路
参数：起始节点 和 到达节点
返回：0 失败 1 成功
说明： 八个字向定义 设 人物到 点 1 3 5 7 距离均为 10 设 人物到 点 0 2 4 6 距离均为 14
0 1 2 -1,-1 0,-1 1,-1
7 ★ 3
6 5 4
-1,0 ★ 1,0


-1,1 0,1 1,1
-------------------------------------------------------------------- }
function TAStart.FindRoad(Start, Goal: Tpoint): bool;
const //0 1 2 3 4 5 6 7 方向
PositionX : array [0..7] of integer = (-1, 0, 1, 1, 1, 0, -1, -1); //x方向
PositionY : array [0..7] of integer = (-1,-1,-1, 0, 1, 1, 1, 0); //y方向
PositionV : array [0..7] of integer = (14,10,14,10,14,10, 14, 10); //距离
var
NowNode : TPoint;
test : TPoint;
i : integer;
begin
push(Start); //开始节点加入开放列表

//如开放列表是空的 结束循环.寻路失败
while OpenList.Count > 0 do
begin
NowNode := GetMinFNode(); //将最小F值做为当前块
NodeData[NowNode.X, NowNode.Y].flag := 2;
pop(OpenList, NowNode); //将最小F值从开放列表中删除

for i := 0 to 7 do
begin
test.X := NowNode.X + PositionX[i];
test.Y := NowNode.Y + PositionY[i];
//如果将终点加入开放列表,返回成功,结束循环
if (test.X = Goal.X) and (test.Y = Goal.Y) then
begin
NodeData[Goal.X, Goal.Y].father := NowNode;
result := True;
exit;
end;

//不可行走 超出范围 在封闭列表 则忽略
if (TestPoint(test) = false ) or (TestList(test) = 2) or
(test.Y < 0 ) or (test.Y > MapHeight-1) or
(test.X < 0 ) or (test.X > MapWidth -1) then
begin
Continue;
end;

if (TestList(test) = 1) then
begin //在开放列表
if NodeData[test.X, test.Y].g > NodeData[NowNode.X, NowNode.y].g + PositionV[i] then
begin
NodeData[test.X, test.Y].g := NodeData[NowNode.x, NowNode.y].g + PositionV[i];
NodeData[test.X, test.Y].f := NodeData[test.X, test.Y].h + NodeData[test.X, test.Y].g;
NodeData[test.X, test.Y].father := NowNode;
end;
Continue;
end; //不在开放列表

NodeData[test.X, test.Y].g := NodeData[NowNode.x, NowNode.y].g + PositionV[i];
NodeData[test.X, test.Y].h := judgeH(test, Goal);
NodeData[test.X, test.Y].f := NodeData[test.X, test.Y].h + NodeData[test.X, test.Y].g;
NodeData[test.X, test.Y].father := NowNode;
push(test);
end;
end;
result := false; //寻路失败
end;