Оберон-клуб «ВЄДАsoft»

Твердыня модульных языков
Текущее время: 19 мар 2024, 06:27

Часовой пояс: UTC + 2 часа




Начать новую тему Ответить на тему  [ Сообщений: 4 ] 
Автор Сообщение
 Заголовок сообщения: Pathfinding
СообщениеДобавлено: 15 авг 2017, 16:37 
Не в сети

Сообщения: 104
how to call the function example:
Код: "OBERON"
  1.  
  2. MODULE Hello;
  3. IMPORT B:=Basic,
  4. P:=Path,M:=Mapsquares;
  5. CONST
  6. floor=3;
  7. wall=2;
  8. VAR
  9. result:SHORTINT;
  10. x:SHORTINT;
  11. y:SHORTINT;
  12. BEGIN
  13.  
  14. FOR x:=0 TO 31 DO
  15. FOR y:=0 TO 23 DO
  16. M.SquareType[x][y]:=floor;
  17. END;
  18. END;
  19.  
  20. M.SquareType[0][6]:=wall;
  21. B.AT(6,0);
  22. B.PRSTR( "W");
  23. M.SquareType[1][5]:=wall;
  24. B.AT(5,1);
  25. B.PRSTR( "W");
  26.  
  27. result:=P.FindPath (0,5,15,5,1,1);
  28.  
  29. END Hello.


You have to specify which squares are floor and which are walls
findpath is (startx,starty,endx,endy,countwalls,countunits)

countwalls makes the p ath go around walls
countunits makes the path go around units (game characters)

here is path.mod
Код: "OBERON"
  1.  
  2. MODULE path;
  3. IMPORT B := Basic,
  4. M:=MapSquares;
  5. CONST
  6. found=1;
  7. pathsuccess=1;
  8. CantCreatePathError=2;
  9. startisenderror=3;
  10. occupiederror=4;
  11. floor=3;
  12. wall=2;
  13. maxopenlistitems=99;
  14. TYPE
  15. string=ARRAY OF CHAR;
  16. VAR
  17. path:INTEGER;
  18. StepsOnPath*:INTEGER;
  19. PathBlockedByPerson:SHORTINT;
  20. PathBlocker:INTEGER;
  21. numberofopenlistitems:INTEGER;
  22. LowestFCostSquareX:SHORTINT;
  23. LowestFCostSquareY:SHORTINT;
  24. xiter:SHORTINT;
  25. yiter:SHORTINT;
  26. SquareState*:ARRAY 32,24 OF SHORTINT;
  27. OpenListX:ARRAY 100 OF SHORTINT;
  28. OpenListY:ARRAY 100 OF SHORTINT;
  29. SquareParentX:ARRAY 32,24 OF SHORTINT;
  30. SquareParentY:ARRAY 32,24 OF SHORTINT;
  31. HCost:ARRAY 32,24 OF SHORTINT;
  32. PathToWalkX*:ARRAY 100 OF SHORTINT;
  33. PathToWalkY*:ARRAY 100 OF SHORTINT;
  34. SquaresChecked*:INTEGER;
  35.  
  36. (*PROCEDURE pathfindmessage(msg:string);
  37. BEGIN
  38. B.PRSTR(msg);
  39. END pathfindmessage;
  40. *)
  41.  
  42. PROCEDURE ClearPath*();
  43. VAR
  44. x,y:SHORTINT;
  45. BEGIN
  46. (*
  47. FOR x:=0 TO 31 DO
  48. FOR y:=0 TO 23 DO
  49. Graph.RedrawSquare(x,y);
  50. END;
  51. END;
  52. *)
  53. FOR x:=0 TO maxopenlistitems DO
  54. OpenListX[x]:=0;
  55. OpenListY[x]:=0;
  56. END;
  57.  
  58. FOR x:=0 TO 31 DO
  59. FOR y:=0 TO 23 DO
  60. SquareState[x][y]:=0;
  61. SquareParentX[x][y]:=0;
  62. SquareParentY[x][y]:=0;
  63. HCost[x][y]:=0;
  64.  
  65.  
  66. END;
  67. END;
  68.  
  69. SquaresChecked:=0;
  70. StepsOnPath:=0;
  71. PathBlockedByPerson:=0;
  72. PathBlocker:=0;
  73. numberofopenlistitems:=0;
  74.  
  75. END ClearPath;
  76. PROCEDURE GetHCost(squarex:SHORTINT;squarey:SHORTINT;targetx:SHORTINT;targety:SHORTINT):SHORTINT;
  77. BEGIN
  78. RETURN (ABS(squarex-targetx)+ABS(squarey-targety));
  79. END GetHCost;
  80.  
  81. PROCEDURE OnOpenList(squarex:INTEGER;squarey:INTEGER):INTEGER;
  82. BEGIN
  83. IF SquareState[squarex][squarey]=1 THEN
  84. RETURN 1;
  85. END;
  86. RETURN 0;
  87. END OnOpenList;
  88.  
  89. PROCEDURE OnClosedList(squarex:INTEGER; squarey:INTEGER):SHORTINT;
  90. BEGIN
  91. IF SquareState[squarex][squarey]=2 THEN
  92. RETURN 1
  93. END;
  94. RETURN 0
  95. END OnClosedList;
  96.  
  97.  
  98. PROCEDURE AddToOpenList(squarex:SHORTINT;squarey:SHORTINT;parx:SHORTINT;pary:SHORTINT);
  99. VAR
  100. iter:SHORTINT;
  101. inserted:SHORTINT;
  102. BEGIN
  103. inserted:=0;
  104. SquareParentX[squarex][squarey]:=parx;
  105. SquareParentY[squarex][squarey]:=pary;
  106. numberofopenlistitems:=numberofopenlistitems+1;
  107.  
  108. IF numberofopenlistitems>maxopenlistitems THEN
  109. B.AT(0,0);
  110. B.PRSTR("open list items ");
  111. B.PRINT(numberofopenlistitems);
  112. END;
  113.  
  114. IF HCost[squarex][squarey]<HCost[LowestFCostSquareX][LowestFCostSquareY] THEN
  115. LowestFCostSquareX:=squarex;
  116. LowestFCostSquareY:=squarey;
  117. END;
  118.  
  119. SquareState[squarex][squarey]:=1;
  120.  
  121. FOR iter:=0 TO maxopenlistitems DO
  122. IF inserted=0 THEN
  123. IF OpenListY[iter]=0 THEN
  124. OpenListX[iter]:=squarex;
  125. OpenListY[iter]:=squarey;
  126. inserted:=1;
  127. END;
  128. END;
  129. END;
  130.  
  131.  
  132. B.AT(squarey,squarex);
  133.  
  134. B.PRSTR( "O");
  135.  
  136. END AddToOpenList;
  137.  
  138. PROCEDURE AddToClosedList(squarex:SHORTINT;squarey:SHORTINT);
  139. VAR
  140. dist:INTEGER;
  141. chosenX:SHORTINT;
  142. chosenY:SHORTINT;
  143. x:SHORTINT;
  144. y:SHORTINT;
  145. iter:SHORTINT;
  146. lowesthcost:SHORTINT;
  147. BEGIN
  148. IF LowestFCostSquareX=squarex THEN
  149. IF LowestFCostSquareY=squarey THEN
  150. chosenX:=-1;
  151. chosenY:=-1;
  152.  
  153. dist:=9999;
  154. (*
  155. FOR x:=0 TO 32 DO
  156. FOR y:=0 TO 23 DO
  157. IF OnOpenList(x,y)=1 THEN
  158. IF HCost[x][y]<dist THEN
  159. dist:=HCost[x][y];
  160. chosenX:=x;
  161. chosenY:=y;
  162. END;
  163. END;
  164. END;
  165. END;
  166.  
  167. *)
  168.  
  169. FOR iter:=0 TO maxopenlistitems DO
  170. IF OpenListY[iter]>0 THEN
  171. x:=OpenListX[iter];
  172. y:=OpenListY[iter];
  173. IF (x#squarex) OR (y#squarey) THEN
  174. lowesthcost:=HCost[x][y];
  175. IF lowesthcost<dist THEN
  176. dist:=lowesthcost;
  177. chosenX:=x;
  178. chosenY:=y;
  179. END;
  180. ELSE
  181. OpenListX[iter]:=0;
  182. OpenListY[iter]:=0;
  183. END;
  184.  
  185. END;
  186. END;
  187.  
  188. IF chosenX>-1 THEN
  189. LowestFCostSquareX:=chosenX;
  190. LowestFCostSquareY:=chosenY;
  191. END;
  192.  
  193. END;
  194. END;
  195.  
  196. IF SquareState[squarex][squarey]=1 THEN
  197. numberofopenlistitems:=numberofopenlistitems-1;
  198. END;
  199. SquareState[squarex][squarey]:=2;
  200.  
  201. B.AT(squarey,squarex);
  202. B.PRSTR( "C");
  203.  
  204. END AddToClosedList;
  205.  
  206. PROCEDURE AddToPath(squarex:SHORTINT;squarey:SHORTINT);
  207. BEGIN
  208.  
  209. B.AT(squarey,squarex);
  210. B.PRSTR( "P");
  211.  
  212. END AddToPath;
  213.  
  214. PROCEDURE CreatePath(StartX:SHORTINT;StartY:SHORTINT;TargetX:SHORTINT;TargetY:SHORTINT) :SHORTINT;
  215. VAR
  216. PathCreated:SHORTINT;
  217. ParX:SHORTINT;
  218. ParY:SHORTINT;
  219. NewParX:SHORTINT;
  220. NewParY:SHORTINT;
  221. BEGIN
  222. PathBlockedByPerson:=0;
  223. PathBlocker:=0;
  224. PathCreated:=0;
  225. StepsOnPath:=StepsOnPath+1;
  226. PathToWalkX[StepsOnPath]:=TargetX;
  227. PathToWalkY[StepsOnPath]:=TargetY;
  228. ParX:=PathToWalkX[StepsOnPath];
  229. ParY:=PathToWalkY[StepsOnPath];
  230. AddToPath(ParX,ParY);
  231. WHILE PathCreated=0 DO
  232. NewParX:=SquareParentX[ParX][ParY];
  233. NewParY:=SquareParentY[ParX][ParY];
  234. ParX:=NewParX;
  235. ParY:=NewParY;
  236. AddToPath(ParX,ParY);
  237. StepsOnPath:=StepsOnPath+1;
  238. IF StepsOnPath>254 THEN
  239. RETURN 2
  240. END;
  241. PathToWalkX[StepsOnPath]:=ParX;
  242. PathToWalkY[StepsOnPath]:=ParY;
  243.  
  244. (*
  245. M.SquareType[PathToWalkY[StepsOnPath],PathToWalkX[StepsOnPath]]:=floor;
  246. M.SquareNumber[PathToWalkY[StepsOnPath],PathToWalkX[StepsOnPath]]:=99;
  247. *)
  248. IF (PathToWalkX[StepsOnPath]=StartX) & (PathToWalkY[StepsOnPath]=StartY) THEN
  249. PathCreated:=1;
  250. END;
  251.  
  252. END;
  253.  
  254. RETURN 1;
  255. END CreatePath;
  256.  
  257.  
  258.  
  259.  
  260. PROCEDURE CheckSquare(squarex:SHORTINT;squarey:SHORTINT;targetx:SHORTINT;targety:SHORTINT;originalx:SHORTINT;originaly:SHORTINT;countwalls:SHORTINT;countgoblins:SHORTINT);
  261. BEGIN
  262. SquaresChecked:=SquaresChecked+1;
  263. IF squarex>-1 THEN
  264. IF squarex<32 THEN
  265. IF squarey>-1 THEN
  266. IF squarey<24 THEN
  267.  
  268. (*B.PRSTR("Check square");*)
  269. (*CHR(squarex+48)+" "+STR(squarey));*)
  270. IF (M.SquareOccupied[squarex][squarey]=0) OR (countwalls=0) OR (countgoblins=0) THEN
  271. IF (M.SquareType[squarex][squarey]=floor) OR (countwalls=0) THEN
  272. IF OnClosedList(squarex,squarey)=0 THEN
  273.  
  274. IF OnOpenList(squarex,squarey)=0 THEN
  275. (*pathfindmessage("not on open list");*)
  276.  
  277. IF (squarex=targetx)&(squarey=targety)THEN
  278. path:=found;
  279. END;
  280.  
  281. HCost[squarex][squarey]:=GetHCost(squarex,squarey,targetx,targety);
  282.  
  283. AddToOpenList(squarex,squarey,originalx,originaly);
  284.  
  285. IF path=found THEN
  286. SquareParentX[squarex][squarey]:=originalx;
  287. SquareParentY[squarex][squarey]:=originaly;
  288. (*pathfindmessage("path is found");*)
  289. AddToClosedList(squarex,squarey);
  290.  
  291. END;
  292.  
  293.  
  294. END;
  295. END;
  296.  
  297. END;
  298. END;
  299. END;
  300. END;
  301. END;
  302. END;
  303. END CheckSquare;
  304.  
  305. PROCEDURE FindPath *(startx:SHORTINT;starty:SHORTINT;targetx:SHORTINT;targety:SHORTINT;countwalls:SHORTINT;countgoblins:SHORTINT):SHORTINT;
  306. VAR
  307. DebugIter:INTEGER;
  308. lowx:SHORTINT;
  309. lowy:SHORTINT;
  310.  
  311. BEGIN
  312. ClearPath();
  313. DebugIter:=0;
  314.  
  315. (*
  316. B.AT(starty,startx);
  317. B.PRSTR("S");
  318. B.AT(targety,targetx);
  319. B.PRSTR("E");
  320. *)
  321. (*
  322. B.PRINT(startx);
  323. B.PRSTR(" ");
  324. B.PRINT(starty);
  325. B.PRSTR(" ");
  326. B.PRINT(targetx);
  327. B.PRSTR(" ");
  328. B.PRINT(targety);
  329. *)
  330.  
  331. IF (startx =targetx) & (starty = targety) THEN
  332. B.AT(2,0);
  333. B.PRSTR("target square = start square");
  334. RETURN startisenderror
  335. END;
  336. IF (M.SquareOccupied[targetx][targety]#0) & (countgoblins=1) THEN
  337. (*B.AT(2,0);
  338. B.PRSTR("target square occupied");
  339. *)
  340. RETURN occupiederror
  341. END;
  342. HCost[startx][starty]:=GetHCost(startx,starty,targetx,targety);
  343. AddToOpenList(startx,starty,startx,starty);
  344. LowestFCostSquareX:=startx;
  345. LowestFCostSquareY:=starty;
  346.  
  347. path:=-1;
  348.  
  349. WHILE (path=-1) DO
  350. DebugIter:=DebugIter+1;
  351.  
  352. IF DebugIter>400 THEN
  353. B.AT(2,0);
  354. B.PRSTR("done 400 iters");
  355.  
  356. path:=-2
  357. END;
  358.  
  359. IF numberofopenlistitems=0 THEN
  360. (*B.AT(2,0);
  361. B.PRSTR("no more open list items");
  362. *)
  363. path:=-2
  364. END;
  365.  
  366. (*pathfindmessage("Lowest f cost square "+STR(LowestFCostSquareX)+" "+STR(LowestFCostSquareY))*)
  367.  
  368.  
  369. lowx:=LowestFCostSquareX;
  370. lowy:=LowestFCostSquareY;
  371. CheckSquare(lowx+1,lowy,targetx,targety,lowx,lowy,countwalls,countgoblins);
  372. CheckSquare(lowx-1,lowy,targetx,targety,lowx,lowy,countwalls,countgoblins);
  373. CheckSquare(lowx,lowy+1,targetx,targety,lowx,lowy,countwalls,countgoblins);
  374. CheckSquare(lowx,lowy-1,targetx,targety,lowx,lowy,countwalls,countgoblins);
  375. IF path#found THEN
  376. AddToClosedList(lowx,lowy);
  377. END;
  378.  
  379. END;
  380.  
  381. IF path = found THEN
  382. (*Print "path was found"*)
  383. IF CreatePath(startx , starty , targetx ,targety)#1 THEN
  384. RETURN CantCreatePathError;
  385. END;
  386.  
  387. RETURN 1 ;
  388. END;
  389.  
  390. RETURN 0;
  391. END FindPath;
  392.  
  393. BEGIN
  394.  
  395. FOR xiter:=0 TO 22 DO
  396. FOR yiter:=0 TO 31 DO
  397. SquareState[xiter][yiter]:=0;
  398. END;
  399. END;
  400.  
  401. END path.
  402.  
  403.  


and MapSquares.mod

Код: "OBERON"
  1.  
  2. MODULE MapSquares;
  3. IMPORT B:=Basic;
  4. VAR
  5. SquareOccupied*:ARRAY 32,24 OF SHORTINT;
  6. SquareNumber*:ARRAY 32,24 OF SHORTINT;
  7. SquareType*:ARRAY 32,24 OF SHORTINT;
  8. xiter:INTEGER;
  9. yiter:INTEGER;
  10.  
  11. BEGIN
  12. B.AT(3,0);
  13. B.PRSTR("Mapsquares");
  14. FOR xiter:=0 TO 31 DO
  15. FOR yiter:=0 TO 23 DO
  16. SquareOccupied[xiter][yiter]:=0;
  17. SquareNumber[xiter][yiter]:=0;
  18. SquareType[xiter][yiter]:=0;
  19. END;
  20. END;
  21.  
  22.  
  23. END MapSquares.
  24.  


Вернуться к началу
 Профиль  
Ответить с цитатой  
 Заголовок сообщения: Re: Pathfinding
СообщениеДобавлено: 16 авг 2017, 13:32 
Не в сети
Аватара пользователя

Сообщения: 1019
Откуда: Днепропетровская обл.
Thanks! Looks very awesome!


Вернуться к началу
 Профиль  
Ответить с цитатой  
 Заголовок сообщения: Re: Pathfinding
СообщениеДобавлено: 16 авг 2017, 13:35 
Не в сети

Сообщения: 104
you're welcome

the array M.SquareOccupied[squarex][squarey]

is for keeping track of game characters being on what squares

SquareNumber[][] isnt used and can be removed


Вернуться к началу
 Профиль  
Ответить с цитатой  
 Заголовок сообщения: Re: Pathfinding
СообщениеДобавлено: 17 авг 2017, 08:11 
Не в сети
Аватара пользователя

Сообщения: 1019
Откуда: Днепропетровская обл.
Aha OK.

Btw, if you like, just write arr[x, y] instead of arr[x][y] - Oberon-way vs C-way. Both are supported.


Вернуться к началу
 Профиль  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Часовой пояс: UTC + 2 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
© VEDAsoft Oberon Club