Advertisement
Guest User

Untitled

a guest
Sep 6th, 2011
156
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 6.64 KB | None | 0 0
  1. int sizeX, sizeY;
  2. int drawSize;
  3. int curX, curY;
  4.  
  5. int visibility;;
  6. int posX, posY;
  7.  
  8. int[][] maze;
  9. ArrayList<String> stack;
  10.  
  11. float ms;
  12.  
  13. boolean displaySolution;
  14.  
  15. void setup()
  16. {
  17.   ms = millis();
  18.  
  19.   sizeX = 100;
  20.   sizeY = 100;
  21.   drawSize = 10;
  22.  
  23.   visibility = 20;
  24.  
  25.   sizeX = round(sizeX / 2) * 2 - 1;
  26.   sizeY = round(sizeY / 2) * 2 - 1;
  27.  
  28.   size(sizeX * drawSize, sizeY * drawSize);
  29.  
  30.   maze = new int[sizeX][sizeY];
  31.   stack = new ArrayList<String>();
  32.  
  33.   displaySolution = false;
  34.  
  35.   //Maze setup
  36.   for (int x = 0; x < sizeX; x++) {
  37.     for (int y = 0; y < sizeY; y++) {
  38.       if ((x % 2 == 0) || (y % 2 == 0) || (x == 0) || (y == 0) || (x == sizeX - 1) || (y == sizeY - 1)) { // is a wall of some sort
  39.         maze[x][y] = 2;
  40.       }
  41.       else {
  42.         maze[x][y] = 0;
  43.       }
  44.     }
  45.   }
  46.  
  47.   curX = 1;
  48.   curY = 1;
  49.  
  50.   // set first cell to visited, add to stack
  51.   stack.add(curX + " " + curY);
  52.  
  53.   while (stack.size () > 0) {
  54.     maze[curX][curY] = 1; //set current cell to visited
  55.  
  56.     // find adjacent cells
  57.     ArrayList<String> adjCells = new ArrayList<String>();
  58.     if (curX > 1) {
  59.       if (maze[curX - 2][curY] == 0) {
  60.         adjCells.add((curX - 2) + " " + curY);
  61.       }
  62.     }
  63.  
  64.     if (curY > 1) {
  65.       if (maze[curX][curY - 2] == 0) {
  66.         adjCells.add(curX + " " + (curY - 2));
  67.       }
  68.     }
  69.  
  70.     if (curX < sizeX - 3) {
  71.       if (maze[curX + 2][curY] == 0) {
  72.         adjCells.add((curX + 2) + " " + curY);
  73.       }
  74.     }
  75.  
  76.     if (curY < sizeY - 3) {
  77.       if (maze[curX][curY + 2] == 0) {
  78.         adjCells.add(curX + " " + (curY + 2));
  79.       }
  80.     }
  81.  
  82.     if (adjCells.size() > 0) {
  83.       if (adjCells.size() > 1) {
  84.         stack.add(curX + " " + curY);
  85.       }
  86.  
  87.       String rAdjCell = adjCells.get( randint(0, adjCells.size() - 1) );
  88.  
  89.       int newX = int(rAdjCell.split(" ")[0]);
  90.       int newY = int(rAdjCell.split(" ")[1]);
  91.  
  92.       // remove the wall between the old cell and the new one
  93.       maze[(curX + newX) / 2][(curY + newY) / 2] = 3;
  94.  
  95.       curX = newX;
  96.       curY = newY;
  97.     }
  98.     else {
  99.       // backtrack through the stack
  100.       curX = int(stack.get(stack.size() - 1).split(" ")[0]);
  101.       curY = int(stack.get(stack.size() - 1).split(" ")[1]);
  102.  
  103.       stack.remove(stack.size() - 1);
  104.     }
  105.   }
  106.  
  107.  
  108.  
  109.   //
  110.   // now to solve the maze with breadth first search...
  111.   //
  112.  
  113.   String[][] parentNodes = new String[sizeX][sizeY];
  114.   ArrayList<String> activeNodes = new ArrayList<String>();
  115.  
  116.   activeNodes.add( (sizeX - 2) + " " + (sizeY - 2) );
  117.   parentNodes[sizeX - 2][sizeY - 2] = "END";
  118.  
  119.   boolean breakOut = false;
  120.  
  121.   while (!breakOut) {
  122.     ArrayList<String> newActiveNodes = activeNodes;
  123.  
  124.     for (int i = 0; i < activeNodes.size(); i++) {
  125.       int cx = int(activeNodes.get(i).split(" ")[0]);
  126.       int cy = int(activeNodes.get(i).split(" ")[1]);
  127.  
  128.       if (cx == 1 && cy == 1) { // FOUND IT
  129.         String curParentNode = parentNodes[1][1];
  130.         while (true) {
  131.           maze[cx][cy] = 4;
  132.  
  133.           curParentNode = parentNodes[cx][cy];
  134.  
  135.           if (curParentNode == "END") {
  136.             break;
  137.           }
  138.  
  139.           cx = int(curParentNode.split(" ")[0]);
  140.           cy = int(curParentNode.split(" ")[1]);
  141.         }
  142.  
  143.         breakOut = true;
  144.         break;
  145.       }
  146.  
  147.       if ((maze[cx - 1][cy] <= 1 || maze[cx - 1][cy] == 3) && parentNodes[cx - 1][cy] == null) { // is white, not spread to yet
  148.         newActiveNodes.add( (cx - 1) + " " + cy );
  149.         parentNodes[cx - 1][cy] = cx + " " + cy;
  150.       }
  151.  
  152.       if ((maze[cx + 1][cy] <= 1 || maze[cx + 1][cy] == 3) && parentNodes[cx + 1][cy] == null) {
  153.         newActiveNodes.add( (cx + 1) + " " + cy );
  154.         parentNodes[cx + 1][cy] = cx + " " + cy;
  155.       }
  156.  
  157.       if ((maze[cx][cy - 1] <= 1 || maze[cx][cy - 1] == 3) && parentNodes[cx][cy - 1] == null) {
  158.         newActiveNodes.add( cx + " " + (cy - 1) );
  159.         parentNodes[cx][cy - 1] = cx + " " + cy;
  160.       }
  161.  
  162.       if ((maze[cx][cy + 1] <= 1 || maze[cx][cy + 1] == 3) && parentNodes[cx][cy + 1] == null) {
  163.         newActiveNodes.add( cx + " " + (cy + 1) );
  164.         parentNodes[cx][cy + 1] = cx + " " + cy;
  165.       }
  166.     }
  167.  
  168.     activeNodes = newActiveNodes;
  169.   }
  170.  
  171.   // remove the entrance and exit walls and set them as part of the solution
  172.   maze[1][0] = 4;
  173.   maze[sizeX - 2][sizeY - 1] = 4;
  174.  
  175.   posX = 1;
  176.   posY = 0;
  177.  
  178.   //redraw = true;
  179. }
  180.  
  181. void draw()
  182. {
  183.   background(0);
  184.  
  185.   noSmooth();
  186.   noStroke();
  187.  
  188.   rectMode(CORNER);
  189.  
  190.   ArrayList<String> nodes = new ArrayList<String>();
  191.   nodes.add(posX + " " + posY);
  192.   String visitedCells = "";
  193.  
  194.   visibility = 40;
  195.   for(int a = 0; a <= visibility; a++) {
  196.     ArrayList<String> newNodes = new ArrayList<String>();
  197.     for(int i = 0; i < nodes.size(); i++) {
  198.       int nX = int(nodes.get(i).split(" ")[0]);
  199.       int nY = int(nodes.get(i).split(" ")[1]);
  200.      
  201.       visitedCells += nX + " " + nY + ",";
  202.      
  203.       int cVal = (int) ((1.0 - a / ((float) visibility)) * 255.0);
  204.       fill(255, 255, 255, cVal);
  205.       rect(nX * drawSize, nY * drawSize, drawSize, drawSize);
  206.      
  207.       if(isCell(nX - 1, nY) && match(visitedCells, (nX - 1) + " " + (nY) + ",") == null) {
  208.         newNodes.add( (nX - 1) + " " + (nY) );
  209.       }
  210.      
  211.       if(isCell(nX + 1, nY) && match(visitedCells, (nX + 1) + " " + (nY) + ",") == null) {
  212.         newNodes.add( (nX + 1) + " " + (nY) );
  213.       }
  214.      
  215.       if(isCell(nX, nY - 1) && match(visitedCells, (nX) + " " + (nY - 1) + ",") == null) {
  216.         newNodes.add( (nX) + " " + (nY - 1) );
  217.       }
  218.      
  219.       if(isCell(nX, nY + 1) && match(visitedCells, (nX) + " " + (nY + 1) + ",") == null) {
  220.         newNodes.add( (nX) + " " + (nY + 1) );
  221.       }
  222.     }
  223.    
  224.     nodes = newNodes;
  225.   }
  226.  
  227.   fill(255, 0, 0);
  228.   rect(posX * drawSize, posY * drawSize, drawSize, drawSize);
  229. }
  230.  
  231. void mouseClicked()
  232. {
  233.   displaySolution = !displaySolution;
  234.   redraw = true;
  235. }
  236.  
  237. int randint(int low, int high)
  238. {
  239.   return round( random(low - 0.4999, high + 0.4999) );
  240. }
  241.  
  242. boolean isCell(int xp, int yp)
  243. {
  244.   if((xp >= 0) && (yp >= 0) && (xp <= sizeX - 1) && (yp <= sizeY - 1)) {
  245.     // not a wall
  246.     return maze[xp][yp] != 2;
  247.   } else {
  248.     // outside the bounds of the maze, return false
  249.     return false;
  250.   }
  251. }
  252.  
  253. void keyPressed()
  254. {
  255.   // Left = 37, Up = 38, Right = 39, Down = 40
  256.   if(keyCode == 37 && isCell(posX - 1, posY)) { // left
  257.     posX -= 1;
  258.   }
  259.  
  260.   if(keyCode == 38 && isCell(posX, posY - 1)) { // up
  261.     posY -= 1;
  262.   }
  263.  
  264.   if(keyCode == 39 && isCell(posX + 1, posY)) { // right
  265.     posX += 1;
  266.   }
  267.  
  268.   if(keyCode == 40 && isCell(posX, posY + 1)) { // down
  269.     posY += 1;
  270.   }
  271.  
  272.   if(keyCode == 82) { // r key
  273.     setup();
  274.   }
  275. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement