Advertisement
Guest User

Untitled

a guest
Oct 26th, 2014
1,290
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 13.33 KB | None | 0 0
  1. import java.awt.Color;
  2. import java.awt.Dimension;
  3. import java.awt.Graphics;
  4. import java.awt.Graphics2D;
  5. import java.awt.RenderingHints;
  6. import java.awt.FlowLayout;
  7. import java.awt.Insets;
  8. import java.awt.geom.*;
  9. import java.awt.Stroke;
  10. import java.awt.BasicStroke;
  11. import java.awt.GridLayout;
  12. import java.util.Random;
  13. import javax.swing.JFrame;
  14. import javax.swing.JPanel;
  15. import javax.swing.SwingUtilities;
  16. import javax.swing.JComponent;
  17. import javax.swing.JButton;
  18. import javax.swing.BoxLayout;
  19. import java.util.*;
  20. import java.awt.event.*;
  21.  
  22. class Config {
  23.   public static int CELL_SIZE = 25;
  24. }
  25.  
  26. enum CellType {
  27.   FREE, WALL, START, END
  28. }
  29.  
  30. class Cell extends JComponent {
  31.   private Rectangle2D rect;
  32.   private CellType type;
  33.   private Graphics2D graphics;
  34.   private int row;
  35.   private int col;
  36.   private Grid grid;
  37.   private Color color;
  38.   private boolean isHiglighted;
  39.  
  40.   public Cell(int col, int row, CellType type, Grid grid) {
  41.     super();
  42.     this.isHiglighted = false;
  43.     this.type = CellType.FREE;
  44.     this.col = col;
  45.     this.row = row;
  46.     this.grid = grid;
  47.     setType(type);
  48.     int x = col * Config.CELL_SIZE;
  49.     int y = row * Config.CELL_SIZE;
  50.     setBounds(x, y, Config.CELL_SIZE - 2, Config.CELL_SIZE - 2);
  51.   }
  52.  
  53.   public void onClick(MouseEvent ev) {
  54.     setType(grid.getSelectedType());
  55.     grid.repaint();
  56.   }
  57.  
  58.   public void onDrag(MouseEvent ev) {
  59.     setType(grid.getSelectedType());
  60.     grid.repaint();
  61.   }
  62.  
  63.   public int getCol() {
  64.     return this.col;
  65.   }
  66.  
  67.   public int getRow() {
  68.     return this.row;
  69.   }
  70.  
  71.   public void setType(CellType type) {
  72.     this.type = type;
  73.     color = Color.white;
  74.     if (type == CellType.FREE) {
  75.       color = Color.white;
  76.     } else if (type == CellType.WALL) {
  77.       color = Color.darkGray;
  78.     } else if (type == CellType.START) {
  79.       color = Color.green;
  80.       if (grid.getStartNode() != null) {
  81.         grid.getStartNode().setType(CellType.FREE);
  82.       }
  83.       grid.setStartNode(this);
  84.     } else if (type == CellType.END) {
  85.       color = Color.red;
  86.       if (grid.getEndNode() != null) {
  87.         grid.getEndNode().setType(CellType.FREE);
  88.       }
  89.       grid.setEndNode(this);
  90.     }
  91.   }
  92.  
  93.   public CellType getType() {
  94.     return this.type;
  95.   }
  96.  
  97.   private void drawMe() {
  98.     graphics.setColor(color);
  99.     double w = Config.CELL_SIZE;
  100.     graphics.fill(new Rectangle2D.Double(0, 0, w, w));
  101.     if (isHiglighted) {
  102.       graphics.setColor(Color.orange);
  103.       double radius = 3.0;
  104.       graphics.draw(new Ellipse2D.Double(Config.CELL_SIZE / 2.0 - radius, Config.CELL_SIZE / 2.0 - radius, 2.0 * radius, 2.0 * radius));
  105.     }
  106.   }
  107.  
  108.   public void highlightMe() {
  109.     this.isHiglighted = true;
  110.   }
  111.  
  112.   public void dehighlightMe() {
  113.     this.isHiglighted = false;
  114.   }
  115.  
  116.   public void setColor(Color color) {
  117.     this.color = color;
  118.   }
  119.  
  120.   @Override
  121.   public void paintComponent(Graphics g) {
  122.     super.paintComponent(g);
  123.     graphics = (Graphics2D)g;
  124.     graphics.setStroke(new BasicStroke(3));
  125.     graphics.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
  126.     drawMe();
  127.   }
  128. }
  129.  
  130. class Grid extends JPanel {
  131.   private int rows;
  132.   private int columns;
  133.   private List<Cell> cells;
  134.   private Cell startNode;
  135.   private Cell endNode;
  136.   private CellType selectedType = CellType.FREE;
  137.   private PathFinder pathfinder;
  138.  
  139.   public Grid(int columns, int rows) {
  140.     super();
  141.     this.columns = columns;
  142.     this.rows = rows;
  143.     this.cells = new ArrayList<Cell>();
  144.     this.pathfinder = new PathFinder(this);
  145.     setLayout(null);
  146.  
  147.     for(int row = 0; row < rows; ++row) {
  148.       for (int col = 0; col < columns; ++col) {
  149.         Cell cell = new Cell(col, row, CellType.FREE, this);
  150.         cells.add(cell);
  151.         add(cell);
  152.       }
  153.     }
  154.  
  155.     Grid grid = this;
  156.     addMouseMotionListener(new MouseMotionAdapter() {
  157.       public void mouseDragged(MouseEvent ev) {
  158.         int x = ev.getX();
  159.         int y = ev.getY();
  160.         int col = (int) Math.floor(x / Config.CELL_SIZE);
  161.         int row = (int) Math.floor(y / Config.CELL_SIZE);
  162.         grid.getCell(col, row).onDrag(ev);
  163.         grid.showPath();
  164.       }
  165.     });
  166.  
  167.     addMouseListener(new MouseAdapter() {
  168.       public void mouseClicked(MouseEvent ev) {
  169.         int x = ev.getX();
  170.         int y = ev.getY();
  171.         int col = (int) Math.floor(x / Config.CELL_SIZE);
  172.         int row = (int) Math.floor(y / Config.CELL_SIZE);
  173.         grid.getCell(col, row).onClick(ev);
  174.         grid.showPath();
  175.       }
  176.     });
  177.   }
  178.  
  179.   public int getColumns() {
  180.     return this.columns;
  181.   }
  182.  
  183.   public int getRows() {
  184.     return this.rows;
  185.   }
  186.  
  187.   public List<Cell> getNeighbours(Cell c) {
  188.     int row = c.getRow();
  189.     int col = c.getCol();
  190.     List<Cell> out = new ArrayList<Cell>();
  191.     int numCells = cells.size();
  192.  
  193.     // north
  194.     int curRow = row - 1;
  195.     int curCol = col;
  196.     if (curRow >= 0 && curRow < rows && curCol >= 0 && curCol < columns) {
  197.       Cell cell = getCell(curCol, curRow);
  198.       if (cell.getType() != CellType.WALL)
  199.         out.add(cell);
  200.     }
  201.  
  202.     // south
  203.     curRow = row + 1;
  204.     curCol = col;
  205.     if (curRow >= 0 && curRow < rows && curCol >= 0 && curCol < columns) {
  206.       Cell cell = getCell(curCol, curRow);
  207.       if (cell.getType() != CellType.WALL)
  208.         out.add(cell);
  209.     }
  210.  
  211.     // west
  212.     curRow = row;
  213.     curCol = col - 1;
  214.     if (curRow >= 0 && curRow < rows && curCol >= 0 && curCol < columns) {
  215.       Cell cell = getCell(curCol, curRow);
  216.       if (cell.getType() != CellType.WALL)
  217.         out.add(cell);
  218.     }
  219.  
  220.     // east
  221.     curCol = col + 1;
  222.     curRow = row;
  223.     if (curRow >= 0 && curRow < rows && curCol >= 0 && curCol < columns) {
  224.       Cell cell = getCell(curCol, curRow);
  225.       if (cell.getType() != CellType.WALL)
  226.         out.add(cell);
  227.     }
  228.  
  229.     // north east
  230.     curCol = col + 1;
  231.     curRow = row - 1;
  232.     if (curRow >= 0 && curRow < rows && curCol >= 0 && curCol < columns) {
  233.       Cell cell = getCell(curCol, curRow);
  234.       if (cell.getType() != CellType.WALL)
  235.         out.add(cell);
  236.     }
  237.     // north west
  238.     curCol = col - 1;
  239.     curRow = row - 1;
  240.     if (curRow >= 0 && curRow < rows && curCol >= 0 && curCol < columns) {
  241.       Cell cell = getCell(curCol, curRow);
  242.       if (cell.getType() != CellType.WALL)
  243.         out.add(cell);
  244.     }
  245.     // south east
  246.     curCol = col + 1;
  247.     curRow = row + 1;
  248.     if (curRow >= 0 && curRow < rows && curCol >= 0 && curCol < columns) {
  249.       Cell cell = getCell(curCol, curRow);
  250.       if (cell.getType() != CellType.WALL)
  251.         out.add(cell);
  252.     }
  253.     // south west
  254.     curCol = col - 1;
  255.     curRow = row + 1;
  256.     if (curRow >= 0 && curRow < rows && curCol >= 0 && curCol < columns) {
  257.       Cell cell = getCell(curCol, curRow);
  258.       if (cell.getType() != CellType.WALL)
  259.         out.add(cell);
  260.     }
  261.     return out;
  262.   }
  263.  
  264.   public List<Cell> getCells() {
  265.     return cells;
  266.   }
  267.  
  268.   public Cell getCell(int col, int row) {
  269.     int index = col + row * columns;
  270.     return cells.get(index);
  271.   }
  272.  
  273.   public Cell getEndNode() {
  274.     return this.endNode;
  275.   }
  276.  
  277.   public void setEndNode(Cell endNode) {
  278.     this.endNode = endNode;
  279.   }
  280.  
  281.   public Cell getStartNode() {
  282.     return this.startNode;
  283.   }
  284.  
  285.   public void setStartNode(Cell startNode) {
  286.     this.startNode = startNode;
  287.   }
  288.  
  289.   public CellType getSelectedType() {
  290.     return this.selectedType;
  291.   }
  292.  
  293.   public void setSelectedType(CellType type) {
  294.     this.selectedType = type;
  295.   }
  296.  
  297.   @Override
  298.   public Dimension getPreferredSize() {
  299.     return new Dimension(Config.CELL_SIZE * columns, Config.CELL_SIZE * rows);
  300.   }
  301.  
  302.   @Override
  303.   public Dimension getMinimumSize() {
  304.     return getPreferredSize();
  305.   }
  306.  
  307.   public void showPath() {
  308.     for (Cell c : getCells()) {
  309.       c.dehighlightMe();
  310.     }
  311.     if (getStartNode() == null || getEndNode() == null)
  312.       return;
  313.     List<Cell> path = pathfinder.find(getStartNode(), getEndNode());
  314.     for (Cell c : path) {
  315.       c.highlightMe();
  316.     }
  317.     repaint();
  318.   }
  319. }
  320.  
  321. class PathFinder {
  322.   private Set<Cell> closed;
  323.   private HashMap<Cell, Node> open;
  324.   private PriorityQueue<PathFinder.Node> queue;
  325.   private Grid grid;
  326.  
  327.   private final double DIAGONAL_COST = 14.0f;
  328.   private final double STRAIGHT_COST = 10.0f;
  329.  
  330.   static class Node implements Comparable<Node> {
  331.     public Node parent;
  332.     public Cell cell;
  333.     public double g, h, f;
  334.     public Node(Cell cell, Node parent, double g, double h) {
  335.       this.cell = cell;
  336.       this.g = g;
  337.       this.h = h;
  338.       this.parent = parent;
  339.       this.f = g + h;
  340.     }
  341.     @Override
  342.     public boolean equals(Object other) {
  343.       if (other == this)
  344.         return true;
  345.       if (other == null || other.getClass() != this.getClass())
  346.         return false;
  347.       Node n = (Node) other;
  348.       return n.f == this.f;
  349.     }
  350.     @Override
  351.     public int compareTo(Node other) {
  352.       return (other.f < this.f) ? 1 : (other.f > this.f) ? -1 : 0;
  353.     }
  354.   }
  355.  
  356.   public PathFinder(Grid grid) {
  357.     this.grid = grid;
  358.     closed = new HashSet<Cell>();
  359.     open = new HashMap<Cell, Node>();
  360.     queue = new PriorityQueue<PathFinder.Node>();
  361.   };
  362.  
  363.   public List<Cell> find(Cell from, Cell to) {
  364.     closed.clear();
  365.     open.clear();
  366.     queue.clear();
  367.     List<Cell> out = new ArrayList<Cell>();
  368.     Node node = new Node(from, null, 0.0, 0.0);
  369.     open.put(from, node);
  370.     queue.add(node);
  371.     while(queue.size() > 0) {
  372.       Node curNode = queue.poll();
  373.       Cell curCell = curNode.cell;
  374.       if (curCell == to) {
  375.         Node parent = curNode;
  376.         while (parent != null) {
  377.           out.add(parent.cell);
  378.           parent = parent.parent;
  379.         }
  380.         break;
  381.       }
  382.       closed.add(curCell);
  383.       List<Cell> neighbours = grid.getNeighbours(curCell);
  384.       for (Cell neigh : neighbours) {
  385.         double g = DIAGONAL_COST;
  386.         if ((curCell.getRow() == neigh.getRow()) || (curCell.getCol() == neigh.getCol()))
  387.           g = STRAIGHT_COST;
  388.         if (closed.contains(neigh))
  389.           continue;
  390.         if (!open.containsKey(neigh)) {
  391.           int xDiff = Math.abs(neigh.getCol() - curCell.getCol());
  392.           int yDiff = Math.abs(neigh.getRow() - curCell.getRow());
  393.           double h = STRAIGHT_COST * (xDiff + yDiff) + (DIAGONAL_COST - 2 * STRAIGHT_COST) * Math.min(xDiff, yDiff);
  394.           node = new Node(neigh, curNode, curNode.g + g, h);
  395.           queue.add(node);
  396.           open.put(neigh, node);
  397.         } else {
  398.           Node n = open.get(neigh);
  399.           if ((curNode.g + g) < n.g) {
  400.             n.g = curNode.g + g;
  401.             n.f = n.h + n.g;
  402.             n.parent = curNode;
  403.           }
  404.         }
  405.       }
  406.     }
  407.     return out;
  408.   }
  409. }
  410.  
  411. public class javastar extends JFrame {
  412.   public javastar() {
  413.     initUI();
  414.   }
  415.  
  416.   private void initUI() {
  417.     setTitle("A* pathfinding");
  418.     setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  419.  
  420.     JPanel container = new JPanel();
  421.     Grid grid = new Grid(25, 20);
  422.  
  423.     container.setLayout(new BoxLayout(container, BoxLayout.Y_AXIS));
  424.     container.add(grid);
  425.     add(container);
  426.  
  427.     JPanel btnContainer = new JPanel();
  428.     btnContainer.setLayout(new BoxLayout(btnContainer, BoxLayout.X_AXIS));
  429.     container.add(btnContainer);
  430.  
  431.     ActionListener myListener = new ActionListener() {
  432.       public void actionPerformed(ActionEvent e) {
  433.         switch (((JButton)e.getSource()).getText()) {
  434.           case "S": {
  435.             grid.setSelectedType(CellType.START);
  436.             break;
  437.           }
  438.           case "E": {
  439.             grid.setSelectedType(CellType.END);
  440.             break;
  441.           }
  442.           case "F": {
  443.             grid.setSelectedType(CellType.FREE);
  444.             break;
  445.           }
  446.           case "B": {
  447.             grid.setSelectedType(CellType.WALL);
  448.             break;
  449.           }
  450.           default: {
  451.             grid.setSelectedType(CellType.FREE);
  452.           }
  453.         }
  454.       }
  455.     };
  456.  
  457.     JButton start = new JButton("S");
  458.     JButton end = new JButton("E");
  459.     JButton free = new JButton("F");
  460.     JButton wall = new JButton("B");
  461.     JButton fpath = new JButton("Find path!");
  462.  
  463.     fpath.addActionListener(new ActionListener() {
  464.       public void actionPerformed(ActionEvent e) {
  465.         grid.showPath();
  466.       }
  467.     });
  468.  
  469.     start.addActionListener(myListener);
  470.     end.addActionListener(myListener);
  471.     free.addActionListener(myListener);
  472.     wall.addActionListener(myListener);
  473.  
  474.     start.setBackground(Color.green);
  475.     end.setBackground(Color.red);
  476.     free.setBackground(Color.white);
  477.     wall.setBackground(Color.darkGray);
  478.  
  479.     Dimension pfDim = new Dimension(Config.CELL_SIZE, Config.CELL_SIZE);
  480.     start.setPreferredSize(pfDim);
  481.     end.setPreferredSize(pfDim);
  482.     free.setPreferredSize(pfDim);
  483.     wall.setPreferredSize(pfDim);
  484.     fpath.setPreferredSize(pfDim);
  485.  
  486.     btnContainer.add(start);
  487.     btnContainer.add(end);
  488.     btnContainer.add(free);
  489.     btnContainer.add(wall);
  490.     btnContainer.add(fpath);
  491.  
  492.     container.add(btnContainer);
  493.  
  494.     Dimension dims = grid.getPreferredSize();
  495.     setSize(dims.width, dims.height + 2 * Config.CELL_SIZE);
  496.     setLocationRelativeTo(null);
  497.   }
  498.  
  499.   public static void main(String[] args) {
  500.     SwingUtilities.invokeLater(new Runnable() {
  501.       @Override
  502.       public void run() {
  503.         javastar ps = new javastar();
  504.         ps.setVisible(true);
  505.       }
  506.     });
  507.   }
  508. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement