Hier mal mein Waypoint System!
Das abeitet nach einem Algorytmus, der erst die Distanzen zu den einzelnen Wegpunkten vom Startpunkt berechnet, und dann einfach den Weg vom Zielpunkt zum startpunkt rekonstruiert.
Delphi-Quellcode:
TWP = record
x,Y : Integer;
Connections : Array [0..5] of TConnection;
Distances : Array [0..5] of Integer;
end;
var
WPmax : Integer;
WPS : Array [1..200] of TWP;
WPd : Array [1..200] of Integer;
[....]
procedure ExpandD;
var i,j,x : Integer;
begin
for i := 1 to high(WPs) do
for j := 0 to 5 do
begin
If (WPS[i].Connections[j].AimID<>0) then
begin
x := WPD[i] + WPS[i].Distances[j];
If (x < WPD[WPS[i].Connections[j].AimID]) then
begin
WPd[WPS[i].Connections[j].AimID] := x;
ExpandD;
exit;
end;
end;
end;
end;
function GetShortWay(Start, Fin: Integer; var Way: TStringList): Boolean;
var i,x,j: Integer;
Pos : Integer;
begin
Result := false;
try
for i := 0 to 200 do
WPd[i] := maxint div 2 -1;
WPD[Start] := 0;
ExpandD;
If Way=nil then Way := TStringList.Create;
Way.Clear;
Way.Add(IntToStr(Fin));
Pos := 1;
Pos := Fin;
If Pos=0 then Pos := 1;
repeat
inc(j);
for i := 0 to 5 do
begin
x := WPS[Pos].Connections[i].AimID;
If not (x=0) then
begin
If ((WPD[Pos]-WPS[Pos].Distances[i]) = WPD[WPS[Pos].Connections[i].AimID]) then
begin
Pos := WPS[Pos].Connections[i].AimID;
Way.Insert(0,IntToStr(Pos));
j := 0;
end;
end;
end;
if j>20 then Pos := Start;
until Pos = Start;
If Way.Count<=1 then Way.Add(IntToStr(Start));
Result := true;
except
end;
end;
function GetRndWay(Start, Fin: Integer; var Way: TStringList): Boolean;
var i,x,j : Integer;
b : Boolean;
Pos : Integer;
begin
Result := false;
try
for i := 0 to 200 do
WPd[i] := maxint div 2 -1;
WPD[Start] := 0;
WPmax := WPmax;
ExpandD;
If Way=nil then Way := TStringList.Create;
Way.Clear;
Way.Add(IntToStr(Fin));
Pos := 1;
Pos := Fin;
If Pos=0 then Pos := 1;
repeat
i := 0;
If not (Pos = Start) then
begin
repeat
x := random(5);
inc(i);
If (i>30) then
begin
exit;
end;
until (WPS[Pos].Connections[x].AimID>0) and (WPD[WPS[Pos].Connections[x].AimID]<WPD[Pos]);
Pos := WPS[Pos].Connections[x].AimID;
end;
Way.Insert(0,IntToStr(Pos));
until Pos = Start;
Result := true;
finally
If Way.Count<=1 then Way.Insert(0,IntToStr(Start));
end;
end;
Und den gesamten Code als
Unit: