API tools faq
paste
Advertisement
Guest User

Maze

a guest
Apr 24th, 2018
69
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.48 KB | None | 0 0
raw download clone embed print report
  1. import java.util.*;
  2.  
  3. public class Maze {
  4. private final static int DIRECTION_UP = 0;
  5. private final static int DIRECTION_RIGHT = 1;
  6. private final static int DIRECTION_DOWN = 2;
  7. private final static int DIRECTION_LEFT = 3;
  8.  
  9. public final int corner = 1;
  10. public final int hWall = 4;
  11. public final int vWall = 3;
  12. public final int empty = 0;
  13. public final int blind = -1;
  14. public final int path = 2;
  15.  
  16. private int width;
  17. private int height;
  18. private MazePoint[][] matrix;
  19. public int[][] maze;
  20.  
  21. /*
  22. * constructor, initial width, height and matrix
  23. */
  24. public Maze(int width, int height) {
  25. this.width = width;
  26. this.height = height;
  27. this.matrix = new MazePoint[height][width];
  28. for (int i=0; i<height; i++)
  29. for (int j=0; j<width; j++)
  30. matrix[i][j] = new MazePoint();
  31. this.maze = new int[2*height+1][2*width+1];
  32. }
  33.  
  34. /*
  35. * check if the target neighbor can be visited
  36. */
  37. public boolean checkNeighbor(int x, int y, int dir) {
  38. boolean neighborVisited = false;
  39. switch ( dir ) {
  40. case DIRECTION_UP:
  41. if ( x <= 0 )
  42. neighborVisited = true;
  43. else
  44. neighborVisited = matrix[x-1][y].visited();
  45. break;
  46. case DIRECTION_RIGHT:
  47. if ( y >= width - 1 )
  48. neighborVisited = true;
  49. else
  50. neighborVisited = matrix[x][y+1].visited();
  51. break;
  52. case DIRECTION_DOWN:
  53. if ( x >= height - 1 )
  54. neighborVisited = true;
  55. else
  56. neighborVisited = matrix[x+1][y].visited();
  57. break;
  58. case DIRECTION_LEFT:
  59. if ( y <= 0 )
  60. neighborVisited = true;
  61. else
  62. neighborVisited = matrix[x][y-1].visited();
  63. break;
  64. }
  65. return !neighborVisited;
  66. }
  67.  
  68. /*
  69. * check if the neighbors have at least one non-visited point
  70. */
  71. public boolean checkNeighbor(int x, int y) {
  72. return (this.checkNeighbor(x, y, DIRECTION_UP) ||
  73. this.checkNeighbor(x, y, DIRECTION_RIGHT) ||
  74. this.checkNeighbor(x, y, DIRECTION_DOWN) ||
  75. this.checkNeighbor(x, y, DIRECTION_LEFT));
  76. }
  77.  
  78. /*
  79. * pick up a random traversal direction
  80. */
  81. public int getRandDirection(int x, int y) {
  82. int dir = -1;
  83. Random rand = new Random();
  84. if ( checkNeighbor(x, y) ) {
  85. do {
  86. dir = rand.nextInt(4);
  87. } while ( !checkNeighbor(x, y, dir) );
  88. }
  89. return dir;
  90. }
  91.  
  92.  
  93. /*
  94. * push down the wall between the adjacent two points
  95. */
  96. public void pushWall(int x, int y, int dir) {
  97. switch ( dir ) {
  98. case DIRECTION_UP:
  99. matrix[x][y].setTop(false);
  100. matrix[x-1][y].setBottom(false);
  101. break;
  102. case DIRECTION_RIGHT:
  103. matrix[x][y].setRight(false);
  104. matrix[x][y+1].setLeft(false);
  105. break;
  106. case DIRECTION_DOWN:
  107. matrix[x][y].setBottom(false);
  108. matrix[x+1][y].setTop(false);
  109. break;
  110. case DIRECTION_LEFT:
  111. matrix[x][y].setLeft(false);
  112. matrix[x][y-1].setRight(false);
  113. break;
  114. }
  115. }
  116.  
  117. /*
  118. * depth first search traversal
  119. */
  120. public void traversal() {
  121. int x = 0;
  122. int y = 0;
  123. Stack<Integer> stackX = new Stack<Integer>();
  124. Stack<Integer> stackY = new Stack<Integer>();
  125. do {
  126. MazePoint p = matrix[x][y];
  127. if ( !p.visited() ) {
  128. p.setVisited(true);
  129. }
  130. if ( checkNeighbor(x, y) ) {
  131. int dir = this.getRandDirection(x, y);
  132. this.pushWall(x, y, dir);
  133. stackX.add(x);
  134. stackY.add(y);
  135. switch ( dir ) {
  136. case DIRECTION_UP:
  137. x--;
  138. break;
  139. case DIRECTION_RIGHT:
  140. y++;
  141. break;
  142. case DIRECTION_DOWN:
  143. x++;
  144. break;
  145. case DIRECTION_LEFT:
  146. y--;
  147. break;
  148. }
  149. }
  150. else {
  151. x = stackX.pop();
  152. y = stackY.pop();
  153. }
  154.  
  155. } while ( !stackX.isEmpty() );
  156. }
  157.  
  158.  
  159.  
  160. public void contributeMaze() {
  161. for (int j=0; j<2*width+1; j++)
  162. { if (j%2 == 0)
  163. maze[0][j] = corner;
  164. else
  165. maze[0][j] = hWall;
  166. }
  167.  
  168. for (int i=0; i<height; i++) {
  169. maze[2*i+1][0] = vWall;
  170. for (int j=0; j<width; j++) {
  171. maze[2*i+1][2*j+1] = empty;
  172. if ( matrix[i][j].isRight() )
  173. maze[2*i+1][2*j+2] = vWall;
  174. else
  175. maze[2*i+1][2*j+2] = empty;
  176. }
  177. maze[2*i+2][0] = 1;
  178. for (int j=0; j<width; j++) {
  179. if ( matrix[i][j].isBottom() )
  180. maze[2*i+2][2*j+1] = 4;
  181. else
  182. maze[2*i+2][2*j+1] = empty;
  183. maze[2*i+2][2*j+2] = corner;
  184. }
  185.  
  186. }
  187.  
  188. maze[0][1] = empty;
  189. maze[2*width][2*height-1] = empty;
  190.  
  191. }
  192.  
  193. /*
  194. * print the matrix
  195. */
  196. public void print() {
  197. for (int i=0; i<2*height+1; i++) {
  198. for (int j=0; j<2*width+1; j++)
  199. if ( maze[i][j] == corner )
  200. System.out.print("+");
  201. else if ( maze[i][j] == vWall )
  202. System.out.print("|");
  203. else if ( maze[i][j] == hWall )
  204. System.out.print("-");
  205. else if ( maze[i][j] == path )
  206. System.out.print("#");
  207. else
  208. System.out.print(" ");
  209. System.out.println();
  210. }
  211. }
  212.  
  213. public void printOrder() {
  214. for (int i=0; i<2*height+1; i++) {
  215. for (int j=0; j<2*width+1; j++)
  216. if ( maze[i][j] == corner )
  217. System.out.print("+");
  218. else if ( maze[i][j] == vWall )
  219. System.out.print("|");
  220. else if ( maze[i][j] == hWall )
  221. System.out.print("-");
  222. else if ( maze[i][j] == path )
  223. System.out.print(i);
  224.  
  225. else
  226. System.out.print(" ");
  227. System.out.println();
  228. }
  229. }
  230.  
  231.  
  232. public int getBreakOutDir(int x, int y) {
  233. int dir = -1;
  234. if ( maze[x][y+1] == 0 )
  235. dir = DIRECTION_RIGHT;
  236. else if ( maze[x+1][y] == 0 )
  237. dir = DIRECTION_DOWN;
  238. else if ( maze[x][y-1] == 0 )
  239. dir = DIRECTION_LEFT;
  240. else if ( maze[x-1][y] == 0 )
  241. dir = DIRECTION_UP;
  242. return dir;
  243. }
  244.  
  245. /*
  246. * find the path from (1, 1) to (2*height-1, 2*width-1)
  247. */
  248. public void findPathDFS() {
  249. int x = 1;
  250. int y = 1;
  251. Stack<Integer> stackX = new Stack<Integer>();
  252. Stack<Integer> stackY = new Stack<Integer>();
  253. do {
  254. int dir = this.getBreakOutDir(x, y);
  255. if ( dir == -1 ) {
  256. maze[x][y] = blind;
  257. x = stackX.pop();
  258. y = stackY.pop();
  259. }
  260. else {
  261. maze[x][y] = path;
  262. stackX.add(x);
  263. stackY.add(y);
  264. switch ( dir ) {
  265. case DIRECTION_UP:
  266. x--;
  267. break;
  268. case DIRECTION_RIGHT:
  269. y++;
  270. break;
  271. case DIRECTION_DOWN:
  272. x++;
  273. break;
  274. case DIRECTION_LEFT:
  275. y--;
  276. break;
  277. }
  278. }
  279. }
  280.  
  281. while ( !(x == 2*height-1 && y == 2*width-1) );
  282. maze[x][y] = path;
  283. }
  284.  
  285. public void findPathBFS() {
  286.  
  287. int x = 1;
  288. int y = 1;
  289.  
  290. Queue<Integer> queueX = new LinkedList<Integer>();
  291. Queue<Integer> queueY = new LinkedList<Integer>();
  292.  
  293. do {
  294. int dir = this.getBreakOutDir(x, y);
  295. if ( dir == -1 ) {
  296. maze[x][y] = blind;
  297. x = queueX.poll();
  298. y = queueY.poll();
  299. }
  300. else {
  301. maze[x][y] = path;
  302. queueX.add(x);
  303. queueY.add(y);
  304. switch ( dir ) {
  305. case DIRECTION_UP:
  306. x--;
  307. break;
  308. case DIRECTION_RIGHT:
  309. y++;
  310. break;
  311. case DIRECTION_DOWN:
  312. x++;
  313. break;
  314. case DIRECTION_LEFT:
  315. y--;
  316. break;
  317. }
  318. }
  319. } while ( !(x == 2*height-1 && y == 2*width-1) );
  320.  
  321. maze[x][y] = path;
  322. }
  323.  
  324. public void reset() {
  325. for (int i=0; i<2*height+1; i++)
  326. for (int j=0; j<2*width+1; j++)
  327. if ( maze[i][j] == path )
  328. maze[i][j] = empty;
  329.  
  330. }
  331.  
  332. public static void main(String[] args) {
  333. Maze maze = new Maze(4, 4);
  334. maze.traversal();
  335. maze.contributeMaze();
  336. System.out.println("Create new map");
  337. maze.print();
  338. maze.findPathDFS();
  339. System.out.println("Find DFS Solution");
  340. maze.print();
  341. maze.printOrder();
  342.  
  343. maze.reset();
  344. System.out.println("Reset to new map");
  345. maze.print();
  346.  
  347.  
  348. maze.findPathBFS();
  349. System.out.println("Find BFS Solution");
  350. maze.print();
  351. maze.printOrder();
  352. }
  353.  
  354.  
  355.  
  356. public int getRandDirectionJUnits(int x, int y) {
  357. int dir = -1;
  358. Random rand = new Random(0);
  359. if ( checkNeighbor(x, y) ) {
  360. do {
  361. dir = rand.nextInt(4);
  362. } while ( !checkNeighbor(x, y, dir) );
  363. }
  364. return dir;
  365. }
  366.  
  367. public void traversalJUnits() {
  368. int x = 0;
  369. int y = 0;
  370. Stack<Integer> stackX = new Stack<Integer>();
  371. Stack<Integer> stackY = new Stack<Integer>();
  372. do {
  373. MazePoint mp = matrix[x][y];
  374. if ( !mp.visited() ) {
  375. mp.setVisited(true);
  376. }
  377. if ( checkNeighbor(x, y) ) {
  378. int dir = this.getRandDirectionJUnits(x, y);
  379. this.pushWall(x, y, dir);
  380. stackX.add(x);
  381. stackY.add(y);
  382. switch ( dir ) {
  383. case DIRECTION_UP:
  384. x--;
  385. break;
  386. case DIRECTION_RIGHT:
  387. y++;
  388. break;
  389. case DIRECTION_DOWN:
  390. x++;
  391. break;
  392. case DIRECTION_LEFT:
  393. y--;
  394. break;
  395. }
  396. }
  397. else {
  398. x = stackX.pop();
  399. y = stackY.pop();
  400. }
  401.  
  402. } while ( !stackX.isEmpty() );
  403. }
  404.  
  405.  
  406. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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!