mixster

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, oh, ch: Integer;
  closed, open, neigh: TIntegerArray;
begin
  h := High(grid) + 1;
  w := High(grid[0]) + 1;
  nh := (w * h);
  SetLength(nodes, nh);
  SetLength(open, nh);
  SetLength(closed, nh);
  nh := 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(10 * Distance(x, 0, en.x, 0) + Distance(0, y, 0, en.y));
      f := g + h;
      cl := False;
      op := False;
    end;
  end;

  open[0] := (st.y * w) + st.x;
  nodes[open[0]].op := True;
  oh := 0;
  ch := -1;
  repeat
    ti := 0;
    tf := nodes[open[0]].f;
    for i := 1 to oh 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[oh]);
    oh := oh - 1;
    ch := ch + 1;
    closed[ch] := 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, nh))) then
        continue;
      if (nodes[neigh[i]].cl) then
        continue;
      if (nodes[neigh[i]].op) then
      begin
        if (nodes[ti].f < nodes[neigh[i]].g) 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;
        end;
      end
      else
      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;
        nodes[neigh[i]].op := True;
        oh := oh + 1;
        open[oh] := neigh[i];
      end;
    end;
    if (oh = -1) 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;
  InvertTPA(path);
end;

var
  g: array of array of Integer;
  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;}
  Writeln('Begin');
  SetLength(g, 20);
   g[0] := [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
   g[1] := [0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0];
   g[2] := [0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0];
   g[3] := [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0];
   g[4] := [0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0];
   g[5] := [0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0];
   g[6] := [0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0];
   g[7] := [0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0];
   g[8] := [0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0];
   g[9] := [0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0];
  g[10] := [0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0];
  g[11] := [0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0];
  g[12] := [0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0];
  g[13] := [0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0];
  g[14] := [0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0];
  g[15] := [0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0];
  g[16] := [0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0];
  g[17] := [0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0];
  g[18] := [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0];
  g[19] := [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];

  for y := 0 to High(g) do
    for x := 0 to High(g[y]) do
      if (g[y][x] = 0) then
        g[y][x] := 255;
  x := GetSystemTime;
  AStarGrid(p, Point(1, 1), Point(18, 18), g);
  x := GetSystemTime - x;
  Writeln('Took ' + IntToStr(x) + 'ms');

  DisplayDebugImgWindow(Length(g[0]) * 10, Length(g) * 10);
  for y := 0 to High(g) do
    for x := 0 to High(g[y]) do
    begin
      GetDebugCanvas.Brush.Color := RGBToColor(g[y][x] * 1, g[y][x] * 1, g[y][x] * 1);
      GetDebugCanvas.Rectangle(x * 10, y * 10, (x + 1) * 10, (y + 1) * 10);
    end;
  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;
  Writeln('End');
end.