AI Assignment 2 - Completed

tsp.java

import java.io.*;
import java.util.*;


public class tsp {

    public static void main(String[] args) throws IOException{
        int taskNumber = Integer.parseInt(args[1]);
        Graph g = new Graph();
        buildShortestPathGraph(g,taskNumber,args);
    }

    private static void buildShortestPathGraph(Graph g,int taskNumber, String... args) throws IOException
    {
        //first build the maze
        BufferedReader inputFile = new BufferedReader(new FileReader(args[3]));
        PrintWriter pathLogFile = new PrintWriter(args[5]);
        PrintWriter traverseLogFile = new PrintWriter(args[7]);
        Maze maze = new Maze(inputFile);
        //get all the checkpoints
        Character [] checkpoints = maze.returnCheckpointNames();
        g.numNodes = checkpoints.length;
        g.initialState = checkpoints[0].toString();
        for (int i = 0;i<checkpoints.length;i++)
        {
            for (int j = i+1;j<checkpoints.length;j++)
            {
                if (taskNumber == 1)
                {
                    traverseLogFile.println("from \'" + checkpoints[i] + "\' to \'" + checkpoints[j]+ "\'");
                    traverseLogFile.println("---------------------------------------------");
                    traverseLogFile.println("x,y,g,h,f");
                }
                Maze tmpMaze = new Maze (maze);
                Map <Character, Cell> myMap = tmpMaze.returnCheckpoints();
                Cell startCell = new Cell (myMap.get(checkpoints[i]));
                Cell goalCell = new Cell (myMap.get(checkpoints[j]));
                AStar(startCell, goalCell, tmpMaze, pathLogFile, traverseLogFile,g, taskNumber);
                if (taskNumber == 1)
                    traverseLogFile.println("---------------------------------------------");
            }
        }
        if (taskNumber == 1)
        {
            traverseLogFile.close();
            pathLogFile.close();
        }
        g.search(pathLogFile, traverseLogFile);
    }

    /*
        The A* algorithm is adapted from :  http://en.wikipedia.org/wiki/A*_search_algorithm
     */
    private static void AStar(Cell startCell, Cell goalCell, Maze maze, PrintWriter pathLogFile, PrintWriter traverseLogFile, Graph g, int taskNumber) throws IOException
    {
        List<Cell> visited = new ArrayList<Cell>();
        startCell.g_score = 0;
        startCell.f_score = startCell.g_score + tsp.manhattanDistance(startCell,goalCell);

        PriorityQueue<Cell> openset = new PriorityQueue<Cell>(1, new Comparator<Cell>() {
            @Override
            public int compare(Cell o1, Cell o2) {
                if (o1.f_score == o2.f_score)
                {
                    if (o1.row != o2.row)
                        return (o1.row - o2.row);
                    else if (o1.col != o2.col)
                        return (o1.col - o2.col);
                }
                return (int)(o1.f_score - o2.f_score);
            }
        });
        openset.add(startCell);

        while (!openset.isEmpty())
        {
            Cell current = openset.poll();
            if (taskNumber == 1)
                traverseLogFile.println(current.col + "," + current.row + "," + current.g_score + "," + (double)tsp.manhattanDistance(current, goalCell) + "," + current.f_score);
            if (current.name.equals(goalCell.name)) {
                g.addEdge(startCell.name.toString(), goalCell.name.toString(), current.f_score);
                if (taskNumber == 1)
                    pathLogFile.println(startCell.name + "," + goalCell.name + "," + current.f_score);
                break;
            }
            visited.add(current);
            current.setVisited();
            List<Cell> neighbours = current.getNeighbours(maze,goalCell);
            for(Cell n: neighbours)
            {
                if (visited.contains(n) || n.isVisited())
                    continue;
                double tentative_g_score = current.g_score + tsp.manhattanDistance(current,n);

                if (!openset.contains(n) || tentative_g_score < n.g_score)
                {
                    n.g_score = tentative_g_score;
                    n.f_score = n.g_score + tsp.manhattanDistance(n,goalCell);
                    if (!openset.contains(n))
                    {
                        openset.add(n);
                    }
                }

            }

        }


    }

    public static int manhattanDistance (Cell start, Cell end)
    {
        int distance = Math.abs(start.row-end.row) + Math.abs(start.col-end.col);
        return distance;
    }
}



class Cell {
    public int row, col;
    private boolean visited = false;
    Character name;
    public double f_score = 0, g_score = 0;

    public Cell(Cell newCell)
    {
        this.row = newCell.row;
        this.col = newCell.col;
        this.name = newCell.name;
        this.f_score = newCell.f_score;
        this.g_score = newCell.g_score;
        this.visited = newCell.visited;
    }

    Cell(int row, int col, Character name)
    {
        this.row = row;
        this.col = col;
        this.name = name;
        this.visited = false;
    }

    public boolean isVisited()
    {
        return this.visited;
    }

    public void setVisited()
    {
        this.visited = true;
    }

    public void unsetAllFields()
    {
        this.f_score = 0;
        this.g_score = 0;
        this.visited = false;
    }

    public boolean isWall()
    {
        if (this.name == '*')
            return true;
        else
            return false;
    }

    public List<Cell> getNeighbours(Maze maze, Cell goalCell){
        List<Cell> neighbours = new ArrayList<Cell>();
        Cell right = maze.returnCell(this.row , this.col + 1);
        Cell left = maze.returnCell(this.row, this.col - 1);
        Cell up =  maze.returnCell(this.row - 1, this.col);
        Cell down = maze.returnCell(this.row +1 , this.col);

        if (up!=null && !up.isVisited() && !up.isWall())
            neighbours.add(up);
        if (left!=null && !left.isVisited() && !left.isWall())
            neighbours.add(left);
        if (right!=null && !right.isVisited() && !right.isWall())
            neighbours.add(right);
        if (down!=null && !down.isVisited() && !down.isWall())
            neighbours.add(down);

        return neighbours;
    }
}

class Maze {

    private  ArrayList<Cell> mymaze = new ArrayList<Cell>();
    public int ROW_MAX, COL_MAX;
    private HashMap <Character,Cell> checkpoints = new HashMap <Character, Cell>();


    public Maze (Maze newMaze)
    {
        this.mymaze = new ArrayList<Cell>(newMaze.mymaze);
        this.ROW_MAX = newMaze.ROW_MAX;
        this.COL_MAX = newMaze.COL_MAX;
        this.checkpoints = new HashMap<Character, Cell>(newMaze.checkpoints);
        for(Cell m : this.mymaze)
        {
            m.unsetAllFields();
        }
    }

    Maze(BufferedReader inputFile) throws IOException
    {
        String str = null;
        int j = 0;
        while ((str = inputFile.readLine()) !=null)
        {
            for (int i=0;i<str.length();i++)
            {
                this.mymaze.add(new Cell(j,i,str.charAt(i)));
                if (str.charAt(i)!= '*' && str.charAt(i)!= ' ')
                {
                    this.checkpoints.put(str.charAt(i),new Cell(j,i,str.charAt(i)));
                }
                COL_MAX = i;
            }
            j++;
        }
        ROW_MAX = j;

    }

    public Cell returnCell(int x, int y)
    {
        for(Cell cell: mymaze)
        {
            if (cell.row == x && cell.col == y)
            {
                return cell;
            }
        }
        return null;
    }

    public Character[] returnCheckpointNames()
    {
        Character [] result = this.checkpoints.keySet().toArray(new Character[this.checkpoints.keySet().size()]);
        Arrays.sort(result);
        return result;
    }

    public HashMap<Character, Cell> returnCheckpoints()
    {
        return this.checkpoints;
    }

}

class Node{

    protected String name;

    protected double dist = 0;

    public Node(String name,double dist){
        this.name = name;
        this.dist = dist;
    }
}

class NodeInfo {
    String nodeName;
    ArrayList<String> path = new ArrayList<String>();
    double g;
    double h;
    double f;


    public NodeInfo(String nodeName, ArrayList<String>path,double g){
        this.nodeName = nodeName;
        this.g = g;
        for(String s:path){
            this.path.add(s);
        }
        this.h = 0.0;
    }

    public NodeInfo(String nodeName, ArrayList<String>path,double g,double h){

        this.nodeName = nodeName;
        this.g = g;
        for(String s:path){
            this.path.add(s);
        }
        this.h = h;
    }

    public NodeInfo(String nodeName){
        this.nodeName = nodeName;
        this.g = 0.0;
        this.h = 0.0;
    }

    public NodeInfo(String nodeName,double g){
        this.nodeName = nodeName;
        this.g = g;
        this.h = 0.0;
        this.f= 0.0;

    }

}

class Graph {
    public int numNodes;
    public String initialState;
    Node child;
    List<Node> childList;
    NodeInfo childData, endTour;
    NodeInfo node;
    double gcost, hcost;
    List<String> explored = new ArrayList<String>();
    List<String> current = new ArrayList<String>();
    Map<String, List<Node>> graph = new TreeMap<String, List<Node>>();

    public void addEdge(String from, String to, double weight)
    {
        if (!graph.containsKey(from))
        {
            List <Node> tmpNode1 = new ArrayList<Node>();
            graph.put(from,tmpNode1);
        }
        if (!graph.containsKey(to))
        {
            List <Node> tmpNode2 = new ArrayList<Node>();
            graph.put(to,tmpNode2);

        }
        if(!graph.get(from).contains(new Node(to,weight).name))
        {
            graph.get(from).add(new Node(to,weight));
        }
        if(!graph.get(to).contains(new Node(from, weight).name))
        {
            graph.get(to).add(new Node(from, weight));
        }
    }

    public void printGraph ()
    {
        for (Map.Entry<String, List <Node>> entry: graph.entrySet())
        {
            for (Node n : entry.getValue())
            {
                System.out.println(entry.getKey() + "," + n.name + "," + n.dist);
            }
        }
    }

    PriorityQueue<NodeInfo> front = new PriorityQueue<NodeInfo>(1,new Comparator<NodeInfo>() {
        public int compare(NodeInfo o1, NodeInfo o2) {
            return Double.valueOf(o1.f).compareTo(o2.f);
        }
    });


    private double getHeuristicCost(NodeInfo child) {
        double h = 0.0;
        explored.clear();
        current.clear();
        List<Node> pNodes;
        double min = 0.0;
        String minNode = null;

        for(String s: child.path){
            if(!s.equals(this.initialState)){
                explored.add(s);
            }
        }
        current.add(child.nodeName);
        explored.add(child.nodeName);
        while(explored.size() <= (this.numNodes - 1)){
            min = 99999999.99999;
            for(String s:current){
                pNodes = this.graph.get(s);
                for(Node p: pNodes){
                    if(!explored.contains(p.name)){
                        if(p.dist < min){
                            min = p.dist;
                            minNode = p.name;
                        }
                    }
                }
            }
            explored.add(minNode);
            current.add(minNode);
            h += min;
        }
        return h;
    }

    private void addChildNodes(List<Node> children, boolean last) {
        int i = 0;
        if (last == false) {
            while (i < children.size()) {
                child = children.get(i);
                if (!(node.path.contains(child.name))) {
                    gcost = child.dist + node.g;
                    hcost = 0.0;
                    childData = new NodeInfo(child.name, node.path, gcost,hcost);
                    childData.path.add(node.nodeName);
                    hcost = getHeuristicCost(childData);
                    childData.h = hcost;
                    childData.f = gcost + hcost;
                    front.add(childData);
                }
                i++;
            }
        }
        else {
            int j = 0;
            while (j < children.size()) {
                double gcost = 0.0;
                child = children.get(j);
                if (child.name.equals(this.initialState)) {
                    gcost = child.dist + node.g;
                    endTour = new NodeInfo(child.name, node.path, gcost);
                    endTour.path.add(node.nodeName);
                    endTour.path.add(child.name);
                    endTour.f = endTour.g + endTour.h;
                    break;
                }
                j++;
            }
        }
    }

    protected static void logPath(NodeInfo node, PrintWriter traverseLogFile) {

        String tmp = new String();
        for (String s : node.path) {
            tmp = tmp.concat(s);
        }
        tmp = tmp.concat(node.nodeName);
        traverseLogFile.println(tmp + "," + node.g + "," + node.h + "," + node.f);
    }

    protected static void printTour(NodeInfo endTour, PrintWriter pathLogFile, PrintWriter traverseLogFile) {
        String tmp = new String();
        for (String s : endTour.path) {
            tmp = tmp.concat(s);
            pathLogFile.println(s);
        }
        pathLogFile.println("Total Tour Cost: " + (endTour.f));
        traverseLogFile.println(tmp + "," + endTour.g + "," + endTour.h + "," + endTour.f);
        pathLogFile.close();
        traverseLogFile.close();
    }

    public void search(PrintWriter pathLogFile, PrintWriter traverseLogFile) {
        node = new NodeInfo(this.initialState);
        front.add(node);
        node.h = getHeuristicCost(node);
        node.f = node.g + node.h;
        while (true) {
            if (front.peek() == null) {
                return;
            }
            node = front.remove();
            if (node.path.size() == (this.numNodes - 1)) {
                //this.logPath(node);
                childList = this.graph.get(node.nodeName);
                addChildNodes(childList, true);
                this.printTour(endTour, pathLogFile, traverseLogFile);
                return;
            }
            else {
                this.logPath(node, traverseLogFile);
            }
            childList = this.graph.get(node.nodeName);
            addChildNodes(childList, false);

        }
    }
}