path.pas

千年2的脱机源代码

unit path;

interface

uses Windows,SysUtils,Classes,Dialogs;
  
type
    TNode = record //节点信息
    g : integer;       // g值
    h : integer;       // h 值
    f : integer;       // f 值
    father : TPoint;  // 父亲节点
    flag : integer;
    end;

type
    TAStart = class (Tobject)
    public
        NodeData : array of array of TNode;
        function FindRoad(Start, Goal: TPoint): bool;//寻路
        function TestPoint(point: TPoint): bool;               //测试是否为障碍点
        constructor Create;
        Destructor  Destroy; override;

    private
        OpenList : TList;
        MapWidth, MapHeight : integer;
        procedure push(node: TPoint);  //往列表中加入节点
        procedure pop(list: Tlist; node: TPoint);       //往列表中删除节点
        function GetMinFNode : TPoint;          //获取最小F值的点
        function TestList(node: TPoint): integer; //测试点是否在封闭列表
        function judgeH(test, Goal: TPoint):integer;   //计算H值
    end;

var
    AStart : TAStart;

implementation

uses MapInfo;

constructor TAStart.Create;
var
    x,y,c : integer;
begin
    inherited Create;
    OpenList := TList.Create;
//    MapWidth := MapInfor.GetMapWidth;
//    MapHeight := MapInfor.GetMapHeight;
  
    //模拟一个地图
    MapInfor := TMapInfo.Create;
    MapWidth := MapInfor.GetMapWidth;
    MapHeight := MapInfor.GetMapHeight;
    SetLength(MapInfor.MapData, MapWidth, MapHeight);
     
  {  c := 0;
    for x := 5 to MapWidth - 10 do
        for y := 5 to MapHeight - 10 do
        begin
            if c = 0 then c := 1
            else c:= 0;
            MapInfor.MapData[x,y] := c;
        end;
       c := 0;   } 
 //   for y := 10 to MapHeight -100 do
 //           MapInfor.MapData[50,y] := 1;

    SetLength(NodeData, MapWidth, MapHeight);  //初始化节点数据存储单元
end;

Destructor TAStart.Destroy;
begin
    OpenList.Free;
end;

procedure TAStart.push(node: TPoint); //往列表中加入节点
var
    pnode : ^TPoint;
begin
    new(pnode);
    pnode.X := node.X;
    pnode.Y := node.Y;
    OpenList.Add(pnode);
    NodeData[node.X, node.Y].flag := 1;
end;

procedure TAStart.pop(list: Tlist; node: TPoint);    //往列表中删除节点
var
    i : integer;
    temp : ^TPoint;
begin
    if List.Count = 1 then
    begin
        List.Delete(0);
        exit;   //只有 1个
    end;
    
    for i := 0 to List.Count - 2 do
    begin
        temp := List.Items[i];
        if (temp.X = node.X) and (temp.Y = node.Y) then
            List.Delete(i);
    end;   
    NodeData[node.X, node.Y].flag := 2;
end;

function TAStart.GetMinFNode(): TPoint;          //获取最小F值的点
var
    i : integer;
    value,temp : ^TPoint;
begin
    if OpenList.Count = 1 then
    begin
        temp := OpenList.First;
        result.X := temp.X;
        result.Y := temp.Y;
        exit;   //只有 1个
    end;
    value := OpenList.first;
    for i := 1 to OpenList.Count -1 do
    begin
        temp := OpenList.Items[i];
        if NodeData[value.X, value.Y].f > NodeData[temp.X, temp.Y].f then
        begin
             value := temp;
        end;
    end;
    result.X := value.X;
    result.Y := value.Y;
end;

//--------------------------------------------------------------------
//函数：TestList
//功能：测试点的状态
//参数：node 要测试点的坐标 (该过程中还会调用到二维数组 nodedata)
//返回：integer 型 1  在开放列表   2 在封闭列表  0 未访问过
//说明：
//--------------------------------------------------------------------
function TAStart.TestList(node: TPoint): integer;
begin
    result := NodeData[node.X, node.Y].flag;
end;
//--------------------------------------------------------------------
//函数：TestPoint
//功能：测试点是否可行走
//参数：node 要测试点的坐标 (该过程中还会调用到地图二维数组 mapdata)
//返回：bool型 True可以行走 false 不可行走
//说明：
//--------------------------------------------------------------------
function TAStart.TestPoint(point: TPoint): bool;
begin
    if (point.X < 0) or (point.Y < 0) or
       (point.x >= MapWidth - 1) or (point.Y >= MapHeight -1) then
    begin
        result := False;
        exit;
    end;    
    if MapInfor.MapData[point.x, point.y] = 0 then
        result := True                  // 数据值为0   可行走
    else
        result := False;                // 数据值不为0 不可行走
end;
{--------------------------------------------------------------------
函数：judgeH
功能：计算H值
参数：test 测试点 Goal 终点
返回: True可以行走 false 不可行走
说明：ABs  求绝对值
-------------------------------------------------------------------- }
function TAStart.judgeH(test, Goal: TPoint):integer;
begin
    result := (Abs(Goal.X - test.x)) * 10 + (Abs(Goal.Y - test.y)) * 10 ;
end;

{--------------------------------------------------------------------
函数：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;

end.