package edu.hawaii.ics.yucheng;
import java.util.ArrayList;
import java.util.PriorityQueue;
/**
* A class that finds a path from a location to the base of a graph.
*/
public class PathFinder {
/**
* A node that keeps information for the A* algorithm matrix.
*/
private class Node implements Comparable<Node> {
/** The cost getting to this node. */
public final int cost;
/** The distance from this node to the base. */
public final int distance;
/** The node along the path. */
public final Node parent;
/** The sum of the cost and the distance. */
public final int sum;
/** The vertex representing this node location. */
public final Vertex vertex;
/**
* Initializes a new instance of the Node class.
*
* @param cost The cost getting to this node.
*
* @param vertex The coordinate of the node.
*
* @param graph The graph.
*
* @param parent The node visited before this one.
*/
public Node(final int cost, final Vertex vertex, final Graph graph,
final Node parent) {
assert null != vertex;
assert null != graph;
this.cost = cost;
this.vertex = vertex;
this.parent = parent;
distance = Math.abs(graph.base.x - vertex.x)
+ Math.abs(graph.base.y - vertex.y);
sum = this.cost + distance;
}
/**
* Compares this node and another one. The sums are compared.
*
* @param n The other node.
*
* @return The comparison value for the priority queue.
*/
public int compareTo(final Node n) {
assert null != n;
return sum - n.sum;
}
}
/**
* Verifies a pointer is not null.
*
* @param pointer The pointer object.
*
* @param name The name of the parameter.
*/
private static void verifyPointer(final Object pointer, final String name) {
if (pointer == null)
throw new NullPointerException(name);
}
/**
* Verifies a pointer is not null.
*
* @param value The value.
*
* @param max The maximum value (exclusive).
*
* @param name The name of the parameter.
*/
private static void verifyRange(final int value, final int max,
final String name) {
if (value < 0 || value >= max)
throw new IllegalArgumentException(name);
}
/** The cost of the path. */
private int myCost;
/** The graph. */
private final Graph myGraph;
/** The nodes used to compute the path. */
private final Node[] myNodes;
/** The path. */
private Vertex[] myPath;
/** The priority queue used to compute the path. */
private final PriorityQueue<Node> myQueue;
/**
* Initializes a new instance of the PathFinder class.
*
* @param g The graph.
*
* @param x The x location away from the base.
*
* @param y The y location away from the base.
*/
public PathFinder(final Graph g, final int x, final int y) {
verifyPointer(g, "g");
verifyRange(x, g.width, "x");
verifyRange(y, g.height, "y");
myGraph = g;
myNodes = new Node[myGraph.width * myGraph.height];
myQueue = new PriorityQueue<Node>();
myCost = Integer.MAX_VALUE;
search(x, y);
}
/**
* Returns the total cost of the path.
*
* @return The total cost of the path.
*/
public int cost() {
return myCost;
}
/**
* Returns the path computed by the class or null if there is no path.
*
* @return The path.
*/
public Vertex[] getPath() {
if (myPath == null)
return null;
final Vertex[] result = new Vertex[myPath.length];
for (int i = 0; i < myPath.length; i++)
result[i] = myPath[i];
return result;
}
/**
* Returns the A* matrix index.
*
* @param x The x coordinate.
*
* @param y The y coordinate.
*
* @return The array index.
*/
private int indexAt(final int x, final int y) {
return myGraph.width * y + x;
}
/**
* Returns true if a location is blocked in the graph.
*
* @param x The x coordinate.
*
* @param y The y coordinate.
*
* @return True indicates the path is blocked.
*/
private boolean isBlockedLocation(final int x, final int y) {
// Check if this is not on the graph.
if (x < 0 || x >= myGraph.width || y < 0 || y >= myGraph.height)
return true;
// Check if this is an obstacle.
return myGraph.isObstacle(x, y);
}
/**
* Returns true if a path was found.
*
* @return True indicates a path was found.
*/
public boolean isFound() {
return myPath != null;
}
/**
* Saves the result. The best path is stored to the class data.
*
* @param node The last node visited in the iterative loop from search.
*/
private void saveResult(final Node node) {
// Store the queue.
final ArrayList<Vertex> path = new ArrayList<Vertex>();
for (Node n = node; n != null; n = n.parent)
path.add(0, n.vertex);
myPath = new Vertex[path.size()];
path.toArray(myPath);
myCost = node.cost;
// Empty out the priority queue so that no more attempts are made to find
// solutions.
myQueue.clear();
}
/**
* Searches for a path based on the next item from the priority queue.
*/
private void search() {
// Get the most desirable starting point.
final Node node = myQueue.poll();
final int nx = node.vertex.x;
final int ny = node.vertex.y;
// Check if this is a blocked path.
if (isBlockedLocation(nx, ny))
return;
// Check if this is the base. Save the result if it is.
if (nx == myGraph.base.x && ny == myGraph.base.y) {
saveResult(node);
return;
}
// Check if this is a previously visited node.
if (myNodes[indexAt(nx, ny)] != null)
return;
// Save this node. It is now visited.
myNodes[indexAt(nx, ny)] = node;
// Compute a new cost from this location.
final int newCost = node.cost + 1;
// Add nodes in each possible direction.
myQueue.add(new Node(newCost, new Vertex(nx + 1, ny), myGraph, node));
myQueue.add(new Node(newCost, new Vertex(nx - 1, ny), myGraph, node));
myQueue.add(new Node(newCost, new Vertex(nx, ny + 1), myGraph, node));
myQueue.add(new Node(newCost, new Vertex(nx, ny - 1), myGraph, node));
}
/**
* Searches for a path.
*
* @param x The initial x location.
*
* @param y The initial y location.
*/
private void search(final int x, final int y) {
// Create a new node representing this initial location.
final Node initialNode = new Node(0, new Vertex(x, y), myGraph, null);
// Put this node into the priority queue as an initial starting point.
myQueue.add(initialNode);
// Loop until the queue is empty.
while (myQueue.size() > 0)
search();
}
/**
* Returns the string representation of the class data.
*
* @return The string representation of the class data.
*/
@Override
public String toString() {
final StringBuilder builder = new StringBuilder();
builder.append("Cost: " + cost() + "; Path: ");
if (myPath == null)
builder.append("null");
else
for (int i = 0; i < myPath.length; i++) {
builder.append(myPath[i]);
if (i + 1 < myPath.length)
builder.append(" --> ");
}
return builder.toString();
}
}
