home *** CD-ROM | disk | FTP | other *** search
/ Reverse Code Engineering RCE CD +sandman 2000 / ReverseCodeEngineeringRceCdsandman2000.iso / RCE / Anachriz / programming / Maze.java.txt < prev    next >
Encoding:
Text File  |  2000-05-25  |  4.9 KB  |  181 lines
  1. /*
  2.     Copyright (c) 1998 Anarchriz. All rights reserved. You may copy portions
  3.     of code if you credit me.
  4.     
  5.     TO-DO: comment the stuff
  6. */
  7.  
  8. import java.awt.*;
  9.  
  10. public class Maze
  11. {
  12.  
  13.     public Maze(byte maze[][], int M, int N)
  14.     {
  15.         this.M = 6;
  16.         this.N = 7;
  17.         shortestPath = 0x7fffffff;
  18.         numberOfCoordinates = 1;
  19.         ready = false;
  20.         this.maze = maze;
  21.         this.M = M;
  22.         this.N = N;
  23.         mazeCounter = new int[M][N];
  24.         coArray = new int[M * N][2];
  25.         mazeCounter[0][0] = 0x7fffffff;
  26.     }
  27.  
  28.     public void solve()
  29.     {
  30.         ready = false;
  31.         do
  32.         {
  33.             lengthPath++;
  34.             nextNumberOfCoordinates = 0;
  35.             for(int i = 0; i < numberOfCoordinates; i++)
  36.             {
  37.                 int row = coArray[i][0];
  38.                 int column = coArray[i][1];
  39.                 coArray[i][0] = 0;
  40.                 coArray[i][1] = 0;
  41.                 if(isZero(row, column + 1))
  42.                     addCoordinate(row, column + 1);
  43.                 if(ready)
  44.                     break;
  45.                 if(isZero(row + 1, column))
  46.                     addCoordinate(row + 1, column);
  47.                 if(ready)
  48.                     break;
  49.                 if(isZero(row, column - 1))
  50.                     addCoordinate(row, column - 1);
  51.                 if(ready)
  52.                     break;
  53.                 if(isZero(row - 1, column))
  54.                     addCoordinate(row - 1, column);
  55.                 if(ready)
  56.                     break;
  57.             }
  58.  
  59.             numberOfCoordinates = nextNumberOfCoordinates;
  60.             if(numberOfCoordinates == 0)
  61.                 ready = true;
  62.             if(!ready)
  63.                 wipeCoArrayClean();
  64.         }
  65.         while(!ready);
  66.     }
  67.  
  68.     private void addCoordinate(int row, int column)
  69.     {
  70.         int pos = findPos();
  71.         coArray[pos][0] = row;
  72.         coArray[pos][1] = column;
  73.         mazeCounter[row][column] = lengthPath;
  74.         nextNumberOfCoordinates++;
  75.         if(row == M - 1 && column == N - 1)
  76.         {
  77.             ready = true;
  78.             shortestPath = lengthPath;
  79.             tracePad();
  80.         }
  81.     }
  82.  
  83.     private void wipeCoArrayClean()
  84.     {
  85.         int pos = findPos();
  86.         if(pos >= numberOfCoordinates)
  87.             return;
  88.         for(int i = coArray.length - 1; i >= 0; i--)
  89.         {
  90.             pos = findPos();
  91.             if(pos >= numberOfCoordinates)
  92.                 return;
  93.             if(coArray[i][0] != 0 || coArray[i][1] != 0)
  94.             {
  95.                 coArray[pos][0] = coArray[i][0];
  96.                 coArray[pos][1] = coArray[i][1];
  97.                 coArray[i][0] = 0;
  98.                 coArray[i][1] = 0;
  99.             }
  100.         }
  101.  
  102.     }
  103.  
  104.     private int findPos()
  105.     {
  106.         for(int pos = 0; pos < coArray.length; pos++)
  107.             if(coArray[pos][0] == 0 && coArray[pos][1] == 0)
  108.                 return pos;
  109.  
  110.         return 0x7fffffff;
  111.     }
  112.  
  113.     private void tracePad()
  114.     {
  115.         int row = M - 1;
  116.         int column = N - 1;
  117.         coArray[lengthPath][0] = row;
  118.         coArray[lengthPath][1] = column;
  119.         mazeCounter[0][0] = 0;
  120.         for(int i = lengthPath - 1; i >= 0; i--)
  121.         {
  122.             if(isThis(row - 1, column, i))
  123.                 row--;
  124.             else
  125.             if(isThis(row, column - 1, i))
  126.                 column--;
  127.             else
  128.             if(isThis(row + 1, column, i))
  129.                 row++;
  130.             else
  131.             if(isThis(row, column + 1, i))
  132.                 column++;
  133.             coArray[i][0] = row;
  134.             coArray[i][1] = column;
  135.         }
  136.  
  137.     }
  138.  
  139.     private boolean isThis(int row, int column, int value)
  140.     {
  141.         if(row < 0 || row >= M || column < 0 || column >= N)
  142.             return false;
  143.         return mazeCounter[row][column] == value;
  144.     }
  145.  
  146.     private boolean isZero(int row, int column)
  147.     {
  148.         if(row < 0 || row >= M || column < 0 || column >= N)
  149.             return false;
  150.         return maze[row][column] == 0 && mazeCounter[row][column] == 0;
  151.     }
  152.  
  153.     public void printMaze(Panel panel, TextField output)
  154.     {
  155.         if(shortestPath == 0x7fffffff)
  156.         {
  157.             output.setText("There is no path.");
  158.             return;
  159.         }
  160.         output.setText("A shortest path is " + shortestPath + " steps!");
  161.         for(int i = 0; i <= shortestPath; i++)
  162.         {
  163.             TextField t = (TextField)panel.getComponent(coArray[i][0] * N + coArray[i][1]);
  164.             t.setBackground(Color.green);
  165.             t.setText("");
  166.         }
  167.  
  168.     }
  169.  
  170.     private byte maze[][];
  171.     private int M;
  172.     private int N;
  173.     private int shortestPath;
  174.     private int lengthPath;
  175.     private int mazeCounter[][];
  176.     private int coArray[][];
  177.     private int numberOfCoordinates;
  178.     private int nextNumberOfCoordinates;
  179.     private boolean ready;
  180. }
  181.