API tools faq
paste
armark1ng

Untitled

armark1ng
May 28th, 2016
79
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 31.01 KB | None | 0 0
raw download clone embed print report
  1. package com.rs.game.route;
  2.  
  3. import com.rs.game.Region;
  4. import com.rs.game.RegionMap;
  5. import com.rs.game.World;
  6.  
  7. /**
  8. * Walking route finder working on third flag range, designed for walking routes.
  9. * @author Mangis
  10. */
  11. public class WalkRouteFinder {
  12. private static final int GRAPH_SIZE = 128;
  13. private static final int QUEUE_SIZE = (GRAPH_SIZE * GRAPH_SIZE) / 4; // we do /4 because each tile can only be accessed from single direction
  14. private static final int ALTERNATIVE_ROUTE_MAX_DISTANCE = 100;
  15. private static final int ALTERNATIVE_ROUTE_RANGE = 10;
  16.  
  17. private static final int DIR_NORTH = 0x1;
  18. private static final int DIR_EAST = 0x2;
  19. private static final int DIR_SOUTH = 0x4;
  20. private static final int DIR_WEST = 0x8;
  21.  
  22. private static final int[][] directions = new int[GRAPH_SIZE][GRAPH_SIZE];
  23. private static final int[][] distances = new int[GRAPH_SIZE][GRAPH_SIZE];
  24. private static final int[][] clip = new int[GRAPH_SIZE][GRAPH_SIZE];
  25. private static final int[] bufferX = new int[QUEUE_SIZE];
  26. private static final int[] bufferY = new int[QUEUE_SIZE];
  27. private static int exitX = -1;
  28. private static int exitY = -1;
  29. private static boolean isAlternative;
  30.  
  31. public static boolean debug = true;
  32. public static long debug_transmittime = 0;
  33.  
  34.  
  35.  
  36. /**
  37. * Find's route using given strategy.
  38. * Returns amount of steps found.
  39. * If steps > 0, route exists.
  40. * If steps = 0, route exists, but no need to move.
  41. * If steps < 0, route does not exist.
  42. */
  43. protected static int findRoute(int srcX, int srcY, int srcZ, int srcSizeXY, RouteStrategy strategy, boolean findAlternative) {
  44. isAlternative = false;
  45. for (int x = 0; x < GRAPH_SIZE; x++) {
  46. for (int y = 0; y < GRAPH_SIZE; y++) {
  47. directions[x][y] = 0;
  48. distances[x][y] = 99999999;
  49. }
  50. }
  51.  
  52. if (debug) {
  53. long start = System.nanoTime();
  54. transmitClipData(srcX, srcY, srcZ);
  55. debug_transmittime = System.nanoTime() - start;
  56. }
  57. else {
  58. transmitClipData(srcX, srcY, srcZ);
  59. }
  60.  
  61. // we could use performCalculationSX() for every size, but since most common size's are 1 and 2,
  62. // we will have optimized algorhytm's for them.
  63. boolean found = false;
  64. switch (srcSizeXY) {
  65. case 1:
  66. found = performCalculationS1(srcX, srcY, strategy);
  67. break;
  68. case 2:
  69. found = performCalculationS2(srcX, srcY, strategy);
  70. break;
  71. default:
  72. found = performCalculationSX(srcX, srcY, srcSizeXY, strategy);
  73. break;
  74. }
  75.  
  76. if (!found && !findAlternative)
  77. return -1;
  78.  
  79. // when we start searching for path, we position ourselves in the middle of graph
  80. // so the base(minimum) position is source_pos - HALF_GRAPH_SIZE.
  81. int graphBaseX = srcX - (GRAPH_SIZE / 2);
  82. int graphBaseY = srcY - (GRAPH_SIZE / 2);
  83. int endX = exitX;
  84. int endY = exitY;
  85.  
  86. if (!found && findAlternative) {
  87. isAlternative = true;
  88. int lowestCost = Integer.MAX_VALUE;
  89. int lowestDistance = Integer.MAX_VALUE;
  90.  
  91. int approxDestX = strategy.getApproxDestinationX();
  92. int approxDestY = strategy.getApproxDestinationY();
  93.  
  94. // what we will do here is search the coordinates range of destination +- ALTERNATIVE_ROUTE_RANGE
  95. // to see if at least one position in that range is reachable, and reaching it takes no longer than ALTERNATIVE_ROUTE_MAX_DISTANCE steps.
  96. // if we have multiple positions in our range that fits all the conditions, we will choose the one which takes fewer steps.
  97.  
  98. for (int checkX = (approxDestX - ALTERNATIVE_ROUTE_RANGE); checkX <= (approxDestX + ALTERNATIVE_ROUTE_RANGE); checkX++) {
  99. for (int checkY = (approxDestY - ALTERNATIVE_ROUTE_RANGE); checkY <= (approxDestY + ALTERNATIVE_ROUTE_RANGE); checkY++) {
  100. int graphX = checkX - graphBaseX;
  101. int graphY = checkY - graphBaseY;
  102. if (graphX < 0 || graphY < 0 || graphX >= GRAPH_SIZE || graphY >= GRAPH_SIZE || distances[graphX][graphY] >= ALTERNATIVE_ROUTE_MAX_DISTANCE)
  103. continue; // we are out of graph's bounds or too much steps.
  104. // calculate the delta's.
  105. // when calculating, we are also taking the approximated destination size into account to increase precise.
  106. int deltaX = 0;
  107. int deltaY = 0;
  108. if (approxDestX <= checkX) {
  109. deltaX = 1 - approxDestX - (strategy.getApproxDestinationSizeX() - checkX);
  110. //deltaX = (approxDestX + (strategy.getApproxDestinationSizeX() - 1)) < checkX ? (approxDestX - (checkX - (strategy.getApproxDestinationSizeX() + 1))) : 0;
  111. } else
  112. deltaX = approxDestX - checkX;
  113. if (approxDestY <= checkY) {
  114. deltaY = 1 - approxDestY - (strategy.getApproxDestinationSizeY() - checkY);
  115. //deltaY = (approxDestY + (strategy.getApproxDestinationSizeY() - 1)) < checkY ? (approxDestY - (checkY - (strategy.getApproxDestinationSizeY() + 1))) : 0;
  116. } else
  117. deltaY = approxDestY - checkY;
  118.  
  119. int cost = (deltaX * deltaX) + (deltaY * deltaY);
  120. if (cost < lowestCost || (cost <= lowestCost && distances[graphX][graphY] < lowestDistance)) {
  121. // if the cost is lower than the lowest one, or same as the lowest one, but less steps, we accept this position as alternate.
  122. lowestCost = cost;
  123. lowestDistance = distances[graphX][graphY];
  124. endX = checkX;
  125. endY = checkY;
  126. }
  127. }
  128. }
  129.  
  130. if (lowestCost == Integer.MAX_VALUE || lowestDistance == Integer.MAX_VALUE)
  131. return -1; // we didin't find any alternative route, sadly.
  132. }
  133.  
  134. if (endX == srcX && endY == srcY)
  135. return 0; // path was found, but we didin't move
  136.  
  137. // what we will do now is trace the path from the end position
  138. // for faster performance, we are reusing our queue buffer for another purpose.
  139. int steps = 0;
  140. int traceX = endX;
  141. int traceY = endY;
  142. int direction = directions[traceX - graphBaseX][traceY - graphBaseY];
  143. int lastwritten = direction;
  144. // queue destination position and start tracing from it
  145. bufferX[steps] = traceX;
  146. bufferY[steps++] = traceY;
  147. while (traceX != srcX || traceY != srcY) {
  148. if (lastwritten != direction) {
  149. // we changed our direction, write it
  150. bufferX[steps] = traceX;
  151. bufferY[steps++] = traceY;
  152. lastwritten = direction;
  153. }
  154.  
  155. if ((direction & DIR_EAST) != 0)
  156. traceX++;
  157. else if ((direction & DIR_WEST) != 0)
  158. traceX--;
  159.  
  160. if ((direction & DIR_NORTH) != 0)
  161. traceY++;
  162. else if ((direction & DIR_SOUTH) != 0)
  163. traceY--;
  164.  
  165. direction = directions[traceX - graphBaseX][traceY - graphBaseY];
  166. }
  167.  
  168. return steps;
  169. }
  170.  
  171.  
  172. /**
  173. * Perform's size 1 calculations.
  174. */
  175. private static boolean performCalculationS1(int srcX, int srcY, RouteStrategy strategy) {
  176. // first, we will cache our static fields to local variables, this is done for performance, because
  177. // modern jit compiler's usually takes advantage of things like this
  178. int[][] _directions = directions;
  179. int[][] _distances = distances;
  180. int[][] _clip = clip;
  181. int[] _bufferX = bufferX;
  182. int[] _bufferY = bufferY;
  183.  
  184.  
  185. // when we start searching for path, we position ourselves in the middle of graph
  186. // so the base(minimum) position is source_pos - HALF_GRAPH_SIZE.
  187. int graphBaseX = srcX - (GRAPH_SIZE / 2);
  188. int graphBaseY = srcY - (GRAPH_SIZE / 2);
  189. int currentX = srcX;
  190. int currentY = srcY;
  191. int currentGraphX = srcX - graphBaseX;
  192. int currentGraphY = srcY - graphBaseY;
  193.  
  194. // setup information about source tile.
  195. _distances[currentGraphX][currentGraphY] = 0;
  196. _directions[currentGraphX][currentGraphY] = 99;
  197.  
  198. // queue variables
  199. int read = 0, write = 0;
  200. // insert our current position as first queued position.
  201. _bufferX[write] = currentX;
  202. _bufferY[write++] = currentY;
  203.  
  204. while (read != write) {
  205. currentX = _bufferX[read];
  206. currentY = _bufferY[read];
  207. read = (read + 1) & (QUEUE_SIZE - 1);
  208.  
  209. currentGraphX = currentX - graphBaseX;
  210. currentGraphY = currentY - graphBaseY;
  211.  
  212. if (strategy.canExit(currentX, currentY, 1, _clip, graphBaseX, graphBaseY)) {
  213. // we found a path!
  214. exitX = currentX;
  215. exitY = currentY;
  216. return true;
  217. }
  218.  
  219. // if we can't exit at current tile, check where we can go from this tile
  220. int nextDistance = _distances[currentGraphX][currentGraphY] + 1;
  221. if (currentGraphX > 0 && _directions[currentGraphX - 1][currentGraphY] == 0 && (_clip[currentGraphX - 1][currentGraphY] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_EAST_BLOCKSWALK_ALTERNATIVE)) == 0) {
  222. // we can go to west, queue it
  223. _bufferX[write] = currentX - 1;
  224. _bufferY[write] = currentY;
  225. write = (write + 1) & (QUEUE_SIZE - 1);
  226.  
  227. _directions[currentGraphX - 1][currentGraphY] = DIR_EAST;
  228. _distances[currentGraphX - 1][currentGraphY] = nextDistance;
  229. }
  230. if (currentGraphX < (GRAPH_SIZE - 1) && _directions[currentGraphX + 1][currentGraphY] == 0 && (_clip[currentGraphX + 1][currentGraphY] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_WEST_BLOCKSWALK_ALTERNATIVE)) == 0) {
  231. // we can go to east, queue it
  232. _bufferX[write] = currentX + 1;
  233. _bufferY[write] = currentY;
  234. write = (write + 1) & (QUEUE_SIZE - 1);
  235.  
  236. _directions[currentGraphX + 1][currentGraphY] = DIR_WEST;
  237. _distances[currentGraphX + 1][currentGraphY] = nextDistance;
  238. }
  239. if (currentGraphY > 0 && _directions[currentGraphX][currentGraphY - 1] == 0 && (_clip[currentGraphX][currentGraphY - 1] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_NORTH_BLOCKSWALK_ALTERNATIVE)) == 0) {
  240. // we can go to south, queue it
  241. _bufferX[write] = currentX;
  242. _bufferY[write] = currentY - 1;
  243. write = (write + 1) & (QUEUE_SIZE - 1);
  244.  
  245. _directions[currentGraphX][currentGraphY - 1] = DIR_NORTH;
  246. _distances[currentGraphX][currentGraphY - 1] = nextDistance;
  247. }
  248. if (currentGraphY < (GRAPH_SIZE - 1) && _directions[currentGraphX][currentGraphY + 1] == 0 && (_clip[currentGraphX][currentGraphY + 1] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_SOUTH_BLOCKSWALK_ALTERNATIVE)) == 0) {
  249. // we can go to north, queue it
  250. _bufferX[write] = currentX;
  251. _bufferY[write] = currentY + 1;
  252. write = (write + 1) & (QUEUE_SIZE - 1);
  253.  
  254. _directions[currentGraphX][currentGraphY + 1] = DIR_SOUTH;
  255. _distances[currentGraphX][currentGraphY + 1] = nextDistance;
  256. }
  257. // diagonal checks, comment them to disable diagonal routes.
  258. if (currentGraphX > 0 && currentGraphY > 0 && _directions[currentGraphX - 1][currentGraphY - 1] == 0 && (_clip[currentGraphX - 1][currentGraphY - 1] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_NORTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_EAST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_NORTHEAST_BLOCKSWALK_ALTERNATIVE)) == 0 && (_clip[currentGraphX - 1][currentGraphY] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_EAST_BLOCKSWALK_ALTERNATIVE)) == 0 && (clip[currentGraphX][currentGraphY - 1] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_NORTH_BLOCKSWALK_ALTERNATIVE)) == 0) {
  259. // we can go to south west, queue it
  260. _bufferX[write] = currentX - 1;
  261. _bufferY[write] = currentY - 1;
  262. write = (write + 1) & (QUEUE_SIZE - 1);
  263.  
  264. _directions[currentGraphX - 1][currentGraphY - 1] = DIR_NORTH | DIR_EAST;
  265. _distances[currentGraphX - 1][currentGraphY - 1] = nextDistance;
  266. }
  267. if (currentGraphX < (GRAPH_SIZE - 1) && currentGraphY > 0 && _directions[currentGraphX + 1][currentGraphY - 1] == 0 && (_clip[currentGraphX + 1][currentGraphY - 1] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_NORTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_WEST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_NORTHWEST_BLOCKSWALK_ALTERNATIVE)) == 0 && (_clip[currentGraphX + 1][currentGraphY] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_WEST_BLOCKSWALK_ALTERNATIVE)) == 0 && (_clip[currentGraphX][currentGraphY - 1] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_NORTH_BLOCKSWALK_ALTERNATIVE)) == 0) {
  268. // we can go to south east, queue it
  269. _bufferX[write] = currentX + 1;
  270. _bufferY[write] = currentY - 1;
  271. write = (write + 1) & (QUEUE_SIZE - 1);
  272.  
  273. _directions[currentGraphX + 1][currentGraphY - 1] = DIR_NORTH | DIR_WEST;
  274. _distances[currentGraphX + 1][currentGraphY - 1] = nextDistance;
  275. }
  276. if (currentGraphX > 0 && currentGraphY < (GRAPH_SIZE - 1) && _directions[currentGraphX - 1][currentGraphY + 1] == 0 && (_clip[currentGraphX - 1][currentGraphY + 1] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_EAST_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_SOUTH_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_SOUTHEAST_BLOCKSWALK_ALTERNATIVE)) == 0 && (_clip[currentGraphX - 1][currentGraphY] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_EAST_BLOCKSWALK_ALTERNATIVE)) == 0 && (_clip[currentGraphX][currentGraphY + 1] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_SOUTH_BLOCKSWALK_ALTERNATIVE)) == 0) {
  277. // we can go to north west, queue it.
  278. _bufferX[write] = currentX - 1;
  279. _bufferY[write] = currentY + 1;
  280. write = (write + 1) & (QUEUE_SIZE - 1);
  281.  
  282. _directions[currentGraphX - 1][currentGraphY + 1] = DIR_SOUTH | DIR_EAST;
  283. _distances[currentGraphX - 1][currentGraphY + 1] = nextDistance;
  284. }
  285. if (currentGraphX < (GRAPH_SIZE - 1) && currentGraphY < (GRAPH_SIZE - 1) && _directions[currentGraphX + 1][currentGraphY + 1] == 0 && (_clip[currentGraphX + 1][currentGraphY + 1] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_SOUTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_WEST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_SOUTHWEST_BLOCKSWALK_ALTERNATIVE)) == 0 && (_clip[currentGraphX + 1][currentGraphY] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_WEST_BLOCKSWALK_ALTERNATIVE)) == 0 && (_clip[currentGraphX][currentGraphY + 1] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_SOUTH_BLOCKSWALK_ALTERNATIVE)) == 0) {
  286. // we can go to north east, queue it.
  287. _bufferX[write] = currentX + 1;
  288. _bufferY[write] = currentY + 1;
  289. write = (write + 1) & (QUEUE_SIZE - 1);
  290.  
  291. _directions[currentGraphX + 1][currentGraphY + 1] = DIR_SOUTH | DIR_WEST;
  292. _distances[currentGraphX + 1][currentGraphY + 1] = nextDistance;
  293. }
  294.  
  295. }
  296.  
  297. exitX = currentX;
  298. exitY = currentY;
  299. return false;
  300. }
  301.  
  302. /**
  303. * Perform's size 2 calculations.
  304. */
  305. private static boolean performCalculationS2(int srcX, int srcY, RouteStrategy strategy) {
  306. return performCalculationSX(srcX, srcY, 2, strategy); // TODO optimized algorhytm's.
  307. }
  308.  
  309. /**
  310. * Perform's size x calculations.
  311. */
  312. private static boolean performCalculationSX(int srcX, int srcY, int size, RouteStrategy strategy) {
  313. // first, we will cache our static fields to local variables, this is done for performance, because
  314. // modern jit compiler's usually takes advantage of things like this
  315. int[][] _directions = directions;
  316. int[][] _distances = distances;
  317. int[][] _clip = clip;
  318. int[] _bufferX = bufferX;
  319. int[] _bufferY = bufferY;
  320.  
  321.  
  322. // when we start searching for path, we position ourselves in the middle of graph
  323. // so the base(minimum) position is source_pos - HALF_GRAPH_SIZE.
  324. int graphBaseX = srcX - (GRAPH_SIZE / 2);
  325. int graphBaseY = srcY - (GRAPH_SIZE / 2);
  326. int currentX = srcX;
  327. int currentY = srcY;
  328. int currentGraphX = srcX - graphBaseX;
  329. int currentGraphY = srcY - graphBaseY;
  330.  
  331. // setup information about source tile.
  332. _distances[currentGraphX][currentGraphY] = 0;
  333. _directions[currentGraphX][currentGraphY] = 99;
  334.  
  335. // queue variables
  336. int read = 0, write = 0;
  337. // insert our current position as first queued position.
  338. _bufferX[write] = currentX;
  339. _bufferY[write++] = currentY;
  340.  
  341. while (read != write) {
  342. currentX = _bufferX[read];
  343. currentY = _bufferY[read];
  344. read = (read + 1) & (QUEUE_SIZE - 1);
  345.  
  346. currentGraphX = currentX - graphBaseX;
  347. currentGraphY = currentY - graphBaseY;
  348.  
  349. if (strategy.canExit(currentX, currentY, size, _clip, graphBaseX, graphBaseY)) {
  350. // we found a path!
  351. exitX = currentX;
  352. exitY = currentY;
  353. return true;
  354. }
  355.  
  356. // if we can't exit at current tile, check where we can go from this tile
  357. int nextDistance = _distances[currentGraphX][currentGraphY] + 1;
  358. if (currentGraphX > 0 && _directions[currentGraphX - 1][currentGraphY] == 0 && (_clip[currentGraphX - 1][currentGraphY] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_NORTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_EAST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_NORTHEAST_BLOCKSWALK_ALTERNATIVE)) == 0 && (_clip[currentGraphX - 1][currentGraphY + (size - 1)] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_EAST_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_SOUTH_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_SOUTHEAST_BLOCKSWALK_ALTERNATIVE)) == 0) {
  359. exit: do {
  360. for (int y = 1; y < (size - 1); y++) {
  361. if ((_clip[currentGraphX - 1][currentGraphY + y] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_NORTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_EAST_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_SOUTH_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_NORTHEAST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_SOUTHEAST_BLOCKSWALK_ALTERNATIVE)) != 0)
  362. break exit;
  363. }
  364. // we can go to west, queue it
  365. _bufferX[write] = currentX - 1;
  366. _bufferY[write] = currentY;
  367. write = (write + 1) & (QUEUE_SIZE - 1);
  368.  
  369. _directions[currentGraphX - 1][currentGraphY] = DIR_EAST;
  370. _distances[currentGraphX - 1][currentGraphY] = nextDistance;
  371. }
  372. while (false);
  373. }
  374. if (currentGraphX < (GRAPH_SIZE - size) && _directions[currentGraphX + 1][currentGraphY] == 0 && (_clip[currentGraphX + size][currentGraphY] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_NORTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_WEST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_NORTHWEST_BLOCKSWALK_ALTERNATIVE)) == 0 && (_clip[currentGraphX + size][currentGraphY + (size - 1)] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_SOUTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_WEST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_SOUTHWEST_BLOCKSWALK_ALTERNATIVE)) == 0) {
  375. exit: do {
  376. for (int y = 1; y < (size - 1); y++) {
  377. if ((_clip[currentGraphX + size][currentGraphY + y] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_NORTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_SOUTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_WEST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_NORTHWEST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_SOUTHWEST_BLOCKSWALK_ALTERNATIVE)) != 0)
  378. break exit;
  379. }
  380. // we can go to east, queue it
  381. _bufferX[write] = currentX + 1;
  382. _bufferY[write] = currentY;
  383. write = (write + 1) & (QUEUE_SIZE - 1);
  384.  
  385. _directions[currentGraphX + 1][currentGraphY] = DIR_WEST;
  386. _distances[currentGraphX + 1][currentGraphY] = nextDistance;
  387. }
  388. while (false);
  389. }
  390. if (currentGraphY > 0 && _directions[currentGraphX][currentGraphY - 1] == 0 && (_clip[currentGraphX][currentGraphY - 1] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_NORTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_EAST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_NORTHEAST_BLOCKSWALK_ALTERNATIVE)) == 0 && (_clip[currentGraphX + (size - 1)][currentGraphY - 1] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_NORTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_WEST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_NORTHWEST_BLOCKSWALK_ALTERNATIVE)) == 0) {
  391. exit: do {
  392. for (int y = 1; y < (size - 1); y++) {
  393. if ((_clip[currentGraphX + y][currentGraphY - 1] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_NORTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_EAST_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_WEST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_NORTHWEST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_NORTHEAST_BLOCKSWALK_ALTERNATIVE)) != 0)
  394. break exit;
  395. }
  396. // we can go to south, queue it
  397. _bufferX[write] = currentX;
  398. _bufferY[write] = currentY - 1;
  399. write = (write + 1) & (QUEUE_SIZE - 1);
  400.  
  401. _directions[currentGraphX][currentGraphY - 1] = DIR_NORTH;
  402. _distances[currentGraphX][currentGraphY - 1] = nextDistance;
  403. }
  404. while (false);
  405. }
  406. if (currentGraphY < (GRAPH_SIZE - size) && _directions[currentGraphX][currentGraphY + 1] == 0 && (_clip[currentGraphX][currentGraphY + size] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_EAST_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_SOUTH_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_SOUTHEAST_BLOCKSWALK_ALTERNATIVE)) == 0 && (_clip[currentGraphX + (size - 1)][currentGraphY + size] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_SOUTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_WEST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_SOUTHWEST_BLOCKSWALK_ALTERNATIVE)) == 0) {
  407. exit: do {
  408. for (int y = 1; y < (size - 1); y++) {
  409. if ((_clip[currentGraphX + y][currentGraphY + size] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_EAST_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_SOUTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_WEST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_SOUTHEAST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_SOUTHWEST_BLOCKSWALK_ALTERNATIVE)) != 0)
  410. break exit;
  411. }
  412. // we can go to north, queue it
  413. _bufferX[write] = currentX;
  414. _bufferY[write] = currentY + 1;
  415. write = (write + 1) & (QUEUE_SIZE - 1);
  416.  
  417. _directions[currentGraphX][currentGraphY + 1] = DIR_SOUTH;
  418. _distances[currentGraphX][currentGraphY + 1] = nextDistance;
  419. }
  420. while (false);
  421. }
  422. // diagonal checks, comment them to disable diagonal routes.
  423. if (currentGraphX > 0 && currentGraphY > 0 && _directions[currentGraphX - 1][currentGraphY - 1] == 0 && (_clip[currentGraphX - 1][currentGraphY - 1] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_NORTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_EAST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_NORTHEAST_BLOCKSWALK_ALTERNATIVE)) == 0) {
  424. exit: do {
  425. for (int y = 1; y < size; y++) {
  426. if ((_clip[currentGraphX - 1][currentGraphY + (y - 1)] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_NORTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_EAST_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_SOUTH_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_NORTHEAST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_SOUTHEAST_BLOCKSWALK_ALTERNATIVE)) != 0 || (_clip[currentGraphX + (y - 1)][currentGraphY - 1] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_NORTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_EAST_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_WEST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_NORTHWEST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_NORTHEAST_BLOCKSWALK_ALTERNATIVE)) != 0)
  427. break exit;
  428. }
  429. // we can go to south west, queue it
  430. _bufferX[write] = currentX - 1;
  431. _bufferY[write] = currentY - 1;
  432. write = (write + 1) & (QUEUE_SIZE - 1);
  433.  
  434. _directions[currentGraphX - 1][currentGraphY - 1] = DIR_NORTH | DIR_EAST;
  435. _distances[currentGraphX - 1][currentGraphY - 1] = nextDistance;
  436. }
  437. while (false);
  438. }
  439. if (currentGraphX < (GRAPH_SIZE - size) && currentGraphY > 0 && _directions[currentGraphX + 1][currentGraphY - 1] == 0 && (_clip[currentGraphX + size][currentGraphY - 1] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_NORTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_WEST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_NORTHWEST_BLOCKSWALK_ALTERNATIVE)) == 0) {
  440. exit: do {
  441. for (int y = 1; y < size; y++) {
  442. if ((_clip[currentGraphX + size][currentGraphY + (y - 1)] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_NORTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_SOUTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_WEST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_NORTHWEST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_SOUTHWEST_BLOCKSWALK_ALTERNATIVE)) != 0 || (_clip[currentGraphX + y][currentGraphY - 1] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_NORTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_EAST_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_WEST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_NORTHWEST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_NORTHEAST_BLOCKSWALK_ALTERNATIVE)) != 0)
  443. break exit;
  444. }
  445. // we can go to south east, queue it
  446. _bufferX[write] = currentX + 1;
  447. _bufferY[write] = currentY - 1;
  448. write = (write + 1) & (QUEUE_SIZE - 1);
  449.  
  450. _directions[currentGraphX + 1][currentGraphY - 1] = DIR_NORTH | DIR_WEST;
  451. _distances[currentGraphX + 1][currentGraphY - 1] = nextDistance;
  452. }
  453. while (false);
  454. }
  455. if (currentGraphX > 0 && currentGraphY < (GRAPH_SIZE - size) && _directions[currentGraphX - 1][currentGraphY + 1] == 0 && (_clip[currentGraphX - 1][currentGraphY + size] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_EAST_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_SOUTH_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_SOUTHEAST_BLOCKSWALK_ALTERNATIVE)) == 0) {
  456. exit: do {
  457. for (int y = 1; y < size; y++) {
  458. if ((_clip[currentGraphX - 1][currentGraphY + y] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_NORTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_EAST_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_SOUTH_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_NORTHEAST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_SOUTHEAST_BLOCKSWALK_ALTERNATIVE)) != 0 || (_clip[currentGraphX + (y - 1)][currentGraphY + size] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_EAST_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_SOUTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_WEST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_SOUTHEAST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_SOUTHWEST_BLOCKSWALK_ALTERNATIVE)) != 0)
  459. break exit;
  460. }
  461. // we can go to north west, queue it.
  462. _bufferX[write] = currentX - 1;
  463. _bufferY[write] = currentY + 1;
  464. write = (write + 1) & (QUEUE_SIZE - 1);
  465.  
  466. _directions[currentGraphX - 1][currentGraphY + 1] = DIR_SOUTH | DIR_EAST;
  467. _distances[currentGraphX - 1][currentGraphY + 1] = nextDistance;
  468. }
  469. while (false);
  470. }
  471. if (currentGraphX < (GRAPH_SIZE - size) && currentGraphY < (GRAPH_SIZE - size) && _directions[currentGraphX + 1][currentGraphY + 1] == 0 && (_clip[currentGraphX + size][currentGraphY + size] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_SOUTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_WEST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_SOUTHWEST_BLOCKSWALK_ALTERNATIVE)) == 0) {
  472. exit: do {
  473. for (int y = 1; y < size; y++) {
  474. if ((_clip[currentGraphX + y][currentGraphY + size] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_EAST_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_SOUTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_WEST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_SOUTHEAST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_SOUTHWEST_BLOCKSWALK_ALTERNATIVE)) != 0 || (_clip[currentGraphX + size][currentGraphY + y] & (Flags.FLOOR_BLOCKSWALK | Flags.FLOORDECO_BLOCKSWALK | Flags.OBJ_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_NORTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_SOUTH_BLOCKSWALK_ALTERNATIVE | Flags.WALLOBJ_WEST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_NORTHWEST_BLOCKSWALK_ALTERNATIVE | Flags.CORNEROBJ_SOUTHWEST_BLOCKSWALK_ALTERNATIVE)) != 0)
  475. break exit;
  476. }
  477. // we can go to north east, queue it.
  478. _bufferX[write] = currentX + 1;
  479. _bufferY[write] = currentY + 1;
  480. write = (write + 1) & (QUEUE_SIZE - 1);
  481.  
  482. _directions[currentGraphX + 1][currentGraphY + 1] = DIR_SOUTH | DIR_WEST;
  483. _distances[currentGraphX + 1][currentGraphY + 1] = nextDistance;
  484. }
  485. while (false);
  486. }
  487.  
  488. }
  489.  
  490. exitX = currentX;
  491. exitY = currentY;
  492. return false;
  493. }
  494.  
  495.  
  496. /**
  497. * Transmit's clip data to route finder buffers.
  498. */
  499. private static void transmitClipData(int x, int y, int z) {
  500. int graphBaseX = x - (GRAPH_SIZE / 2);
  501. int graphBaseY = y - (GRAPH_SIZE / 2);
  502.  
  503. for (int transmitRegionX = graphBaseX >> 6; transmitRegionX <= (graphBaseX + (GRAPH_SIZE - 1)) >> 6; transmitRegionX++) {
  504. for (int transmitRegionY = graphBaseY >> 6; transmitRegionY <= (graphBaseY + (GRAPH_SIZE - 1)) >> 6; transmitRegionY++) {
  505. int startX = Math.max(graphBaseX, transmitRegionX << 6), startY = Math.max(graphBaseY, transmitRegionY << 6);
  506. int endX = Math.min(graphBaseX + GRAPH_SIZE, (transmitRegionX << 6) + 64), endY = Math.min(graphBaseY + GRAPH_SIZE, (transmitRegionY << 6) + 64);
  507. Region region = World.getRegion(transmitRegionX << 8 | transmitRegionY, true);
  508. RegionMap map = region.getRegionMap();
  509. if (map == null || region.getLoadMapStage() != 2 || !region.isLoadedObjectSpawns()) {
  510. for (int fillX = startX; fillX < endX; fillX++)
  511. for (int fillY = startY; fillY < endY; fillY++)
  512. clip[fillX - graphBaseX][fillY - graphBaseY] = -1;
  513. }
  514. else {
  515. int[][] masks = map.getMasks()[z];
  516. for (int fillX = startX; fillX < endX; fillX++) {
  517. for (int fillY = startY; fillY < endY; fillY++) {
  518. clip[fillX - graphBaseX][fillY - graphBaseY] = masks[fillX & 0x3F][fillY & 0x3F];
  519. }
  520. }
  521. }
  522. }
  523. }
  524. }
  525.  
  526.  
  527.  
  528. /**
  529. * Get's last path buffer x.
  530. * Modifying the buffer in any way is prohibited.
  531. */
  532. protected static int[] getLastPathBufferX() {
  533. return bufferX;
  534. }
  535.  
  536. /**
  537. * Get's last path buffer y.
  538. * Modifying the buffer in any way is prohibited.
  539. */
  540. protected static int[] getLastPathBufferY() {
  541. return bufferY;
  542. }
  543.  
  544. /**
  545. * Whether last path is only alternative path.
  546. */
  547. protected static boolean lastIsAlternative() {
  548. return isAlternative;
  549. }
  550. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!