Advertisement
Guest User

Untitled

a guest
Aug 28th, 2014
213
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 9.08 KB | None | 0 0
  1. package astaralgorithm;
  2.  
  3. public class Cell {
  4.    
  5.     private int x,y,g,h,f;
  6.     private Cell parent;
  7.     private boolean isBarrier;
  8.    
  9.     public Cell (int x,int y,boolean isBarrier){
  10.         this.x=x;
  11.         this.y=y;
  12.         this.isBarrier=isBarrier;
  13.     }
  14.     public boolean isBarrier() {
  15.         return isBarrier;
  16.     }
  17.     public void setBarrier(boolean isBarrier) {
  18.         this.isBarrier = isBarrier;
  19.     }
  20.     public int getX() {
  21.         return x;
  22.     }
  23.     public void setX(int x) {
  24.         this.x = x;
  25.     }
  26.     public int getY() {
  27.         return y;
  28.     }
  29.     public void setY(int y) {
  30.         this.y = y;
  31.     }
  32.     public int getG() {
  33.         return g;
  34.     }
  35.     public void setG(int g) {
  36.         this.g = g;
  37.     }
  38.     public int getH() {
  39.         return h;
  40.     }
  41.     public void setH(int h) {
  42.         this.h = h;
  43.     }
  44.     public int getF() {
  45.         return f;
  46.     }
  47.     public void setF(int f) {
  48.         this.f = f;
  49.     }
  50.     public Cell getParent() {
  51.         return parent;
  52.     }
  53.     public void setParent(Cell parent) {
  54.         this.parent = parent;
  55.     }
  56.    
  57.    
  58.    
  59.  
  60. }
  61.  
  62. import java.util.ArrayList;
  63. import java.util.List;
  64. import java.io.BufferedReader;
  65. import java.io.File;
  66. import java.io.FileReader;
  67. import java.io.IOException;
  68. import java.lang.Math;
  69.  
  70. public class Maze {
  71.    
  72.     private int width, height, startY, startX, goalY, goalX;
  73.  
  74.     private List<String> barriers = new ArrayList<String>();
  75.     private List<ArrayList<Cell>> maze = new ArrayList<ArrayList<Cell>>();
  76.    
  77.     public Maze(int index){
  78.        
  79.         /*this.width = width;
  80.         this.height = height;
  81.         this.startY = startY;
  82.         this.startX = startX;
  83.         this.goalY = goalY;
  84.         this.goalX = goalX;*/
  85.        
  86.         organizeInput(index);
  87.        
  88.         for(int i=0;i<width;i++){
  89.             ArrayList<Cell> list= new ArrayList<Cell>();
  90.             for(int j=0;j<height;j++){
  91.                 Cell cell = new Cell(i,j,false);
  92.                 list.add(cell);
  93.                 }
  94.             maze.add(list);
  95.         }
  96.         this.addWalls(barriers);
  97.        
  98.     }
  99.    
  100.     public void organizeInput(int indx){
  101.         String[] mazeInfo = getInputMaze(indx);
  102.         for(int i=0; i<mazeInfo.length; i++){
  103.             String[] infoSplit = mazeInfo[i].split(",");
  104.                   switch(i){
  105.                           case(0): this.width = Integer.parseInt(infoSplit[0]);
  106.                                    this.height = Integer.parseInt(infoSplit[1]);
  107.                                    break;
  108.                           case(1): this.startX = Integer.parseInt(infoSplit[0]);
  109.                                    this.startY = Integer.parseInt(infoSplit[1]);
  110.                                    break;
  111.                           case(2): this.goalX = Integer.parseInt(infoSplit[0]);
  112.                                    this.goalY = Integer.parseInt(infoSplit[1]);
  113.                                    break;
  114.                   }
  115.                           if(i>2){
  116.                                   barriers.add(mazeInfo[i]);
  117.                           }
  118.                   }
  119.     }
  120.    
  121.     private static String[] getInputMaze(int mazeNum){
  122.           String mazeString="";
  123.           try {
  124.                   File file = new File("/Users/Engh/Desktop/maze.txt");
  125.                   FileReader fileReader = new FileReader(file);
  126.                   BufferedReader bufferedReader = new BufferedReader(fileReader);
  127.                   String line;
  128.                   int i=0;
  129.                   while ((line = bufferedReader.readLine()) != null) {
  130.                           if(i==mazeNum){
  131.                                   mazeString=line;
  132.                                   break;
  133.                           }
  134.                           i++;
  135.                   }
  136.                   fileReader.close();
  137.           } catch (IOException e) {
  138.                   e.printStackTrace();
  139.           }
  140.           return mazeString.split(";");
  141.     }
  142.    
  143.     public void addWalls(List<String> barriers){
  144.         int x,y,width,height;
  145.         for(int i=0;i<barriers.size();i++){
  146.             String[] infoSplit = barriers.get(i).split(",");
  147.             x = Integer.parseInt(infoSplit[0]);
  148.             y = Integer.parseInt(infoSplit[1]);
  149.             width = Integer.parseInt(infoSplit[2]);
  150.             height = Integer.parseInt(infoSplit[3]);
  151.            
  152.             for(int j=x;j<x+width;j++){
  153.                 for(int k=y;k<y+height;k++){
  154.                     setCellisBarrier(j, k, true);
  155.                 }
  156.             }
  157.            
  158.         }
  159.        
  160.     }
  161.    
  162.     public Cell getCell(int x,int y){
  163.         ArrayList<Cell> list = maze.get(y);
  164.         return list.get(x);
  165.        
  166.     }
  167.    
  168.     public void setCellisBarrier(int x,int y,boolean isBarrier){
  169.         Cell cell = getCell(x, y);
  170.         cell.setBarrier(isBarrier);
  171.        
  172.     }
  173.    
  174.     public ArrayList<Cell> getNeighbourCell(Cell cell){
  175.         ArrayList<Cell> cellList = new ArrayList<Cell>();
  176.        
  177.         if(cell.getX() < width-1 && cell.getX() >= 0){
  178.             cellList.add(this.getCell(cell.getX()+1, cell.getY()));
  179.         }
  180.         if(cell.getY() > 0 && cell.getY() < height){
  181.             cellList.add(this.getCell(cell.getX(), cell.getY()-1));
  182.         }
  183.         if(cell.getX() > 0 && cell.getX() < width){
  184.             cellList.add(this.getCell(cell.getX()-1, cell.getY()));
  185.         }
  186.         if(cell.getY() < height-1 && cell.getY() >= 0 ){
  187.             cellList.add(this.getCell(cell.getX(), cell.getY()+1));
  188.         }
  189.         return cellList;
  190.        
  191.     }
  192.    
  193.     private int getHeuristic(int x, int y){
  194.         int goalX = this.getGoalX();
  195.         int goalY = this.getGoalY();
  196.        
  197.         return (Math.abs(goalX-x) + Math.abs(goalY-y));
  198.     }
  199.    
  200.     public void updateCell(Cell neighbour, Cell currentCell){
  201.         neighbour.setG(currentCell.getG()+1);
  202.         neighbour.setH(this.getHeuristic(neighbour.getX(),neighbour.getY()));
  203.         neighbour.setParent(currentCell);
  204.         int f = neighbour.getG() + neighbour.getH();
  205.         neighbour.setF(f);
  206.     }
  207.    
  208.    
  209.  
  210.     public int getWidth() {
  211.         return width;
  212.     }
  213.  
  214.     public void setWidth(int width) {
  215.         this.width = width;
  216.     }
  217.  
  218.     public int getHeight() {
  219.         return height;
  220.     }
  221.  
  222.     public void setHeight(int height) {
  223.         this.height = height;
  224.     }
  225.  
  226.     public int getStartY() {
  227.         return startY;
  228.     }
  229.  
  230.     public void setStartY(int startY) {
  231.         this.startY = startY;
  232.     }
  233.  
  234.     public int getStartX() {
  235.         return startX;
  236.     }
  237.  
  238.     public void setStartX(int startX) {
  239.         this.startX = startX;
  240.     }
  241.  
  242.     public int getGoalY() {
  243.         return goalY;
  244.     }
  245.  
  246.     public void setGoalY(int goalY) {
  247.         this.goalY = goalY;
  248.     }
  249.  
  250.     public int getGoalX() {
  251.         return goalX;
  252.     }
  253.  
  254.     public void setGoalX(int goalX) {
  255.         this.goalX = goalX;
  256.     }
  257.  
  258. }
  259. import java.util.ArrayList;
  260. import java.util.Comparator;
  261. import java.util.Scanner;
  262. import java.io.BufferedReader;
  263. import java.io.File;
  264. import java.io.FileReader;
  265. import java.io.IOException;
  266. import java.util.PriorityQueue;
  267.  
  268. public class Algorithm {
  269.        
  270.         static String[] mazeInfo;
  271.         static int index;
  272.         static Maze maze;
  273.         static PriorityQueue<Cell> openQueue = new PriorityQueue<Cell>(1000, new Comparator<Cell>()
  274.                 {
  275.             public int compare(Cell cell1, Cell cell2){
  276.                 return (cell1.getF() - cell2.getF());
  277.             }
  278.                 });
  279.        
  280.         static ArrayList<Cell> closedList = new ArrayList<Cell>();
  281.        
  282.         public static void main(String[] args) {
  283.            
  284.             try {
  285.                
  286.        
  287.             Scanner in = new Scanner(System.in);
  288.             System.out.println("Choose a maze (0-5): ");
  289.             while(index!=-1){
  290.                     index = Integer.parseInt(in.nextLine());
  291.                     maze = new Maze(index);
  292.                     break;
  293.                    
  294.             }
  295.            
  296.             addToQueue(maze.getCell(maze.getStartX(), maze.getStartY()));
  297.            
  298.             while (!openQueue.isEmpty()){
  299.                
  300.                 Cell primaryCell = openQueue.poll();
  301.                 closedList.add(primaryCell);
  302.                 if( (primaryCell.getX()==maze.getGoalX() && primaryCell.getY()==maze.getGoalY())){
  303.                     System.out.println("a");
  304.                    
  305.                     while (primaryCell != maze.getCell(maze.getStartX(), maze.getStartX())){
  306.                         int x = primaryCell.getX();
  307.                         int y = primaryCell.getY();
  308.                         System.out.print(x);System.out.print(",");System.out.print(y);System.out.println();
  309.                         primaryCell = primaryCell.getParent();
  310.                     }
  311.                    
  312.                    
  313.                     break;
  314.                 }
  315.                 System.out.println("b");
  316.                 ArrayList<Cell> neighbourCells = maze.getNeighbourCell(primaryCell);
  317.                 System.out.println("c");
  318.                
  319.                 for (int i=0;i<neighbourCells.size();i++){
  320.                     System.out.println(i);
  321.                    
  322.                     Cell secondaryCell = neighbourCells.get(i);
  323.                    
  324.                     if(!secondaryCell.isBarrier() && !closedList.contains(secondaryCell)){
  325.                        
  326.                         if(openQueue.contains(secondaryCell)){
  327.                            
  328.                             if(secondaryCell.getG() > primaryCell.getG() + 1){
  329.                                 maze.updateCell(secondaryCell, primaryCell);
  330.                             }
  331.                         }
  332.                    
  333.                         else{
  334.                             maze.updateCell(secondaryCell, primaryCell);
  335.                             openQueue.add(secondaryCell);
  336.                         }
  337.                     }
  338.                    
  339.                 }
  340.             }
  341.             } catch (Throwable ex) {
  342.                 System.err.println("Uncaught exception - " + ex.getMessage());
  343.                 ex.printStackTrace(System.err);
  344.             }
  345.         }
  346.            
  347.        
  348.        
  349.         public static void addToQueue(Cell cell){
  350.            
  351.             openQueue.add(cell);
  352.            
  353.             //Bruke PriorityQueue som heap
  354.         }
  355.        
  356. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement