This current algorithm I’m using is quick for down and right, slow for up and left, and really slow for diagonal moves… So much that it OutOfMemoryExceptions get thrown… I was wondering if anyone would be able to help make it faster or get me some more efficient code?
http://www.mediafire.com/?8b3gmpbj1sz9cil
AStar.java
package citystates.astar;
import java.awt.Point;
import java.util.*;
public abstract class AStar
{
private PriorityQueue<Path> paths;
private HashMap<Node, Double> mindists;
private Double lastCost;
private int expandedCounter;
Point goal;
private boolean reverse;
// Default constructor.
public AStar ()
{
paths = new PriorityQueue<Path> ();
mindists = new HashMap<Node, Double> ();
expandedCounter = 0;
lastCost = 0.0;
}
protected abstract List<Node> generateSuccessors (Node node);
//Check if the current node is a goal for the problem.
protected abstract boolean isGoal (Node node);
//Cost for the operation to go to <code>to</code> from <code>from</from>.
protected abstract Double g (Node from, Node to);
// Estimated cost to reach a goal node. An admissible heuristic never gives a cost bigger than the real one.
protected abstract Double h (Node from, Node to);
// Check how many times a node was expanded.
public int getExpandedCounter ()
{
return expandedCounter;
}
// Total cost function to reach the node <code>to</code> from <code>from</code>
protected Double f (Path p, Node from, Node to)
{
Double g = g (from, to) + ((p.parent != null) ? p.parent.g : 0.0);
Double h = h (from, to);
p.g = g;
p.f = g + h;
return p.f;
}
// Expand a path.
private void expand (Path path)
{
Node p = path.getPoint ();
Double min = mindists.get (path.getPoint ());
//If a better path passing for this point already exists then don't expand it.
if (min == null || min.doubleValue () > path.f.doubleValue ())
{
mindists.put (path.getPoint (), path.f);
} else
{
return;
}
List<Node> successors = generateSuccessors (p);
for (Node t : successors)
{
Path newPath = new Path (path);
newPath.setPoint (t);
f (newPath, path.getPoint (), t);
paths.offer (newPath);
}
expandedCounter++;
}
// Get the cost to reach the last node in the path.
public Double getCost ()
{
return lastCost;
}
//Find the shortest path to a goal starting from the start
public List<Node> compute (Node start, Node end)
{
try
{
Node startNode = null;
Node endNode = null;
if (end.y < start.y || end.x < start.x)
{
startNode = end;
endNode = start;
reverse = true;
}
else
{
startNode = start;
endNode = end;
reverse = false;
}
goal = new Point(endNode.x, endNode.y);
start = startNode;
Path root = new Path ();
root.setPoint (start);
//Needed if the initial point has a cost.
f (root, start, start);
expand (root);
while (true)
{
Path p = paths.poll ();
if (p == null)
{
lastCost = Double.MAX_VALUE;
return null;
}
Node last = p.getPoint ();
lastCost = p.g;
if (isGoal (last))
{
LinkedList<Node> retPath = new LinkedList<Node> ();
for (Path i = p; i != null; i = i.parent)
{
retPath.addFirst (i.getPoint ());
}
if (!reverse)
{
return retPath;
}
else
{
LinkedList<Node> retPath2 = new LinkedList();
for (int i = retPath.size () - 1; i > 0; i --)
{
retPath2.add (retPath.get (i));
}
return retPath2;
}
}
expand (p);
}
} catch (Exception e)
{
e.printStackTrace ();
}
return null;
}
}
PathFinder.java
package citystates.astar;
import java.awt.Point;
import java.util.*;
public class PathFinder extends AStar
{
private int[][] map;
public PathFinder (int[][] map)
{
this.map = map;
}
protected boolean isGoal (Node node)
{
return (node.x == goal.x) && (node.y == goal.y);
}
protected Double g (Node from, Node to)
{
if (from.x == to.x && from.y == to.y)
{
return 0.0;
}
if (map[to.y][to.x] == 1)
{
return 1.0;
}
return Double.MAX_VALUE;
}
protected Double h (Node from, Node to)
{
// Use the Manhattan distance heuristic.
return new Double (Math.abs (map[0].length - 1 - to.x) + Math.abs (map.length - 1 - to.y));
}
protected List<Node> generateSuccessors (Node node)
{
List<Node> returnList = new LinkedList<Node> ();
int x = node.x;
int y = node.y;
// DOWN
if (y < map.length - 1 && map[y + 1][x] == 1)
{
returnList.add (new Node (x, y + 1));
}
// UP
if (y > 0 && map[y - 1][x] == 1)
{
returnList.add (new Node (x, y - 1));
}
// RIGHT
if (x < map[0].length - 1 && map[y][x + 1] == 1)
{
returnList.add (new Node (x + 1, y));
}
// LEFT
if (x > 0 && map[y][x - 1] == 1)
{
returnList.add (new Node (x - 1, y));
}
// TOP LEFT
if (x > 0 && y > 0 && map[y - 1][x - 1] == 1)
{
returnList.add (new Node (y - 1, x - 1));
}
// TOP RIGHT
if (x < map[0].length - 1 && y > 1 && map[y - 1][x + 1] == 1)
{
returnList.add (new Node (y - 1, x + 1));
}
// BOTTOM LEFT
if (y < map.length - 1 && x > 1 && map[y + 1][x - 1] == 1)
{
returnList.add (new Node (y + 1, x - 1));
}
if (y < map.length - 1 && x < map[0].length - 1 && map[y + 1][x + 1] == 1)
{
returnList.add (new Node (y + 1, x + 1));
}
return returnList;
}
}