public class PathFinder {

                private boolean[][] map;

                private int [][] blocks;


                public PathFinder(){

                        map = null;

                        blocks = null;

                }


                public ArrayList<RSTile> generatePath (RSTile cur, RSTile dest) {

                        ArrayList<PathTile> closed = new ArrayList(), open = new ArrayList();

                        ArrayList<RSTile> path = new ArrayList();

                        int baseX = Bot.getClient().getBaseX(),

                                        baseY = Bot.getClient().getBaseY(),

                                        curX = cur.getX() - baseX,

                                        curY = cur.getY() - baseY,

                                        destX = dest.getX() - baseX,

                                        destY = dest.getY() - baseY;

                        /*

                         * If tile isn't in the current region, return null because we cannot

                         * create a valid path

                         */

                        if(curX < 0 || curX >= 104 || curY < 0 || curY >= 104 || (curX == destX && curY == destY))

                                return null;

                        if(destX < 0)

                                destX = 0;

                        if(destY < 0)

                                destY = 0;

                        if(destX >= 104)

                                destX = 103;

                        if(destY >= 104) 

                                destY = 103;

                        PathTile current = new PathTile(curX, curY),

                                        destination = new PathTile(destX, destY);

                        if(map == null)

                                loadMap(curX, curY, baseX, baseY);

                        open.add(current);

                        boolean found = false;

                        while(open.size() > 0 && !found){

                                current = cheapestTile(open);

                                closed.add(current);

                                open.remove(open.indexOf(current));

                                for(PathTile t : adjacentTilesTo(current))

                                        if(map[t.getX()][t.getY()]/* && canReach(

                                                        (Object)(t.toRSTile(baseX, baseY)),

                                                                (getObjectAt(t.toRSTile(

                                                                baseX, baseY)) != null))*/

                                                        && !listContains(closed, t)){

                                                if(!listContains(open, t)){

                                                        PathTile added = new PathTile(t.getX(), t.getY());

                                                        added.parent = current;

                                                        added.gScore = current.gScore + calculateGCost(added, current);

                                                        added.fScore = added.gScore + calculateHCost(added, destination);

                                                        open.add(added);

                                                } else {

                                                        PathTile old = getFromList(open, t);

                                                        if(current.gScore + calculateGCost(old, current) < old.gScore){

                                                                old.parent = current;

                                                                old.gScore = current.gScore + calculateGCost(old, current);

                                                                old.fScore = old.gScore + calculateHCost(old, destination);

                                                        }

                                                }

                                        }

                                if(listContains(closed, destination))

                                        found = true;

                        }

                        if(found)

                                return generatePath(closed.get(closed.size()-1), baseX, baseY);

                        if(path.size() > 0)

                                return path;

                        return null;

                }


                private ArrayList<RSTile> generatePath(PathTile pathEnd, int baseX, int baseY){

                        ArrayList<RSTile> reversePath = new ArrayList();

                        PathTile p = pathEnd;

                        while(p.parent != null){

                                reversePath.add(p.toRSTile(baseX, baseY));

                                int next = (int)(Math.random()*4 + 5);

                                for(int i = 0; i < next && p.parent != null; i++)

                                        p = p.parent;

                        }

                        ArrayList<RSTile> fixedPath = new ArrayList();

                        for(int i = reversePath.size() -1; i >= 0; i--)

                                fixedPath.add(reversePath.get(i));

                        return fixedPath;

                }


                private PathTile getFromList(ArrayList<PathTile> list, PathTile key){

                        for(int i = 0; i < list.size(); i++){

                                PathTile t = list.get(i);

                                if(t.equals(key))

                                        return t;

                        }

                        return null;

                }


                private boolean listContains(ArrayList<PathTile> list, PathTile key){

                        for(PathTile t : list)

                                if(t.equals(key))

                                        return true;

                        return false;

                }


                /*private ArrayList<PathTile> adjacentTilesTo(PathTile t){

                        ArrayList<PathTile> adjacents = new ArrayList();

                        for(int y = -1; y < 2; y++)

                                for(int x = -1; x < 2; x++)

                                        if((x != 0 || y != 0) && t.getX() + x >= 0

                                                        && t.getY() + y >= 0 && t.getX() + x < 104

                                                        && t.getY() + y < 104)

                                                if((Math.abs(x) != Math.abs(y))

                                                        || (map[t.getX() + x][t.getY()] &&

                                                        map[t.getX()][t.getY() + y]))

                                                        adjacents.add(new PathTile(t.getX() + x,

                                                                t.getY() + y));

                        return adjacents;

                }*/

                private ArrayList<PathTile> adjacentTilesTo(PathTile t){

                        ArrayList<PathTile> tiles = new ArrayList();

                        if(blocks == null)

                                blocks = Bot.getClient().getGroundDataArray()[Bot.getClient().getPlane()].getBlocks();

                        int curX = t.x, curY = t.y;

                        //Northwest

                        if(curX > 0 && curY < 103 && map[curX - 1][curY + 1]

                                        && (blocks[curX - 1][curY + 1] & 0x1280138) == 0

                                        && (blocks[curX - 1][curY] & 0x1280108) == 0

                                        && (blocks[curX][curY + 1] & 0x1280120) == 0)

                                tiles.add(new PathTile(curX-1, curY+1));

                        //North

                        if (curY < 103 && map[curX][curY + 1]

                                        && (blocks[curX][curY + 1] & 0x1280120) == 0)

                                tiles.add(new PathTile(curX, curY+1));

                        //North east

                        if (curX > 0 && curY < 104 - 1 && map[curX - 1][curY + 1]

                                        && (blocks[curX - 1][curY + 1] & 0x1280138) == 0

                                        && (blocks[curX - 1][curY] & 0x1280108) == 0

                                        && (blocks[curX][curY + 1] & 0x1280120) == 0)

                                tiles.add(new PathTile(curX+1, curY+1));

                        if (curX > 0 && map[curX - 1][curY]

                                        && (blocks[curX - 1][curY] & 0x1280108) == 0)

                                tiles.add(new PathTile(curX-1, curY));

                        if (curX < 104 - 1 && map[curX + 1][curY]

                                        && (blocks[curX + 1][curY] & 0x1280180) == 0)

                                tiles.add(new PathTile(curX+1, curY));

                        if (curX > 0 && curY > 0 && map[curX - 1][curY - 1]

                                        && (blocks[curX - 1][curY - 1] & 0x128010e) == 0

                                        && (blocks[curX - 1][curY] & 0x1280108) == 0

                                        && (blocks[curX][curY - 1] & 0x1280102) == 0)

                                tiles.add(new PathTile(curX - 1, curY - 1));

                        if (curY > 0 &&map[curX][curY - 1]

                                        && (blocks[curX][curY - 1] & 0x1280102) == 0)

                                tiles.add(new PathTile(curX, curY - 1));

                        if (curX < 104 - 1 && curY > 0 && map[curX + 1][curY - 1]

                                        && (blocks[curX + 1][curY - 1] & 0x1280183) == 0

                                        && (blocks[curX + 1][curY] & 0x1280180) == 0

                                        && (blocks[curX][curY - 1] & 0x1280102) == 0)

                                tiles.add(new PathTile(curX+1, curY-1));

                        return tiles;

                }


                private PathTile cheapestTile(ArrayList<PathTile> open){

                        PathTile c = null;

                        for(PathTile t : open)

                                if(c == null || t.fScore < c.fScore)

                                        c = t;

                        return c;

                }


                private int calculateGCost(PathTile from, PathTile to){

                        return (int)(Math.sqrt(Math.pow(from.getX() - to.getX(), 2) + Math.pow(from.getY() - to.getY(), 2))*10);

                }


                private int calculateHCost(PathTile to, PathTile from){

                        return (Math.abs(to.getX() - from.getX()) + Math.abs(to.getY() - from.getY()))*10;

                }


                public void loadMap(int startX, int startY, int baseX, int baseY){

                        map = new boolean[104][104];

                        for(int y = 0; y < map[0].length; y++)

                                for(int x = 0; x < map.length; x++)

                                        map[x][y] = Calculations.canReach(startX, startY, x, y,

                                                        (getObjectAt(new PathTile(x, y).toRSTile(

                                                                baseX, baseY))) != null);

                }


                public class PathTile{


                        public PathTile (int x, int y) {

                           this.x = x;

                           this.y = y;

                                fScore = gScore = 0;

                        }


                        public boolean isValid(){

                                return !(x < 0 || y < 0 || x >= 104 || y >= 104);

                        }


                        public RSTile toRSTile(int baseX, int baseY){

                                return new RSTile(x + baseX, y + baseY);

                        }


                        public int getX(){

                                return x;

                        }


                        public int getY(){

                                return y;

                        }


                        public boolean equals(PathTile another){

                                return x == another.getX() && y == another.getY();

                        }


                        private int x, y;

                        public PathTile parent;

                        public int gScore, fScore;


                }

        }