Pathfinder

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import com.gpg.forest.game.Level;
import com.gpg.forest.util.Vector2;

/*
 * Pathfinder inspired by post by Rayvolution on java-gaming.org
 * http://www.java-gaming.org/topics/slick2d-retro-pixel-castles/33101/view.html
 */

public class Pathfinder {

    private final byte UNCHECKED = 0;
    private final byte CHECKED = 1;

    public enum Direction{

        N(0, -1, 0x96E5FF),
        S(0, 1, 0xA2F536),
        E(1, 0, 0x363636),
        W(-1, 0, 0xDBDBDB),
        NE(1, -1, 0xEA4AFF),
        SE(1, 1, 0xFF0000),
        SW(-1, 1, 0x005EFF),
        NW(-1, -1, 0xFFE100);

        public int xo, yo;
        public int color; //Used for visualising direction

        Direction(int xo, int yo, int color){
            this.xo = xo;
            this.yo = yo;
            this.color = color;
        }
    }

    private Level level;

    private byte[][] tileStatus;

    private List<TileInfo> masterArray;
    private List<TileInfo> tempArray;
    private boolean routeBlocked;

    private double startTime;

    public Pathfinder(Level level){
        this.level = level;

        tileStatus = new byte[level.getWidth()][level.getHeight()];
        masterArray = new ArrayList<TileInfo>();
        tempArray = new ArrayList<TileInfo>();
        routeBlocked = true;

        startTime = 0;

        for(int y = 0; y < level.getHeight(); y++){
            for(int x = 0; x < level.getWidth(); x++){
                if(level.getTile(x, y).isSolid()) tileStatus[x][y] = CHECKED;
                else tileStatus[x][y] = UNCHECKED;
            }
        }
    }

    public class TileInfo{
        public Vector2 pos;
        public TileInfo parentInfo;
        public Direction dirToParent;

        public TileInfo(Vector2 pos, TileInfo parentInfo, Direction dirToParent){
            this.pos = pos;
            this.parentInfo = parentInfo;
            this.dirToParent = dirToParent;
        }

        @Override
        public String toString(){
            return "(" + pos.toString() + ") ParentDir: " + dirToParent.name();
        }
    }

    public List<TileInfo> findPath(Vector2 start, Vector2 target){
        System.out.println("Finding path between: " + start.toString() + " and " + target.toString());

        //Add the target tile to the master array to be checked.
        TileInfo destInfo =  new TileInfo(new Vector2(target.x, target.y), null, null);
        checkTile(target, destInfo, null);
        masterArray.remove(destInfo);

        startTime = System.nanoTime();
        int tries = 0;

        //Loop over master array, keep checking tiles till start has been reached
        while(true){
            tries++;
            routeBlocked = true;
            //Use an iterator to loop master array so objects can be removed
            Iterator<TileInfo> i = masterArray.iterator();
            while(i.hasNext()){
                TileInfo info = i.next();
                checkTile(info.pos, info, i);

                //If start is reached, return the route from start to target
                if(info.pos.x == start.x && info.pos.y == start.y){
                    return getShortestRoute(info);
                }
            }

            //The route is blocked, cannot find path.
            if(routeBlocked && tries > 1){
                System.out.println("Route is blocked, took " + tries + " tries in " + ((System.nanoTime() - startTime) / 1000000) + "ms");
                clearArrays();
                return null;
            }

            //Add TileInfo objects from temp array into master array, clear the temp array
            masterArray.clear();
            masterArray.addAll(tempArray);
            tempArray.clear();

            //Return null if its taken too long
            if(tries > 10000){
                System.out.println("Could not find short enough path");
                clearArrays();
                return null;
            }
        }
    }

    private List<TileInfo> getShortestRoute(TileInfo info){
        List<TileInfo> shortestRoute = new ArrayList<TileInfo>();

        shortestRoute.add(info);

        while(true){
            TileInfo parentInfo = shortestRoute.get(shortestRoute.size() - 1).parentInfo;
            if(parentInfo != null){
                shortestRoute.add(parentInfo);
            }else{
                System.out.println("Found path in " + ((System.nanoTime() - startTime) / 1000000) + "ms");
                System.out.println("Array Size: " + masterArray.size() + " to find path length " + shortestRoute.size());
                clearArrays();
                return shortestRoute;
            }
        }
    }

    //Check the tiles around a parent tile
    private void checkTile(Vector2 pos, TileInfo parentInfo, Iterator<TileInfo> i){
        //Check tiles around parent tile
        for(Direction dir : Direction.values()) checkNeighbour(pos.x + dir.xo, pos.y + dir.yo, dir, parentInfo);

        //Parent tile has been checked can be removed from master array (through Iterator) to save looping over previously checked tiles.
        tileStatus[pos.x][pos.y] = CHECKED;
        if(i != null) i.remove();
    }


    private void checkNeighbour(int x, int y, Direction dir, TileInfo parentInfo){
        //Check if out of bounds or previously checked
        if(checkBounds(x, y)) return;
        if(tileStatus[x][y] == CHECKED) return;

        //A new traversable has been found, therefore the route can't be blocked yet
        routeBlocked = false;

        //Add the TileInfo to the temp array. Tile is now checked
        tempArray.add(new TileInfo(new Vector2(x, y), parentInfo, findOppositeDir(dir)));
        tileStatus[x][y] = CHECKED;
    }

    //Get the opposite of a direction
    private Direction findOppositeDir(Direction dir){
        for(Direction d : Direction.values()) if(dir.xo * -1 == d.xo && dir.yo * -1 == d.yo) return d;
        return null;
    }

    private boolean checkBounds(int x, int y){
        return checkBounds(new Vector2(x, y));
    }

    private boolean checkBounds(Vector2 pos){
        return pos.x < 0 || pos.y < 0 || pos.x >= level.getWidth() || pos.y >= level.getHeight();
    }

    private void clearArrays(){
        masterArray.clear();
        tempArray.clear();
    }
}