Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package astaralgorithm;
- public class Cell {
- private int x,y,g,h,f;
- private Cell parent;
- private boolean isBarrier;
- public Cell (int x,int y,boolean isBarrier){
- this.x=x;
- this.y=y;
- this.isBarrier=isBarrier;
- }
- public boolean isBarrier() {
- return isBarrier;
- }
- public void setBarrier(boolean isBarrier) {
- this.isBarrier = isBarrier;
- }
- public int getX() {
- return x;
- }
- public void setX(int x) {
- this.x = x;
- }
- public int getY() {
- return y;
- }
- public void setY(int y) {
- this.y = y;
- }
- public int getG() {
- return g;
- }
- public void setG(int g) {
- this.g = g;
- }
- public int getH() {
- return h;
- }
- public void setH(int h) {
- this.h = h;
- }
- public int getF() {
- return f;
- }
- public void setF(int f) {
- this.f = f;
- }
- public Cell getParent() {
- return parent;
- }
- public void setParent(Cell parent) {
- this.parent = parent;
- }
- }
- import java.util.ArrayList;
- import java.util.List;
- import java.io.BufferedReader;
- import java.io.File;
- import java.io.FileReader;
- import java.io.IOException;
- import java.lang.Math;
- public class Maze {
- private int width, height, startY, startX, goalY, goalX;
- private List<String> barriers = new ArrayList<String>();
- private List<ArrayList<Cell>> maze = new ArrayList<ArrayList<Cell>>();
- public Maze(int index){
- /*this.width = width;
- this.height = height;
- this.startY = startY;
- this.startX = startX;
- this.goalY = goalY;
- this.goalX = goalX;*/
- organizeInput(index);
- for(int i=0;i<width;i++){
- ArrayList<Cell> list= new ArrayList<Cell>();
- for(int j=0;j<height;j++){
- Cell cell = new Cell(i,j,false);
- list.add(cell);
- }
- maze.add(list);
- }
- this.addWalls(barriers);
- }
- public void organizeInput(int indx){
- String[] mazeInfo = getInputMaze(indx);
- for(int i=0; i<mazeInfo.length; i++){
- String[] infoSplit = mazeInfo[i].split(",");
- switch(i){
- case(0): this.width = Integer.parseInt(infoSplit[0]);
- this.height = Integer.parseInt(infoSplit[1]);
- break;
- case(1): this.startX = Integer.parseInt(infoSplit[0]);
- this.startY = Integer.parseInt(infoSplit[1]);
- break;
- case(2): this.goalX = Integer.parseInt(infoSplit[0]);
- this.goalY = Integer.parseInt(infoSplit[1]);
- break;
- }
- if(i>2){
- barriers.add(mazeInfo[i]);
- }
- }
- }
- private static String[] getInputMaze(int mazeNum){
- String mazeString="";
- try {
- File file = new File("/Users/Engh/Desktop/maze.txt");
- FileReader fileReader = new FileReader(file);
- BufferedReader bufferedReader = new BufferedReader(fileReader);
- String line;
- int i=0;
- while ((line = bufferedReader.readLine()) != null) {
- if(i==mazeNum){
- mazeString=line;
- break;
- }
- i++;
- }
- fileReader.close();
- } catch (IOException e) {
- e.printStackTrace();
- }
- return mazeString.split(";");
- }
- public void addWalls(List<String> barriers){
- int x,y,width,height;
- for(int i=0;i<barriers.size();i++){
- String[] infoSplit = barriers.get(i).split(",");
- x = Integer.parseInt(infoSplit[0]);
- y = Integer.parseInt(infoSplit[1]);
- width = Integer.parseInt(infoSplit[2]);
- height = Integer.parseInt(infoSplit[3]);
- for(int j=x;j<x+width;j++){
- for(int k=y;k<y+height;k++){
- setCellisBarrier(j, k, true);
- }
- }
- }
- }
- public Cell getCell(int x,int y){
- ArrayList<Cell> list = maze.get(y);
- return list.get(x);
- }
- public void setCellisBarrier(int x,int y,boolean isBarrier){
- Cell cell = getCell(x, y);
- cell.setBarrier(isBarrier);
- }
- public ArrayList<Cell> getNeighbourCell(Cell cell){
- ArrayList<Cell> cellList = new ArrayList<Cell>();
- if(cell.getX() < width-1 && cell.getX() >= 0){
- cellList.add(this.getCell(cell.getX()+1, cell.getY()));
- }
- if(cell.getY() > 0 && cell.getY() < height){
- cellList.add(this.getCell(cell.getX(), cell.getY()-1));
- }
- if(cell.getX() > 0 && cell.getX() < width){
- cellList.add(this.getCell(cell.getX()-1, cell.getY()));
- }
- if(cell.getY() < height-1 && cell.getY() >= 0 ){
- cellList.add(this.getCell(cell.getX(), cell.getY()+1));
- }
- return cellList;
- }
- private int getHeuristic(int x, int y){
- int goalX = this.getGoalX();
- int goalY = this.getGoalY();
- return (Math.abs(goalX-x) + Math.abs(goalY-y));
- }
- public void updateCell(Cell neighbour, Cell currentCell){
- neighbour.setG(currentCell.getG()+1);
- neighbour.setH(this.getHeuristic(neighbour.getX(),neighbour.getY()));
- neighbour.setParent(currentCell);
- int f = neighbour.getG() + neighbour.getH();
- neighbour.setF(f);
- }
- public int getWidth() {
- return width;
- }
- public void setWidth(int width) {
- this.width = width;
- }
- public int getHeight() {
- return height;
- }
- public void setHeight(int height) {
- this.height = height;
- }
- public int getStartY() {
- return startY;
- }
- public void setStartY(int startY) {
- this.startY = startY;
- }
- public int getStartX() {
- return startX;
- }
- public void setStartX(int startX) {
- this.startX = startX;
- }
- public int getGoalY() {
- return goalY;
- }
- public void setGoalY(int goalY) {
- this.goalY = goalY;
- }
- public int getGoalX() {
- return goalX;
- }
- public void setGoalX(int goalX) {
- this.goalX = goalX;
- }
- }
- import java.util.ArrayList;
- import java.util.Comparator;
- import java.util.Scanner;
- import java.io.BufferedReader;
- import java.io.File;
- import java.io.FileReader;
- import java.io.IOException;
- import java.util.PriorityQueue;
- public class Algorithm {
- static String[] mazeInfo;
- static int index;
- static Maze maze;
- static PriorityQueue<Cell> openQueue = new PriorityQueue<Cell>(1000, new Comparator<Cell>()
- {
- public int compare(Cell cell1, Cell cell2){
- return (cell1.getF() - cell2.getF());
- }
- });
- static ArrayList<Cell> closedList = new ArrayList<Cell>();
- public static void main(String[] args) {
- try {
- Scanner in = new Scanner(System.in);
- System.out.println("Choose a maze (0-5): ");
- while(index!=-1){
- index = Integer.parseInt(in.nextLine());
- maze = new Maze(index);
- break;
- }
- addToQueue(maze.getCell(maze.getStartX(), maze.getStartY()));
- while (!openQueue.isEmpty()){
- Cell primaryCell = openQueue.poll();
- closedList.add(primaryCell);
- if( (primaryCell.getX()==maze.getGoalX() && primaryCell.getY()==maze.getGoalY())){
- System.out.println("a");
- while (primaryCell != maze.getCell(maze.getStartX(), maze.getStartX())){
- int x = primaryCell.getX();
- int y = primaryCell.getY();
- System.out.print(x);System.out.print(",");System.out.print(y);System.out.println();
- primaryCell = primaryCell.getParent();
- }
- break;
- }
- System.out.println("b");
- ArrayList<Cell> neighbourCells = maze.getNeighbourCell(primaryCell);
- System.out.println("c");
- for (int i=0;i<neighbourCells.size();i++){
- System.out.println(i);
- Cell secondaryCell = neighbourCells.get(i);
- if(!secondaryCell.isBarrier() && !closedList.contains(secondaryCell)){
- if(openQueue.contains(secondaryCell)){
- if(secondaryCell.getG() > primaryCell.getG() + 1){
- maze.updateCell(secondaryCell, primaryCell);
- }
- }
- else{
- maze.updateCell(secondaryCell, primaryCell);
- openQueue.add(secondaryCell);
- }
- }
- }
- }
- } catch (Throwable ex) {
- System.err.println("Uncaught exception - " + ex.getMessage());
- ex.printStackTrace(System.err);
- }
- }
- public static void addToQueue(Cell cell){
- openQueue.add(cell);
- //Bruke PriorityQueue som heap
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement