mixster

program New;

type
  node = record
    parent: Integer;
    x, y: Integer;
    f, g, h: Integer;
    cl, op: Boolean;
  end;

procedure AStarGrid(var path: TPointArray; st, en: TPoint; grid: T2DIntArray);
var
  nodes: array of node;
  w, h, i, nh, ti, tf, x, y: Integer;
  closed, open, neigh: TIntegerArray;
begin
  h := High(grid) + 1;
  w := High(grid[0]) + 1;
  nh := (w * h) - 1
  SetLength(nodes, nh + 1);
  for i := 0 to nh do
  begin
    with nodes[i] do
    begin
      parent := -1;
      x := i mod w;
      y := Trunc(i / w);
      g := grid[y][x];
      h := Round(Distance(x, 0, en.x, 0) + Distance(0, y, 0, en.y));
      f := g + h;
      cl := False;
      op := False;
    end;
  end;

  SetLength(open, 1);
  open[0] := (st.y * w) + st.x;
  nodes[open[0]].op := True;
  repeat
    ti := 0;
    tf := nodes[open[0]].f;
    if (High(open) <> 0) then
      for i := 1 to High(open) do
      begin
        if (nodes[open[i]].f < tf) then
        begin
          ti := i;
          tf := nodes[open[i]].f;
        end;
      end;
    i := ti;
    ti := open[ti];
    nodes[ti].cl := True;
    nodes[ti].op := False;
    Swap(open[i], open[High(open)]);
    SetLength(open, High(open));
    SetLength(closed, High(closed) + 2);
    closed[High(closed)] := ti;
    if ((nodes[ti].x = en.x) and (nodes[ti].y = en.y)) then
      break;

    with nodes[ti] do
    begin
      neigh := [(ti - w) - 1, (ti - w), (ti - w) + 1, ti - 1, ti + 1, (ti + w) - 1, (ti + w), (ti + w) + 1];
    end;

    for i := 0 to 7 do
    begin
      if (not (InRange(neigh[i], 0, High(nodes)))) then
        continue;
      if (nodes[neigh[i]].cl) then
        continue;
      if (((nodes[neigh[i]].op) and (nodes[ti].f < nodes[neigh[i]].g)) or (not nodes[neigh[i]].op)) then
      begin
        nodes[neigh[i]].parent := ti;
        nodes[neigh[i]].g := nodes[ti].g + grid[nodes[neigh[i]].y][nodes[neigh[i]].x];
        nodes[neigh[i]].f := nodes[neigh[i]].g + nodes[neigh[i]].h;
        if (not nodes[neigh[i]].op) then
        begin
          nodes[neigh[i]].op := True;
          SetLength(open, High(open) + 2);
          open[High(open)] := neigh[i];
        end;
      end;
    end;
    if (Length(open) = 0) then
      exit;
  until false;

  SetLength(path, 0);
  repeat
    SetLength(path, High(path) + 2);
    path[High(path)] := IntToPoint(nodes[ti].x, nodes[ti].y);
    ti := nodes[ti].parent;
  until (nodes[ti].parent = -1);
  SetLength(path, High(path) + 2);
  path[High(path)] := IntToPoint(nodes[ti].x, nodes[ti].y);
  ti := nodes[ti].parent;
end;

var
  g: T2DIntArray;
  x, y: Integer;
  p: TPointArray;
  s: string;
begin
  SetLength(g, 10);
  for y := 0 to High(g) do
  begin
    SetLength(g[y], 10);
    s := '';
    for x := 0 to High(g[y]) do
    begin
      //g[y][x] := 1;
      g[y][x] := Random(9) + 1;
      s := s + IntToStr(g[y][x]);
    end;
    Writeln(s);
  end;


  AStarGrid(p, Point(2, 2), Point(8, 8), g);
  for y := 0 to High(p) do
    Writeln(IntToStr(p[y].x) + ',' + IntToStr(p[y].y));

  DisplayDebugImgWindow(100, 100);
  for y := 0 to High(g) do
    for x := 0 to High(g[y]) do
    begin
      GetDebugCanvas.Brush.Color := RGBToColor(g[y][x] * 25, g[y][x] * 25, g[y][x] * 25);
      GetDebugCanvas.Rectangle(x * 10, y * 10, (x + 1) * 10, (y + 1) * 10);
    end;
  Wait(2500);
  GetDebugCanvas.Brush.Color := clRed;
  for y := 0 to High(p) do
  begin
    GetDebugCanvas.Ellipse((p[y].x * 10) + 2, (p[y].y * 10) + 2, (p[y].x * 10) + 8, (p[y].y * 10) + 8);
    Writeln(IntToStr(p[y].x) + ',' + IntToStr(p[y].y) + ' - ' + IntToStr(g[p[y].y][p[y].x]));
  end;
end.