package cn.org.matrix.gmatrix.practice.arithmetic;

/**
 * 地图中的节点
 * 按照A*算法：h=f+g,
 * h为从起点A到终点B的评估耗费，
 * g为从起点A，沿着产生的路径，移动到网格上指定方格的移动耗费,
 * f为从网格上那个方格移动到终点B的预估移动耗费
 * @author cleverpig
 *
 */
public class Node {
        //从起点A沿着产生的路径移动到当前节点的预估移动耗费
        public int costFromStart=0;
        //从当前节点移动到终点B的预估移动耗费
        public int costToGoal=0;
        //从起点A到终点B的评估耗费
        public int totalCost=0;
        public Location location=null;
        public Node parent;
        
        public boolean equals(Object node){
                if (((Node)node).location.equals(location)){
                        return true;
                }
                else{
                        return false;
                }
        }
        
        public String toString(){
                return "x="+location.x+" y="+location.y+" G="+costFromStart
                +" H="+costToGoal+" F="+totalCost;
        }
        
}

package cn.org.matrix.gmatrix.practice.arithmetic;

import java.util.Vector;
/**
 * 节点列表：用于开启列表和关闭列表
 * @author cleverpig
 *
 */
public class NodeList extends Vector{
        /**
         * 
         */
        private static final long serialVersionUID = 1L;
//        private Vector v=null;
        public NodeList(){
//                v=new Vector();
                super();
        }
        
        /**
         * 获得第一个节点（最小的）
         * @return 第一个节点
         */
        public Node pop(){
                if (this!=null){
                        Node node=(Node)this.elementAt(0);
                        this.removeElement(node);
                        return node;
                }
                else{
                        return null;
                }
        }
        /**
         * 按照升序添加节点
         * @param node 被添加的节点
         */
        public void addNode(Node node){
                if (this.size()==0){
                        this.addElement(node);
                }
                else{
                        for(int i=0;i<this.size();i++){
                                Node temp=(Node)this.elementAt(i);
                                if (temp.totalCost>=node.totalCost){
                                        this.insertElementAt(node,i);
                                        return;
                                }
                        }
                        this.addElement(node);
                }
        }
        
        public void sort(){
                if (this.size()==0){
                        return;
                }
                else{
                        for(int i=0;i<this.size()-1;i++){
                                Node first=(Node)this.elementAt(i);
                                Node next=(Node)this.elementAt(i+1);
                                if (first.totalCost>next.totalCost){
//                                        Node temp=first;
//                                        first=next;
//                                        next=temp;
                                        this.setElementAt(next,i);
                                        this.setElementAt(first,i+1);
                                }
                        }
                }
        }
        
        public String toString(){
                String s="";
                for(int i=0;i<this.size();i++){
                        s+=((Node)this.elementAt(i)).toString()+"\n";
                }
                return s;
        }

}

package cn.org.matrix.gmatrix.practice.arithmetic;

/**
 * 节点位置对象
 * @author cleverpig
 *
 */
public class Location {
        public int x=0;
        public int y=0;
        
        public Location(int x,int y){
                this.x=x;
                this.y=y;
        }
        
        public boolean equals(Object obj){
                if ((((Location)obj).x==x)&&(((Location)obj).y==y)){
                        return true;
                }
                else{
                        return false;
                }
        }
        
        public String toString(){
                return "x="+x+" y="+y;
        }
}

package cn.org.matrix.gmatrix.practice.arithmetic;

/**
 * 用于计算预估耗费的常量
 * @author cleverpig
 *
 */
public class Constants {
        //NOTHING
        public static final int NOTHING = -1;
        //无任何障碍对应cost数组的下标
        public static final int EMPTY = 0;
        //地形1对应cost数组的下标
    public static final int TERRAIN1 = 1;
    //地形2对应cost数组的下标
    public static final int TERRAIN2 = 2;
    //地形3对应cost数组的下标
    public static final int TERRAIN3 = 3;
    //不可穿过的固体对应cost数组的下标
    public static final int SOLID = 4;
    //起始点对应cost数组的下标
    public static final int START = 5;
    //终点对应cost数组的下标
    public static final int FINISH = 6;
    //数组的数量
    public static final int NUMCOLORS = FINISH + 1;
}

package cn.org.matrix.gmatrix.practice.arithmetic;

import java.util.Vector;
/**
 * 实现A*算法
 * @author cleverpig
 *
 */
public class AStar {
        //地图数组
        int[][] grid=null;
        //路径寻找的开始位置
        Location start=null;
        //路径寻找的目的位置
        Location goal=null;
        //开启节点列表
        NodeList open=null;
        //关闭节点列表
        NodeList closed=null;
        //预估耗费用的常量
        int[] cost=null;
        //直线单元耗费值
        public static final int linealCost=10;
        //对角线单元耗费值
        public static final int diagonalCost=14;
        //左上
        final int LEFT_TOP=1;
        //左下
        final int LEFT_BOTTOM=4;
        //右上
        final int RIGHT_TOP=6;
        //右下
        final int RIGHT_BOTTOM=8;
        
        public AStar(int[][] grid,int[] cost,Location start,Location goal){
                this.grid=grid;
                this.start=start;
                this.goal=goal;
                open=new NodeList();
                closed=new NodeList();
                this.cost=cost;
        }
        
        /**
         * 释放节点，从起点到指定节点的所有节点
         * @param node 指定节点
         * @return 从起点到指定节点的所有节点的集合
         */
        private Vector solve(Node node) {
        Vector solution = new Vector();
        
        solution.addElement(node);
        while(node.parent != null) {
            solution.insertElementAt(node.parent, 0);
            node = node.parent;
        }
        
        return solution;
    }
        
        /**
         * 进行路径查找
         * @return 返回路径集合
         */
        public Vector find(){
                long startTime=System.currentTimeMillis();
                //为起点赋初值
                Node startNode=new Node();
                startNode.location=start;
                startNode.costFromStart=0;
                startNode.costToGoal=currnetToGoalCostEstimate(start,goal);
                startNode.totalCost=startNode.costToGoal+startNode.costFromStart;
                startNode.parent=null;
                
                open.addNode(startNode);
                        
                while(open.size()>0){
                        //寻找开启列表中F值最低的格子。我们称它为当前格
                        Node currentNode=open.pop();
                        System.out.println("寻找开启列表中F值最低的格子:"+currentNode);
                        
                        //把目标格添加进了开启列表，这时候路径被找到
                        if (currentNode.location.equals(goal)){
                                System.out.println("路径被找到");
                                System.out.println("共耗时:"+(System.currentTimeMillis()-startTime)+"ms");
                                return solve(currentNode);
                        }
                        else{
                                //把当前格切换到关闭列表
                                closed.addNode(currentNode);
                                //获得当前附近的节点集合
                                Vector neighborList=getNeighbors(currentNode);
                                
                                boolean inOpenList=false;
                                boolean inClosedList=false;
                                
                                for(int i=0;i<neighborList.size();i++){
//                                        System.out.println("开启列表内容:\n"+open);
                                        //计算邻居节点的耗费值
                                        Node neighborNode=(Node)neighborList.elementAt(i);
                                        
                                        System.out.println("比较邻居节点:"+neighborNode);
                                        
                                        inOpenList=open.contains(neighborNode);
                                        inClosedList=closed.contains(neighborNode);
                                        
                                        System.out.println("is in Open="+inOpenList);
                                        System.out.println("is in Closed="+inClosedList);
                                        //如果它不可通过或者已经在关闭列表中，略过它
                                        if (inClosedList){
                                                System.out.println("邻居节点已经在关闭列表!");
                                                continue;
                                        }
                                        //如果它不在开启列表中，把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。
                                        else{
                                                if (inOpenList==false){
                                                        System.out.println("记录这一格的F,G,和H值");
                                                        neighborNode.costFromStart=currentNode.costFromStart
                                                                +neighborToCurrentCostEstimate(currentNode,neighborNode);
                                                        neighborNode.costToGoal=currnetToGoalCostEstimate(neighborNode.location,goal);
                                                        neighborNode.totalCost=neighborNode.costFromStart+neighborNode.costToGoal;
                                                        neighborNode.parent=currentNode;
                                                        System.out.println("把它添加进开启表:"+neighborNode);
                                                        open.addNode(neighborNode);
                                                        System.out.println("邻居节点不在开启列表中，被添加:\n"+neighborNode);
                                                }
                                                //如果它已经在开启列表中，用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。
                                                //如果是这样，就把这一格的父节点改成当前格，并且重新计算这一格的G和F值。
                                                //如果你保持你的开启列表按F值排序，改变之后你可能需要重新对开启列表排序。
                                                else{
                                                        if ((currentNode.costFromStart+neighborToCurrentCostEstimate(currentNode,neighborNode))
                                                                        <currentNode.costFromStart){
                                                                System.out.println("邻居节点是G值低的\n"+neighborNode);
                                                                currentNode=neighborNode.parent;
                                                                neighborNode.costToGoal=currnetToGoalCostEstimate(neighborNode.location,goal);
                                                                neighborNode.totalCost=neighborNode.costFromStart+neighborNode.costToGoal;
                                                                open.sort();
                                                                System.out.println("重新对开启列表排序:\n"+open);
                                                        }
                                                        
                                                }
                                                        
                                                        
                                        }
                                }
                        }
                }
                System.out.println("路径没有被找到");
                System.out.println("共耗时:"+(System.currentTimeMillis()-startTime)+"ms");
                return null;
        }
        
        /**
         * 计算从start到goal的矩形区域中平均耗费值
         * @param start 起始位置
         * @param goal 目标位置
         * @return 从start到goal的矩形区域中平均耗费值
         */
//        private double getAverageCost(Location start,Location goal){
//                int left=Math.min(start.x,goal.x);
//                int top=Math.min(start.y,goal.y);
//                int right=Math.max(start.x,goal.x);
//                int bottom=Math.max(start.y,goal.y);
//                double totalValue=0;
//                double count=0;
//                for(int i=left;i<=right;i++){
//                        for(int j=top;j<=bottom;j++){
//                                if (grid[i][j]!=Constants.NOTHING){
//                                        totalValue+=cost[grid[i][j]];
//                                        count++;
//                                }
//                        }
//                }
//                return totalValue/count/1.1;
//        }
        
        /**
         * 计算从某节点到目标节点的预估耗费
         * @param start 计算的起始点
         * @param goal 计算的终点
         * @return 返回从某节点到目标节点的预估耗费
         */
        private int currnetToGoalCostEstimate(Location start,Location goal){
                int dx=Math.abs(start.x-goal.x);
                int dy=Math.abs(start.y-goal.y);
                return (dx+dy)*linealCost;
        }
        
        /**
         * 计算从当前节点到其周围的邻居节点的预估耗费
         * @param currentNode 当前节点
         * @param neighborNode 邻居节点
         * @return 从当前节点到其周围的邻居节点的预估耗费
         */
        private int neighborToCurrentCostEstimate(Node currentNode,Node neighborNode){
                int dx=Math.abs(currentNode.location.x-neighborNode.location.x);
                int dy=Math.abs(currentNode.location.y-neighborNode.location.y);
                //如果为对角线方向
                if (dx==1&&dy==1){
                        //G=(x轴距离+y轴距离)*对角线单位耗费+当前节点的耗费
                        return (dx+dy)*diagonalCost+cost[grid[neighborNode.location.x][neighborNode.location.y]];
                }
                //如果为直线方向
                else{
                        //G=(x轴距离+y轴距离)*直线单位耗费+当前节点的耗费
                        return (dx+dy)*linealCost+cost[grid[neighborNode.location.x][neighborNode.location.y]];
                }//+cost[grid[neighborNode.location.x][neighborNode.location.y]];
        }
        
        /**
         * 边界检测
         * @param x x轴坐标
         * @param y y轴坐标
         * @return 如果出边界，则返回true
         */
        private boolean isOutOfBorder(int x,int y){
                //测试边界
                if (x<0||x>=grid.length){
                        return true;
                }
                //测试边界
                if (y<0||y>=grid[0].length){
                        return true;
                }
                return false;
        }
        
        /**
         * 条件性的增加节点
         * @param neighborList 邻居列表
         * @param location 当前节点的坐标
         * @param dx x轴坐标增量
         * @param dy y轴坐标增量
         */
        private void conditionalAdd(Vector neighborList,Location location,int dx,int dy){
                int x=location.x;
                int y=location.y;
                int newX=x+dx;
                int newY=y+dy;
                
                //测试边界
                if (isOutOfBorder(newX,newY)){
                        return;
                }
                
                //跳过不能通过的物体
                if (grid[newX][newY]==Constants.SOLID){
                        return;
                }
                
                //判断左上角邻居节点
                if ((dx==-1)&&(dy==-1)){
                        if (isSkiped(LEFT_TOP,newX,newY)){
                                System.out.println("跳过节点"+location+"的左上角邻居节点");
                                return;
                        }
                }
                
                //判断左下角邻居节点
                if ((dx==-1)&&(dy==1)){
                        if (isSkiped(LEFT_BOTTOM,newX,newY)){
                                System.out.println("跳过节点"+location+"的左下角邻居节点");
                                return;
                        }
                }
                
                //判断右上角邻居节点
                if ((dx==1)&&(dy==-1)){
                        if (isSkiped(RIGHT_TOP,newX,newY)){
                                System.out.println("跳过节点"+location+"的右上角邻居节点");
                                return;
                        }
                }
                
                //判断右下角邻居节点
                if ((dx==1)&&(dy==1)){
                        if (isSkiped(RIGHT_BOTTOM,newX,newY)){
                                System.out.println("跳过节点"+location+"的右下角邻居节点");
                                return;
                        }
                }
                
                Node neighbor=new Node();
                neighbor.location=new Location(newX,newY);
                neighborList.addElement(neighbor);
        }
        
        /**
         * 判断处于拐弯处（左上、右上、左下、右下）的邻居节点，是否邻着不可穿透的固体，如果是则该节点被跳过
         * @param direction 表示邻居节点与当前节点位置关系的左上、右上、左下、右下方向常量
         * @param x 邻居节点的x坐标
         * @param y 邻居节点的y坐标
         * @return 判断处于拐弯处（左上、右上、左下、右下）的邻居节点，是否邻着不可穿透的固体，如果是则返回true
         */
        private boolean isSkiped(int direction,int x,int y){
                int x1=0,y1=0;
                int x2=0,y2=0;
                
                switch(direction){
                        //如果当前位置为左上角，则判断其下方和右侧是否为不可穿过的固体
                        case LEFT_TOP:
                                x1=x;
                                y1=y+1;
                                x2=x+1;
                                y2=y;
                                break;
                        //如果当前位置为右上角，则判断其下方和左侧是否为不可穿过的固体
                        case RIGHT_TOP:
                                x1=x;
                                y1=y+1;
                                x2=x-1;
                                y2=y;
                                break;
                        //如果当前位置为左下角，则判断其上方和右侧是否为不可穿过的固体
                        case LEFT_BOTTOM:
                                x1=x;
                                y1=y-1;
                                x2=x+1;
                                y2=y;
                                break;
                        //如果当前位置为右下角，则判断其上方和左侧是否为不可穿过的固体
                        case RIGHT_BOTTOM:
                                x1=x;
                                y1=y-1;
                                x2=x-1;
                                y2=y;
                                break;
                }
                if (isOutOfBorder(x1,y1)==false){
                        if (grid[x1][y1]==Constants.SOLID){
                                return true;
                        }
                        else{
                                return false;
                        }
                }
                if (isOutOfBorder(x2,y2)==false){
                        if (grid[x2][y2]==Constants.SOLID){
                                return true;
                        }
                        else{
                                return false;
                        }
                }
                return false;
        }
        
        /**
         * 获得当前节点周围的邻居节点集合
         * @param currentNode 当前节点
         * @return 当前节点周围的邻居节点集合
         */
        private Vector getNeighbors(Node currentNode){
                Vector neighborList=new Vector();
                
                //增加左上角邻居节点
                conditionalAdd(neighborList,currentNode.location,-1,-1);
                
                //增加左侧邻居节点
                conditionalAdd(neighborList,currentNode.location,-1,0);
                
                //增加左下角的邻居节点
                conditionalAdd(neighborList,currentNode.location,-1,1);

                //增加上方邻居节点
                conditionalAdd(neighborList,currentNode.location,0,-1);
                
                //增加下方邻居节点
                conditionalAdd(neighborList,currentNode.location,0,1);
                
                //增加右上角邻居节点
                conditionalAdd(neighborList,currentNode.location,1,-1);
                
                //增加右侧邻居节点
                conditionalAdd(neighborList,currentNode.location,1,0);
                
                //增加右下角邻居节点
                conditionalAdd(neighborList,currentNode.location,1,1);
                
                return neighborList;
                
        }
}

package cn.org.matrix.gmatrix.practice.arithmetic;

import java.applet.*;
import java.awt.*;
import java.awt.event.*;
import java.util.Vector;

public class AStarApplet extends Applet implements MouseListener, MouseMotionListener {

    /**
         * 
         */
        private static final long serialVersionUID = 847097589329261438L;

        /**
         * 
         */

        static final int appletWidth = 601, appletHeight = 401, gridWidth = appletHeight,
                     numRows = 20;
    
    static final int cellWidth = gridWidth / numRows;

                     
    static final int pad = 10;
    static int current = Constants.EMPTY, startI = Constants.NOTHING, startJ = Constants.NOTHING, finishI = Constants.NOTHING,
               finishJ = Constants.NOTHING;
    
    static Color[] tColor = new Color[Constants.NUMCOLORS];
    
    static int[][] grid = new int[numRows][numRows];
    static int[] costs = new int[Constants.NUMCOLORS];
    static Graphics g;
    
    public void init() {
        g = getGraphics();
        resize(appletWidth, appletHeight);
        tColor[Constants.EMPTY] = Color.black;
        costs[Constants.EMPTY] = 1*AStar.linealCost;
        tColor[Constants.TERRAIN1] = new Color(0, 88, 0);
        costs[Constants.TERRAIN1] = 5*AStar.linealCost;
        tColor[Constants.TERRAIN2] = new Color(99, 77, 0);
        costs[Constants.TERRAIN2] = 10*AStar.linealCost;
        tColor[Constants.TERRAIN3] = Color.blue;
        costs[Constants.TERRAIN3] = 15*AStar.linealCost;
        tColor[Constants.SOLID] = Color.white;
        costs[Constants.SOLID] = Constants.NOTHING;
        tColor[Constants.START] = Color.green;
        costs[Constants.START] = 1*AStar.linealCost;
        tColor[Constants.FINISH] = Color.red;
        costs[Constants.FINISH] = 1*AStar.linealCost;
        addMouseListener(this);
        addMouseMotionListener(this);
    }
    
    public void start() {
        paint(getGraphics());
    }
    
    public void stop() {
    }
        
    public void paint(Graphics g) {
        g.setColor(Color.black);
        g.fillRect(0, 0, appletWidth, appletHeight);
        drawAll();
    }
    
    public void update(Graphics g) {
        paint(g);
    }
    
    private void drawAll() {
        for(int i = 0; i < numRows; i++) {
            for(int j = 0; j < numRows; j++) {
                drawCell(i, j);
            }
        }
        if(startI != Constants.NOTHING) {
            drawCell(startI, startJ);
        }
        if(finishI != Constants.NOTHING) {
            drawCell(finishI, finishJ);
        }
        int left = gridWidth + pad;
        for(int i = Constants.EMPTY; i <= Constants.FINISH; i++) {
            int top = pad + (cellWidth + pad) * i;
            drawTerrainButton(i, left, top, (current == i ? true : false));
        }
        drawButtons();
    }
    
    int buttonsLeft = gridWidth + pad * 2;
    int buttonsWidth = appletWidth - gridWidth - pad * 4;
    int buttonsHeight = 20;
    int goTop = appletHeight - pad - (buttonsHeight + pad) * 2;
    int clearTop = appletHeight - pad - (buttonsHeight + pad);
    
    private void drawButtons() {
        int halfWidth = buttonsLeft + buttonsWidth / 2;
        String goString = "计算", clearString = "清除路径";
        g.setColor(Color.white);
        g.drawRect(buttonsLeft, goTop, buttonsWidth, buttonsHeight);
        g.drawRect(buttonsLeft, clearTop, buttonsWidth, buttonsHeight);
        g.setFont(new Font("SansSerif", Font.BOLD, 12));
        g.drawString(goString, halfWidth - g.getFontMetrics().stringWidth(goString) / 2, goTop + 15);
        g.drawString(clearString, halfWidth - g.getFontMetrics().stringWidth(clearString) / 2, clearTop + 15);
    }
    
    private void drawCell(int i, int j) {
        int left = i * cellWidth, top = j * cellWidth;
        g.setColor(Color.lightGray);
        g.drawRect(left, top, cellWidth, cellWidth);
        if(grid[i][j] == Constants.START) {
            g.setColor(tColor[Constants.START]);
            g.drawRect(left, top, cellWidth, cellWidth);
            g.setColor(Color.black);
            g.fillRect(left + 1, top + 1, cellWidth - 1, cellWidth - 1);
        } else if(grid[i][j] == Constants.FINISH) {
            g.setColor(tColor[Constants.FINISH]);
            g.drawRect(left, top, cellWidth, cellWidth);
            g.setColor(Color.black);
            g.fillRect(left + 1, top + 1, cellWidth - 1, cellWidth - 1);
        } else if(grid[i][j] == Constants.NOTHING) {
            g.setColor(Color.black);
            g.fillRect(left + 1, top + 1, cellWidth - 1, cellWidth - 1);
        } else {
            g.setColor(tColor[grid[i][j]]);
            g.fillRect(left + 1, top + 1, cellWidth - 1, cellWidth - 1);
        }
    }
    
    private void drawTerrainButton(int i, int left, int top, boolean on) {
        g.setFont(new Font("SansSerif", Font.BOLD, 12));
        if(i == Constants.START || i == Constants.FINISH) {
            g.setColor(tColor[i]);
            g.drawRect(left, top, cellWidth, cellWidth);
            g.setColor(Color.white);
            if(i == Constants.START) {
                g.drawString("起始点",left + cellWidth + pad * 2, top + cellWidth);
            } else if(i == Constants.FINISH) {
                g.drawString("终点",left + cellWidth + pad * 2, top + cellWidth);
            }
        } else {
                if (i>Constants.NOTHING){
                    g.setColor(tColor[i]);
                    g.fillRect(left, top, cellWidth, cellWidth);
                    g.setColor(Color.white);
                    g.drawRect(left, top, cellWidth, cellWidth);
                    g.setColor(Color.white);
                    g.drawString((i == Constants.SOLID ? "固体" : String.valueOf(costs[i])),left + cellWidth + pad * 2, top + cellWidth);
                }
        }
        if(on) {
            g.setColor(Color.red);
        } else {
            g.setColor(Color.black);
        }
        g.fillRect(left + cellWidth + pad / 2, top, pad / 2, cellWidth + 1);
    }
    
//    private void drawStartStop(int i, int left, int top, boolean on) {
//        if(on) {
//            g.setColor(Color.red);
//        } else {
//            g.setColor(Color.black);
//        }
//        g.fillRect(left + cellWidth + pad / 2, top, pad / 2, cellWidth + 1);
//    }
    
    public void mouseClicked(MouseEvent e) {}

    public void mousePressed(MouseEvent e) {
        int x = e.getX(), y = e.getY();
        
        if(x < gridWidth - 1) {
            checkGrid(x, y);
        } else {
            int left = gridWidth + pad;
            int old = current;
            boolean selected = false;
            for(int i = Constants.EMPTY; i <= Constants.FINISH; i++) {
                int top = pad + (cellWidth + pad) * i;
                if(checkBounds(left, top, cellWidth, cellWidth, x, y)) {
                    drawTerrainButton(current = i, left, top, true);
                    selected = true;
                    break;
                }
            }
            if(!selected) {
                current = Constants.NOTHING;
                if(checkBounds(buttonsLeft, goTop, buttonsWidth, buttonsHeight, x, y) && startI != Constants.NOTHING && finishI != Constants.NOTHING) {
                    AStar a = new AStar(grid, costs, new Location(startI, startJ), new Location(finishI, finishJ));
                    Vector solution = a.find();
                    if(solution != null) {
                        g.setFont(new Font("SansSerif", Font.BOLD, 12));
                        for(int i = 0; i < solution.size(); i++) {
                            Location nodeLoc = ((Node)solution.elementAt(i)).location;
                            drawDot(nodeLoc.x, nodeLoc.y);

                            try {
                                Thread.sleep(300);
                            } catch(InterruptedException ex) {
                            }
                        }
                    }
                } else if(checkBounds(buttonsLeft, clearTop, buttonsWidth, buttonsHeight, x, y)) {
                    drawAll();
                }
            }
            if(old != current) {
                drawTerrainButton(old, left, pad + (cellWidth + pad) * old, false);
            }
        }
    }
    
    
    public void mouseDragged(MouseEvent e) {
        int x = e.getX(), y = e.getY();
        
        checkGrid(x, y);
    }
    
    private void checkGrid(int x, int y) {
        if(x < gridWidth - 1) {
            if(current != Constants.NOTHING) {
                int i = x / numRows, j = y / numRows;
                if(grid[i][j] == Constants.START) {
                    startI = finishJ = Constants.EMPTY;
                }
                if(grid[i][j] == Constants.FINISH) {
                    finishI = finishJ = Constants.EMPTY;
                }
                if(current == Constants.START) {
                    if(startI != Constants.NOTHING) {
                        grid[startI][startJ] = Constants.EMPTY;
                        drawCell(startI, startJ);
                    }
                    startI = i;
                    startJ = j;
                } else if(current == Constants.FINISH) {
                    if(finishI != Constants.NOTHING) {
                        grid[finishI][finishJ] = Constants.EMPTY;
                        drawCell(finishI, finishJ);
                    }
                    finishI = i;
                    finishJ = j;
                }
                grid[i][j] = current;
                drawCell(i, j);
            }
        }
    }
    
    public void mouseMoved(MouseEvent e) {}
    
    private void drawDot(int i, int j) {
        int left = i * cellWidth + 1, top = j * cellWidth + 1, right = left + cellWidth - 2, bottom = top + cellWidth - 2;
        g.setColor(Color.yellow);
        g.drawLine(left + cellWidth / 2 - 1, top, right, top + cellWidth / 2 - 1);
        g.drawLine(right, top + cellWidth / 2 - 1, left + cellWidth / 2 - 1, bottom);
        g.drawLine(left + cellWidth / 2 - 1, bottom, left, top + cellWidth / 2 - 1);
        g.drawLine(left, top + cellWidth / 2 - 1, left + cellWidth / 2 - 1, top);
    }
    
    public void mouseReleased(MouseEvent e) {}
    public void mouseEntered(MouseEvent e) {}
    public void mouseExited(MouseEvent e) {}
   
    private boolean checkBounds(int left, int top, int buttonWidth, int buttonHeight, int x, int y) {
        return (x >= left && x < left + buttonWidth && y >= top && y < top + buttonHeight);
    }

}