MODULE path;
IMPORT B := Basic,
M:=MapSquares;
CONST
found=1;
pathsuccess=1;
CantCreatePathError=2;
startisenderror=3;
occupiederror=4;
floor=3;
wall=2;
maxopenlistitems=99;
TYPE
string=ARRAY OF CHAR;
VAR
path:INTEGER;
StepsOnPath*:INTEGER;
PathBlockedByPerson:SHORTINT;
PathBlocker:INTEGER;
numberofopenlistitems:INTEGER;
LowestFCostSquareX:SHORTINT;
LowestFCostSquareY:SHORTINT;
xiter:SHORTINT;
yiter:SHORTINT;
SquareState*:ARRAY 32,24 OF SHORTINT;
OpenListX:ARRAY 100 OF SHORTINT;
OpenListY:ARRAY 100 OF SHORTINT;
SquareParentX:ARRAY 32,24 OF SHORTINT;
SquareParentY:ARRAY 32,24 OF SHORTINT;
HCost:ARRAY 32,24 OF SHORTINT;
PathToWalkX*:ARRAY 100 OF SHORTINT;
PathToWalkY*:ARRAY 100 OF SHORTINT;
SquaresChecked*:INTEGER;
(*PROCEDURE pathfindmessage(msg:string);
BEGIN
B.PRSTR(msg);
END pathfindmessage;
*)
PROCEDURE ClearPath*();
VAR
x,y:SHORTINT;
BEGIN
(*
FOR x:=0 TO 31 DO
FOR y:=0 TO 23 DO
Graph.RedrawSquare(x,y);
END;
END;
*)
FOR x:=0 TO maxopenlistitems DO
OpenListX[x]:=0;
OpenListY[x]:=0;
END;
FOR x:=0 TO 31 DO
FOR y:=0 TO 23 DO
SquareState[x][y]:=0;
SquareParentX[x][y]:=0;
SquareParentY[x][y]:=0;
HCost[x][y]:=0;
END;
END;
SquaresChecked:=0;
StepsOnPath:=0;
PathBlockedByPerson:=0;
PathBlocker:=0;
numberofopenlistitems:=0;
END ClearPath;
PROCEDURE GetHCost(squarex:SHORTINT;squarey:SHORTINT;targetx:SHORTINT;targety:SHORTINT):SHORTINT;
BEGIN
RETURN (ABS(squarex-targetx)+ABS(squarey-targety));
END GetHCost;
PROCEDURE OnOpenList(squarex:INTEGER;squarey:INTEGER):INTEGER;
BEGIN
IF SquareState[squarex][squarey]=1 THEN
RETURN 1;
END;
RETURN 0;
END OnOpenList;
PROCEDURE OnClosedList(squarex:INTEGER; squarey:INTEGER):SHORTINT;
BEGIN
IF SquareState[squarex][squarey]=2 THEN
RETURN 1
END;
RETURN 0
END OnClosedList;
PROCEDURE AddToOpenList(squarex:SHORTINT;squarey:SHORTINT;parx:SHORTINT;pary:SHORTINT);
VAR
iter:SHORTINT;
inserted:SHORTINT;
BEGIN
inserted:=0;
SquareParentX[squarex][squarey]:=parx;
SquareParentY[squarex][squarey]:=pary;
numberofopenlistitems:=numberofopenlistitems+1;
IF numberofopenlistitems>maxopenlistitems THEN
B.AT(0,0);
B.PRSTR("open list items ");
B.PRINT(numberofopenlistitems);
END;
IF HCost[squarex][squarey]<HCost[LowestFCostSquareX][LowestFCostSquareY] THEN
LowestFCostSquareX:=squarex;
LowestFCostSquareY:=squarey;
END;
SquareState[squarex][squarey]:=1;
FOR iter:=0 TO maxopenlistitems DO
IF inserted=0 THEN
IF OpenListY[iter]=0 THEN
OpenListX[iter]:=squarex;
OpenListY[iter]:=squarey;
inserted:=1;
END;
END;
END;
B.AT(squarey,squarex);
B.PRSTR( "O");
END AddToOpenList;
PROCEDURE AddToClosedList(squarex:SHORTINT;squarey:SHORTINT);
VAR
dist:INTEGER;
chosenX:SHORTINT;
chosenY:SHORTINT;
x:SHORTINT;
y:SHORTINT;
iter:SHORTINT;
lowesthcost:SHORTINT;
BEGIN
IF LowestFCostSquareX=squarex THEN
IF LowestFCostSquareY=squarey THEN
chosenX:=-1;
chosenY:=-1;
dist:=9999;
(*
FOR x:=0 TO 32 DO
FOR y:=0 TO 23 DO
IF OnOpenList(x,y)=1 THEN
IF HCost[x][y]<dist THEN
dist:=HCost[x][y];
chosenX:=x;
chosenY:=y;
END;
END;
END;
END;
*)
FOR iter:=0 TO maxopenlistitems DO
IF OpenListY[iter]>0 THEN
x:=OpenListX[iter];
y:=OpenListY[iter];
IF (x#squarex) OR (y#squarey) THEN
lowesthcost:=HCost[x][y];
IF lowesthcost<dist THEN
dist:=lowesthcost;
chosenX:=x;
chosenY:=y;
END;
ELSE
OpenListX[iter]:=0;
OpenListY[iter]:=0;
END;
END;
END;
IF chosenX>-1 THEN
LowestFCostSquareX:=chosenX;
LowestFCostSquareY:=chosenY;
END;
END;
END;
IF SquareState[squarex][squarey]=1 THEN
numberofopenlistitems:=numberofopenlistitems-1;
END;
SquareState[squarex][squarey]:=2;
B.AT(squarey,squarex);
B.PRSTR( "C");
END AddToClosedList;
PROCEDURE AddToPath(squarex:SHORTINT;squarey:SHORTINT);
BEGIN
B.AT(squarey,squarex);
B.PRSTR( "P");
END AddToPath;
PROCEDURE CreatePath(StartX:SHORTINT;StartY:SHORTINT;TargetX:SHORTINT;TargetY:SHORTINT) :SHORTINT;
VAR
PathCreated:SHORTINT;
ParX:SHORTINT;
ParY:SHORTINT;
NewParX:SHORTINT;
NewParY:SHORTINT;
BEGIN
PathBlockedByPerson:=0;
PathBlocker:=0;
PathCreated:=0;
StepsOnPath:=StepsOnPath+1;
PathToWalkX[StepsOnPath]:=TargetX;
PathToWalkY[StepsOnPath]:=TargetY;
ParX:=PathToWalkX[StepsOnPath];
ParY:=PathToWalkY[StepsOnPath];
AddToPath(ParX,ParY);
WHILE PathCreated=0 DO
NewParX:=SquareParentX[ParX][ParY];
NewParY:=SquareParentY[ParX][ParY];
ParX:=NewParX;
ParY:=NewParY;
AddToPath(ParX,ParY);
StepsOnPath:=StepsOnPath+1;
IF StepsOnPath>254 THEN
RETURN 2
END;
PathToWalkX[StepsOnPath]:=ParX;
PathToWalkY[StepsOnPath]:=ParY;
(*
M.SquareType[PathToWalkY[StepsOnPath],PathToWalkX[StepsOnPath]]:=floor;
M.SquareNumber[PathToWalkY[StepsOnPath],PathToWalkX[StepsOnPath]]:=99;
*)
IF (PathToWalkX[StepsOnPath]=StartX) & (PathToWalkY[StepsOnPath]=StartY) THEN
PathCreated:=1;
END;
END;
RETURN 1;
END CreatePath;
PROCEDURE CheckSquare(squarex:SHORTINT;squarey:SHORTINT;targetx:SHORTINT;targety:SHORTINT;originalx:SHORTINT;originaly:SHORTINT;countwalls:SHORTINT;countgoblins:SHORTINT);
BEGIN
SquaresChecked:=SquaresChecked+1;
IF squarex>-1 THEN
IF squarex<32 THEN
IF squarey>-1 THEN
IF squarey<24 THEN
(*B.PRSTR("Check square");*)
(*CHR(squarex+48)+" "+STR(squarey));*)
IF (M.SquareOccupied[squarex][squarey]=0) OR (countwalls=0) OR (countgoblins=0) THEN
IF (M.SquareType[squarex][squarey]=floor) OR (countwalls=0) THEN
IF OnClosedList(squarex,squarey)=0 THEN
IF OnOpenList(squarex,squarey)=0 THEN
(*pathfindmessage("not on open list");*)
IF (squarex=targetx)&(squarey=targety)THEN
path:=found;
END;
HCost[squarex][squarey]:=GetHCost(squarex,squarey,targetx,targety);
AddToOpenList(squarex,squarey,originalx,originaly);
IF path=found THEN
SquareParentX[squarex][squarey]:=originalx;
SquareParentY[squarex][squarey]:=originaly;
(*pathfindmessage("path is found");*)
AddToClosedList(squarex,squarey);
END;
END;
END;
END;
END;
END;
END;
END;
END;
END CheckSquare;
PROCEDURE FindPath *(startx:SHORTINT;starty:SHORTINT;targetx:SHORTINT;targety:SHORTINT;countwalls:SHORTINT;countgoblins:SHORTINT):SHORTINT;
VAR
DebugIter:INTEGER;
lowx:SHORTINT;
lowy:SHORTINT;
BEGIN
ClearPath();
DebugIter:=0;
(*
B.AT(starty,startx);
B.PRSTR("S");
B.AT(targety,targetx);
B.PRSTR("E");
*)
(*
B.PRINT(startx);
B.PRSTR(" ");
B.PRINT(starty);
B.PRSTR(" ");
B.PRINT(targetx);
B.PRSTR(" ");
B.PRINT(targety);
*)
IF (startx =targetx) & (starty = targety) THEN
B.AT(2,0);
B.PRSTR("target square = start square");
RETURN startisenderror
END;
IF (M.SquareOccupied[targetx][targety]#0) & (countgoblins=1) THEN
(*B.AT(2,0);
B.PRSTR("target square occupied");
*)
RETURN occupiederror
END;
HCost[startx][starty]:=GetHCost(startx,starty,targetx,targety);
AddToOpenList(startx,starty,startx,starty);
LowestFCostSquareX:=startx;
LowestFCostSquareY:=starty;
path:=-1;
WHILE (path=-1) DO
DebugIter:=DebugIter+1;
IF DebugIter>400 THEN
B.AT(2,0);
B.PRSTR("done 400 iters");
path:=-2
END;
IF numberofopenlistitems=0 THEN
(*B.AT(2,0);
B.PRSTR("no more open list items");
*)
path:=-2
END;
(*pathfindmessage("Lowest f cost square "+STR(LowestFCostSquareX)+" "+STR(LowestFCostSquareY))*)
lowx:=LowestFCostSquareX;
lowy:=LowestFCostSquareY;
CheckSquare(lowx+1,lowy,targetx,targety,lowx,lowy,countwalls,countgoblins);
CheckSquare(lowx-1,lowy,targetx,targety,lowx,lowy,countwalls,countgoblins);
CheckSquare(lowx,lowy+1,targetx,targety,lowx,lowy,countwalls,countgoblins);
CheckSquare(lowx,lowy-1,targetx,targety,lowx,lowy,countwalls,countgoblins);
IF path#found THEN
AddToClosedList(lowx,lowy);
END;
END;
IF path = found THEN
(*Print "path was found"*)
IF CreatePath(startx , starty , targetx ,targety)#1 THEN
RETURN CantCreatePathError;
END;
RETURN 1 ;
END;
RETURN 0;
END FindPath;
BEGIN
FOR xiter:=0 TO 22 DO
FOR yiter:=0 TO 31 DO
SquareState[xiter][yiter]:=0;
END;
END;
END path.