unit pathfinding;

interface

uses records, constants, path_map;

const
  tsPath       = 1; // путь
  tsUnvisited  = 2; // непосещенная точка
  tsBound      = 3; // граничная точка
  tsPassed     = 4; // проверенная точка
  tsStart      = 5; // точка старта
  tsFinish     = 6; // точка финиша

 courses : array [1..8] of RPFPoint = ((X:0;Y:-1),(X:1;Y:-1),(X:1;Y:0),(X:1;Y:1),
                                       (X:0;Y:1),(X:-1;Y:1),(X:-1;Y:0),(X:-1;Y:-1));

 marks : set of byte = [tsPath, tsBound, tsPassed];

type
 temp_bound  = array[1..max_path_length] of RPFPoint;

var
 temp_map : array[1..max_path_map_width, 1..max_path_map_height] of RWayPoint;

function FindPath(sx, sy, fx, fy : integer; pm : RPathMap) : RPath;

implementation

function GetPFPoint(x, y : integer): RPFPoint;
begin
result.x := x;
result.y := y;
end;

function MaxValue(x, y : single) : single;
begin
if x > y then result := x else result := y;
end;

function MinValue(x, y : single) : single;
begin
if x > y then result := y else result := x;
end;

function CountCost(x1, y1, x2, y2 : integer; rx, ry : single) : single;
var
dx, dy, cross : single;
begin
dx := x1 - x2;
dy := y1 - y2;
cross := dx * ry - rx * dy;
if cross < 0 then cross := -cross;
result := MaxValue(abs(dx), abs(dy)) + cross * 0.001;
end;   

function FindPath(sx, sy, fx, fy : integer; pm : RPathMap) : RPath;
var
a : RPFPoint;
i1, i2, k : byte;
dx, dy : single;
bound : temp_bound;
bound_size : integer;

const moving_cost : array[0..1] of single = (1.42,1);

procedure ResetTemp;
var
e1, e2 : integer;
begin
for e1 := 1 to pm.width do
  for e2 := 1 to pm.height do
    with pm.map[e1, e2] do
      begin
        temp_map[e1, e2].dangerous := dangerous;
        if not walk then temp_map[e1, e2].dangerous := 0;
        temp_map[e1, e2].mode := tsUnvisited;
        temp_map[e1, e2].px := 0;
        temp_map[e1, e2].py := 0;
      end;
end;

function FindMin : integer;
var
i, n: integer;
begin
n := 1;
for i := 1 to bound_size do
  if temp_map[bound[n].x, bound[n].y].f >
     temp_map[bound[i].x, bound[i].y].f then n := i;
result := n;
end;

procedure SavePath;
var
s1, s2, tw1, tw2 : integer;
begin
s1 := fx;
s2 := fy;
result.length := 1;
repeat
result.length := result.length + 1;
tw1 := s1; tw2 := s2;
s1 := temp_map[tw1, tw2].px;
s2 := temp_map[tw1, tw2].py;
with result.points[result.length] do
  begin
    x := s1;
    y := s2;
  end;
until (s1 = sx) and (s2 = sy);
end;

procedure AddToBound(p : RPFPoint);
begin
if bound_size >= max_path_length then exit;
bound_size := bound_size + 1;
bound[bound_size] := p;
end;

begin
ResetTemp;
result.exists := true;
dx := sx - fx;
dy := sy - fy;
temp_map[sx, sy].mode := tsBound;
temp_map[fx, fy].mode := tsFinish;
bound_size := 1;
temp_map[sx,sy].g := 0;
temp_map[sx,sy].h := CountCost(sx, sy, fx, fy, dx, dy);
temp_map[sx,sy].f := temp_map[sx, sy].g + temp_map[sx, sy].h +
  temp_map[sx, sy].dangerous;
bound[1] := GetPFPoint(sx, sy);
while bound_size > 0 do
  begin
    k := FindMin;
    i1 := Bound[k].x;
    i2 := Bound[k].y;
    temp_map[bound[k].x, bound[k].y].mode := tsPassed;
    bound[k] := bound[bound_size];
    bound_size := bound_size - 1;
    for k := 1 to 8 do
      begin
        a.x := i1 + courses[k].x;
        a.y := i2 + courses[k].y;
        with temp_map[a.x, a.y] do
          if dangerous > 0 then
            case mode of
              tsUnvisited :
                begin
                  g := temp_map[i1, i2].g + dangerous * moving_cost[k mod 2];
                  f := g + CountCost(a.x, a.y, fx, fy, dx, dy);
                  px := i1;
                  py := i2;
                  mode := tsBound;
                  AddToBound(a);
                end;
              tsFinish :
                begin
                  px := i1;
                  py := i2;
                  mode := tsStart;
                  SavePath;
                  exit;
                end;
            end;
      end;
  end;
temp_map[sx, sy].mode := tsStart;
result.exists := false;
end;

end.
