Skip to content

Instantly share code, notes, and snippets.

@pradeep1288
Created February 26, 2014 09:11
Show Gist options
  • Save pradeep1288/9226262 to your computer and use it in GitHub Desktop.
Save pradeep1288/9226262 to your computer and use it in GitHub Desktop.
Assignment 2 - AI
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;
/**
* Created with IntelliJ IDEA.
* User: pradeepnayak
* Date: 23/02/14
* Time: 3:45 PM
* To change this template use File | Settings | File Templates.
*/
public class tsp {
private static ArrayList<Cell> maze = new ArrayList<Cell>();
//note all checkpoints and positions
private static int ROW_MAX, COL_MAX;
public static void main(String[] args) throws IOException{
int taskNumber = Integer.parseInt(args[1]);
if (taskNumber == 1)
buildShortestPathGraph(args);
else
{
buildShortestPathGraph(args);
findShortestPath(args);
}
}
private static void buildShortestPathGraph(String... args) throws IOException
{
//first build the maze
BufferedReader inputFile = new BufferedReader(new FileReader(args[3]));
Maze maze = new Maze(inputFile);
//get all the checkpoints
Character [] checkpoints = maze.returnCheckpointNames();
for (int i = 0;i<checkpoints.length;i++)
{
for (int j = i+1;j<checkpoints.length;j++)
{
System.out.println("from \'" + checkpoints[i] + "\' to \'" + checkpoints[j]+ "\'");
System.out.println("---------------------------------------------");
System.out.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);
System.out.println("---------------------------------------------");
}
}
}
/*
The A* algorithm is adapted from : http://en.wikipedia.org/wiki/A*_search_algorithm
*/
private static void AStar(Cell startCell, Cell goalCell, Maze maze)
{
List<Cell> visited = new ArrayList<Cell>();
startCell.g_score = 0;
startCell.f_score = startCell.g_score + tsp.manhattanDistacne(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
return (o1.col - o2.col);
}
return (o1.f_score - o2.f_score);
}
});
openset.add(startCell);
while (!openset.isEmpty())
{
Cell current = openset.poll();
System.out.println(current.col + "," + current.row + "," + current.g_score + "," + tsp.manhattanDistacne(current,goalCell) + "," + current.f_score);
if (current.name.equals(goalCell.name)) {
break;
}
visited.add(current);
current.setVisited();
List<Cell> neighbours = current.getNeighbours(maze,goalCell);
for(Cell n: neighbours)
{
if (visited.contains(n) || n.isVistited())
continue;
int tentative_g_score = current.g_score + tsp.manhattanDistacne(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.manhattanDistacne(n,goalCell);
if (!openset.contains(n))
{
openset.add(n);
}
}
}
}
}
private static void readInputFile(BufferedReader inputFile) throws IOException
{
}
private static void findShortestPath(String... args) throws IOException
{
}
public static int manhattanDistacne (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;
Character name;
public int f_score, g_score;
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 isVistited()
{
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.isVistited() && !up.isWall())
neighbours.add(up);
if (left!=null && !left.isVistited() && !left.isWall())
neighbours.add(left);
if (right!=null && !right.isVistited() && !right.isWall())
neighbours.add(right);
if (down!=null && !down.isVistited() && !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()
{
Map myMap = this.checkpoints;
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment