F34r0fTh3D4rk - Do 07.07.05 18:44
Titel: Probleme beim Rekursiven Backtracking Algo
Hallo Leute, ich wollte gerade mal ein kleines Backtracking programm schreiben, welches den Weg findet und kleine Waypoints setzt, denen die Figur später nachlaufen kann, ich habe 2 arrays:
Delphi-Quelltext
1:
2:
| Map: array [1..15] of array [1..15] of integer;
TrackMatrix: array [1..15] of array [1..15] of integer; |
Trackmatrix ist die WayPoint-Matrix
...ein paar Konstanten:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
| const
None = -1;
Floor = 0;
Wall = 1;
Start = 0;
Finish = 1;
DUp = 10;
DDown = 20;
DLeft = 30;
DRight = 40; |
...eine Prozedur zum Waypoint setzen:
Delphi-Quelltext
1:
2:
3:
4:
| procedure SetTrack(x, y: integer; number: integer);
begin
TrackMatrix[x, y] := number;
end; |
...und mein Backtracking:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
| procedure BackTracking(x, y: integer; Direction: integer);
begin
if (Map[x, y] = floor) or ((x = FinishP.x) and (y = FinishP.y)) then
begin
if ((x = FinishP.x) and (y = FinishP.y)) then
exit else
if (Map[x, y] = floor) then
begin
SetTrack(x, y, Direction);
BackTracking(x, y + 1, DDown);
BackTracking(x + 1, y, DRight);
BackTracking(x, y - 1, DUp);
BackTracking(x - 1, y, DLeft);
end;
end;
end; |
dann zeichne ich noch die waypoint matrix (zu testzwecken):
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
| procedure DrawTracknumbers;
var
i, j: integer;
begin
for i := 1 to 15 do
for j := 1 to 15 do
with MainForm.DXDraw1.Surface.Canvas do
begin
brush.style := bsclear;
pen.color := clred;
font.name := 'Arial';
font.size := 12;
textout((i - 1) * 23, (j - 1) * 23, inttostr(TrackMatrix[i, j]));
Release;
end;
end; |
im timer:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
| procedure TMainForm.DXTimer1Timer(Sender: TObject; LagCount: Integer);
begin
DXDraw1.Surface.Fill(clblack);
DrawMap; DrawPath; DrawSelRect; DrawTracknumbers;
DXDraw1.Flip;
end; |
so, wenn ich jetzt das backtracking starte:
Delphi-Quelltext
1:
2:
3:
4:
| procedure TMainForm.BTN_StartClick(Sender: TObject);
begin
BackTracking(StartP.x, StartP.y, none);
end; |
hängt sich das programm auf, ist meine backtracking prozedur falsch, oder liegt das problem woanders ?
F34r0fTh3D4rk - So 10.07.05 10:27
es kam zu einer endlosschleife, weil der weg zurückgegangen wurde, dann wieder vorwärts ... das war die ursache, dann hab ichs nochmal n bisschen gekürzt und funzt :wink:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
| procedure BackTracking(x, y: integer; Direction: integer);
begin
if (Map[x, y] = floor) then
begin
if (TrackMatrix[x, y] = 0) or (TrackMatrix[x, y] = -1) then
begin
SetTrack(x, y, Direction);
Application.ProcessMessages;
if Direction <> DUp then
BackTracking(x, y + 1, DDown);
if Direction <> DLeft then
BackTracking(x + 1, y, DRight);
if Direction <> DDown then
BackTracking(x, y - 1, DUp);
if Direction <> DRight then
BackTracking(x - 1, y, DLeft);
end;
end;
end; |