Hallo liebe Community,
ich habe ein kleines Problem bei meinem A*-Algorithmus. Ich habe ihn für ein Projekt der Uni programmiert und habe versucht den A* mit dem ExecutorService ein bisschen flotter zu machen. Leider ist das Gegenteil eingetreten. Mit dem ExcecutorService braucht der A* 3 mal so lange um den Weg zu finden. Ich hoffe mir kann da jemand weiterhelfen.
Hier der Code:
ich habe ein kleines Problem bei meinem A*-Algorithmus. Ich habe ihn für ein Projekt der Uni programmiert und habe versucht den A* mit dem ExecutorService ein bisschen flotter zu machen. Leider ist das Gegenteil eingetreten. Mit dem ExcecutorService braucht der A* 3 mal so lange um den Weg zu finden. Ich hoffe mir kann da jemand weiterhelfen.
Hier der Code:
Java:
package pp2012.pathfinding;
import java.awt.Point;
import java.util.ArrayList;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import pp2012.world.Tile;
import pp2012.world.Unit;
public class AStar{
private static AStar aStar = new AStar();
/** The AStar class is a Singleton Class*/
private AStar() {
}
/**
* Method takes the tileMap and the unit and calculates the shortest path from
* the unit location to the unit destination and returns the shortest path.
* If no path is found the algorithm returns a null value
* The algorithm uses the heapsort algorithm to sort the openList to guarantee
* a time complexity of O(n lg n)
*
*
* @param tileMap
* @param unit
* @return path
*/
public ArrayList<Point> getPath(final Tile[][] tileMap, final Unit unit) {
final ArrayList<AStarNode> openList = new ArrayList<>();
final ArrayList<AStarNode> closedList = new ArrayList<>();
ArrayList<Point> path = new ArrayList<>();
Heapsort heapSort = Heapsort.getInstance();
ExecutorService executor;
Point unitLocation = unit.getDestination();
Point unitDestination = unit.getLocation();
double edgeCosts = tileMap[(int) unitLocation.getX()][(int) unitLocation.getY()].getCosts();
double estimatedHeuristicCosts = Math.sqrt(unitLocation.distanceSq(unitDestination));
AStarNode startNode = new AStarNode(null, edgeCosts, estimatedHeuristicCosts, (int) unitLocation.getX(), (int) unitLocation.getY());
openList.add(startNode);
while (!openList.isEmpty()) {
heapSort.heapsort(openList);
AStarNode currentNode = openList.remove(0);
if (currentNode.getX() == unitDestination.getX() && currentNode.getY() == unitDestination.getY()) {
/** Saves the path from the unit location to the destination of a unit
* into a path ArrayList */
while (currentNode.getPredecessor() != null) {
currentNode = currentNode.getPredecessor();
Point point = new Point(currentNode.getX(), currentNode.getY());
path.add(point);
}
/** Path is returned */
return path;
}
/** If the currentNode is not the goal than add it to the closedList and continue with the algorithm */
closedList.add(currentNode);
executor = Executors.newFixedThreadPool(8);
final AStarNode currentNodeCopy = currentNode;
/** Examine all eight neighbor around the currentNode */
for(int x = -1; x < 2; x++){
for(int y = -1; y < 2; y++){
if(x == 0 && y == 0){
continue;
}
final int xCopy = x;
final int yCopy = y;
executor.submit(new Runnable() {
@Override
public void run() {
examineNeighbours(currentNodeCopy, currentNodeCopy.getX() - xCopy, currentNodeCopy.getY() - yCopy, tileMap, unit, openList, closedList);
}
});
}
}
executor.shutdown();
try {
executor.awaitTermination(1, TimeUnit.DAYS);
} catch (InterruptedException e) {}
}
/** If no path is found the algorithm returns a null value */
return null;
}
/**
* Method checks the neighbor nodes and calculates the edge, heurisitic and sum costs.
* If the node which is beeing examined is already in the openList oder closedList the
* method terminates.
* If the node is not in the openList the node is added to it.
*
* @param currentNode
* @param x
* @param y
* @param tileMap
* @param unit
* @param openList
* @param closedList
*
*/
private void examineNeighbours(AStarNode currentNode, int x, int y, Tile[][] tileMap, Unit unit, ArrayList<AStarNode> openList, ArrayList<AStarNode> closedList){
Point unitDestination = unit.getLocation();
try{
if(tileMap[x][y].isWalkable(unit.getType()) && (tileMap[x][y].getWorldObject() == null) || unitDestination.equals(new Point(x,y))){
double edgeCosts = tileMap[x][y].getCosts();
double diagonalMovingCosts = Math.sqrt(2) * edgeCosts;
double heuristicCost = calcEstimatedHeuristicCosts(currentNode, unitDestination);
AStarNode node = new AStarNode(currentNode, x, y);
/** If the node is in the closedList the rest of the code will be skipped
* The Query is at the start to optimize the run time of the algorithm */
for(AStarNode compareNode : closedList){
if(compareNode.getX() == node.getX() && compareNode.getY() == node.getY()){
return;
}
}
/** If the node is already in the openList the rest of the code will be skipped
* The Query is at the start to optimize the run time of the
* algorithm */
for(AStarNode compareNode : openList){
if(compareNode.getX() == node.getX() && compareNode.getY() == node.getY()){
return;
}
}
/** If the node is a diagonal node it costs are set in the next four
* queries.
* If the node is a vertical or a horizontal the costs are set in
* the else statement. */
if (node.getX() - 1 == currentNode.getX() && node.getY() - 1 == currentNode.getY()){
node.setEdgeCosts(diagonalMovingCosts);
node.setEstimatedHeuristicCosts(heuristicCost);
node.setSumCosts(heuristicCost + node.getEdgeCosts());
}else if(node.getX() - 1 == currentNode.getX() && node.getY() + 1 == currentNode.getY()){
node.setEdgeCosts(diagonalMovingCosts);
node.setEstimatedHeuristicCosts(heuristicCost);
node.setSumCosts(node.getEdgeCosts() + node.getEstimatedHeuristicCosts());
}else if(node.getX() + 1 == currentNode.getX() && node.getY() - 1 == currentNode.getY()){
node.setEdgeCosts(diagonalMovingCosts);
node.setEstimatedHeuristicCosts(heuristicCost);
node.setSumCosts(node.getEdgeCosts() + node.getEstimatedHeuristicCosts());
}else if(node.getX() + 1 == currentNode.getX() && node.getY() + 1 == currentNode.getY()){
node.setEdgeCosts(diagonalMovingCosts);
node.setEstimatedHeuristicCosts(heuristicCost);
node.setSumCosts(node.getEdgeCosts() + node.getEstimatedHeuristicCosts());
}else{
node.setEdgeCosts(edgeCosts);
node.setEstimatedHeuristicCosts(heuristicCost);
node.setSumCosts(node.getEdgeCosts() + node.getEstimatedHeuristicCosts());
}
/** If the node is not in the openList it costs are calculated and it
* is added to the openList */
node.setEdgeCosts(edgeCosts + node.getPredecessor().getEdgeCosts());
node.setEstimatedHeuristicCosts(calcEstimatedHeuristicCosts(node,unitDestination));
node.setSumCosts(node.getEdgeCosts() +node.getEstimatedHeuristicCosts());
synchronized(this) {
openList.add(node);
}
}
}catch(ArrayIndexOutOfBoundsException aioobe){
}
}
/**
* Calculates the estimated heuristic costs using euclidean distance from
* currentNode to the endPoint node.
*
* @param currentNode
* @param endPoint
* @return estimatedHeuristicCosts
*
*/
private double calcEstimatedHeuristicCosts(AStarNode currentNode, Point endPoint) {
int distanceX = Math.abs(currentNode.getX() - endPoint.x);
int distanceY = Math.abs(currentNode.getY() - endPoint.y);
return Math.sqrt(Math.pow(distanceX, 2) + Math.pow(distanceY, 2));
}
/** Returns an instance of the singleton class */
public static AStar getInstance() {
return aStar;
}
}
