uastar.pas

这是对A*寻路算法的一个封装.使用非常简单:1.指定寻路区域的大小(网格) 2.指定哪些节点是障碍物 3.给定出发节点点和目标节点, 寻路! 将返回最短路径. 另外, 还可以设定遇到障碍物时只能绕着障

//==================================
//    A*算法封装类
//-------------------------------
//                 Lsp.2008.4.26
//==================================

unit UAStar;


interface
uses Types, Classes, Lists, Padlock;



type

    //节点
  PAStarNode = ^TAStarNode;
  TAStarNode = packed record
    case Boolean of
      FALSE: (Obstacle: Boolean);   //是否为障碍物
      TRUE : (F, G, H: Word;        //这些值由TAStar类计算填充, 以实现启发式搜索
              Parent_Pt: TSmallPoint); //父节点坐标(便于最后形成路径)
  end;




  //-----------------------------------
  //  A* 算法封装类
  //-----------------------------------

  TAStar = class
  protected
    FWidth, FHeight: Integer;            //区域的列数, 行数
//    FAreaBuffer: array of TAStarNode;    //要搜索的区域(被分割成二维数组)
    FAreaBuffer: array of array of TAStarNode;    //要搜索的区域(被分割成二维数组)
    FMoveAroundObstacleCorner: Boolean;  //遇到障碍物时只能绕着障碍物的角走

    FSearching: Boolean;                 //表明是否正在搜索路径
    FStartNode_Pt, FDestNode_Pt: TSmallPoint;  //最近一次搜索的开始节点和目标节点的坐标

    function GetNodes(x,y: Integer): PAStarNode;  //将上面的一维数组翻译成二维数组, 没有实际用途, 只是增加可读性
    function GetNodesByPt(node_pt: TSmallPoint): PAStarNode;  //同上
    procedure CalcGValue(sel_pt: TSmallPoint); virtual;       //计算start_node到sel_node的G值
    function CalcGValueFromCurNode(cur_pt, dest_pt: TSmallPoint): Integer; virtual;       //计算经由cur_node到dest_node的G值
    procedure CalcHValue(sel_pt: TSmallPoint); virtual;       //计算sel_node到dest_node的H值
    procedure CalcFValue(sel_pt: TSmallPoint); virtual;       //计算sel_node的F值(正常情况下, 就是G+H)

  public
    constructor Create();        
    destructor Destroy(); override;

    procedure ResetArea(area_width, area_height: Integer);         //重新设置区域, 清空其中所有数据
    procedure SetObstacle(clear_old: Boolean; bostacle_nodes_pt: array of TSmallPoint); overload; //设置区域中的障碍物节点(凡是参数中指明的均为不可通过节点)
    procedure SetObstacle(clear_old: Boolean; bostacle_nodes_pt: TSmallPointList); overload; //设置区域中的障碍物节点(凡是参数中指明的均为不可通过节点)
    procedure SetObstacleXY(clear_old: Boolean; bostacle_nodes_xy: array of SmallInt);   //设置区域中的障碍物节点(凡是参数中指明的均为不可通过节点)
    function SearchPath(start_pt, dest_pt: TSmallPoint;        //按A*算法查找路径
                        path_pt: TSmallPointList): Boolean;    //若成功, 则返回TRUE, 且path返回最"短"路径经过的节点列表(List of PAStarNode)

    property Width: Integer read FWidth;
    property Height: Integer read FHeight;
    property Nodes[x,y: Integer]: PAStarNode read GetNodes;
    property NodesByPt[node_pt: TSmallPoint]: PAStarNode read GetNodesByPt;

    property MoveAroundObstacleCorner: Boolean read FMoveAroundObstacleCorner write FMoveAroundObstacleCorner;  //遇到障碍物时只能绕着障碍物的角走
  end;




implementation



constructor TAStar.Create();
begin
  inherited Create();

  FSearching := FALSE;
  FWidth := 0;      FHeight := 0;
  FStartNode_Pt := SmallPoint(-1, -1);
  FDestNode_Pt := SmallPoint(-1, -1);
  FMoveAroundObstacleCorner := TRUE;
end;



destructor TAStar.Destroy();
begin
  SetLength(FAreaBuffer, 0);
  inherited Destroy();
end;




function TAStar.GetNodes(x,y: Integer): PAStarNode;  //将上面的一维数组翻译成二维数组, 没有实际用途, 只是增加可读性
begin
//  result := @FAreaBuffer[FWidth*y+x];
  result := @FAreaBuffer[x,y];
end;




function TAStar.GetNodesByPt(node_pt: TSmallPoint): PAStarNode;
begin
//  result := @FAreaBuffer[FWidth*node_pt.y+node_pt.x];
  result := @FAreaBuffer[node_pt.x, node_pt.y];
end;




procedure TAStar.CalcGValue(sel_pt: TSmallPoint);  //计算从开始节点到sel_node的G值(移动代价)
var
  sel, parent: PAStarNode;
begin
  sel := NodesByPt[sel_pt];
  parent := NodesByPt[sel^.Parent_Pt];
  if (sel^.Parent_Pt.x = sel_pt.x) or (sel^.Parent_Pt.y = sel_pt.y) then    //直接上/下/左/右移动一格
    sel^.G := parent^.G + 10
  else sel^.G := parent^.G + 14;                                            //按斜对角线移动一格
end;




function TAStar.CalcGValueFromCurNode(cur_pt, dest_pt: TSmallPoint): Integer;  //计算经由cur_node到dest_node的G值
begin
  if (cur_pt.x = dest_pt.x) or (cur_pt.y = dest_pt.y) then
    result := NodesByPt[cur_pt]^.G + 10
  else result := NodesByPt[cur_pt]^.G + 14;
end;





procedure TAStar.CalcHValue(sel_pt: TSmallPoint);  //计算从sel_node到目标节点的H值(移动代价)
begin
  NodesByPt[sel_pt]^.H := (abs(sel_pt.x-FDestNode_Pt.x) + abs(sel_pt.y-FDestNode_Pt.y)) * 10;
end;




procedure TAStar.CalcFValue(sel_pt: TSmallPoint);  //计算sel_node的F值(正常情况下, 就是G+H)
begin
  with NodesByPt[sel_pt]^ do begin
    CalcGValue(sel_pt);
    if (H<=0) then CalcHValue(sel_pt);    //H值一经计算, 就不会再改变了(依据上面CalcHValue的算法, 又因为目标节点的位置没有改变, ...)
    F := G + H;
  end;
end;





procedure TAStar.ResetArea(area_width, area_height: Integer);
begin
//  SetLength(FAreaBuffer, area_width*area_height);
  SetLength(FAreaBuffer, area_width, area_height);
  FWidth := area_width;
  FHeight := area_height;
  FillChar(FAreaBuffer[0,0], sizeof(TAStarNode)*length(FAreaBuffer), 0);
end;




procedure TAStar.SetObstacle(clear_old: Boolean; bostacle_nodes_pt: array of TSmallPoint);  //设置区域中的障碍物节点(凡是参数中指明的均为不可通过节点)
var
  i: Integer;
begin
  if (clear_old) then FillChar(FAreaBuffer[0,0], sizeof(TAStarNode)*FWidth*FHeight, 0);

  for i:=0 to Length(bostacle_nodes_pt)-1 do
    NodesByPt[bostacle_nodes_pt[i]]^.Obstacle := TRUE;
end;



procedure TAStar.SetObstacle(clear_old: Boolean; bostacle_nodes_pt: TSmallPointList);  //设置区域中的障碍物节点(凡是参数中指明的均为不可通过节点)
var
  i: Integer;
begin
  if (clear_old) then FillChar(FAreaBuffer[0,0], sizeof(TAStarNode)*FWidth*FHeight, 0);

  for i:=0 to bostacle_nodes_pt.Count-1 do
    NodesByPt[bostacle_nodes_pt[i]]^.Obstacle := TRUE;
end;




procedure TAStar.SetObstacleXY(clear_old: Boolean; bostacle_nodes_xy: array of SmallInt);
var
  i: Integer;
begin
  if (clear_old) then FillChar(FAreaBuffer[0,0], sizeof(TAStarNode)*FWidth*FHeight, 0);

  for i:=0 to (Length(bostacle_nodes_xy) div 2) - 1 do
    Nodes[bostacle_nodes_xy[2*i], bostacle_nodes_xy[2*i+1]]^.Obstacle := TRUE;
end;






function TAStar.SearchPath(start_pt, dest_pt: TSmallPoint;        //按A*算法查找路径
                           path_pt: TSmallPointList): Boolean;    //若成功, 则返回TRUE, 且path返回最"短"路径经过的节点列表(List of PAStarNode)
var
  opened_pt, closed_pt: TSmallPointList;     //开放列表, 封闭列表
  cur_pt: TSmallPoint;                       //当前节点的坐标
  i: Integer;
  neighbor: TSmallPointList;                //当前节点的8个相邻节点
  tG: Integer;
begin
  result := FALSE;

  if (FSearching) then exit;

  FSearching := TRUE;
  opened_pt := TSmallPointList.Create();
  closed_pt := TSmallPointList.Create();
  neighbor := TSmallPointList.Create();
  try
    FStartNode_Pt := start_pt;
    FDestNode_Pt := dest_pt;
    path_pt.Clear();

      //1.将开始节点放到开放列表
    opened_pt.Add(FStartNode_Pt);

      //2.重复查找...
    repeat
        //2.1.查找开放列表中具有最小F值的节点, 作为当前节点
      if (opened_pt.Count=0) then break;    //如果开放列表是空的, 说明没有路径! 退出...
      cur_pt := opened_pt[0];
      for i:=opened_pt.Count-1 downto 1 do begin
        if (NodesByPt[cur_pt]^.F > NodesByPt[opened_pt[i]]^.F) then
          cur_pt := opened_pt[i];
      end;

        //2.2.将找到的当前节点放入封闭列表中
      opened_pt.Remove(cur_pt);
      closed_pt.Add(cur_pt);

        //2.3.对当前节点的8个相邻节点中的每一个进行操作
      neighbor.Clear();
      with cur_pt do begin
        if (x>0) then begin          //左边的三个
          if (y>0) then neighbor.Add(SmallPoint(x-1, y-1));
          neighbor.Add(SmallPoint(x-1, y));
          if (y<FHeight-1) then neighbor.Add(SmallPoint(x-1, y+1));
        end;
        if (y>0) then neighbor.Add(SmallPoint(x, y-1));            //上面的一个
        if (y<FHeight-1) then neighbor.Add(SmallPoint(x, y+1));    //下面的一个
        if (x<FWidth-1) then begin   //右边的三个
          if (y>0) then neighbor.Add(SmallPoint(x+1, y-1));
          neighbor.Add(SmallPoint(x+1, y));
          if (y<FHeight-1) then neighbor.Add(SmallPoint(x+1, y+1));
        end;
      end;//with

      for i:=0 to neighbor.Count-1 do begin
          //如果这个邻居不可走, 或者已经在封闭列表中了, 则忽略之!
        if (NodesByPt[neighbor[i]].Obstacle) or (List_IndexOf(closed_pt, Pointer(neighbor[i]))>=0) then continue;
          //如果遇到障碍物时只能绕着障碍物的角走, 则下面得检测是否能直接走对角线到达这个邻居
        if (MoveAroundObstacleCorner) and (cur_pt.x<>neighbor[i].x) and (cur_pt.y<>neighbor[i].y) then begin
          if (Nodes[cur_pt.x, neighbor[i].y]^.Obstacle) or (Nodes[neighbor[i].x, cur_pt.y]^.Obstacle) then continue;
        end;
        
          //如果这个邻居不在开放列表中, 则添加之, 并以当前节点作为其parent, 计算其F, G, H值
        if (List_IndexOf(opened_pt, Pointer(neighbor[i]))<0) then begin
          opened_pt.Add(neighbor[i]);
          with NodesByPt[neighbor[i]]^ do begin
            Parent_Pt := cur_pt;
            CalcFValue(neighbor[i]);
          end;
          if (neighbor[i].x=FDestNode_Pt.x) and (neighbor[i].y=FDestNode_Pt.y) then begin
            result := TRUE;
            break;  //说明找到路径啦!
          end;
        end
        else begin  //如果它已经在开放列表了, 则检查到达它的路径是否有更优的(G值更小的)
          tG := CalcGValueFromCurNode(cur_pt, neighbor[i]);
          if (tG<NodesByPt[neighbor[i]]^.G) then begin        //如果经由cur_pt到达neighbor[i]有更好的路径(G更小)
            NodesByPt[neighbor[i]]^.Parent_Pt := cur_pt;      //则将此邻居的parent改为cur_pt
            CalcFValue(neighbor[i]);                          //  并重新计算此邻居的F值
            break;
          end; 
        end; 
      end;                                 

    until result;


      //3.构造路径
    if (result) then begin
      cur_pt := FDestNode_Pt;
      path_pt.Insert(0, cur_pt);
      while (Integer(cur_pt)<>Integer(FStartNode_Pt)) do begin
        cur_pt := NodesByPt[cur_pt]^.Parent_Pt;
        path_pt.Insert(0, cur_pt);
      end;//while
    end;

  finally
    FSearching := FALSE;
    neighbor.Free();
    opened_pt.Free();
    closed_pt.Free();
  end;
end;




end.