Witam, mam problem odnośnie szukanie najkrótszej drogi. Potrzebne mi to jest do gry snake, do duszków, które będą usiłować zjeść papu przed nami. Oto problematyczny kawałek kodu. Problem tkwi w tym, że debugger nie chce za pomocą trace into wejść wewnątrz wewnątrz funkcji makeRoad..
Juz objaśniam koncepcję - za pomocą makeGraph tworzę graf reprezentowany jako macierz odległości. Wszystkie punkty z mapy to wierzchołki grafu i układam je w kolejności wg. wzoru c= x + (y-1) *78 (78 punków w wierszu).
W tablicy map[][] mam przechowane współrzędne przeszkód i teleportów. (map[][1] to współrzędne x, map[][2] to y, map[1][], i map[2][] to są dwa teleporty, dalej są przeszkody, kończę gdy spotkam wartość 99).
Mogę liczyć na pomoc?
type
matrix = array[1..300] of array[1..2] of integer; //do wczytywania plansz
psnake=^snake;//waz
point=record //jedzenie
x,y:integer;
typ:string;
end;
snake=record
x,y:integer;
next,prev:psnake;
end;
graf=array[1..3354]of array[1..3354] of integer; //graf do dijkstry, 3354-ilosc pol wewnatrz planszy
distances=array[1..3354]of integer; //wektor odleglosci od głowy do punktów distances[i] wg wzoru nr wieszcholka c=x+(y-1)*78;
queue=array[1..3354]of boolean;//za pomoca tego wierzchołki przez które już przeszedłem false-juz byl, true w kolejce
pmoves=^moves;
moves=record//kolejne pola do ruchu dla ai
x,y:integer;
next,prev:pmoves;
end;
function dijkstra(map:matrix;head:psnake;food:point;ggraf:graf):distances;//zwraca tablice najkrotszych drog do wszystkich punktow
var
D:distances;
Q:queue;
i,j,c,min:integer;
function isEmpty(Q:queue):boolean;//czy sa jeszcze punkty do badania
var
i:integer;
begin
isEmpty:=true;
i:=1;
while isEmpty do begin
if Q[i] then isEmpty:=false;
i:=i+1;
end;
end;
function minimum(D:distances):integer;//zwraca indeks i dla ktorego D[i] jest najmniejsze (obecny najkrotszy wektor)
var
i:integer;
begin
minimum:=0;
i:=1;
while minimum=0 do begin
if Q[i]=true then minimum:=i;
i:=i+1;
end;
for i:=1 to 3354 do
if (Q[i]=true) and (D[i]<D[minimum]) then minimum:=i;
end;
begin
c:=head^.x+(head^.y-1)*78;//nr kol. glowy weza - wieszcholka poczatkowego
for i:=1 to 3354 do begin //ustawiam zbior punktow Q, oraz poczatkowe odleglosci D
D[i]:=ggraf[c][i];
if i<>c then Q[i]:=true
else Q[i]:=false;
end;
while not isEmpty(Q) do begin
min:=minimum(D);
Q[min]:=false;
for i:=1 to 3354 do begin
if ggraf[min][i]=1 then
if D[i]>D[min]+1 then D[i]:=D[min]+1;
end;
end;
dijkstra:=D;
end;
function makeRoad(map:matrix;head:psnake;food:point):pmoves;
var
q:pmoves;
D:distances;
c:integer;
ggraf:graf;
function makeGraf(map:matrix;head:psnake):graf;
var
x,y,c:integer;
function obstacle(x,y:integer):boolean;
var
i:integer;
q:psnake;
begin
obstacle:=false;
i:=3;
while map[i][1]<>99 do begin
if (map[i][1]=x) and (map[i][2]=y) then obstacle:=true;
i:=i+1;
end;
q:=head;
while q<>nil do begin
if (q^.x=x) and (q^.y=y) then obstacle:=true;
q:=q^.next;
end;
end;
begin
{c = x+(y-1)*78(max_x-2)
x=c mod 78
y=c div 78 +1
}
//ustawiam graf na domyslna wersje - zero powiazan i 0 na przekatnej
for x:=1 to 3354 do
for y:=1 to 3354 do
makeGraf[x][y]:=INF;
for x:=1 to 3354 do
makeGraf[x][x]:=0;
//teraz zalatwiam srodkowa czesc
for x:=2 to 77 do begin
for y:=2 to 42 do begin
c:=x+(y-1)*78;
if not obstacle(x-1,y+1) then makeGraf[c][x-1+(y)*78]:=1;
if not obstacle(x,y+1) then makeGraf[c][x+(y)*78]:=1;
if not obstacle(x+1,y+1) then makeGraf[c][x+1+(y)*78]:=1;
if not obstacle(x-1,y) then makeGraf[c][x-1+(y-1)*78]:=1;
if not obstacle(x+1,y) then makeGraf[c][x+1+(y-1)*78]:=1;
if not obstacle(x-1,y-1) then makeGraf[c][x-1+(y-2)*78]:=1;
if not obstacle(x,y-1) then makeGraf[c][x+(y-2)*78]:=1;
if not obstacle(x+1,y-1) then makeGraf[c][x+1+(y-2)*78]:=1;
end;
end;
//teraz wypelniam 4 krawedzie
for x:=1 to 78 do begin
if not obstacle(x,0) then makeGraf[x][x+42*78]:=1;
if not obstacle(x,44) then makeGraf[x+42*78][x]:=1;
end;
for y:=1 to 43 do begin
if not obstacle(0,y) then makeGraf[1+(y-1)*78][78+(y-1)*78]:=1;
if not obstacle(79,y) then makeGraf[78+(y-1)*78][1+(y-1)*78]:=1;
end;
//pora i na teleporty
if not obstacle(map[2][1],map[2][2]+1) then makeGraf[map[1][1]+(map[1][2]-2)*78][map[2][1]+(map[2][2])*78]:=1;
if not obstacle(map[2][1]-1,map[2][2]) then makeGraf[map[1][1]+1+(map[1][2]-1)*78][map[2][1]-1+(map[2][2]-1)*78]:=1;
if not obstacle(map[2][1],map[2][2]-1) then makeGraf[map[1][1]+(map[1][2])*78][map[2][1]+(map[2][2]-2)*78]:=1;
if not obstacle(map[2][1]+1,map[2][2]) then makeGraf[map[1][1]-1+(map[1][2]-1)*78][map[2][1]+1+(map[2][2]-1)*78]:=1;
if not obstacle(map[1][1],map[1][2]+1) then makeGraf[map[2][1]+(map[2][1]-2)*78][map[1][1]+(map[1][2])*78]:=1;
if not obstacle(map[1][1]-1,map[1][2]) then makeGraf[map[2][1]+1+(map[2][1]-1)*78][map[1][1]-1+(map[1][2]-1)*78]:=1;
if not obstacle(map[1][1],map[1][2]-1) then makeGraf[map[2][1]+(map[2][1])*78][map[1][1]+(map[1][2]-2)*78]:=1;
if not obstacle(map[1][1]+1,map[1][2]) then makeGraf[map[2][1]-1+(map[2][1]-1)*78][map[1][1]+1+(map[1][2]-1)*78]:=1;
end;
begin
ggraf:=makeGraf(map,head);
D:=dijkstra(map,head,food,ggraf);
new(q);
q^.next:=nil;
q^.prev:=nil;
q^.x:=food.x;
q^.y:=food.y;
while (q^.x<>head^.x) or (q^.y<>head^.y) do begin
c:=1;
while (D[c]<>D[q^.x+(q^.y-1)*78]-1) or (ggraf[q^.x+(q^.y-1)*78][c]<>1) do c:=c+1;
new(q^.prev);
q^.prev^.next:=q;
q:=q^.prev;
q^.prev:=nil;
q^.x:=c mod 78;
q^.y:=(c div 78)+1;
end;
makeRoad:=q;
end;